Position-based weighted round-robin arbitration for equality of service in many-core network-on-chips

ABSTRACT

This paper presents the position-based weighted round-robin arbitration for equality of service in many-core network-on-chips employing a deterministic routing algorithm. We concentrate on the network saturation induced by the hot-spot traffic that occurs when the threads running on the system simultaneously access shared data, global shared locks, etc. It exploits the deterministic properties of the interconnect network---the topology and the routing algorithm. This leads to the omission of additional information in packet headers, compared to the previous approaches. The hardware overhead is minimal, requiring only the weight counters in addition to a typical round-robin arbiter. Compared with the previous work, the proposed algorithm also reduces the critical path delay due to its simplicity. Although designed against the hot-spot traffic, the proposed arbitration scheme shows little performance degradation under other traffic patterns in terms of the average latency and the saturation throughput.

References

1. J. L. Hennessy and D. A. Patterson, Computer Architecture: A Quantitative Approach, 5th ed., MA: Morgan Kaufmann, 2012.
2. ITRS, "International Technology Roadmap for Semiconductors 2011," 2011. {Online}. Available: http://www.itrs.net/Links/2011ITRS/Home2011.htm.
3. M. M. Lee, J. Kim, D. Abts, M. Marty, and J. W. Lee, "Probabilistic distance-based arbitration: providing equality of service for many-core CMPs," in 43rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-43), Georgia, 2010.
4. G. F. Pfister and V. A. Norton, ""Hot Spot" Contention and Combining in Multistage Interconnection Networks," IEEE Transactions on Computers, vol. c-34, no. 10, pp. 943--948, 1985.
5. L. L. Peterson and B. S. Davie, Computer Networks: A Systems Approach, 5th ed., MA: Morgan Kaufmann, 2012.
6. A. K. Parekh and R. G. Gallager, "A generalized processor sharing approach to flow control in integrated services networks: The sigle-node case," IEEE/ACM Transactions on Networking, vol. 1, no. 3, pp. 344--357, 1993.
7. J. B. Nagle, "On packet switches with infinite storage," IEEE Transactions on Communications, vol. 35, no. 4, pp. 435--438, 1987.
8. D. Abts and D. Weisser, "Age-based packet arbitration in large-radix k-ary n-cubes," in 2007 Supercomputing (SC07), Reno, 2007.
9. C. J. Glass and L. M. Ni, "The turn model for adaptive routing," Journal of the Association for Computing Machinery, vol. 41, no. 5, pp. 874--902, 1994.
10. P. Gupta and N. McKeown, "Designing and implementing a fast crossbar scheduler," IEEE Micro, pp. 20--28, Jan/Feb 1999.
11. W. J. Dally and B. Towles, Principles and Practices of Interconnection Networks, CA: Morgan Kaufmann, 2004.
12. W. J. Dally and C. L. Seitz, "Deadlock-free message routing in multiprocessor interconnection networks," IEEE Transactions on Computers, vol. c-36, no. 5, pp. 547--553, 1987.
13. Accellera Systems Initiative, "SystemC," {Online}. Available: http://www.accellera.org.
14. J. Howard, S. Dighe, Y. Hoskote, S. Vangal, D. Finan, G. Ruhl, D. Jenkins, H. Wilson, N. Borkar, G. Schrom, F. Pailet, S. Jain, T. Jacob, S. Yada, S. Marella, P. Salihundam, V. Erraguntla, M. Konow, M. Riepen, G. Droege, J. Lindemann, M. Gries, T. Apel, K. Henriss, T. Lund-Larsen, S. Steibl, S. Borkar, V. De, R. V. D. Wijngaart, and T. Mattson, "A 48-core IA-32 message-passing processor with DVFS in 45nm CMOS," in IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC), 2010.
15. S. Bell, B. Edwards, J. Amann, R. Conlin, K. Joyce, V. Leung, J. MacKay, M. Reif, L. Bao, J. Brown, M. Mattina, C.-C. Miao, C. Ramey, D. Wentzlaff, W. Anderson, E. Berger, N. Fairbanks, D. Khan, F. Montenegro, J. Stickney, and J. Zook, "TILE64 processor: A 64-core SoC with mesh interconnect," in IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC), 2008.

Index Terms

• Networks

  • Network architectures