Block data decomposition for partial-homogeneous parallel networks

This paper describes a block data partitioning algorithm suited to parallel processing in a heterogeneous network environment where some of the processors have the same performance capacity. Grid problems are particularly suited to block data partitioning schemes where communication cost is reduced by locating a grid point and its neighbors on the same physical processor whenever possible. Our algorithm for partial homogeneous decomposition minimizes the cost of communication in a heterogeneous block decomposition by preserving rectangularity and taking advantage of any available processor homogeneity when partitioning the problem space.<>