Parallel Execution Models for Future Multicore Architectures

February 17, 2006
Guri Sohi | University of Wisconsin-Madison

With uniprocessor performance increases leveling off, and with the semiconductor industry moving towards multicore processors, novel ways of parallelizing the execution of a variety of computing applications will be needed. To be viable, a parallel execution model for future multicore architectures should not only mesh well with the programming styles that we expect in the future, but perhaps even leverage the characteristics of such programming styles.

This talk will review proposed parallel execution models and present Program Demultiplexing (PD), an execution model that creates concurrency in sequential programs by “demultiplexing” methods (functions or subroutines). Call sites of a demultiplexed method in the program are associated with handlers that allow the method to be separated from the sequential program and executed on an auxillary processor. The demultiplexed execution of a method (and its handler) is speculative and occurs when the inputs of the method are (speculatively) available, which is typically far in advance of when the method is actually called in the sequential execution. A trigger, composed of predicates that are based on program counters and memory write addresses, launches the (speculative) execution of the method on another processor.

Results from our initial experience with a simulation model for PD will be presented. For eight integer benchmarks from the SPEC2000 suite, programs written in C with no explicit concurrency and/or motivation to create concurrency, we achieve a harmonic mean speedup of 1.8x on four processors. We believe that PD can achieve further speedup when opportunities for concurrency are exposed to programmers and/or on applications that use modern object-oriented languages.

Given time, the talk will touch on some other hardware trends that are likely to have implications for how software is written in the future.

Speaker Details

Guri Sohi received a Ph.D in Electrical and Computer Engineering from the University of Illinois in 1985. He has been a faculty member at the University of Wisconsin-Madison since graduation, and is currently the Chair of the Computer Sciences Department. Sohi’s research has been in the design of high-performance computer systems. Topics that he has investigated in the past or continues to investigate include include dynamically-scheduled instruction-level parallel processors, out-of-order execution with precise exceptions, non-blocking caches, decentralized microarchitectures, speculative multithreading, computation reuse, memory dependence speculation and prediction, value degree of use prediction, and chip multiprocessors.He received the 1999 ACM SIGARCH Maurice Wilkes award “for seminal contributions in the areas of high issue rate processors and instruction level parallelism”. At the University of Wisconsin he was selected as a Vilas Associate in 1997 and won the WARF Kellett Mid-Career Faculty Researcher award in 2000. He is a Fellow of both the ACM and the IEEE.