Application-aware deadlock-free oblivious routing

ABSTRACT

Conventional oblivious routing algorithms are either not application-aware or assume that each flow has its own private channel to ensure deadlock avoidance. We present a framework for application-aware routing that assures deadlock-freedom under one or more channels by forcing routes to conform to an acyclic channel dependence graph. Arbitrary minimal routes can be made deadlock-free through appropriate static channel allocation when two or more channels are available. Given bandwidth estimates for flows, we present a mixed integer-linear programming (MILP) approach and a heuristic approach for producing deadlock-free routes that minimize maximum channel load. The heuristic algorithm is calibrated using the MILP algorithm and evaluated on a number of benchmarks through detailed network simulation. Our framework can be used to produce application-aware routes that target the minimization of latency, number of flows through a link, bandwidth, or any combination thereof.

REFERENCES

• 1: Tobias Bjerregaard , Shankar Mahadevan, A survey of research and practices of Network-on-chip, ACM Computing Surveys (CSUR), v.38 n.1, p.1-es, 2006 [doi>http://doi.acm.org/10.1145/1132952.1132953]
• 2: ]]Tobias Bjerregaard and Jens Sparsø. Virtual channel designs for guaranteeing bandwidth in asynchronous network-on-chip. In Proceedings of the IEEE Norchip Conference (NORCHIP 2004). IEEE, 2004.
• 3: Ge-Ming Chiu, The Odd-Even Turn Model for Adaptive Routing, IEEE Transactions on Parallel and Distributed Systems, v.11 n.7, p.729-738, July 2000 [doi>10.1109/71.877831]
• 4: Myong Hyon Cho , Chih-Chi Cheng , Michel Kinsy , G. Edward Suh , Srinivas Devadas, Diastolic arrays: throughput-driven reconfigurable computing, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
• 5: ]]M. H. Cho, M. Lis, K. S. Shim, M. Kinsy, T. Wen, and S. Devadas. Oblivious routing in on-chip bandwidth-adaptive networks. Technical Report CSAIL--TR--2009--011 (http://hdl.handle.net/1721.1/44958), Massachusetts Institute of Technology, March 2009.
• 6: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 7: ]]William J. Dally, P. P. Carvey, and L. R. Dennison. The Avici terabit switch/router. In Proceedings of the Symposium on Hot Interconnects, pages 41--50, August 1998.
• 8: W. J. Dally , C. L. Seitz, Deadlock-Free Message Routing in Multiprocessor Interconnection Networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987 [doi>10.1109/TC.1987.1676939]
• 9: William Dally , Brian Towles, Principles and Practices of Interconnection Networks, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 10: W. J. Dally, Virtual-Channel Flow Control, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.194-205, March 1992 [doi>10.1109/71.127260]
• 11: José Duato, A New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks, IEEE Transactions on Parallel and Distributed Systems, v.4 n.12, p.1320-1331, December 1993 [doi>10.1109/71.250114]
• 12: José Duato, A Necessary and Sufficient Condition for Deadlock-Free Adaptive Routing in Wormhole Networks, IEEE Transactions on Parallel and Distributed Systems, v.6 n.10, p.1055-1067, October 1995 [doi>10.1109/71.473515]
• 13: ]]Mike Galles. Scalable pipelined interconnect for distributed endpoint routing: The SGI SPIDER chip. In Proceedings of the Symposium on Hot Interconnects, pages 141--146, August 1996.
• 14: Roman Gindin , Israel Cidon , Idit Keidar, NoC-Based FPGA: Architecture and Routing, Proceedings of the First International Symposium on Networks-on-Chip, p.253-264, May 07-09, 2007 [doi>10.1109/NOCS.2007.31]
• 15: Christopher J. Glass , Lionel M. Ni, The turn model for adaptive routing, Journal of the ACM (JACM), v.41 n.5, p.874-902, Sept. 1994 [doi>10.1145/185675.185682]
• 16: Thomas Gross , David R. O'Hallaron, iWarp: anatomy of a parallel computing system, MIT Press, Cambridge, MA, 1998
• 17: Zvika Guz , Isask'har Walter , Evgeny Bolotin , Israel Cidon , Ran Ginosar , Avinoam Kolodny, Efficient link capacity and QoS design for network-on-chip, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 18: Jingcao Hu , Radu Marculescu, Exploiting the Routing Flexibility for Energy/Performance Aware Mapping of Regular NoC Architectures, Proceedings of the conference on Design, Automation and Test in Europe, p.10688, March 03-07, 2003
• 19: Jingcao Hu , Radu Marculescu, DyAD: smart routing for networks-on-chip, Proceedings of the 41st annual Design Automation Conference, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996638]
• 20: Natalie Enright Jerger , Li-Shiuan Peh , Mikko Lipasti, Virtual Circuit Tree Multicasting: A Case for On-Chip Hardware Multicast Support, Proceedings of the 35th International Symposium on Computer Architecture, p.229-240, June 21-25, 2008
• 21: ]]N. K. Kavaldjiev, G. J. M. Smit, and P. G. Jansen. A virtual channel router for on-chip networks. In IEEE Int. SOC Conf., Santa Clara, California, pages 289--293. IEEE Computer Society Press, September 2004.
• 22: ]]Jon Michael Kleinberg. Approximation algorithms for disjoint paths problems. PhD thesis, Massachusetts Institute of Technology, 1996. Supervisor-Michel X. Goemans.
• 23: Amit Kumar , Li-Shiuan Peh , Partha Kundu , Niraj K. Jha, Toward Ideal On-Chip Communication Using Express Virtual Channels, IEEE Micro, v.28 n.1, p.80-90, January 2008 [doi>10.1109/MM.2008.18]
• 24: Olav Lysne , José Duato, Fast Dynamic Reconfiguration in Irregular Networks, Proceedings of the Proceedings of the 2000 International Conference on Parallel Processing, p.449, August 21-24, 2000
• 25: 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
• 26: ]]Srinivasan Murali, David Atienz, Luca Benini, and Giovanni De Micheli. A Method for Routing Packets Across Multiple Paths in NoCs with In-Order Delivery and FaultTolerance Gaurantees. VLSI Design, 2007.
• 27: Srinivasan Murali , Giovanni De Micheli, SUNMAP: a tool for automatic topology selection and generation for NoCs, Proceedings of the 41st annual Design Automation Conference, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996809]
• 28: 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]
• 29: Lionel M. Ni , Philip K. McKinley, A Survey of Wormhole Routing Techniques in Direct Networks, Computer, v.26 n.2, p.62-76, February 1993 [doi>10.1109/2.191995]
• 30: Chrysostomos A. Nicopoulos , Dongkook Park , Jongman Kim , N. Vijaykrishnan , Mazin S. Yousif , Chita R. Das, ViChaR: A Dynamic Virtual Channel Regulator for Network-on-Chip Routers, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.333-346, December 09-13, 2006 [doi>10.1109/MICRO.2006.50]
• 31: Maurizio Palesi , Rickard Holsmark , Shashi Kumar , Vincenzo Catania, A methodology for design of application specific deadlock-free routing algorithms for NoC systems, Proceedings of the 4th international conference on Hardware/software codesign and system synthesis, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176254.1176289]
• 32: Maurizio Palesi , Giuseppe Longo , Salvatore Signorino , Rickard Holsmark , Shashi Kumar , Vincenzo Catania, Design of Bandwidth Aware and Congestion Avoiding Efficient Routing Algorithms for Networks-on-Chip Platforms, Proceedings of the Second ACM/IEEE International Symposium on Networks-on-Chip, p.97-106, April 07-10, 2008
• 33: ]]Li-Shiuan Peh and William J. Dally. Flit-reservation flow control. In In Proc. of the 6th Int. Symp. on High-Performance Computer Architecture (HPCA), pages 73--84, January 2000. 37
• 34: 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
• 35: Loren Schwiebert, Deadlock-free oblivious wormhole routing with cyclic dependencies, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.149-158, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258507]
• 36: Daeho Seo , Akif Ali , Won-Taek Lim , Nauman Rafique , Mithuna Thottethodi, Near-Optimal Worst-Case Throughput Routing for Two-Dimensional Mesh Networks, Proceedings of the 32nd annual international symposium on Computer Architecture, p.432-443, June 04-08, 2005
• 37: ]]K. S. Shim, M. H. Cho, M. Kinsy, T. Wen, M. Lis, G. E. Suh, and S. Devadas. Static Virtual Channel Allocation in Oblivious Routing. In Proceedings of the 3rd ACM/IEEE International Symposium on Networks-on-Chip, May 2009.
• 38: ]]Craig B. Stunkel and Peter H. Hochschild. SP2 high-performance switch architecture. In Proceedings of the Symposium on Hot Interconnects, pages 115--121, August 1994.
• 39: ]]Craig B. Stunkel, Dennis G. Shea, Don G. Grice, Peter H. Hochschild, and Michael Tsao. The SP1 high-performance switch. In Proceedings of the Scalable High Performance Computing Conference, pages 150--157, May 1994.
• 40: Brian Towles , William J. Dally , Stephen Boyd, Throughput-centric routing algorithm design, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777444]
• 41: L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]
• 42: ]]Krzysztof Walkowiak. New algorithms for the unsplittable flow problem. In ICCSA (2), volume 3981 of Lecture Notes in Computer Science, pages 1101--1110, 2006.
• 43: Xiaoxiong Zhong , Virginia Mary Lo, Application-Specific Deadlock Free Wormhole Routing on Multicomputers, Proceedings of the 4th International PARLE Conference on Parallel Architectures and Languages Europe, p.193-208, June 15-18, 1992

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

General Terms:
Algorithms, Design, Performance

Keywords:
oblivious routing, on-chip interconnection networks, systems-on-chip