Algorithms Minimizing Peak Energy on Mesh-Connected Systems

Patrick Poon
Quentin F. Stout
Computer Science and Engineering, University of Michigan


Abstract: Energy consumption has become a critical factor constraining the design of massively parallel computers, necessitating the development of new models and energy-efficient algorithms. The primary component of on-chip energy consumption is data movement, and the mesh computer is a natural model of this, explicitly taking distance into account. Unfortunately the dark silicon problem increasingly constrains the number of bits which can be moved simultaneously.

For sorting, standard mesh algorithms minimize time and total data movement, and hence constraining the mesh to use only half its processors at any instant must double the time. It is anticipated that on-chip optics will be used to minimize the energy needed to move bits, but they have constraints on their layout. In an abstract model, we show that a pyramidal layout and a new power-aware algorithm allows one to sort with only a square root increase in time as the fraction of processors simultaneously powered decreases. Previous algorithms assumed fully powered systems, hence pyramid sorting was of no interest since when fully powered they are no faster than the base mesh. Our results show asymptotic theoretical limits of computation and energy usage on a model which takes physical constraints and developing interconnection technology into account.

Keywords: peak power consumption, low power, low energy algorithm, mesh-connected computer, optical interconnect, network on a chip (NoC), pyramid computer, sorting, nearest neighbor, minimum spanning tree, parallel computing, supercomputing, exascale, dark silicon

Complete paper. This paper appears in Proc. IEEE Parallel and Distributed Systems (IPDPS) 2013.


Related Work:

Quentin's Home Copyright © 2013-2016 Quentin F. Stout.