Energy-efficient Algorithms Based On Reversible Computing Model

In 2016,the Moore law has been announced to be failed,the energy consumption of computation constrains the integration and the computing speed of semiconductor circuits.Many works have been done in optimizing energy consumption through adjusting the architecture of circuits or optimizing the compilation with low-energy instructions.But these previous techniques will face the limit of Landauer's principle sooner or later.The Landauer's limit shows that any irreversible operation that erases or loses one bit information will consume kTln2 energy at least.Therefore,only through reversible computing can the energy of computation be reduced lower than Landauer's limit,and the computation costs zero energy theoretically.Reversible computing was proposed by Rolf Landauer in 1961,which requires both logical and physical reversibilities.But the energy consumption of computation was far more than Landauer limit in the late 60 s,so the reversible computing didn't gain much attention.But during the past 50 years,there were still much progress achieved in reversible computing area,such as the reversible Turing Machine and the reversible logic circuits.What's more,with the technology of adiabatic circuits which promises that little energy or even no energy dissipates in the cirtuits,many researchers paied attention to reversible computing.Adiabatic reversible adders,mulituplires,ALU and even the reversible processor named Pendulum have been implemented physically.On the basis of the adiabatic reversible circuits,the architecture of reversible computer and the reversible instruction set were proposed,and many reversible languages were realized.But the reversibility in algorithms still doesn't gain much attention and little work has been done on reversible algorithms.Traditional algorithms are not designed from reversible aspects,thus many information are lost and erased during the process.To make traditional algorithms reversible,garbage space is needed to store the lost information.Unlike the general reversible simulation methods,the reversible simulation of algorithms cannot be achieved by simple translation.One has to be aware of the lost information first,so that the garbage space can achieve optimal.In the thesis many common structures and algorithms are simulated reversibly,which covers Queue,Binary Heap,Priority Queue,Search Tree and Black-Red Tree.All the operations of reversible structures use optimal garbage space and maintains the original time complexity.Sorting algorithms and graph algorithms are also analyzed and reversiblized in the thesis.All the algorithms achieve least garbage space while not increasing the time complexity.What's more,a general method is proposed for reversible simulation of Dynamic Programming algorithms and needs no garbage space at all.