Time-stamp generation for optimistic parallel computing

Optimistic execution techniques are widely used in the field of parallel discrete event simulation. In this paper, we show that optimistic execution can also be used to parallelize program control structures. We discuss the requirements for handling unbounded constructs and demonstrate the need for a flexible time-stamp allocation scheme. We present a scheme using variable-length time-stamps which allows an arbitrary number of time-stamps to be generated between any pair of existing time-stamps. The ordering relation defined for these time-stamps is similar to that for fractional numbers: for two consecutive numbers of a given length it is always possible to generate a number whose value falls between them. Optimizations which improve the efficiency of time-stamp allocation for typical program structures are presented, together with an analysis of the cost. We show that the size of time-stamps is manageable even for programs with large, complex, control structures. Finally, we give an example of the use of time-stamps in parallelizing a simple control structure