Efficient implementations of irregular problems on vector and parallel architectures are generally hard to realize. An important class of problems are Gaus-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.
['Hans-Christian Hege', 'H. Stüben']
Vectorization and parallelization of irregular problems via graph coloring