Near-Optimal Universal Scheduling for Moldable Tasks: The Fair Algorithm

Near-Optimal Universal Scheduling for Moldable Tasks: The Fair Algorithm | 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 Research Article Near-Optimal Universal Scheduling for Moldable Tasks: The Fair Algorithm Lucas Perotin, Thomas Verrecchia, Padma Raghavan This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-8251720/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 The problem of scheduling moldable tasks on multiprocessor systems with the goal of minimizing the makespan has received significant attention, especially in contexts where tasks have dependence constraints (task graphs) or arrive dynamically (online scheduling). However, the combined setting — online scheduling of moldable task graphs — remains less explored. Prior studies have addressed this problem by designing algorithms specifically tailored to particular speedup models, such as Amdahl, Communication, or Roofline. Although these specialized algorithms achieve constant competitive ratios under their respective models, their applicability is severely limited in practice: each requires tasks to strictly adhere to a predefined speedup model, making them impractical for general scenarios or hybrid environments. In this paper, we introduce a novel, universal online algorithm capable of handling arbitrary moldable tasks without assumptions about their speedup behavior. Remarkably, when applied to the specific speedup models previously studied, our algorithm achieves competitive ratios comparable to — or better than — those obtained by the specialized algorithms. Extensive experiments confirm that our universal approach consistently matches or outperforms existing model-specific algorithms, thus bridging the gap between theoretical guarantees and practical applicability. Online scheduling Moldable tasks Task graphs Competitive analysis Speedup models 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-8251720","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":573876855,"identity":"5e1ad392-6780-499f-900f-09498b03e477","order_by":0,"name":"Lucas Perotin","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAABHUlEQVRIiWNgGAWjYBACPmTOAYYKEJXAwMxgYAFiGWDTwoZgMgO1nIFrkZAgSgsDYxtMCwMeLRLJDz/+YLgjZ97ef/Bw4bzD8ubsycc+FxRI1DGwN2+TwKolzViah+GZscyZwwyHZ247bLiz51ny7Bkgh/EcK8OuJYdBmoHhcOIMiWSGw7zb0hg33MgxZuYBaZHIMcOhhfnnD4bD9RAtc9LsN9zI/wzRIv8GlxY2CR6GwwkSYC0NNolAW5ihtvBg18LzzMyax+CZ4QyewwaHeY7ZJG8488yYGegXyTaetGILLFr42ZMf3/xRcUdegr3x8WeeGgnbDceTHzMX/LHh52c/vPEGtlAGA4MD2ByAUzkYYNMyCkbBKBgFowAKAFjrV6hShqJjAAAAAElFTkSuQmCC","orcid":"","institution":"Vanderbilt University","correspondingAuthor":true,"prefix":"","firstName":"Lucas","middleName":"","lastName":"Perotin","suffix":""},{"id":573876856,"identity":"fc3d6121-af2b-4794-a0c4-ec80d283eaf8","order_by":1,"name":"Thomas Verrecchia","email":"","orcid":"","institution":"","correspondingAuthor":false,"prefix":"","firstName":"Thomas","middleName":"","lastName":"Verrecchia","suffix":""},{"id":573876858,"identity":"577f6dee-9aa3-4fe1-960e-b4eb0be38e7c","order_by":2,"name":"Padma Raghavan","email":"","orcid":"","institution":"Vanderbilt University","correspondingAuthor":false,"prefix":"","firstName":"Padma","middleName":"","lastName":"Raghavan","suffix":""}],"badges":[],"createdAt":"2025-12-01 14:53:30","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-8251720/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-8251720/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":100211706,"identity":"ef3c7516-aff7-4e7a-9d33-75a7ea756aa4","added_by":"auto","created_at":"2026-01-14 07:47:45","extension":"json","order_by":0,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":5322,"visible":true,"origin":"","legend":"","description":"","filename":"1d5b9e9eaa9045649a240113afd1ea7e.json","url":"https://assets-eu.researchsquare.com/files/rs-8251720/v1/61458df515fe9c429afc79e8.json"},{"id":100369360,"identity":"c2227cc8-3467-481d-8adf-f346dd6779cf","added_by":"auto","created_at":"2026-01-16 07:58:58","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":2655340,"visible":true,"origin":"","legend":"","description":"","filename":"PerotinSubmission.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8251720/v1_covered_66d1bb98-eff9-44a6-926e-578bc59d2d04.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Near-Optimal Universal Scheduling for Moldable Tasks: The Fair Algorithm","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":"Online scheduling, Moldable tasks, Task graphs, Competitive analysis, Speedup models","lastPublishedDoi":"10.21203/rs.3.rs-8251720/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-8251720/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eThe problem of scheduling moldable tasks on multiprocessor systems with the goal of minimizing the makespan has received significant attention, especially in contexts where tasks have dependence constraints (task graphs) or arrive dynamically (online scheduling). However, the combined setting — online scheduling of moldable task graphs — remains less explored.\u0026nbsp;\u003c/p\u003e\n\u003cp\u003ePrior studies have addressed this problem by designing algorithms specifically tailored to particular speedup models, such as Amdahl, Communication, or Roofline. Although these specialized algorithms achieve constant competitive ratios under their respective models, their applicability is severely limited in practice: each requires tasks to strictly adhere to a predefined speedup model, making them impractical for general scenarios or hybrid environments.\u0026nbsp;\u003c/p\u003e\n\u003cp\u003eIn this paper, we introduce a novel, universal online algorithm capable of handling arbitrary moldable tasks without assumptions about their speedup behavior. Remarkably, when applied to the specific speedup models previously studied, our algorithm achieves competitive ratios comparable to — or better than — those obtained by the specialized algorithms. Extensive experiments confirm that our universal approach consistently matches or outperforms existing model-specific algorithms, thus bridging the gap between theoretical guarantees and practical applicability.\u003c/p\u003e","manuscriptTitle":"Near-Optimal Universal Scheduling for Moldable Tasks: The Fair Algorithm","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2026-01-14 07:47:40","doi":"10.21203/rs.3.rs-8251720/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":"68a0bf2a-f1e0-4d1f-8e99-96bb65209c47","owner":[],"postedDate":"January 14th, 2026","published":true,"recentEditorialEvents":[{"type":"decision","content":"Revision requested","date":"2026-05-12T20:08:11+00:00","index":"","fulltext":""}],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2026-05-12T20:23:23+00:00","versionOfRecord":[],"versionCreatedAt":"2026-01-14 07:47:40","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-8251720","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-8251720","identity":"rs-8251720","version":["v1"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}