Automatically partitioning threads based on remote paths

In order to program multithreaded architectures effectively, compiler support to automatically partition programs into threads is essential. This paper proposes a remote-path-based thread partitioning framework, which can generate low-level threads from procedural programs automatically. The framewo...

Full description

Saved in:
Bibliographic Details
Main Authors: Xinan Tang, Gao, G.R.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Bandwidth
Buildings
Communication switching
Communication system control
Delay
Parallel processing
Partitioning algorithms
Program processors
Yarn
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In order to program multithreaded architectures effectively, compiler support to automatically partition programs into threads is essential. This paper proposes a remote-path-based thread partitioning framework, which can generate low-level threads from procedural programs automatically. The framework has been implemented in the EARTH-C compiler, which uses a data dependence graph (DDG) as an intermediate representation for thread partitioning. To make the compiler work fast, a practical O(n/sup 2/) algorithm is designed to build a non-redundant DDG. To generate correct and efficient threaded code, the remote path heuristic is employed to satisfy thread partitioning constraints and to schedule threads to run quickly. Experimental results show that the DDG building algorithm is fast and the remote-path-based heuristic is very effective in partitioning programs into "optimized" threads.
ISSN:1521-9097
2690-5965
DOI:10.1109/ICPADS.1998.741146