Dynamic reordering of high latency transactions using a modi ed micropipeline

Abstract Time warp based simulation of discreteevent systems is an ecient way to overcome the syn chronization overhead during distributed simulation As computations may proceed beyond synchronization barriers in time warp multiple checkpoints of state need to be maintained to be able to rollback invalidated branches of the lookahead execution An ecient mechanism to implement state rollback has been proposed in In this environment a dedicated Rollback Chip RBC maintains multiple versions of state by re sponding to a set of control instructions interspersed with the regular stream of dataaccess instructions As these control instructions have latencies that are orders of magnitude more than the latencies of dataaccess instructions a strict ordering of the instructions may lead to large ineciencies This paper describes a dynamic instruction reordering scheme that optimizes multiple pending instruc tions to achieve higher throughput A modi ed asynchronous micropipeline called the Asynchronous Reorder Pipeline ARP has been chosen to implement this scheme ARP can be easily adapted for supporting dy namic instruction reordering in other situations also After outlining the design of the ARP we present its high level protocol and a correctness argument We then present two new primitive asynchronous compo nents that are used in the ARP a lockable Celement LockC and an exchange pipeline stage ExLatc