Vectorization and Parallelization of Irregular Problems via Graph coloring.

Please always quote using this URN: urn:nbn:de:0297-zib-443
  • Efficient implementations of irregular problems on vector and parallel architectures are generally hard to realize. An important class of problems are Gauß-Seidel iteration schemes applied to irregular data sets. The unstructured data dependences arising there prevent restructuring compilers from generating efficient code for vector or parallel machines. It is shown, how to structure the data dependences by decomposing the underlying data set using graph coloring techniques and by specifying a particular execution order already on the algorithm level. Methods to master the irregularities originating from different types of tasks are proposed. An application is given and some open issues and future developments are discussed.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Hans-Christian Hege, Hinnerk Stüben
Document Type:ZIB-Report
Date of first Publication:1990/11/28
Series (Serial Number):ZIB-Report (SC-90-16)
Published in:Appeared in: Proc. of the ACM 1991 Int. Conf. on Supercomputing, June 1991, Cologne, pp. 47-56 (1991)
DOI:https://doi.org//10.1145/109025.109042