Dynamic thread resizing for speculative multithreaded processors

There is a growing interest in the use of speculative multithreading to speed up the execution of a program. In speculative multithreading model, threads are extracted from a sequential program and are speculatively executed in parallel, without violating sequential program semantics. In order to get the best performance from this model, a highly accurate thread selection scheme is needed in order to accurately assign threads to processing elements (PEs) for parallel execution. This is done using a thread predictor that assigns threads to PEs sequentially. However, this in-order thread assignment has severe limitations. One of the limitations is when the thread predictor is unable to predict the successor of a particular thread. This may cause successor PEs to remain idle for many cycles. Another limitation has to do with control independence. When a misprediction occurs, all threads, starting from the misprediction point, get squashed, although many of them may be control independent of the misprediction. In this paper we present a hierarchical technique for building threads, as well as a non-sequential scheme of assigning them to PEs, and a selective approach to squash threads in case of misprediction, in order to take advantage of control independences. This technique uses dynamic resizing, and builds threads in two steps, statically using the compiler as well as dynamically at run-time. Based on the dynamic behavior of the program, a thread can dynamically expand or shrink in size, and can span several PEs. Detailed simulation results show that our dynamic resizing based approach results in a 11.6% average increase in speedup relative to a conventional speculative multithreaded processor.