Vectorization and Parallelization of Irregular Problems via Graph Coloring

Efficient implementations of irregular problems on vector and parallel architectures generally are hard to realize. An important class of irregular 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 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 example of application is given and possible future developments are mentioned. Contents 1 Introduction 1 2 Preliminaries 2 2.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 Data Dependences . . . . . . . . . . . . . . . . . . . . . . . . 3 3 Iteration Schemes 4 4 Gau-Seidel Iterations for Regular Problems 6 5 Ga..