A case for bufferless routing in on-chip networks

ABSTRACT

Buffers in on-chip networks consume significant energy, occupy chip area, and increase design complexity. In this paper, we make a case for a new approach to designing on-chip interconnection networks that eliminates the need for buffers for routing or flow control. We describe new algorithms for routing without using buffers in router input/output ports. We analyze the advantages and disadvantages of bufferless routing and discuss how router latency can be reduced by taking advantage of the fact that input/output buffers do not exist. Our evaluations show that routing without buffers significantly reduces the energy consumption of the on-chip cache/processor-to-cache network, while providing similar performance to that of existing buffered routing algorithms at low network utilization (i.e., on most real applications). We conclude that bufferless routing can be an attractive and energy-efficient design option for on-chip cache/processor-to-cache networks where network utilization is low.

REFERENCES

• 1: Robert Alverson , David Callahan , Daniel Cummings , Brian Koblenz , Allan Porterfield , Burton Smith, The Tera computer system, Proceedings of the 4th international conference on Supercomputing, p.1-6, June 11-15, 1990, Amsterdam, The Netherlands
• 2: P. Baran. On distributed communications networks. IEEE Trans. on Communications, Mar. 1964.
• 3: Luis Gravano , Gustavo D. Pifarré , Pablo E. Berman , Jorge L. C. Sanz, Adaptive Deadlock- and Livelock-Free Routing with All Minimal Paths in Torus Networks, IEEE Transactions on Parallel and Distributed Systems, v.5 n.12, p.1233-1251, December 1994 [doi>10.1109/71.334898]
• 4: Sanjay Bhansali , Wen-Ke Chen , Stuart de Jong , Andrew Edwards , Ron Murray , Milenko Drinić , Darek Mihočka , Joe Chau, Framework for instruction-level tracing and analysis of program executions, Proceedings of the 2nd international conference on Virtual execution environments, June 14-16, 2006, Ottawa, Ontario, Canada [doi>10.1145/1134760.1220164]
• 5: D. Boggs et al. The microarchitecture of the Intel Pentium 4 processor on 90nm technology. Intel Technology Journal, 8(1), Feb. 2004.
• 6: Shekhar Borkar, Thousand core chips: a technology perspective, Proceedings of the 44th annual Design Automation Conference, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278667]
• 7: Stefano Bregni , Achille Pattavina, Performance Evaluation of Deflection Routing in Optical IP Packet-Switched Networks, Cluster Computing, v.7 n.3, p.239-244, July 2004 [doi>10.1023/B:CLUS.0000028002.28138.3b]
• 8: Costas Busch , Maurice Herlihy , Roger Wattenhofer, Routing without flow control, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.11-20, July 2001, Crete Island, Greece [doi>10.1145/378580.378582]
• 9: Sangyeun Cho , Lei Jin, Managing Distributed, Shared L2 Caches through OS-Level Page Allocation, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.455-468, December 09-13, 2006 [doi>10.1109/MICRO.2006.31]
• 10: William J. Dally, Virtual-channel flow control, Proceedings of the 17th annual international symposium on Computer Architecture, p.60-68, May 28-31, 1990, Seattle, Washington, United States
• 11: W. J. Dally and C. L. Seitz. The torus routing chip. Distributed Computing, 1:187--196, 1986.
• 12: William Dally , Brian Towles, Principles and Practices of Interconnection Networks, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 13: Stijn Eyerman , Lieven Eeckhout, System-Level Performance Metrics for Multiprogram Workloads, IEEE Micro, v.28 n.3, p.42-53, May 2008 [doi>10.1109/MM.2008.44]
• 14: U. Feige and P. Raghavan. Exact analysis of hot-potato routing. In STOC, 1992.
• 15: J. M. Frailong, W. Jalby, and J. Lenfant. XOR-Schemes: A flexible data organization in parallel memories. In ICPP, 1985.
• 16: Ron Gabor , Shlomo Weiss , Avi Mendelson, Fairness and Throughput in Switch on Event Multithreading, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.149-160, December 09-13, 2006 [doi>10.1109/MICRO.2006.25]
• 17: Mike Galles, Spider: A High-Speed Network Interconnect, IEEE Micro, v.17 n.1, p.34-39, January 1997 [doi>10.1109/40.566196]
• 18: C. Gomez, M. E. Gomez, P. Lopez, and J. Duato. A bufferless switching technique for NoCs. In Wina, 2008.
• 19: Crispín Gómez , María E. Gómez , Pedro López , José Duato, Reducing Packet Dropping in a Bufferless NoC, Proceedings of the 14th international Euro-Par conference on Parallel Processing, August 26-29, 2008, Las Palmas de Gran Canaria, Spain [doi>10.1007/978-3-540-85451-7_97]
• 20: Michael K. Gowan , Larry L. Biro , Daniel B. Jackson, Power considerations in the design of the Alpha 21264 microprocessor, Proceedings of the 35th annual Design Automation Conference, p.726-731, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277226]
• 21: P. Gratz, B. Grot, and S. W. Keckler. Regional congestion awareness for load balance in networks-on-chip. In HPCA-14, 2008.
• 22: P. Gratz, C. Kim, R. McDonald, S. W. Keckler, and D. Burger. Implementation and evaluation of on-chip network architectures. In ICCD, 2006.
• 23: W. Daniel Hillis, The connection machine, MIT Press, Cambridge, MA, 1989
• 24: Yatin Hoskote , Sriram Vangal , Arvind Singh , Nitin Borkar , Shekhar Borkar, A 5-GHz Mesh Interconnect for a Teraflops Processor, IEEE Micro, v.27 n.5, p.51-61, September 2007 [doi>10.1109/MM.2007.77]
• 25: Natalie D. Enright Jerger , Li-Shiuan Peh , Mikko H. Lipasti, Circuit-Switched Coherence, Proceedings of the Second ACM/IEEE International Symposium on Networks-on-Chip, p.193-202, April 07-10, 2008
• 26: 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
• 27: John Kim , James Balfour , William Dally, Flattened Butterfly Topology for On-Chip Networks, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.172-182, December 01-05, 2007 [doi>10.1109/MICRO.2007.15]
• 28: S. Konstantinidou , L. Snyder, Chaos router: architecture and performance, Proceedings of the 18th annual international symposium on Computer architecture, p.212-221, May 27-30, 1991, Toronto, Ontario, Canada
• 29: David Kroft, Lockup-free instruction fetch/prefetch cache organization, Proceedings of the 8th annual symposium on Computer Architecture, p.81-87, May 12-14, 1981, Minneapolis, Minnesota, United States
• 30: Amit Kumar , Li-Shiuan Peh , Niraj K. Jha, Token flow control, Proceedings of the 2008 41st IEEE/ACM International Symposium on Microarchitecture, p.342-353, November 08-12, 2008 [doi>10.1109/MICRO.2008.4771803]
• 31: Zhonghai Lu , Mingchen Zhong , Axel Jantsch, Evaluation of on-chip networks using deflection routing, Proceedings of the 16th ACM Great Lakes symposium on VLSI, April 30-May 01, 2006, Philadelphia, PA, USA [doi>10.1145/1127908.1127977]
• 32: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 33: K. Luo, J. Gummaraju, and M. Franklin. Balancing throughput and fairness in SMT processors. In ISPASS, 2001.
• 34: Milo M. K. Martin , Daniel J. Sorin , Anatassia Ailamaki , Alaa R. Alameldeen , Ross M. Dickson , Carl J. Mauer , Kevin E. Moore , Manoj Plakal , Mark D. Hill , David A. Wood, Timestamp snooping: an approach for extending SMPs, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.25-36, November 2000, Cambridge, Massachusetts, United States
• 35: G. Michelogiannakis, J. Balfour, and W. J. Dally. Elastic-buffer flow control for on-chip networks. In HPCA-15, 2009.
• 36: George Michelogiannakis , Dionisios Pnevmatikatos , Manolis Katevenis, Approaching Ideal NoC Latency with Pre-Configured Routes, Proceedings of the First International Symposium on Networks-on-Chip, p.153-162, May 07-09, 2007 [doi>10.1109/NOCS.2007.10]
• 37: Micron. 1Gb DDR2 SDRAM Component: MT47H128M8HQ-25, May 2007. http://download.micron.com/pdf/datasheets/dram/ddr2/1GbDDR2.pdf.
• 38: Mikael Millberg , Erland Nilsson , Rikard Thid , Axel Jantsch, Guaranteed Bandwidth Using Looped Containers in Temporally Disjoint Networks within the Nostrum Network on Chip, Proceedings of the conference on Design, automation and test in Europe, p.20890, February 16-20, 2004
• 39: 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
• 40: Onur Mutlu , Thomas Moscibroda, Stall-Time Fair Memory Access Scheduling for Chip Multiprocessors, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.146-160, December 01-05, 2007 [doi>10.1109/MICRO.2007.40]
• 41: Ted Nesson , S. Lennart Johnsson, ROMM routing on mesh and torus networks, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.275-287, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215455]
• 42: John D. Owens , William J. Dally , Ron Ho , D. N. (Jay) Jayasimha , Stephen W. Keckler , Li-Shiuan Peh, Research Challenges for On-Chip Interconnection Networks, IEEE Micro, v.27 n.5, p.96-108, September 2007 [doi>10.1109/MM.2007.91]
• 43: Harish Patil , Robert Cohn , Mark Charney , Rajiv Kapoor , Andrew Sun , Anand Karunanidhi, Pinpointing Representative Portions of Large Intel® Itanium® Programs with Dynamic Instrumentation, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.81-92, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.28]
• 44: 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
• 45: Arjun Singh , William J. Dally , Amit K. Gupta , Brian Towles, GOAL: a load-balanced adaptive routing algorithm for torus networks, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 46: B. J. Smith. A pipelined shared resource MIMD computer. In ICPP, 1978.
• 47: B. J. Smith. Architecture and applications of the HEP multiprocessor computer system. In Proc. of SPIE, 1981.
• 48: B. J. Smith, Apr. 2008. Personal communication.
• 49: Allan Snavely , Dean M. Tullsen, Symbiotic jobscheduling for a simultaneous multithreaded processor, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.234-244, November 2000, Cambridge, Massachusetts, United States
• 50: Michael Bedford Taylor , Walter Lee , Jason Miller , David Wentzlaff , Ian Bratt , Ben Greenwald , Henry Hoffmann , Paul Johnson , Jason Kim , James Psota , Arvind Saraf , Nathan Shnidman , Volker Strumpen , Matt Frank , Saman Amarasinghe , Anant Agarwal, Evaluation of the Raw Microprocessor: An Exposed-Wire-Delay Architecture for ILP and Streams, Proceedings of the 31st annual international symposium on Computer architecture, p.2, June 19-23, 2004, München, Germany
• 51: 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
• 52: X. Wang, A. Morikawa, and T. Aoyama. Burst optical deflection routing protocol for wavelength routing WDM networks. In SPIE/IEEE Opticom, 2004.
• 53: David Wentzlaff , Patrick Griffin , Henry Hoffmann , Liewei Bao , Bruce Edwards , Carl Ramey , Matthew Mattina , Chyi-Chang Miao , John F. Brown III , Anant Agarwal, On-Chip Interconnection Architecture of the Tile Processor, IEEE Micro, v.27 n.5, p.15-31, September 2007 [doi>10.1109/MM.2007.89]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

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

General Terms:
Algorithms, Design, Performance

Keywords:
memory systems, multi-core, on-chip networks, routing