What are the implications on event list management?

Priority queue data structures, such as the Calendar Queue [14], and Splay Tree [92,93], are used to efficiently maintain the list of pending events in timestamp order. In the parallel simulation setting (conservative and optimistic), each processor usually maintains its own local priority queue [27,22,31,32,60,41,42,44,82,86,90,97]. When an event in the past of an LP (i.e., straggler event) arrives at a processor, a rollback to the time of the straggler event would commence. Under PRC, the LP, using only its current state, the last processed event for each sender LP and most recent set of output events to tract down the incorrect forward computation paths, would begin to execute in the reverse direction by scheduling events into the past. Consequently, the event-list algorithm would be required to switch from sorting events by lowest timestamp first (LTF) to highest timestamp first (HTF).

Our solution to this problem is to negate (i.e., flip the sign of) the event timestamps in order to support reverse processing of events. For example, suppose an LP forward processes events at times 5.0, 10.0 and 15.0. For reverse execution, the LP would do -15.0, -10.0 and -5.0. Because the IEEE 754 floating-point standard partitions the representation of floating-point numbers into fields, the sign bit can be readily manipulated without effecting either the mantissa or the exponent fields, which ensures that the magnitude of timestamps will be unaffected by the repeated switch from either forward or reverse execution. The specific reversal of floating-point operations is discussed below. This approach allows the reuse of a standard LTF priority queue data structure for reverse event processing and avoids having to implement a separate HTF priority queue.