Low Power Mesh Algorithms for Image
Problems
Quentin F. Stout
Computer Science and Engineering, University of Michigan
Extended Abstract: We analyze a physically motivated
fine-grained mesh-connected computer model, assuming that
a word of information takes a fixed area and that it takes unit time and unit
energy to move a word unit distance. This is a representation of computing on a
chip with myriad tiny processors arranged as a mesh.
While most mesh algorithms
assume all processors are active at all times, we give
algorithms that have only a few processors active at any one time, which
reduces the power required. We apply this approach to basic problems involving
images, showing that there can be dramatic reductions in the peak power with
only small, if any, changes in the time required.
The algorithms are described in
terms of ``squirrels’’ which carry information from one place to another, or which
take a path in which they are looking for appropriate information. The presence
of a squirrel indicates that the processor is active.
We also show that these
algorithms give a more efficient way to utilize power when more power is
available. Here we still use the same pattern of activating processors,
but use the extra power to increase their clock rate, i.e., to speed up
the computation.
Keywords: fine-grained, mesh-connected computer,
low power algorithm, image processing, connected components, maze, closest
point problems, time/power tradeoffs.
Related work: Much of this work was first disclosed in
an abstract at Symp. Parallelism in
Algorithms and Architectures (SPAA) 2006.
|
|
Copyright
© 2022 Quentin F. Stout. |
