Functional parallelism: Theoretical foundations and implementation
Girkar, Milind Baburao
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/19031
Description
Title
Functional parallelism: Theoretical foundations and implementation
Author(s)
Girkar, Milind Baburao
Issue Date
1992
Doctoral Committee Chair(s)
Polychronopoulos, Constantine D.
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
