The architecture of an optimistic CPU: the WarpEngine

Abstract

The architecture for an optimistic, highly parallel, scalable, shared memory CPU - the WarpEngine - is described. The WarpEngine CPU allows for parallelism down to the level of single instructions and is tolerant of memory latency. Its design is based around time stamping executable instructions and all memory accesses. The TimeWarp algorithm [Jefferson 1985, 1989] is used for managing the time stamps and synchronisation. This algorithm is optimistic and requires that all computations can be rolled back. The basic functions required for implementing the control and memory system used by TimeWarp are described. The WarpEngine memory model presented to the programmer, is a single linear address space which is modified by a single thread of execution. Thus, at the software level there is no need for locks or other explicit synchronising actions when accessing the memory. The actual physical implementation, however, is multiple CPUs with their own caches and local memory with each CPU simultaneously executing multiple threads of control. Reads from memory are optimistic, that is, if there is a local copy of a memory location it is taken as the current value. However, sometimes there will be a write with an earlier time stamp in transit in the system. When it arrives it causes the original read and any dependent calculations to be re-executed.