Energy-Efficient Algorithms on Mesh-Connected Systems With Additional Communication Links

Energy consumption has become a critical factor constraining the design of massively parallel
computers, necessitating the development of new models and energy-efficient algorithms. In this
work we take a fundamental abstract model of massive parallelism, the mesh-connected computer,
and extend it with additional communication links motivated by recent advances in on-chip
photonic interconnects. This new means of communication with optical signals rather than electrical
signals can reduce the energy and/or time of calculations by providing faster communication
between distant processing elements. Processors are arranged in a two-dimensional grid with
wire connections between adjacent neighbors and an additional one or two layers of noncrossing
optical connections.
Varying constraints on the layout of optics affect how powerful the model can be. In this dissertation,
three optical interconnection layouts are defined: the optical mesh, the optical mesh of trees, and
the optical pyramid. For each layout, algorithms for solving important problems are presented. Since
energy usage is an important factor, running times are given in terms of a peak-power constraint,
where peak power is the maximum number of processors active at any one time. These results
demonstrate advantages of optics in terms of improved time and energy usage over the standard
mesh computer without optics. One of the most significant results shows an optimal nonlinear time/
peak-power tradeoff for sorting on the optical pyramid. This work shows asymptotic theoretical
limits of computation and energy usage on an abstract model which takes physical constraints and
developing interconnection technology into account.