A unified approach to constrained mapping and routing on network-on-chip architectures

ABSTRACT

One of the key steps in Network-on-Chip (NoC) based design is spatial mapping of cores and routing of the communication between those cores. Known solutions to the mapping and routing problem first map cores onto a topology and then route communication, using separated and possibly conflicting objective functions. In this paper we present a unified single-objective algorithm, called Unified MApping, Routing and Slot allocation (UMARS). As the main contribution we show how to couple path selection, mapping of cores and TDMA time-slot allocation such that the network required to meet the constraints of the application is minimized. The time-complexity of UMARS is low and experimental results indicate a run-time only 20% higher than that of path selection alone. We apply the algorithm to an MPEG decoder System-on-Chip (SoC), reducing area by 33%, power by 35% and worst-case latency by a factor four over a traditional multi-step approach.

REFERENCES

• 1: Luca Benini , Giovanni De Micheli, Networks on Chips: A New SoC Paradigm, Computer, v.35 n.1, p.70-78, January 2002 [doi>10.1109/2.976921]
• 2: Davide Bertozzi , Antoine Jalabert , Srinivasan Murali , Rutuparna Tamhankar , Stergios Stergiou , Luca Benini , Giovanni De Micheli, NoC Synthesis Flow for Customized Domain Specific Multiprocessor Systems-on-Chip, IEEE Transactions on Parallel and Distributed Systems, v.16 n.2, p.113-129, February 2005 [doi>10.1109/TPDS.2005.22]
• 3: William J. Dally , Brian Towles, Route packets, net wires: on-chip inteconnectoin networks, Proceedings of the 38th conference on Design automation, p.684-689, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379048]
• 4: J. Dielissen et al. Power measurements and analysis of a network-on-chip. Technical Report NL-TN-2005-0282, Philips Research Laboratories, Eindhoven, 2005.
• 5: O. P. Gangwal et al. Dynamic and Robust Streaming In And Between Connected Consumer-Electronics Devices, Building Predictable Systems on Chip: An Analysis of Guaranteed Communication in the AEthereal Network on Chip. Kluwer, 2005.
• 6: Santiago Gonzalez Pestana , Edwin Rijpkema , Andrei Rdulescu , Kees Goossens , Om Prakash Gangwal, Cost-Performance Trade-Offs in Networks on Chip: A Simulation-Based Approach, Proceedings of the conference on Design, automation and test in Europe, p.20764, February 16-20, 2004
• 7: Kees Goossens , John Dielissen , Om Prakash Gangwal , Santiago Gonzalez Pestana , Andrei Radulescu , Edwin Rijpkema, A Design Flow for Application-Specific Networks on Chip with Guaranteed Performance to Accelerate SOC Design and Verification, Proceedings of the conference on Design, Automation and Test in Europe, p.1182-1187, March 07-11, 2005 [doi>10.1109/DATE.2005.11]
• 8: R. Guérin and A. Orda. Networks with advance reservations: The routing perspective. In Proc. INFOCOM, 2000.
• 9: R. Guérin et al. QoS routing mechanisms and OSPF extensions. In GLOBECOM, volume 3, 1997.
• 10: Wai Hong Ho , Timothy Mark Pinkston, A Methodology for Designing Efficient On-Chip Interconnects on Well-Behaved Communication Patterns, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.377, February 08-12, 2003
• 11: Jingcao Hu , Radu Marculescu, Energy-aware mapping for tile-based NoC architectures under performance constraints, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119818]
• 12: 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
• 13: K. Keutzer et al. System-level design: Orthogonalization of concerns and platform-based design. Trans. on CAD of Integrated Circuits and Systems, 19(12), 2000.
• 14: K. Kowalik and M. Collier. Should QoS0 routing algorithms prefer shortest paths? In Proc. ICC, 2003.
• 15: Qingming Ma , P. Steenkiste, On path selection for traffic with bandwidth guarantees, Proceedings of the 1997 International Conference on Network Protocols (ICNP '97), p.191, October 28-31, 1997
• 16: I. Matta and A. Bestavros. A load profiling approach to routing guaranteed bandwidth flows. In Proc. INFOCOM, 1998.
• 17: Srinivasan Murali , Giovanni De Micheli, Bandwidth-Constrained Mapping of Cores onto NoC Architectures, Proceedings of the conference on Design, automation and test in Europe, p.20896, February 16-20, 2004
• 18: Srinivasan Murali , Giovanni De Micheli, SUNMAP: a tool for automatic topology selection and generation for NoCs, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996809]
• 19: Srinivasan Murali , Luca Benini , Giovanni De Micheli, Mapping and physical planning of networks-on-chip architectures with quality-of-service guarantees, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120737]
• 20: E. Rijpkema , K. G. W. Goossens , A. Radulescu , J. Dielissen , J. van Meerbergen , P. Wielage , E. Waterlander, Trade Offs in the Design of a Router with Both Guaranteed and Best-Effort Services for Networks on Chip, Proceedings of the conference on Design, Automation and Test in Europe, p.10350, March 03-07, 2003
• 21: M. Sgroi , M. Sheets , A. Mihal , K. Keutzer , S. Malik , J. Rabaey , A. Sangiovanni-Vencentelli, Addressing the system-on-a-chip interconnect woes through communication-based design, Proceedings of the 38th conference on Design automation, p.667-672, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379045]
• 22: R. Widyono. The design and evaluation of routing algorithms for real-time channels. TR-94-024, Univ. of Calif. at Berkeley & Int'l Comp. Sci. Inst., 1994.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)
          Subjects: Topology (e.g., bus, point-to-point)

General Terms:
Algorithms, Design, Performance

Keywords:
mapping, network-on-chip, quality-of-service, routing, system-on-chip