Analysis of Buffer Arrangements in Low and High Dimensional Networks

N. Alzeidi

Abstract


 Virtual channels have been introduced to enhance the performance of wormhole-switched networks. They are formed by arranging the buffer space dedicated to a given physical channel into multiple parallel buffers that share the physical bandwidth on a demand driven time-multiplexed manner. The question to be answered is: given a fixed amount of finite buffer what is the optimal way to arrange it into virtual channels. There have been few studies attempting to address this issue, however, these studies have so far resorted to simulation experiments and focused on deterministic routing algorithms. In this paper we use analytical performance models to investigate the optimal arrangement of the available buffer space into multiple virtual channels when adaptive routing is used in wormhole-switched k-ary ncubes.

 


Keywords


Interconnection networks, Wormhole switching, Virtual channels, finite buffers, Performance analysis

Full Text:

PDF

References


Adiga, N.R., Blumrich, M.A., Chen, D., Coteus, P., Gara, A., Giampapa, M.E., Heidelberger, P., Singh, S., Steinmacher-Burow, B.D., Takken, T., Tsao, M. and Vranas, P., 2005, "Blue Gene/L Torus Interconnection Network," IBM Journal of Research and Development, Vol. 49, pp. 265-27.

Alzeidi, N., Khonsari, A., Ould-Khaoua, M. and Mackenzie, L.M., 2006, "On the Probability Distribution of Busy Virtual Channels," presented at 20th International Parallel and Distributed Processing Symposium, Rhodes Island, Greece, pp. 7.

Alzeidi, N., Ould-Khaoua, M., Mackenzie, L.M. and Khonsari, A., 2007, "Performance Analysis of Adaptively-Routed Wormhole-Switched Networks with Finite Buffers," presented at IEEE International Conference on Communications (ICC 2007), Glasgow, UK, pp. 38-43.

Boura, Y., Das, C.R. and Jacob, T.M., 1994, "A Performance Model for Adaptive Routing in Hypercubes," presented at International Workshop on Parallel Processing, pp. 11-16.

Chien, A.A., 1998, "Cost and Speed Model for k-ary n-cube Wormhole Routers," IEEE Transactions on Parallel and Distributed Systems, Vol. 9, pp. 150- 162.

Dally, W.J., 1992, "Virtual Channel Flow Control," IEEE Transactions on Parallel and Distributed Systems," Vol. 3, pp. 194-205.

Dally, W.J., Dennison, L.R., Harris, D., Kan, K. and Xanthopoulos, T., 1994, "The Reliable Router:a Reliable and High-performance Communication Substrate for Parallel Computers," presented at First International Workshop on Parallel Computer Routing and Communication, Washington,Seattle, USA, pp. 241-255.

Dally, W.J. and Towles, B., 2004, " Principles and Practices of Interconnection Networks Amsterdam," London: Elsevier/Morgan Kaufmann.

Duato, J., 1993, "A New Theory of Deadlock-Free Adaptive Routing In Wormhole Networks," IEEE Transactions On Parallel And Distributed Systems, Vol. 4, pp. 1320-1331.

Duato, J. and Lopez, P., 1994, "Performance Evaluation of Adaptive Routing Algorithms for kary- n-cubes," presented at First International Workshop on Parallel Computer Routing and Communication, Seattle, Washington, USA, pp. 45-59.

Duato, J., Yalamanchili, S. and Ni, L.M., " Interconnection Networks: An Engineering Approach," San Francisco: Morgan Kaufmann Publishers Inc.

Duato, J., Yalamanchili, S. and Ni, L.M., 2002, " Interconnection Networks: An Engineering Approach," Los Alamitos: Morgan Kaufmann Publishers Inc.

Miller, D. and Najjar, W.A., 1997, "Preliminary Evaluation of a Hybrid Deterministic/Adaptive Router," presented at Parallel Computing, Routing and Communication Workshop, Atlanta, Georgia, USA, pp. 21-32.

Mohapatra, P., 1998, "Wormhole Routing Techniques for Directly Connected Multicomputer Systems," ACM Computing Surveys, Vol. 30, pp. 374-410.

Ould-Khaoua, M., 1999, "A Performance Model for Duato's Fully Adaptive Routing Algorithm in kary n-cubes," IEEE Transactions On Computers, Vol. 48, pp. 1297-1304.

Rezazad, M. and Sarbazi-azad, H., 2005, "The Effect of Virtual Channel Organization on the Performance of Interconnection Networks," presented at 19th IEEE International Parallel and Distributed Processing Symposium, Denver, Colorado, USA, pp.

Rezazad, M. and Sarbazi-Azad, H., 2005, "Performance Evaluation of Fully Adaptive Routing under Different Workloads and Constant Node Buffer Size," presented at International Conference on Parallel and Distributed Systems, Fukuoka, Japan, pp. 510-514.

Sarbazi-Azad, H., Ould-Khaoua, M. and Mackenzie, L.M., 2001, "Analytical Modeling of Wormhole- Routed k-ary n-cubes in the Presence of Hot-spot Traffic," IEEE Transactions on Computers, Vol. 50, pp. 623-634.

Scott, S.L. and Thorson, G.M., 1996, "The Cray T3E Network: Adaptive Routing in a High Performance 3D Torus," presented at Symposium on High Performance Interconnects, Stanford, CA, USA, pp. 147-156.




DOI: http://dx.doi.org/10.24200/tjer.vol7iss2pp80-90

Refbacks

  • There are currently no refbacks.




Copyright (c) 2017 N. Alzeidi

Creative Commons License
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.

TJER 2017-CC BY-ND

This journal and its content is licensed under a Attribution-NoDerivatives 4.0 International.

Flag Counter