{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/90511"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/90511","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Optimizing work stealing algorithms with scheduling constraints","abstract":"The fork-join paradigm of concurrent expression has gained popularity in conjunction with work-stealing schedulers. Random work-stealing schedulers have been shown to effectively perform dynamic load balancing, yielding provably-efficient schedules and space bounds on shared-memory architectures with uniform memory models. However, the advent of hierarchical, non-uniform multicore systems and large-scale distributed-memory architectures has reduced the efficacy of these scheduling policies. Furthermore, random work stealing schedulers do not exploit persistence within iterative, scientific applications. In this thesis, we prove several properties of work-stealing schedulers that enable online tracing of the tasks with very low overhead. We then describe new scheduling policies that use online schedule introspection to understand scheduler placement and thus improve the performance on NUMA and distributed-memory architectures. Finally, by incorporating an inclusive data effect system into fork--join programs with schedule placement knowledge, we show how we can transform a fork-join program to significantly improve locality.","abstract_html":"The fork-join paradigm of concurrent expression has gained popularity in conjunction with work-stealing schedulers. Random work-stealing schedulers have been shown to effectively perform dynamic load balancing, yielding provably-efficient schedules and space bounds on shared-memory architectures with uniform memory models. However, the advent of hierarchical, non-uniform multicore systems and large-scale distributed-memory architectures has reduced the efficacy of these scheduling policies. Furthermore, random work stealing schedulers do not exploit persistence within iterative, scientific applications. In this thesis, we prove several properties of work-stealing schedulers that enable online tracing of the tasks with very low overhead. We then describe new scheduling policies that use online schedule introspection to understand scheduler placement and thus improve the performance on NUMA and distributed-memory architectures. Finally, by incorporating an inclusive data effect system into fork--join programs with schedule placement knowledge, we show how we can transform a fork-join program to significantly improve locality.","abstract_has_math":false,"creators":["Lifflander, Jonathan Josiah"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Kalé, Laxmikant V","Krishnamoorthy, Sriram","Padua, David","Sarkar, Vivek","Snir, Marc"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016-07-07T19:53:25Z","date_published":"2016-07-07T19:53:25Z","updated_at":"2026-07-22T22:26:32Z","subjects":["concurrency","work-stealing","fork-join","scheduling","locality"],"languages":["en"],"rights":["Copyright 2016 Jonathan Josiah Lifflander"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/90511","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kalé, Laxmikant V","Krishnamoorthy, Sriram","Padua, David","Sarkar, Vivek","Snir, Marc"]},{"key":"dc:creator","label":"Author","values":["Lifflander, Jonathan Josiah"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2016-07-07T19:53:25Z","2016-04-11","2016-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["concurrency","work-stealing","fork-join","scheduling","locality"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2016 Jonathan Josiah Lifflander"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/90511"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The fork-join paradigm of concurrent expression has gained popularity in conjunction with work-stealing schedulers. Random work-stealing schedulers have been shown to effectively perform dynamic load balancing, yielding provably-efficient schedules and space bounds on shared-memory architectures with uniform memory models. However, the advent of hierarchical, non-uniform multicore systems and large-scale distributed-memory architectures has reduced the efficacy of these scheduling policies. Furthermore, random work stealing schedulers do not exploit persistence within iterative, scientific applications. In this thesis, we prove several properties of work-stealing schedulers that enable online tracing of the tasks with very low overhead. We then describe new scheduling policies that use online schedule introspection to understand scheduler placement and thus improve the performance on NUMA and distributed-memory architectures. Finally, by incorporating an inclusive data effect system into fork--join programs with schedule placement knowledge, we show how we can transform a fork-join program to significantly improve locality.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-07-07 without embargo terms","The student, Jonathan Lifflander, accepted the attached license on 2016-04-07 at 13:12.","The student, Jonathan Lifflander, submitted this Dissertation for approval on 2016-04-07 at 15:23.","This Dissertation was approved for publication on 2016-04-11 at 16:46.","DSpace SAF Submission Ingestion Package generated from Vireo submission #9163 on 2016-07-07 at 13:28:45","Made available in DSpace on 2016-07-07T19:53:25Z (GMT). No. of bitstreams: 3 LIFFLANDER-DISSERTATION-2016.pdf: 6810679 bytes, checksum: 180780e57ade4e40a6a0ea56dc4ebe38 (MD5) LICENSE.txt: 4216 bytes, checksum: 5c0dec9c8e3f1bd262714bc259401150 (MD5) PROQUEST_LICENSE.txt: 4562 bytes, checksum: 1486bdd71a6e7cea424674ba3e4ceaf7 (MD5) Previous issue date: 2016-04-11"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Optimizing work stealing algorithms with scheduling constraints"]}]}],"canonical_facts":{"dc:contributor":["Kalé, Laxmikant V","Krishnamoorthy, Sriram","Padua, David","Sarkar, Vivek","Snir, Marc"],"dc:creator":["Lifflander, Jonathan Josiah"],"dc:date":["2016-07-07T19:53:25Z","2016-04-11","2016-05"],"dc:description":["The fork-join paradigm of concurrent expression has gained popularity in conjunction with work-stealing schedulers. Random work-stealing schedulers have been shown to effectively perform dynamic load balancing, yielding provably-efficient schedules and space bounds on shared-memory architectures with uniform memory models. However, the advent of hierarchical, non-uniform multicore systems and large-scale distributed-memory architectures has reduced the efficacy of these scheduling policies. Furthermore, random work stealing schedulers do not exploit persistence within iterative, scientific applications. In this thesis, we prove several properties of work-stealing schedulers that enable online tracing of the tasks with very low overhead. We then describe new scheduling policies that use online schedule introspection to understand scheduler placement and thus improve the performance on NUMA and distributed-memory architectures. Finally, by incorporating an inclusive data effect system into fork--join programs with schedule placement knowledge, we show how we can transform a fork-join program to significantly improve locality.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-07-07 without embargo terms","The student, Jonathan Lifflander, accepted the attached license on 2016-04-07 at 13:12.","The student, Jonathan Lifflander, submitted this Dissertation for approval on 2016-04-07 at 15:23.","This Dissertation was approved for publication on 2016-04-11 at 16:46.","DSpace SAF Submission Ingestion Package generated from Vireo submission #9163 on 2016-07-07 at 13:28:45","Made available in DSpace on 2016-07-07T19:53:25Z (GMT). No. of bitstreams: 3 LIFFLANDER-DISSERTATION-2016.pdf: 6810679 bytes, checksum: 180780e57ade4e40a6a0ea56dc4ebe38 (MD5) LICENSE.txt: 4216 bytes, checksum: 5c0dec9c8e3f1bd262714bc259401150 (MD5) PROQUEST_LICENSE.txt: 4562 bytes, checksum: 1486bdd71a6e7cea424674ba3e4ceaf7 (MD5) Previous issue date: 2016-04-11"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/90511"],"dc:language":["en"],"dc:rights":["Copyright 2016 Jonathan Josiah Lifflander"],"dc:subject":["concurrency","work-stealing","fork-join","scheduling","locality"],"dc:title":["Optimizing work stealing algorithms with scheduling constraints"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:32Z"}