Congestion modeling for reconfigurable inter-processor networks

ABSTRACT

In this paper, we attempt to model congestion on a reconfigurable multi-processor communication network. This reconfigurable network adapts its topology at given intervals to the properties of the network traffic, which may alter over time. Using our congestion model, one can quickly estimate packet latency for a given set of network parameters. This allows a network designer to do design-space explorations without having to resort to detailed, slow simulations.The model is derived by viewing the network as an interconnected set of queues and servers. For each reconfiguration interval and each network link, we construct inter-arrival and service time distributions. Queuing theory can now give us the average waiting time on a single link. Combining waiting times per link over a network path yields the congestion experienced by each packet.After presenting the model itself, we show simulation results and determine the accuracy of our model. We analyze the assumptions made by the model, their effect on the accuracy, and propose some possible future improvements.

REFERENCES

• 1: W. Heirman, I. Artundo, L. Desmet, J. Dambre, C. Debaes, H. Thienpont, and J. Van Campenhout. Speeding up multiprocessor machines with reconfigurable optical interconnects. In Proc. SPIE Vol. 6124, Optoelectronic Integrated Circuits VIII, Photonics West, San Jose, California, January 2006.
• 2: W. Heirman , J. Dambre , C. Debaes , H. Thienpont , D. Stroobandt , J. Van Campenhout, Prediction model for evaluation of reconfigurable interconnects in distributed shared-memory systems, Proceedings of the 2005 international workshop on System level interconnect prediction, April 02-03, 2005, San Francisco, California, USA [doi>10.1145/1053355.1053367]
• 3: W. Heirman , J. Dambre , J. Van Campenhout , C. Debaes , H. Thienpont, Traffic Temporal Analysis for Reconfigurable Interconnects in Shared-Memory Systems, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 3, p.150.1, April 04-08, 2005 [doi>10.1109/IPDPS.2005.442]
• 4: Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Wolf-Dietrich Weber , Anoop Gupta , John Hennessy , Mark Horowitz , Monica S. Lam, The Stanford Dash Multiprocessor, Computer, v.25 n.3, p.63-79, March 1992 [doi>10.1109/2.121510]
• 5: Peter S. Magnusson , Magnus Christensson , Jesper Eskilson , Daniel Forsgren , Gustav Hållberg , Johan Högberg , Fredrik Larsson , Andreas Moestedt , Bengt Werner, Simics: A Full System Simulation Platform, Computer, v.35 n.2, p.50-58, February 2002 [doi>10.1109/2.982916]
• 6: D. A. B. Miller , H. M. Ozaktas, Limit to the bit-rate capacity of electrical interconnects from the aspect ratio of the system architecture, Journal of Parallel and Distributed Computing, v.41 n.1, p.42-52, Feb 25 1997 [doi>10.1006/jpdc.1996.1285]
• 7: Thomas G. Robertazzi, Computer Networks and Systems: Queueing Theory and Performance Evaluation, Springer-Verlag New York, Inc., Secaucus, NJ, 2000
• 8: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures
          Subjects: Distributed architectures

General Terms:
Design, Performance

Keywords:
congestion, interconnection network, prediction, reconfiguration