Task Tree Scheduling for Completion Time Saving on Multi-Node Computing Environments

Task Tree Scheduling for Completion Time Saving on Multi-Node Computing Environments | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Article Task Tree Scheduling for Completion Time Saving on Multi-Node Computing Environments Bing Wei, Ming Zhong, Qian Chen, Yi Wu, Yubin Li This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-5778690/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract Task trees are widely used as paradigms on multi-node computing environments for various computational domains, such as the sparse linear algebra and the Cholesky factorizations. These domains provides support for the computation in the Internet of Things. Meanwhile, efficient task tree scheduling approaches are the key to reducing the completion time in the environments. An algorithm for splitting a task tree into a certain number of subtrees for distributed computing on multi-node computing environments with given memory capacity is proposed. The proposed algorithm initially splits a task tree into subtree graphs, then constructs the corresponding reduction tree. The further splitting works on each subtree, which is the critical path element of the reduction tree, since the critical path is dominated by the computation and communication time. If a subtree requires more memory to process, the subtree is further split by removing the maximum node. Finally, the subtrees are merged based on the preference on the minimum increase of completion time. Extensive experimental evaluations show that the completion time can be reduced by up to 36.52% on real-world dataset, and by up to 22.92% on randomly generated instances when the proposed algorithm is applied. Physical sciences/Mathematics and computing/Computer science Physical sciences/Mathematics and computing/Information technology Completion time minimizing distributed processing parallel computing scheduling Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-5778690","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Article","associatedPublications":[],"authors":[{"id":437254501,"identity":"8a426f99-6d85-4e74-892a-96217f00d56f","order_by":0,"name":"Bing Wei","email":"","orcid":"","institution":"Hainan University","correspondingAuthor":false,"prefix":"","firstName":"Bing","middleName":"","lastName":"Wei","suffix":""},{"id":437254502,"identity":"fe302e7d-397c-46b2-810e-638d685cdfbb","order_by":1,"name":"Ming Zhong","email":"","orcid":"","institution":"Hainan University","correspondingAuthor":false,"prefix":"","firstName":"Ming","middleName":"","lastName":"Zhong","suffix":""},{"id":437254503,"identity":"653cec5b-67d2-4d0c-8236-1ad1e69781e8","order_by":2,"name":"Qian Chen","email":"","orcid":"","institution":"Hainan University","correspondingAuthor":false,"prefix":"","firstName":"Qian","middleName":"","lastName":"Chen","suffix":""},{"id":437254504,"identity":"e9d9c30e-90f7-4609-bd48-25a8135be578","order_by":3,"name":"Yi Wu","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAyklEQVRIiWNgGAWjYJCCAx8bGHigbGbitBycSbIWZt4GBJuwcoMbOYaHbXfYyZiznz0mwVBhndjAfvYAIS0Gh3PPJPNY9uSlSTCcSU9s4MlLwKvFDKyljZnH4ECOmQRj2+HEBgkeA8JaLNvqeQzOvwFq+UesFqDhPEAXArU0EKHF/syzgoO9bceBWt4YWyQcSzdu48nBr0WyPXnzh59t1fYG53MMb3yosZbtZz+DXwsDAweSggQgZiOgHgjYHxBWMwpGwSgYBSMbAAA5rkUz9d8RRAAAAABJRU5ErkJggg==","orcid":"","institution":"Hainan University","correspondingAuthor":true,"prefix":"","firstName":"Yi","middleName":"","lastName":"Wu","suffix":""},{"id":437254505,"identity":"632484cb-d6ac-479e-8300-81d544791804","order_by":4,"name":"Yubin Li","email":"","orcid":"","institution":"Hainan University","correspondingAuthor":false,"prefix":"","firstName":"Yubin","middleName":"","lastName":"Li","suffix":""}],"badges":[],"createdAt":"2025-01-07 07:08:22","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-5778690/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-5778690/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":82678086,"identity":"e9f55f12-1636-4160-91c6-703a1a135d3a","added_by":"auto","created_at":"2025-05-14 05:01:51","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":462940,"visible":true,"origin":"","legend":"","description":"","filename":"TaskTreeSchedulingforCompletionTimeSavingonMultiNodeComputingEnvironments.pdf","url":"https://assets-eu.researchsquare.com/files/rs-5778690/v1_covered_bcc4f099-5b5d-4c7b-b749-94bdb8881fa5.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Task Tree Scheduling for Completion Time Saving on Multi-Node Computing Environments","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Completion time minimizing, distributed processing, parallel computing, scheduling","lastPublishedDoi":"10.21203/rs.3.rs-5778690/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-5778690/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Task trees are widely used as paradigms on multi-node computing environments for various computational domains, such as the sparse linear algebra and the Cholesky factorizations. These domains provides support for the computation in the Internet of Things. Meanwhile, efficient task tree scheduling approaches are the key to reducing the completion time in the environments. An algorithm for splitting a task tree into a certain number of subtrees for distributed computing on multi-node computing environments with given memory capacity is proposed. The proposed algorithm initially splits a task tree into subtree graphs, then constructs the corresponding reduction tree. The further splitting works on each subtree, which is the critical path element of the reduction tree, since the critical path is dominated by the computation and communication time. If a subtree requires more memory to process, the subtree is further split by removing the maximum node. Finally, the subtrees are merged based on the preference on the minimum increase of completion time. Extensive experimental evaluations show that the completion time can be reduced by up to 36.52% on real-world dataset, and by up to 22.92% on randomly generated instances when the proposed algorithm is applied.","manuscriptTitle":"Task Tree Scheduling for Completion Time Saving on Multi-Node Computing Environments","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-04-03 13:58:57","doi":"10.21203/rs.3.rs-5778690/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"8709fa8f-2825-4300-9c52-c7a440c74a43","owner":[],"postedDate":"April 3rd, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[{"id":46557102,"name":"Physical sciences/Mathematics and computing/Computer science"},{"id":46557103,"name":"Physical sciences/Mathematics and computing/Information technology"}],"tags":[],"updatedAt":"2025-05-14T04:53:44+00:00","versionOfRecord":[],"versionCreatedAt":"2025-04-03 13:58:57","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-5778690","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-5778690","identity":"rs-5778690","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}