Optimizing Data Intensive Flows for Networks on Chips
Abstract
A novel framework is proposed to find efficient data intensive flow distributions on Networks on Chip (NoC). Voronoi diagram techniques are used to divide a NoC array of homogeneous processors and links into clusters. A new mathematical tool, named the flow matrix, is proposed to find the optimal flow distribution for individual clusters. Individual flow distributions on clusters are reconciled to be more evenly distributed. This leads to an efficient makespan and a significant savings in the number of cores actually used. The approach here is described in terms of a mesh interconnection but is suitable for other interconnection topologies.
Communicated by Andrew Adamatzky
References
- 1. , Introduction to Computer Networking (Springer Science, 2017). Crossref, Google Scholar
- 2. , Networks on chips: A new SoC paradigm, Computer 35(1) (2002) 70–78. Crossref, ISI, Google Scholar
- 3. , Scalable hybrid wireless network-on-chip architectures for multicore systems, IEEE Transactions on Computers 60(10) (2011) 1485–1502. Crossref, ISI, Google Scholar
- 4. , Designing 2D and 3D Network-on-Chip Architectures (Springer, 2016). Google Scholar
- 5. , Job scheduling for the BlueGene/L system, in Workshop on Job Scheduling Strategies for Parallel Processing (Springer, 2002), pp. 38–54. Crossref, Google Scholar
- 6. , Divisible load theory: A new paradigm for load scheduling in distributed systems, Cluster Computing 6(1) (2003) 7–17. Crossref, Google Scholar
- 7. , Scheduling Divisible Loads in Parallel and Distributed Systems (John Wiley & Sons, 1996). Google Scholar
- 8. , Scheduling for Parallel Processing (Springer, 2009). Crossref, Google Scholar
- 9. , Parallel Algorithms (Chapman and Hall/CRC, 2008). Crossref, Google Scholar
- 10. , Optimal divisible job load sharing for bus networks, IEEE Transactions on Aerospace and Electronic Systems 32(1) (1996) 34–40. Crossref, ISI, Google Scholar
- 11. , Data intensive grid scheduling: Multiple sources with capacity constraints, in Fifteenth IASTED International Conference on Parallel and Distributed Computing and Systems, 1 (2003), pp. 7–11. Google Scholar
- 12. , A realistic network/application model for scheduling divisible loads on large-scale platforms, in 19th IEEE International Parallel and Distributed Processing Symposium (IEEE, 2005), 10 pp. Crossref, Google Scholar
- 13. , A linear daisy chain with two divisible load sources, Conference Information Science and Systems
(2005) . Google Scholar - 14. , Multi-source grid scheduling for divisible loads, in Proceedings of the 40th Annual Conference on Information Sciences and Systems (2006), pp. 188–191. Crossref, Google Scholar
- 15. , Spatial Tessellations: Concepts and Applications of Voronoi Diagrams (John Wiley & Sons, 2009). Google Scholar
- 16. , Voronoi diagram and convex hull based geocasting and routing in wireless networks, Wireless Communications and Mobile Computing 6(2) (2006) 247–258. Crossref, ISI, Google Scholar
- 17. , Exposure in wireless ad-hoc sensor networks, in Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (ACM, 2001), pp. 139–150. Crossref, Google Scholar
- 18. , Processor equivalence for daisy chain load sharing processors, IEEE Transactions on Aerospace and Electronic Systems 29(4) (1993) 1216–1221. Crossref, ISI, Google Scholar
- 19. , Scheduling divisible workloads from multiple sources in linear daisy chain networks, in PDPTA
(2007) , pp. 528–534. Google Scholar - 20. J. Zhang, Y. Liu, S. Li and T. G. Robertazzi, Optimizing data intensive flows for networks on chips, arXiv preprint arXiv:1812.07183 (2018). Google Scholar
- 21. J. Zhang, Data distribution equivalence for data intensive interconnection networks, PhD dissertation, Dept. of Applied Mathematics and Statistics, Stony Brook University (2018). Google Scholar
- 22. , Switching in sequential tree networks, IEEE Transactions on Aerospace and Electronic Systems 40(3) (2004) 968–982. Crossref, ISI, Google Scholar
- 23. , Scheduling multisource divisible loads on arbitrary networks, IEEE Transactions on Parallel and Distributed Systems 21(4) (2010) 520–531. Crossref, ISI, Google Scholar
- 24. , Finding the constrained delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear time, SIAM Journal on Computing 28(2) (1998) 471–486. Crossref, ISI, Google Scholar
- 25. , The performance limits of a two dimensional network of load-sharing processors, Foundations of Computing and Decision Sciences 21(1) (1996) 3–15. Google Scholar
- 26. , Performance limits of divisible load processing in systems with limited communication buffers, Journal of Parallel and Distributed Computing 64(8) (2004) 960–973. Crossref, ISI, Google Scholar
- 27. , A multistage load distribution strategy for three-dimensional meshes, Cluster Computing 6(1) (2003) 31–39. Crossref, Google Scholar


