Timed colored Petri net models of distributed memory multithreaded multiprocessors

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

Proc. Workshop on Practical Use of Colored Petri Nets and Design/CPN; Aarhus, Denmark, 8-12 June 1998, pp.253-270.

Abstract:

Distributed-memory multithreaded multiprocessors are composed of a number of (multithreaded) processors, each with its memory, and an interconnecting network. The long memory latencies and 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 systems. Colors are used to represent the progress of remote memory access requests in the interconnecting network as well as to fold the models of individual processors. This paper describes timed colored Petri net models of several multithreaded multiprocessor architectures, and presents some performance characteristics obtained by evaluation of these models.

Keywords:

Instruction-level multithreading, distributed-memory architectures, colored Petri nets, timed Petri nets, discrete-event simulation.

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.
• 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.
• Ferrari, D., Computer systems performance evaluation; Prentice-Hall 1978.
• 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, St. Malo, France, pp.153-162, 1997.
• 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.
• 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.
• King, P.J.B., Computer and communication systems performance modelling; Prentice-Hall 1990.
• Moore, S.W., Multithreaded processor design; Kluwer Academic 1996.
• 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.
• 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.
• 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.
• Zuberek, W.M., Govindarajan, R. "Performance balancing in multithreaded multiprocessor architectures"; Proc. 4-th Australasian Conf. on Parallel and Real-Time Systems (PART'97), Newcastle, Australia, pp.15-26, 1997.

Available in pdf and postscript.