Benutzer-und datengesteuertes Schleifen-Scheduling auf Parallelrechnern mit Distributed Shared Memory

Parallel computer systems with distributed shared memory have a physically distributed main memory and a global coherent address space for programs. When programming these machines, two aspects have to be handled carefully to efficiently utilize these computers especially with a large number of processors: load balance between processors and minimization of interprocessor communication. This thesis introduces two new techniques both based on the principle that parallel tasks are scheduled in a specific manner to processors. The first technique, the user-driven scheduling, was developed for programs where the execution time of tasks can be estimated by the programmer and where the memory access pattern is not complex. Templates are abstract index spaces in which a distribution of tasks to processors can be stored. This thesis introduces special template distributions with which the user is able to discribute parallel tasks to processors in such a way that communication is minimized. The second technique, data-driven scheduling, is suitable for programs with sequentially iterated program regions where task execution times can not be estimated in advance or where the memory access pattern is complex. A compiler modifies the relevant program region in such a way that at runtime statistical data concerning the access behaviour and execution time of tasks is gathered. Based on this data, a special weighted graph is constructed where the nodes represent tasks and where the edges represent communication. Applying graph partitioning techniques, the graph is partitioned in such a way that the sum of the node weights of all subgraphs is equal and the edge cut between the subgraphs is minimal. The computed assignment of nodes to subgraphs represents a distribution of tasks to processors. This schedule is stored in a template and it is used in subsequent executions of this program region to efficiently distribute the tasks to the processors. The advantage in efficiency compared to other techniques is shown for the user-driven as well as for the data-driven scheduling for two different parallel machines with up to 128 processors. (orig.)SIGLEAvailable from TIB Hannover: RA 831(3552) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekDEGerman