Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The trend towards increasing the number of processor cores and cache capacity in future Chip-Multiprocessors (CMPs), will require scalable packet-switched interconnection networks adapted to the restrictions imposed by the CMP environment. This paper presents an innovative router design, which successfully addresses CMP cost/performance constraints. The router structure is based on two independent rings, which force packets to circulate either clockwise or anti-clockwise, traveling through every port of the router. It uses a completely decentralized scheduling scheme, which allows the design to: (1) take advantage of wide links, (2) reduce Head of Line blocking, (3) use adaptive routing, (4) be topology agnostic, (5) scale with network degree, and (6) have reasonable power consumption and implementation cost. A thorough comparative performance analysis against competitive conventional routers shows an advantage for our proposal of up to 50 % in terms of raw performance and nearly 60 % in terms of energy-delay product.

REFERENCES

• 1: N.R. Adiga, et al., "An Overview of the BlueGene/L Supercomputer", Supercomputing 2002.
• 2: James Balfour , William J. Dally, Design tradeoffs for tiled CMP on-chip networks, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia [doi>10.1145/1183401.1183430]
• 3: S. Borkar, et al. "Platform 2015: Intel Platform and Evolution for the Next Decade", Technology@Intel Magazine, March 2005.
• 4: Doug Burger , Stephen W. Keckler , Kathryn S. McKinley , Mike Dahlin , Lizy K. John , Calvin Lin , Charles R. Moore , James Burrill , Robert G. McDonald , William Yoder , the TRIPS Team, Scaling to the End of Silicon with EDGE Architectures, Computer, v.37 n.7, p.44-55, July 2004 [doi>10.1109/MC.2004.65]
• 5: William J. Dally , Brian Towles, Route packets, not wires: on-chip inteconnection networks, Proceedings of the 38th conference on Design automation, p.684-689, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379048]
• 6: William Dally , Brian Towles, Principles and Practices of Interconnection Networks, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 7: R. Gonzalez, M. Horowitz, "Energy Dissipation In General Purpose Microprocessors", IEEE Journal of Solid-State Circuits, Vol. 31, No. 9, pp. 1277--1284, September 1996.
• 8: P. Gratz, C. Kim, R. McDonald, S. W. Keckler, D. Burger, "Implementation and Evaluation of On-Chip Network Architectures", International Conference on Computer Design (ICCD), 2006.
• 9: M. J. Karol, M. G. Hluchyj, S. P. Morgan, "Input versus Output queuing on a space-division packet switch", IEEE Trans. Communication., Vol. 35, no. 12, pp. 1347--1356, December 1987.
• 10: Manolis Katevenis , Panagiota Vatsolaki , Aristides Efthymiou, Pipelined memory shared buffer for VLSI switches, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.39-48, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 11: P. Kermani, L. Kleinrock, "Virtual Cut-Through: A New Computer Communication Switching Technique". Computer Networks, Vol. 3, pp. 267--286, September 1979.
• 12: Changkyu Kim , Doug Burger , Stephen W. Keckler, An adaptive, non-uniform cache structure for wire-delay dominated on-chip caches, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 13: Jongman Kim , Chrysostomos Nicopoulos , Dongkook Park, A Gracefully Degrading and Energy-Efficient Modular Router Architecture for On-Chip Networks, Proceedings of the 33rd annual international symposium on Computer Architecture, p.4-15, June 17-21, 2006
• 14: Jongman Kim , Dongkook Park , T. Theocharides , N. Vijaykrishnan , Chita R. Das, A low latency router supporting adaptivity for on-chip interconnects, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065726]
• 15: Poonacha Kongetira , Kathirgamar Aingaran , Kunle Olukotun, Niagara: A 32-Way Multithreaded Sparc Processor, IEEE Micro, v.25 n.2, p.21-29, March 2005 [doi>10.1109/MM.2005.35]
• 16: Smaragda Konstantinidou , Lawrence Snyder, The Chaos Router, IEEE Transactions on Computers, v.43 n.12, p.1386-1397, December 1994 [doi>10.1109/12.338098]
• 17: Rakesh Kumar , Victor Zyuban , Dean M. Tullsen, Interconnections in Multi-Core Architectures: Understanding Mechanisms, Overheads and Scaling, Proceedings of the 32nd annual international symposium on Computer Architecture, p.408-419, June 04-08, 2005
• 18: Seung Eun Lee , Nader Bagherzadeh, Increasing the throughput of an adaptive router in network-on-chip (NoC), Proceedings of the 4th international conference on Hardware/software codesign and system synthesis, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176254.1176276]
• 19: 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]
• 20: Milo M. K. Martin , Daniel J. Sorin , Bradford M. Beckmann , Michael R. Marty , Min Xu , Alaa R. Alameldeen , Kevin E. Moore , Mark D. Hill , David A. Wood, Multifacet's general execution-driven multiprocessor simulator (GEMS) toolset, ACM SIGARCH Computer Architecture News, v.33 n.4, November 2005 [doi>10.1145/1105734.1105747]
• 21: Shubhendu S. Mukherjee , Peter Bannon , Steven Lang , Aaron Spink , David Webb, The Alpha 21364 Network Architecture, IEEE Micro, v.22 n.1, p.26-35, January 2002 [doi>10.1109/40.988687]
• 22: Robert Mullins , Andrew West , Simon Moore, Low-Latency Virtual-Channel Routers for On-Chip Networks, Proceedings of the 31st annual international symposium on Computer architecture, p.188, June 19-23, 2004, München, Germany
• 23: Kunle Olukotun , Lance Hammond, The future of microprocessors, Queue, v.3 n.7, September 2005 [doi>10.1145/1095408.1095418]
• 24: Li-Shiuan Peh , William J. Dally, A Delay Model and Speculative Architecture for Pipelined Routers, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.255, January 20-24, 2001
• 25: H. Peter Hofstee, Power Efficient Processor Architecture and The Cell Processor, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.258-262, February 12-16, 2005 [doi>10.1109/HPCA.2005.26]
• 26: Partha Pratim Pande , Cristian Grecu , Michael Jones , Andre Ivanov , Resve Saleh, Performance Evaluation and Design Trade-Offs for Network-on-Chip Interconnect Architectures, IEEE Transactions on Computers, v.54 n.8, p.1025-1040, August 2005 [doi>10.1109/TC.2005.134]
• 27: V. Puente , C. Izu , R. Beivide , J. A. Gregorio , F. Vallejo , J. M. Prellezo, The adaptive bubble router, Journal of Parallel and Distributed Computing, v.61 n.9, p.1180-1208, September 2001 [doi>10.1006/jpdc.2001.1746]
• 28: V. Puente , R. Beivide , J. A. Gregorio , J. M. Prellezo , J. Duato , C. Izu, Adaptive Bubble Router: A Design to Improve Performance in Torus Networks, Proceedings of the 1999 International Conference on Parallel Processing, p.58, September 21-24, 1999
• 29: V. Puente, J.A. Gregorio, R. Beivide, "SICOSYS: An Integrated Framework for studying Interconnection Network in Multiprocessor Systems", Euromicro Workshop on Parallel and Distributed Processing, 2002.
• 30: Karthikeyan Sankaralingam , Ramadass Nagarajan , Robert McDonald , Rajagopalan Desikan , Saurabh Drolia , M. S. Govindan , Paul Gratz , Divya Gulati , Heather Hanson , Changkyu Kim , Haiming Liu , Nitya Ranganathan , Simha Sethumadhavan , Sadia Sharif , Premkishore Shivakumar , Stephen W. Keckler , Doug Burger, Distributed Microarchitectural Protocols in the TRIPS Prototype Processor, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.480-491, December 09-13, 2006 [doi>10.1109/MICRO.2006.19]
• 31: Ivan Sutherland , Bob Sproull , David Harris, Logical effort: designing fast CMOS circuits, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 32: Yuval Tamir , Gregory L. Frazier, Dynamically-Allocated Multi-Queue Buffers for VLSI Communication Switches, IEEE Transactions on Computers, v.41 n.6, p.725-737, June 1992 [doi>10.1109/12.144624]
• 33: Hang-Sheng Wang , Xinping Zhu , Li-Shiuan Peh , Sharad Malik, Orion: a power-performance simulator for interconnection networks, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 34: S. J. E. Wilton and N. P. Jouppi. "CACTI: An Enhanced Cache Access and Cycle Time Model", IEEE Journal of Solid-State Circuits, May 1996, pp 677--688.
• 35: http://www.atc.unican.es/investigacion/publicaciones/publicaciones_files/publ_109.pdf

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
chip multi-processors, interconnection networks, router architecture