Communications-Aware Process Placement Taking into Account Symmetries of Topology

摘要

The speed of communications is not uniform in multilevel high-performance computers and multicore clusters. Therefore the communication performance depends on the location of parallel processes within the system. The communication pattern of a parallel algorithm may also be no uniform - different processes may need to exchange different amounts of data. Therefore it is preferable to locate the processes that communicate most to the cores where interconnection is the fastest. The best placement of processes can be found by a combinatorial optimization trying to match the communication pattern to multicore hardware. Topology of multicore clusters often has symmetries, for example the cores on the same chip may have the same communication speed. Therefore in this paper a way is proposed to take such symmetries into account reducing the search space and fasten optimization. A branch and bound algorithm for the process placement is proposed and the impact of the avoidance of exploration of equivalent solutions is demonstrated. An experimental investigation has been carried out to evaluate the performance of the developed algorithm.