Fast Track: A Software System for Speculative Program Optimization

 
Fast track is a software system that enables speculation on unsafe optimizations by leveraging the extra processors in multicore systems.  Fast track consists of a programming interface and a supporting runtime system.   The fast track programming interface lets the programmer install unsafe optimized code while leaving the correctness checking to the runtime system.   The following code snippet demonstrates how to program with fast track.  

while (...) {
    ...
    if (FastTrack ()){
        /* unsafely */
        /* optimized */
        fast_fortuitous();
    }
    else {
        /* safe code */
        safe_sequential();
    }
    EndDualTrack();
    ...
}

Both safe and unsafe version of the same code region are placed within a dual track region.   The safe and unsafe tracks are launched in parallel at runtime.  At the end of the dual track region the final state of the fast track,  which is potentially incorrect,   is checked against the final state of the safe track.   If the fast track has produced correct results,  the system follows control from the fast track and discards the slow track.  Otherwise, the system continues from the slow track and squashes the fast track.  The end-of-check could be perceived as a barrier semantically to guarantee consistency at the end of each dual track region.  However,  if the fast track is correct it implies that the continuation of it is also valid hence shouldn't have been delayed.    The fast track runtime doesn't stall but continues speculatively at the end of a fast track.   The continuous speculation in fast track renders great opportunity to promote aggressive optimization while exploiting parallelism in multicores...

For more details about fast track,  please refer to our paper published in CGO 2009.  portal.acm.org/citation.cfm
 
People:
Kirk Kelsey,  Tongxin Bai,  Chen Ding

Groups: