A Graph-matching based Intra-node Task Assignment Methodology for SMP Clusters

摘要

Load distribution for parallel applications on a cluster of Symmetrical Multi-processors(SMP) poses a challenging problem. A cluster of SMPs essentially comprises of a finite number of computing nodes each comprising of 2 or more identical, tightly coupled processing elements, the nodes being connected over a network. While approximate methods of load balancing using standard methods like graph-partitioning, for example, can produce acceptable task assignment across the nodes, they cannot be applied to obtain optimal task assignment on the processors constituting a node. This is because of the complex optimisation involved when one considers the fact that all the processing elements in a node have only one network interface and the node turn-around time is the minimum when the computation and communication activities of the processing elements can be interleaved optimally. A graph-matching based methodology using multi-level refinement is proposed in this paper. Compared to a traditional graph-matching based load balancing algorithm, where worst case (exponential) complexity occurs in practice as the number of task modules increases, this methodology produces optimal assignments within acceptable run time using a multi-level refinement approach and hence can be used for practical applications.