Analysis of pipeline stall effects in block multithreaded multiprocessors

Zuberek, W.M.

Proc. 16-th Performance Engineering Workshop, Durham, UK, 24-25 July 2000, pp.187-198.

Abstract:

In block multithreaded processors, instruction dependencies occasionally stall the pipeline for one or more processor cycles. The paper uses a timed Petri net model of a multithreaded multiprocessor to study the influence of pipeline stalls on the performance of processors. Presented results are obtained by simulation of the net model.

Keywords:

Instruction-level multithreading, block multithreading, multithreaded multiprocessors, distributed-memory architectures, pipeline stalls, timed Petri nets, discrete-event simulation.

References:

• Agarwal, A., "Performance tradeoffs in multithreaded processors"; IEEE Trans. on Parallel and Distributed Systems, vol.3, no.5, pp.525-539, 1992.
• Alverson, R., Callahan, D., Cummings, D., Koblenz, B., Posterfield, A., Smith, B., "The Tera computer system"; Proc. Int. Conf. on Supercomputing, Amsterdam, The Netherlands, pp.1-6, 1990.
• Boothe, B. and Ranade, A., "Improved multithreading techniques for hiding communication latency in multiprocessors"; Proc. 19-th Annual Int. Symp. on Computer Architecture, pp.214-223, 1992.
• Byrd, G.T., Holliday, M.A., "Multithreaded processor architecture"; IEEE Spectrum, vol.32, no.8, pp.38-46, 1995.
• Flynn, M.J., Hung, P., Rudd, K.W., "Deep-submicron microprocessor design issues"; IEEE MICRO, vol.19, no.4, pp.11-22, 1999.
• Govindarajan, R., Nemawarkar, S.S., LeNir, P., "Design and performance evaluation of a multithreaded architecture"; Proc. First IEEE Symp. on High-Performance Computer Architecture, Raleigh, NC, pp.298-307, 1995.
• Govindarajan, R., Suciu, F., Zuberek, W.M., "Timed Petri net models of multithreaded multiprocessor architectures"; Proc. 7-th Int. Workshop on Petri Nets and Performance Models (PNPM'97), St. Malo, France, pp.153-162, 1997.
• Hamilton, S., "Taking Moore's law into the next century"; IEEE Computer Magazine, vol.32, no.1, pp.43-48, 1999.
• Jain, R., The art of computer systems performance analysis; J. Wiley & Sons 1991.
• Jensen, K., "Coloured Petri nets"; in: Advanced Course on Petri Nets 1986 (Lecture Notes in Computer Science 254), Rozenberg, G. (ed.), pp.248-299, Springer-Verlag 1987.
• Lipasti, M., Shen, J., "Superspeculative microarchitectures for beyond AD 2000"; IEEE Computer Magazine, vol.30, no.9, pp.59-66, 1997.
• Loh, K.S., Wong, W.F., "Multiple context multithreaded superscalar processor architecture"; Journal of Systems Architecture, vol.46, pp.243-258, 2000.
• Murata, T., "Petri nets: properties, analysis and applications"; Proceedings of IEEE, vol.77, no.4, pp.541-580, 1989.
• Reisig, W., Petri nets - an introduction (EATCS Monographs on Theoretical Computer Science 4); Springer-Verlag 1985.
• Smith, J.E., Sofi, G.S., "The microarchitecture of superscalar processors"; Proceedings of the IEEE, vol.83, no.12, pp.1609-1624, 1995.
• 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., "Performance modeling of multithreaded distributed memory architectures", Proc. 2-nd Workshop on Hardware Design and Petri Nets, Williamsburg, VA, pp.63-82, 1999.

Available in pdf and postscript.