654
Boolean Algebra and Computer Logic
speCiaL iNterest paGe
Pruning Chips and Programs
Computer computations (barring coding errors) are
generally viewed as the height of accuracy. Translating truth functions into circuits that produce correct
outputs for given inputs has been the theme of this
chapter. But some computer applications do not require 100% accuracy and can tolerate a certain amount
of error. Image processing is one such application because small variations in an image are imperceptible
to the human eye. (This feature of human eyesight is
used to advantage in JPEG lossy image compression,
as discussed in Section 6.4.)
Recently, researchers looking for increased efficiency in chip design have “pruned” traditional
circuits, essentially cutting away the parts that are seldom used. Pruned chips consume less energy and are
both smaller and faster than the complete chip. We can
lump these three factors—energy, space, and time—
together under the general term “efficiency.” Experimental pruning of a chip’s addition circuit produced a
7.5% gain in overall efficiency. But of course there is
a tradeoff; some percentage of error is introduced in
the chip’s operation. The 7.5% efficiency gain came at
the cost of a 0.25% error rate. For specialized applications such as image processing, where small amounts
of error can be tolerated, the tradeoff seems to be a
good thing. Developers of this technology are looking
toward applications such as hearing aids, cameras, or
even tablet computers that could run on solar power.
The same approach is also being tried with software. For example, “loop perforation” skips some of
the iterations in a loop. This is a particularly evocative
name—“perforating a loop” sounds very much like
“pruning a chip.” Other approaches may skip entire
tasks or randomly discard some input values. “Relaxed program” is a general title for software that has
built-in nondeterminism that can dynamically prune
(skip) some of its instructions or data. The benefit is
increased runtime efficiency. The penalty is some percentage of incorrect results. And the trick, of course, is
to ensure—and formally verify—that such techniques,
while increasing efficiency, keep the output within an
acceptable error range.
“Inexact Design—Beyond Fault Tolerance,” Anthes, G.,
Communications of the ACM, April, 2013.
http://news.rice.edu/2012/05/17/computing-experts-unveilsuperefficient-inexact-chip/
http://web.mit.edu/newsoffice/2010/fuzzy-logic-0103.html
“Proving Acceptability Properties of Relaxed Nondeterministic Approximate Programs,” Carbin, M., Kim,
D., Misailovic, S., Rinard, M., ACM Conference on
Programming Language Design and Implementation,
June 11–16, 2012, Beijing, China.
http://web.mit.edu/newsoffice/2012/loop-perforation-0522.
html
C h a p t e r
8 8
Boolean Algebra and Computer Logic
speCiaL iNterest paGe
Pruning Chips and Programs
Computer computations (barring coding errors) are
generally viewed as the height of accuracy. Translating truth functions into circuits that produce correct
outputs for given inputs has been the theme of this
chapter. But some computer applications do not require 100% accuracy and can tolerate a certain amount
of error. Image processing is one such application because small variations in an image are imperceptible
to the human eye. (This feature of human eyesight is
used to advantage in JPEG lossy image compression,
as discussed in Section 6.4.)
Recently, researchers looking for increased efficiency in chip design have “pruned” traditional
circuits, essentially cutting away the parts that are seldom used. Pruned chips consume less energy and are
both smaller and faster than the complete chip. We can
lump these three factors—energy, space, and time—
together under the general term “efficiency.” Experimental pruning of a chip’s addition circuit produced a
7.5% gain in overall efficiency. But of course there is
a tradeoff; some percentage of error is introduced in
the chip’s operation. The 7.5% efficiency gain came at
the cost of a 0.25% error rate. For specialized applications such as image processing, where small amounts
of error can be tolerated, the tradeoff seems to be a
good thing. Developers of this technology are looking
toward applications such as hearing aids, cameras, or
even tablet computers that could run on solar power.
The same approach is also being tried with software. For example, “loop perforation” skips some of
the iterations in a loop. This is a particularly evocative
name—“perforating a loop” sounds very much like
“pruning a chip.” Other approaches may skip entire
tasks or randomly discard some input values. “Relaxed program” is a general title for software that has
built-in nondeterminism that can dynamically prune
(skip) some of its instructions or data. The benefit is
increased runtime efficiency. The penalty is some percentage of incorrect results. And the trick, of course, is
to ensure—and formally verify—that such techniques,
while increasing efficiency, keep the output within an
acceptable error range.
“Inexact Design—Beyond Fault Tolerance,” Anthes, G.,
Communications of the ACM, April, 2013.
http://news.rice.edu/2012/05/17/computing-experts-unveilsuperefficient-inexact-chip/
http://web.mit.edu/newsoffice/2010/fuzzy-logic-0103.html
“Proving Acceptability Properties of Relaxed Nondeterministic Approximate Programs,” Carbin, M., Kim,
D., Misailovic, S., Rinard, M., ACM Conference on
Programming Language Design and Implementation,
June 11–16, 2012, Beijing, China.
http://web.mit.edu/newsoffice/2012/loop-perforation-0522.
html
C h a p t e r
8 8