{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/19031"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/19031","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Functional parallelism: Theoretical foundations and implementation","abstract":"Thus far, parallelism at the loop level (or data-parallelism) has been almost exclusively the main target of parallelizing compilers. The variety of new parallel architectures and recent progress in interprocedural dependence analysis suggest new directions for the exploitation of parallelism across loop and procedure boundaries (or functional-parallelism). This thesis studies the problem of extracting functional parallelism from sequential programs. It presents the Hierarchical Task Graph (HTG) as an intermediate parallel program representation which encapsulates data and control dependences, and which can be used for the extraction and exploitation of functional parallelism. Control and data dependences require synchronization between tasks, and hence the problem of eliminating redundant control and data dependences is important. We show that determining precedence relationship is crucial in finding the essential data dependences for synchronization purposes, that there exists a unique minimum set of essential data dependences, and that finding this minimum set is NP-hard and NP-easy. We present heuristic algorithms, which appear to work well in practice, to find the minimum set of data dependences. The control and data dependences are used to derive execution conditions for tasks which maximize functional parallelism. We discuss the issue of optimization of such conditions and propose optimization algorithms. The hierarchical nature of the HTG facilitates efficient task-granularity control during code generation, and thus applicability for a variety of parallel architectures. The HTG has been implemented in the Parafrase-2 compiler and is used as the intermediate representation for generating parallel source code.","abstract_html":"Thus far, parallelism at the loop level (or data-parallelism) has been almost exclusively the main target of parallelizing compilers. The variety of new parallel architectures and recent progress in interprocedural dependence analysis suggest new directions for the exploitation of parallelism across loop and procedure boundaries (or functional-parallelism). This thesis studies the problem of extracting functional parallelism from sequential programs. It presents the Hierarchical Task Graph (HTG) as an intermediate parallel program representation which encapsulates data and control dependences, and which can be used for the extraction and exploitation of functional parallelism. Control and data dependences require synchronization between tasks, and hence the problem of eliminating redundant control and data dependences is important. We show that determining precedence relationship is crucial in finding the essential data dependences for synchronization purposes, that there exists a unique minimum set of essential data dependences, and that finding this minimum set is NP-hard and NP-easy. We present heuristic algorithms, which appear to work well in practice, to find the minimum set of data dependences. The control and data dependences are used to derive execution conditions for tasks which maximize functional parallelism. We discuss the issue of optimization of such conditions and propose optimization algorithms. The hierarchical nature of the HTG facilitates efficient task-granularity control during code generation, and thus applicability for a variety of parallel architectures. The HTG has been implemented in the Parafrase-2 compiler and is used as the intermediate representation for generating parallel source code.","abstract_has_math":false,"creators":["Girkar, Milind Baburao"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Polychronopoulos, Constantine D."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T11:54:52Z","date_published":"2011-05-07T11:54:52Z","updated_at":"2026-07-22T22:25:12Z","subjects":["Computer Science"],"languages":["eng"],"rights":["Copyright 1992 Girkar, Milind Baburao"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9215814","(UMI)AAI9215814"],"render_values":[{"text":"AAI9215814","href":null,"code":true},{"text":"(UMI)AAI9215814","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/19031","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Polychronopoulos, Constantine D."]},{"key":"dc:creator","label":"Author","values":["Girkar, Milind Baburao"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T11:54:52Z","10000-01-01","1992"]},{"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":["Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1992 Girkar, Milind Baburao"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9215814","(UMI)AAI9215814","http://hdl.handle.net/2142/19031"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thus far, parallelism at the loop level (or data-parallelism) has been almost exclusively the main target of parallelizing compilers. The variety of new parallel architectures and recent progress in interprocedural dependence analysis suggest new directions for the exploitation of parallelism across loop and procedure boundaries (or functional-parallelism). This thesis studies the problem of extracting functional parallelism from sequential programs. It presents the Hierarchical Task Graph (HTG) as an intermediate parallel program representation which encapsulates data and control dependences, and which can be used for the extraction and exploitation of functional parallelism. Control and data dependences require synchronization between tasks, and hence the problem of eliminating redundant control and data dependences is important. We show that determining precedence relationship is crucial in finding the essential data dependences for synchronization purposes, that there exists a unique minimum set of essential data dependences, and that finding this minimum set is NP-hard and NP-easy. We present heuristic algorithms, which appear to work well in practice, to find the minimum set of data dependences. The control and data dependences are used to derive execution conditions for tasks which maximize functional parallelism. We discuss the issue of optimization of such conditions and propose optimization algorithms. The hierarchical nature of the HTG facilitates efficient task-granularity control during code generation, and thus applicability for a variety of parallel architectures. The HTG has been implemented in the Parafrase-2 compiler and is used as the intermediate representation for generating parallel source code.","Made available in DSpace on 2011-05-07T11:54:52Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9215814.pdf: 4381703 bytes, checksum: 5942409d32d3573a83f5582576175cf0 (MD5) Previous issue date: 1992","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:34:11Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:12:57-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Functional parallelism: Theoretical foundations and implementation"]}]}],"canonical_facts":{"dc:contributor":["Polychronopoulos, Constantine D."],"dc:creator":["Girkar, Milind Baburao"],"dc:date":["2011-05-07T11:54:52Z","10000-01-01","1992"],"dc:description":["Thus far, parallelism at the loop level (or data-parallelism) has been almost exclusively the main target of parallelizing compilers. The variety of new parallel architectures and recent progress in interprocedural dependence analysis suggest new directions for the exploitation of parallelism across loop and procedure boundaries (or functional-parallelism). This thesis studies the problem of extracting functional parallelism from sequential programs. It presents the Hierarchical Task Graph (HTG) as an intermediate parallel program representation which encapsulates data and control dependences, and which can be used for the extraction and exploitation of functional parallelism. Control and data dependences require synchronization between tasks, and hence the problem of eliminating redundant control and data dependences is important. We show that determining precedence relationship is crucial in finding the essential data dependences for synchronization purposes, that there exists a unique minimum set of essential data dependences, and that finding this minimum set is NP-hard and NP-easy. We present heuristic algorithms, which appear to work well in practice, to find the minimum set of data dependences. The control and data dependences are used to derive execution conditions for tasks which maximize functional parallelism. We discuss the issue of optimization of such conditions and propose optimization algorithms. The hierarchical nature of the HTG facilitates efficient task-granularity control during code generation, and thus applicability for a variety of parallel architectures. The HTG has been implemented in the Parafrase-2 compiler and is used as the intermediate representation for generating parallel source code.","Made available in DSpace on 2011-05-07T11:54:52Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9215814.pdf: 4381703 bytes, checksum: 5942409d32d3573a83f5582576175cf0 (MD5) Previous issue date: 1992","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:34:11Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:12:57-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9215814","(UMI)AAI9215814","http://hdl.handle.net/2142/19031"],"dc:language":["eng"],"dc:rights":["Copyright 1992 Girkar, Milind Baburao"],"dc:subject":["Computer Science"],"dc:title":["Functional parallelism: Theoretical foundations and implementation"],"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:25:12Z"}