Design Based Methods for the Mapping of Algorithms to Parallel Processors

We present mapping methods which are derived from combinatorics of experimental designs. Experimental designs also known as combinatorial designs are a part of discrete mathematics, which can provide many useful structures and efficient tools for problems in computer science. This is of much interest especially for parallel processing, as it is still suffering from the lack of theoretical concepts. We will first show how parallel architectures and parallel programs can be described as combinatorial designs. This transformation allows the use of combinatorial methods for the solution of tasks emerging in parallel processing like partitioning, embedding, and mapping. Building up on the concept of parallel algorithms and computers as designs, several mapping strategies evolve. On one hand the use of designs offers much more flexibility than simple graphs, on the other hand the quasi-standard graph description concept can be integrated into the design description concept