Virtual topologies for massively parallel computations. (c2015)

Abstract

In their essence, recursive search tree algorithms are nothing but mere enumeration of the solution space. Most of the time is spent generating new search tree nodes with very little computation performed at each tree node. Massively parallel computations that are based on such algorithms often suffer from a large communication overhead due to the exponential growth in the number of tasks generated at each search-tree level. Cores would spend computation time generating and exchanging tasks rather than traversing the search tree. This communication overhead will only increase as we scale-up the computation, up to the point where adding new cores negatively affects the computational time. To address this issue, we propose virtual topologies: an architecture-oblivious communication graph imposed on top of the physical network to limit and manage core-to-core communication. Using the Cluster Editing problem as a case study, we show that managed cooperation, coupled with an efficient task generation and load balancing strategy, is capable of dramatically reducing the communication overhead and improving the computational throughput.