Modeling and analysis of dual block multithreading

Zuberek, W.M.

in: Applying Formal Methods: Testing, Performance, and M/E-Commerce (Lecture Notes in Computer Science 3236), Proc. European Performance Evaluation Workshop (EPEW'04) of the 24-th IFIP WG 6.1 Int. Conf. on Formal Techniques for Networked and Distributed Systems (FORTE'04), Toledo, Spain, 1-2 October 2004, pp.209-219.

Abstract:

Instruction level multithreading is a technique for tolerating long-latency operations (e.g., cache misses) by switching the processor to another thread instead of waiting for the completion of a lengthy operation. In block multithreading, context switching occurs for each initiated long-latency operation. However, processor cycles during pipeline stalls as well as during context switching are not used in typical block multithreading, reducing the performance of a processor. Dual block multithreading introduces a second active thread which is used for instruction issuing whenever the original (main) thread becomes inactive. Dual block multithreading can be regarded as a simple and specialized case of simultaneous multithreading when two (simultaneous) threads are used to issue instructions for a single pipeline. The paper develops a simple timed Petri net model of a dual block multithreading and uses this model to estimate the performance improvements of the proposed dual block multithreading.

Keywords:

Block multithreading, instruction issuing, pipelined processors, timed Petri nets, performance analysis, event-driven simulation.

References:

• Burger, D., Goodman, J.R., "Billion-transistor architectures: there and back again"; IEEE Computer, vol.37, no.3, pp.22-28, 2004.
• Byrd, G.T., Holliday, M.A., "Multithreaded processor architecture"; IEEE Spectrum, vol.32, no.8, pp.38-46, 1995.
• Dennis, J.B., Gao, G.R., "Multithreaded architectures: principles, projects, and issues"; in Multithreaded Computer Architecture: a Summary of the State of the Art, pp.1-72, Kluwer Academic 1994.
• Hamilton, S., "Taking Moore's law into the next century"; IEEE Computer, vol.32, no.1, pp.43-48, 1999.
• Hennessy, J.L., Patterson, D.A., Computer architecture - a qualitative approach (3 ed.), Morgan Kaufman 2003.
• Jesshope, C., "Multithreaded microprocessors - evolution or revolution"; in Advances in Computer Systems Architecture (LNCS 2823), pp.21-45, 2003.
• Mutlu, O., Stark, J., Wilkerson, C., Patt, Y.N., "Runahead execution: an effective alternative to large instruction windows"; IEEE Micro, vol.23, no.6, pp.20-25, 2003.
• Sinharoy B., "Optimized thread creation for processor multithreading"; The Computer Journal, vol.40, no.6, pp.388-400, 1997.
• Sohi, G.S., "Microprocessors - 10 years back, 10 years ahead"; in Informatics: 10 Years Back, 10 Years Ahead (Lecture Notes in Computer Science 2000), pp.209-218, 2001.
• Sprangle, E., Carmean, D., "Increasing processor performance by implementing deeper pipelines"; Proc. 29-th Annual Int. Symp. on Computer Architecture, Anchorage, Alaska, pp.25-34, 2002.
• Tseng, J., Asanovic, K., "Banked multiport register files for high-frequency superscalar microprocessor"; Proc. 30-th Int. Annual Symp. on Computer Architecture, pp.62-71, 2003.
• Ungerer, T., Robic, G., Silc, J., "Multithreaded processors"; The Computer Journal, vol.43, no.3, pp.320-348, 2002.
• Wilkes, M.V., "The memory gap and the future of high-performance memories"; ACM Architecture News, vol.29, no.1, pp.2-7, 2001.
• Zuberek, W.M., "Timed Petri nets - definitions, properties and applications"; Microelectronics and Reliability (Special Issue on Petri Nets and Related Graph Models), vol.31, no.4, pp.627-644, 1991.
• Zuberek, W.M., "Analysis of pipeline stall effects in block multithreaded multiprocessors"; Proc. 16-th Performance Engineering Workshop, Durham, UK, pp.187-198, 2000.
• Zuberek, W.M., "Analysis of performance bottlenecks in multithreaded multiprocessor systems"; Fundamenta Informaticae, vol.50, no.2, pp.223-241, 2002.

Available in pdf and postscript.