MaTCH : Mapping Data-Parallel Tasks on a Heterogeneous Computing Platform Using the Cross-Entropy Heuristic
S. Sanyal, Sajal Kumar Das · 2005
We propose in this paper a heuristic for mapping a set of interacting tasks of a parallel application onto a heterogeneous computing platform such as a computational grid. Our novel approach is based on the cross-entropy (CE) method, which is a new and extremely robust rare event simulation (RES) technique. We tailor the CE method to the requirements of the problem at hand, develop a mathematical framework, and present our algorithm, called MaTCH. This globally iterative, randomized procedure is then compared to a previously developed genetic algorithm (GA). Our preliminary experiments demonstrate the power of MaTCH, exhibiting remarkable improvements in the quality of mapping. The results indicate that, when compared to the GA, the proposed heuristic MaTCH improves upon the application execution time by over a factor of 38 on a 50-node resource graph. We further attest our results by performing an ANalysis Of VAriance (ANOVA) test on a sample data set to prove the significance of our results.