Data partitioning

Load balancing is crucial in High Performance Computing. Generally, unstructured problems solved with irregular data distributions perform more efficiently than those using a regular data distribution such as block or cyclic. In the case of irregular distribution various partitioning algorithms were designed (see: Sprint, Party, Jostle, Parmetis). They can be categorized as follows:

• edge-based partitioners which use edge information to obtain data distribution patterns,
• coordinate-based partitioners assume that most of the interactions occur between vertices that are physically proximate in two or more dimensions. Usually, they provide faster but lower quality partitioning than the former methods.

The partitioning methods are usually very complex as they also take under consideration generalizations such as different weights for vertices or edges, arbitrary numbers of final partitions, specific load balance criteria or focus on even more complex cost functions. The performance of partitioning methods is highly implementation-dependent and it might be very time consuming for the user to optimize the partitioning code.

Created by Katarzyna Zając