OPTIMIZING GRAPH PARTITIONING FOR HETEROGENEOUS NETWORKS
Priyadarshini Pachaimuthu · OhioLink ETD Center (Ohio Library and Information Network) · 2007
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.