Classification of Partitioning Problems for Networks of Heterogeneous Computers


Alexey Lastovetsky, and Ravi Reddy

Department of Computer Science, University College Dublin
Belfield, Dublin 4, IRELAND

E-mail: {Alexey.Lastovetsky,Manumachu.Reddy}@ucd.ie

Abstract.
The paper presents a classification of mathematical problems encountered during 
partitioning of data when designing parallel algorithms on networks of 
heterogeneous computers. We specify problems with known efficient solutions and 
open problems. Based on this classification, we suggest an API for partitioning 
mathematical objects commonly used in scientific and engineering domains for solving 
problems on networks of heterogeneous computers. These interfaces allow the 
application programmers to specify simple and basic partitioning criteria in the 
form of parameters and functions to partition their mathematical objects. These 
partitioning interfaces are designed to be used along with various programming 
tools for parallel and distributed computing on heterogeneous networks.