SYMPOSIUM MINISYMPOSIA

ABSTRACT

Currently, dynamic unstructured graphs are being used as models in a variety of computationally intensive scientific applications. Weights of vertices represent computational loads while weights of edges represent communication costs. To improve the efficiency of these applications, they are often parallelized. This parallelization requires evenly dividing the graph among the participating processors (termed "partitions") in such a way that the communication cost is minimized. This cost (termed "edge cuts") is measured by summing the weights of those edges which connect vertices across partitions and is the main heuristic used to measure the quality of a given partition.

Several algorithms have been developed for partitioning graphs. Some sacrifice quality in order to achieve relatively fast partitioning times, while others sacrifice short execution times to achieve relatively high quality partitions. In either case, the application could still suffer inefficient execution times due to load imbalances caused by other factors such as systemic interferences from other applications executing on one or more of the participating processors.

To overcome unpredictable load imbalances, dynamic load balancing techniques such as Fractiling have been developed. Fractiling is a dynamic scheduling technique based on a probabilistic analysis that adapts to algorithmic and systemic load imbalances while maximizing data locality. It draws from earlier loop scheduling techniques where iterates are dynamically scheduled in decreasing size chunks to reduce synchronization. The early larger chunks have relatively little overhead while their uneven finishing times are smoothed over by later smaller chunks.

Initially, the work of a Fractiling application is completely and evenly divided among the partitions. Each partition is then responsible for subdividing its own work into the decreasing smaller chunk sizes before processing it. This means that a Fractiling application which uses unstructured graphs as its data model must perform graph partitioning many times throughout its execution. Each partitioning incurs overhead which becomes more cost prohibitive as the number of tiles each partition is responsible for increases. There are several ways in which this could happen. First, a larger graph could be used. Second, the size of the smallest allowable chunk size could be decreased. Lastly, the graph could be dynamic in nature, resulting in nodes being added to the various partitions throughout the execution of the application. Because of this, a highly efficient graph partitioning algorithm must be utilized.

This paper presents a timing and edge cut analysis of the various algorithms implemented in several currently available graph partitioning packages which will be used for Fractiling applications currently under development. These packages include: Chaco, developed at Sandia National Laboratories; Jostle, developed at the University of Greenwich; METIS, developed the University of Minnesota; ParMETIS, also developed at the University of Minnesota; and Party, developed at the University of Paderborn.

Getting More Information

To obtain more information about the meeting send e-mail to: fscc98@pax.st.usm.edu.

Return to PAX
Return to USM

USM
inquire@delphi.st.usm.edu
Updated
http://pax.st.usm.edu