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.

• Space, Time, Power: Evolving Concerns for Parallel Algorithms, a talk about the evolution of parallel computers and the goals/concerns that people had, leading to the current concern about minimizing energy and peak power. It includes mention of optical interconnects.
• My papers in parallel computing, and an overview of my research
• A whimsical explanation of parallel computing, a tutorial, Parallel Computing 101, and a list of parallel computing resources

Copyright © 2013-2018 Quentin F. Stout.