Power, Time, and Location: Parallel algorithms addressing them all

For many real and abstract parallel systems, spatial location is important,
in that processors can only communicate with their neighbors, or the
communication time is a function of distance. This is true for smart
dust, supercomputer interconnection networks, the ZebraNet wildlife tracking
system, etc., and abstract (yet buildable) models such as cellular automata
and mesh-connected computers. Algorithms for such systems often need to
take location into account to minimize time. Meanwhile, power is an
increasingly important aspect of real systems, affecting their design
and algorithmic possibilities. Until now, however, algorithms for
abstract models rarely took power into account.

This expository talk will examine parallel algorithms that optimize both power
and time. In many cases there are simple time/power tradeoffs, but for some
interesting classes of problems it is possible to have the vast majority
of the processors off at any instant without increasing the time
significantly. There are numerous open research problems in this area.