next up previous
Next: What are the implications Up: Design and Implementation of Previous: What is the minimum

How to support the reversible, symmetric flow of control on a collection non-PRC processors?

Control flow can be made perfectly reversible through the use of having additional low-level structures that non-reversible, standard microprocessors do not have, These structures include a branch register, direction bit and a program counter that based on the direction bit, increments or decrements  [40]. The idea here is to use what are called paired branches from the Pendulum Instruction Set which use constructive addition/subtraction operations to record in the branch register from where a computation came. The program counter in microprocessor is conditionally linked to the value contained in the branch register. If the branch register (BR) is zero, the program counter (PC) is incremented to the next instruction or decremented to the previous instruction in the code segment if the direction bit is true. If the branch register is non-zero, the program counter is assigned as $ PC += BR$. When a branch instruction is processed, the branch register is assigned as $ BR += offset$. To support a simple $ if$ statement, two branch instructions are used. The first goes to the destination. At the destination label, a second branch is processed whose destination is the source. Now, using the previously described rules, we observe that $ BR$ equals the offset to destination after it process the first branch. However, when we process the second branch instruction it effectively decrements the $ BR$ to zero and regular forward processing continues. So in effect we are linking branches together to reflect the taken path through the code. Paired branches can be used to support reversible loops and function calls as well. However, how do we efficiently realize this functionality in a high-level programming language?

Because today's microprocessors do not support reverse execution, the solution requires the use of separate code paths. Currently this is the approach in TiPRC. However, in TiPRC, the control state is recorded an stored with the event that is currently being processed. PRC does not retain processed events except for the most recently processed event sent from each distinct LP. Consequently, the reverse execution path is lost using this approach. Thus, we need to develop modeling approaches that allow a symmetric flow of control between the forward and reverse code paths that are based of the state of the LP and the event data. This also suggests that ``stack'' variables such as $ for$ loop index variables that usually only have a temporary life will need to be made persistent and stored within the state of the LP.


next up previous
Next: What are the implications Up: Design and Implementation of Previous: What is the minimum
Christopher D. Carothers 2002-03-07