On the classic parallel computation side, Fujimoto designed the Virtual Time Machine(VTM) [43] and Rollback Chip [46] as hardware mechanisms for realizing optimistic parallel computation of general purpose applications. The key idea here was that basic block structures can be encapsulated into events and scheduled in a virtual-time to runtime code structure mapping. Whenever shared variables are referenced out of time stamp order, the Rollback Chip undoes these computations back by using copies of the state stored in hidden locations in the modified virtual memory structure called Space-Time Memory.
Space-Time Memory treats memory as a 2-dimensional space where all addresses are provided at any given point in the virtual time line. However, this 2-D structure is realized on a 1-D physical memory. Clearly physical memory space is an issue. To tackle this problem, a virtual-time based reference list is kept on each shared variable. Whenever a variable is written, a new version on the list is created. Whenever a process reads the shared variable, the virtual time of the read is recorded on the appropriate version. This structure then allows the immediate detection of out-of-order reads and writes. When detected, the rollback chip re-establishes the past state and erases all incorrect computations.
We propose to investigate how PRC could be applied in a similar way to support the automatic parallelization of sequential yet reversible programs. The key idea here is to exploit reverse computation such that we can remove much of the memory versioning and greatly reduce the overall complexity of Space-Time Memory.