Efficient Parallelization using Combined Loop and Data Transformations

This paper attempts to minimize parallelization overhead on distributed shared memory machines, such as the SGi Origin 2000, by the combination of non-singular loop and data transformations. We show that conflicting requirements on a loop transformation may be resolved by using a data transformation...

Full description

Saved in:
Bibliographic Details
Main Authors: O'Boyle, M. F. P., Knijnenburg, P. M. W.
Format: Conference Proceeding
Language:English
Subjects:
Theory of computation
Theory of computation > Models of computation
Theory of computation > Models of computation > Concurrency
Theory of computation > Models of computation > Concurrency > Parallel computing models
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper attempts to minimize parallelization overhead on distributed shared memory machines, such as the SGi Origin 2000, by the combination of non-singular loop and data transformations. We show that conflicting requirements on a loop transformation may be resolved by using a data transformation and vice-versa. We develop optimization criteria for locality, synchronization and communication and show that neither loop nor data transformations can be solely used for efficient parallelization. This leads to the development of a novel global optimization heuristic which is applied to 3 SPEC kernels where it is shown to outperform techniques solely based on loop or data transformations and to give significant improvement over an existing state-of-the- art commercial auto-parallelizer.
DOI:10.5555/520793.825727