Files in this item



application/pdf9215814.pdf (4MB)Restricted to U of Illinois
(no description provided)PDF


Title:Functional parallelism: Theoretical foundations and implementation
Author(s):Girkar, Milind Baburao
Doctoral Committee Chair(s):Polychronopoulos, Constantine D.
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
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.
Issue Date:1992
Rights Information:Copyright 1992 Girkar, Milind Baburao
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9215814
OCLC Identifier:(UMI)AAI9215814

This item appears in the following Collection(s)

Item Statistics