Rafael H. Saavedra-Barrera and David E. Culler

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-91-623
April 1991

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/CSD-91-623.pdf

Multithreading is an architectural technique aimed at maintaining high processor utilization in the presence of large memory or interprocessor communication latency. While waiting for a remote reference to complete, the processor switches to another execution thread. Several realizations of this concept have been proposed, but little data is available on the actual costs and benefits. This paper presents an analytical model of multithreaded execution, which may serve to guide and explain empirical studies. The model is based on three key parameters: thread run-length, switch cost, and latency. A closed-form expression for processor utilization is obtained for deterministic and stochastic run-lengths. The derivation involves identifying specific patterns in the very large set of equations forming the Markov chain. Using this result, three operating regimes are identified for a multithreaded processor subject to long latencies: linear, where utilization is proportional to the number of threads per processor, saturation, where utilization is determined only by the run-length and switch cost, and transition between the other regimes. The model can be used to estimate the effects of several architectural variations.

BibTeX citation:

@techreport{Saavedra-Barrera:CSD-91-623,
    Author = {Saavedra-Barrera, Rafael H. and Culler, David E.},
    Title = {An Analytical Solution for a Markov Chain Modeling Multithreaded Execution},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1991},
    Month = {Apr},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/6396.html},
    Number = {UCB/CSD-91-623},
    Abstract = {Multithreading is an architectural technique aimed at maintaining high processor utilization in the presence of large memory or interprocessor communication latency. While waiting for a remote reference to complete, the processor switches to another execution thread. Several realizations of this concept have been proposed, but little data is available on the actual costs and benefits. This paper presents an analytical model of multithreaded execution, which may serve to guide and explain empirical studies. The model is based on three key parameters: thread run-length, switch cost, and latency. A closed-form expression for processor utilization is obtained for deterministic and stochastic run-lengths. The derivation involves identifying specific patterns in the very large set of equations forming the Markov chain. Using this result, three operating regimes are identified for a multithreaded processor subject to long latencies: linear, where utilization is proportional to the number of threads per processor, saturation, where utilization is determined only by the run-length and switch cost, and transition between the other regimes. The model can be used to estimate the effects of several architectural variations.}
}

EndNote citation:

%0 Report
%A Saavedra-Barrera, Rafael H.
%A Culler, David E.
%T An Analytical Solution for a Markov Chain Modeling Multithreaded Execution
%I EECS Department, University of California, Berkeley
%D 1991
%@ UCB/CSD-91-623
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/6396.html
%F Saavedra-Barrera:CSD-91-623