Optimizing Graph Partitioning For Heterogeneous Networks

Heterogeneous network of workstations consists of a collection of PC's or workstations connected together by a network to produce high computational power without the high cost of supercomputers. It can be modeled as a graph, and graph partitioning can be used to divide a problem among the different nodes of the network. Traditional graph partitioning algorithms use edge cut as a metric for partitioning. Although it might work for homogeneous networks, heterogeneous network need a better cost function, which takes into account the message latency and network bandwidth. This thesis aims to factor these conditions into a new cost equation which was calculated for a given network. Multilevel graph partitioning tool METIS [9] was used to partition an example graph. The resulting partitions were optimized, with a mapping and boundary removal algorithm based on the new cost equations, and demonstrates that the communication cost of the application was reduced.