About Reversible algorithms and Energy-efficient computing

[Sky89]

Hello,


About Reversible algorithms and Energy-efficient computing

Reversible algorithms behave the same way. “If you can play everything
backwards, then no energy has escaped during your computation,” says
Demaine. “That’s good news. It means we can effectively sidestep
Landauer’s principle.” While conservative computing may enable programs
to run twice as fast, reversible computing could enable them to run
millions of times faster.

Using specially devised theoretical models, Demaine and Lynch have spent
the past six months analyzing basic algorithms to see whether they can
be made reversible—or more reversible. (There’s a fundamental limit on
how reversible some algorithms can be.) Already they’ve found
more-efficient replacements for some algorithms used in everyday
computational tasks such as sorting, searching, and finding the shortest
path between two points in a network. One example is “binary search
trees,” which are procedures for organizing data so the data can be
retrieved quickly. According to Demaine, binary search trees are used in
nearly every computer ever made, and they involve millions of functions
and a lot of energy consumption. “But with a couple of tricks, we got
energy use down to zero,” he says. “With the new algorithms, we require
only the energy needed to store the data, no additional energy to
organize it.”

Demaine is pleased with their progress. “It’s like starting over,” he
says. “Take all the algorithms you learned in your undergraduate class
and throw them out the window, or look at all existing algorithms and
say, OK, this is bad, let’s make it better.” And their results so far
“just scratch the surface of what’s possible,” he says, noting in
particular the huge potential for energy savings in procedures used for
processing big data, such as when running network routers or performing
web searches.


Read more here:

http://energy.mit.edu/news/energy-efficient-computing/


Thank you,
Amine Moulay Ramdane.