Research On The Methods To Realize Dynamic Sets Based On Reversible Computing

With the rapid development of the information industry and its rising status in the world economic structure,the energy consumption brought by computing and communication has also received more and more attention.In the past,people mainly reduced the energy consumption of computers by optimizing the circuit structure or hardware architecture.However,due to various potential obstacles,the development of semiconductor technology will soon reach the turning point,and the growth of energy consumption will reach the limit in the long run.By then,people will need to use new technology to replace semiconductors.Therefore,this paper considers the origin cause of computational energy consumption to find a more energy-efficient computational method.The Landauer limit defines the amount of energy it takes a computer to "erase" a bit of information.With the development of semiconductor technology,the Landauer limit will be reached without a fundamental solution.Reversible computing is the only way to invalidate the Landauer limit.It means that the operation in the computing process can infer the input state according to its output state,thus avoiding the "erase" operation to reduce the energy consumption.However,many operations on generalpurpose computers are irreversible.Therefore,Bennett proposed a method of recording "historical operations" to convert irreversible operations into reversible operations.But this method requires extra space,which we call garbage space.There are usually irreversible operations in the traditional irreversible algorithms.When reversing traditional algorithms,it needs to consume the garbeg space to ensure the reversiblity of the algorithms.In order to decrease the garbage space,this paper designs some reversible methods to optimize the garbage space complexity of the reversible algorithm under the premise of ensuring the time complexity is unchanged.On the other hand,dynamic sets,as the underlying data structure of computer programs,have a wide and very critical application.Dynamic sets are often accompanied by shrinking,increasing,or other changes in the operation of the algorithms.They are very flexible and difficult to reversibly.Different algorithms need to perform various operations on dynamic sets,so this article designs reversible dynamic sets,which will lay the foundation for reversible algorithms.This thesis uses the Janus language and its simulation platform to reversibly design and simulate the data structure of the dynamic sets,including not only the simple data structure,such as stack,queue and linked list,but also the advanced data structure van Emde Boas tree and its related data structures,such as direct addressing,superimposed binary tree structure,superimposed a highly constant binary tree and prototype van Emde Boas structure.The reversibility of these data structures has achieved the optimal garbage space complexity under the premise of ensuring the time complexity is unchanged.What's more,the array representations of these data structures are implemented in the process of reversible simulation.