2026-09-19T03:24:36Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/19031 2023-07-10 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

eng Copyright 1992 Girkar, Milind Baburao Polychronopoulos, Constantine D. Girkar, Milind Baburao 2011-05-07T11:54:52Z 2011-05-07T11:54:52Z 10000-01-01 1992 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 AAI9215814 (UMI)AAI9215814 http://hdl.handle.net/2142/19031 Computer Science Functional parallelism: Theoretical foundations and implementation text Computer Science Computer Science University of Illinois at Urbana-Champaign Dissertation Ph.D.