Communication-driven task binding for multiprocessor with latency insensitive network-on-chip

ABSTRACT

Network-on-Chip is a new design paradigm for designing core based System-on-Chip. It features high degree of reusability and scalability. In this paper, we propose a switch which employs the latency insensitive concepts and applies the round-robin scheduling techniques to achieve high communication resource utilization. Based on the assumptions of the 2D-mesh network topology constructed by the switch, this work not only models the communication and the contention effect of the network, but develops a communication-driven task binding algorithm that employs the divide and conquer strategy to map applications onto the multiprocessor system-on-chip. The algorithm attempts to derive a binding of tasks such that the overall system throughput is maximized. To compare with the task binding without consideration of communication and contention effect, the experimental results demonstrate that the overall improvement of the system throughput is 20% for 844 test cases.

REFERENCES

• 1: Axel Jantsch , Hannu Tenhunen, Networks on chip, Kluwer Academic Publishers, Hingham, MA, 2003
• 2: Adrijean Adriahantenaina , Herve Charlery , Alain Greiner , Laurent Mortiez , Cesar Albenes Zeferino, SPIN: A Scalable, Packet Switched, On-Chip Micro-Network, Proceedings of the conference on Design, Automation and Test in Europe: Designers' Forum, p.20070, March 03-07, 2003
• 3: Cesar Albenes Zeferino , Altamiro Amadeu Susin, SoCIN: A Parametric and Scalable Network-on-Chip, Proceedings of the 16th symposium on Integrated circuits and systems design, p.169, September 08-11, 2003
• 4: Partha Pratim Pande, Cristian Grecu, Andre Ivanov and Res Saleh, "Design of a switch for network on chip applications," in Proceedings of the 2003 International Symposium on Circuits and Systems, volume 5, pp. 217 -- 220, 2003.
• 5: 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]
• 6: Danial M. Chapiro, "Globally-Asynchronous Locally-Synchronous Systems," PH.D. thesis, Stanford University, Oct. 1984.
• 7: A Network on Chip Architecture and Design Methodology, Proceedings of the IEEE Computer Society Annual Symposium on VLSI, p.117, April 25-26, 2002
• 8: Daniel Wiklund , Dake Liu, SoCBUS: Switched Network on Chip for Hard Real Time Embedded Systems, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.78.1, April 22-26, 2003
• 9: Kenichiro Anjo, Yutaka Yamada, Michihiro Koibuchi, Akiya Jouraku and Hideharu Amano, "BLACK-BUS: a new data-transfer technique using local address on networks-on-chips," in Proceedings of the 18th International Parallel and Distributed Processing Symposium, pp. 10 -- 17, 2004.
• 10: Mikael Millberg , Erland Nilsson , Rikard Thid , Shashi Kumar , Axel Jantsch, The Nostrum Backbone - a Communication Protocol Stack for Networks on Chip, Proceedings of the 17th International Conference on VLSI Design, p.693, January 05-09, 2004
• 11: Luca P. Carloni , Kenneth L. McMillan , Alexander Saldanha , Alberto L. Sangiovanni-Vincentelli, A methodology for correct-by-construction latency insensitive design, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.309-315, November 07-11, 1999, San Jose, California, United States
• 12: Luca P. Carloni , Alberto L. Sangiovanni-Vincentelli, Coping with Latency in SOC Design, IEEE Micro, v.22 n.5, p.24-35, September 2002 [doi>10.1109/MM.2002.1044297]
• 13: Tang Lei , Shashi Kumar, A Two-step Genetic Algorithm for Mapping Task Graphs to a Network on Chip Architecture, Proceedings of the Euromicro Symposium on Digital Systems Design, p.180, September 01-06, 2003
• 14: William J. Dally, Performance Analysis of k-ary n-cube Interconnection Networks, IEEE Transactions on Computers, v.39 n.6, p.775-785, June 1990 [doi>10.1109/12.53599]
• 15: 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
• 16: Alexander Marquardt , Vaughn Betz , Jonathan Rose, Timing-driven placement for FPGAs, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.203-213, February 10-11, 2000, Monterey, California, United States [doi>10.1145/329166.329208]
• 17: Carl Ebeling , Larry McMurchie , Scott A. Hauck , Steven Burns, Placement and routing tools for the Triptych FPGA, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.4, p.473-482, Dec. 1995 [doi>10.1109/92.475966]
• 18: C. Y. Lee, "An algorithm for path connections and its applications," in IRE Transactions Electron Computing, volume EC 10, pp. 346 -- 365, 1961.
• 19: E. Dijkstra, "A Note on Two Problems in Connexion with Graphs," in Numerical Math, volume 1, pp. 269 -- 271, 1959.
• 20: Jose Duato , Sudhakar Yalamanchili , Ni Lionel, Interconnection Networks: An Engineering Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2002
• 21: Robert P. Dick , David L. Rhodes , Wayne Wolf, TGFF: task graphs for free, Proceedings of the 6th international workshop on Hardware/software codesign, p.97-101, March 15-18, 1998, Seattle, Washington, United States