Physical optimization algorithms for mapping data to distributed-memory multiprocessors

Abstract

We present three parallel physical optimization algorithms for mapping data to distributed-memory multiprocessors, concentrating on irregular loosely synchronous problems. We also present a technique for efficient mapping of large data sets. The algorithms include a parallel genetic algorithm (PGA), a parallel neural network algorithm (PNN) and a parallel simulated annealing algorithm (PSA). An important feature of these algorithms is that they deviate from the operation of their sequential counterparts in order to achieve reasonable speed-ups and, yet, they maintain similar solution qualities. PGA has excellent speed-ups by virtue of the natural evolution model on which it is based. PSA and PNN include communication schemes adapted to the properties of the mapping problem and of the algorithms themselves for reducing the communication overhead. The performances of the three physical optimization algorithms are evaluated and compared, among themselves and with previous good algorithms, for a variety of test cases. They are found to produce high quality mapping solutions and do not show a bias towards particular problem configurations. However, they are slower than previous algorithms. Further, the comparison results show that the three algorithms are suitable for different requirements of mapping time and quality. PGA produces the best solutions, followed by PSA and then PNN. But, PNN is the fastest and PGA is the slowest. The technique proposed for large problems is based on a pre-mapping graph contraction heuristic algorithm, which results in a smaller search space. Graph contraction leads to remarkable reductions in mapping time, while maintaining good mapping qualities. It allows large-scale mapping to become efficient, especially when the physical optimization algorithms are used.