Tailoring the network to the problem: Topology configuration in hybrid electronic packet switched/optical circuit switched interconnects

We consider a hybrid electronic packet switched and optical circuit switched interconnection network for future high performance computing and datacenter systems. Given the logical task-to-task communication graph of an application, our objective is to cluster the logical parallel tasks to compute resources and configure the (reconfigurable) optical part of the hybrid interconnect to efficiently serve application communication requirements. We formulate the clustering and topology configuration problem in such a network, prove that it is NP-complete, and provide an optimal algorithm to solve it based on an integer linear programming formulation. The integer linear programming algorithm is used to optimally solve small-scale instances of the problem for the purpose of obtaining performance bounds. Aiming at large-scale, we also present a heuristic based on simulated annealing that trades-off performance for responsiveness. We measure the performance of a hybrid interconnect employing the proposed algorithm using real workloads, as well as extrapolated traffic, and compare it against application mapping on conventional fixed, electronic-only interconnects based on toroidal topologies. Copyright © 2013 John Wiley & Sons, Ltd.