Timed Petri net models of multithreaded multiprocessor architectures

Govindarajan, R., Suciu, F., and Zuberek, W.M.

Proc. 7-th Int. Workshop on Petri Net and Performance Models (PNPM'97); St.Malo, France, 3-6 June 1997, pp.153-162.

Abstract:

Multithreaded distributed-memory multiprocessor architectures are composed of a number of (multithreaded) processors, each with its memory, and an interconnection network. The long memory latencies and unpredictable synchronization delays are tolerated by context switching, i.e., by suspending the current thread and switching the processor to another `ready' thread provided such a thread is available. Because of very simple representation of concurrency and synchronization, timed Petri net models seem to be well suited for modeling and evaluation of such architectures. However, accurate net models of multithreaded multiprocessors become quite complicated, so their analysis can be a nontrivial task. This paper describes a timed colored Petri net model of a multithreaded multiprocessor architecture, and presents some results obtained by simulation of this model. A simplified approach to modeling such architectures is also proposed.

References:

• Agrawal, A., Lim, B-H., Kranz, D., Kubiatowicz, J., "April: a processor architecture for multiprocessing"; Proc. 17-th Annual Int. Symp. on Computer Architecture, pp.104-114, 1990.
• Agrawal, A., "Limits on interconnection network performance"; IEEE Trans. on Parallel and Distributed Systems, vol.2, no.4, pp.398-412, 1991.
• Ajmone Marsan, M., Balbo, G., Chiola, G., Conte, G., "Modeling the software architecture of a prototype parallel machine"; Proc. SIGMETRICS'87, Performance Evaluation Review, vol.15, no.1, pp.175-185, 1987.
• Ajmone Marsan, M., Balbo, G., Conte, G., Performance models of multiprocessor systems; MIT Press 1986.
• Alkalaj, L., Boppana, R.V., "Performance of a multithreaded execution in a shared-memory multiprocessor"; Proc. 3-rd Annual IEEE Symp. on Parallel and Distributed Processing, Dallas, TX, pp.330-333, 1991.
• 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.
• Culler, D.E., et al., "Fine-grain parallelism with minimal hardware support: a compiler controlled threaded abstract machine"; Proc. 4-th Int. Conf. on Architectural Support of Programming Languages and Operating Systems, Santa Clara, CA, pp.164-175, 1991.
• Edmondson, J., Rubinfield, P., Preston, R., Rajagopalan, V., "An overview of the 21164 AXP microprocessor"; IEEE Micro, vol.15, no.2, pp.33-43, 1995.
• 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.
• Hirata, H., et al., "An elementary processor architecture with simultaneous instruction issuing from multiple threads"; Proc. 19-th Annual Int. Symp. on Computer Architecture, pp.136-145, 1992.
• Holliday, M.A., Vernon, M.K., "Exact performance estimates for multiprocessor memory and bus interference"; IEEE Trans. on Computers, vol.36, no.1, pp.76-85, 1987.
• 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.
• Johnson, K., "The impact of communication locality on large-scale multiprocessor performance"; Proc. 19-th Annual Int. Symp. on Computer Architecture, pp.392-402, 1992.
• Keckler, S.W., Dally, W.J., "Processor coupling: integration of compile-time and run-time scheduling for parallelism"; Proc. 19-th Annual Int. Symp. on Computer Architecture, pp.202-213, 1992.
• Murata, T., "Petri nets: properties, analysis and applications"; Proceedings of IEEE, vol.77, no.4, pp.541-580, 1989.
• Nemawarkar, S.S., Govindarajan, R., Gao, G.R., Agarwal, V.K., "Analysis of multithreaded multiprocessors with distributed shared memory"; Micronet Report, Department of Electrical Engineering, McGill University, Montreal, Canada H3A 2A7, 1993.
• Nemawarkar, S.S., Gao, G.R., "Performance analysis of multithreaded architectures using an integrated system model"; Parallel Computing (submitted for publication).
• Reisig, W., Petri nets - an introduction (EATCS Monographs on Theoretical Computer Science 4); Springer-Verlag 1985.
• Saavedra-Bareera, R.H., Culler, D.E., von Eicken, T., "Analysis of multithreaded architectures for parallel computing"; Proc. 2-nd Annual Symp. on Parallel Algorithms and Architectures, Crete, Greece, 1990.
• Smith, B.J., "Architecture and applications of the HEP multiprocessor computer System"; Proc. SPIE - Real-Time Signal Processing IV, vol. 298, pp. 241-248, San Diego, CA, 1981.
• Song, S.P., Denman, M., Chang, J., "The PowerPC 604 RISC microprocessor"; IEEE Micro, vol.14, no.5, pp.8-17, 1994.
• Tremblay, M., Greenlay, D., Normoyle, K., "The design of microarchitecture of UltraSPARC-I"; Proceedings of IEEE, vol.83, no.12, pp.1653-1663, 1995.
• Weber, W.D., Gupta, A., "Exploring the benefits of multiple contexts in a multiprocessor architecture: preliminary results"; Proc. 16-th Annual Int. Symp. on Computer Architecture, pp.273-280, 1989.
• 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., "Modeling using timed Petri nets - event-driven simulation"; Technical Report #9602, Department of Computer Science, Memorial Univ. of Newfoundland, St. John's, Canada A1B 3X5, 1996.

Available in pdf and postscript.