World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Optimizing Data Intensive Flows for Networks on Chips

    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. T. G. Robertazzi, Introduction to Computer Networking (Springer Science, 2017). CrossrefGoogle Scholar
    • 2. L. Benini and G. De Micheli, Networks on chips: A new SoC paradigm, Computer 35(1) (2002) 70–78. Crossref, ISIGoogle Scholar
    • 3. A. Ganguly, K. Chang, S. Deb, P. P. Pande, B. Belzer and C. Teuscher, Scalable hybrid wireless network-on-chip architectures for multicore systems, IEEE Transactions on Computers 60(10) (2011) 1485–1502. Crossref, ISIGoogle Scholar
    • 4. K. Tatas, K. Siozios, D. Soudris and A. Jantsch, Designing 2D and 3D Network-on-Chip Architectures (Springer, 2016). Google Scholar
    • 5. E. Krevat, J. G. Castaños and J. E. Moreira, Job scheduling for the BlueGene/L system, in Workshop on Job Scheduling Strategies for Parallel Processing (Springer, 2002), pp. 38–54. CrossrefGoogle Scholar
    • 6. V. Bharadwaj, D. Ghose and T. G. Robertazzi, Divisible load theory: A new paradigm for load scheduling in distributed systems, Cluster Computing 6(1) (2003) 7–17. CrossrefGoogle Scholar
    • 7. V. Bharadwaj, D. Ghose, V. Mani and T. G. Robertazzi, Scheduling Divisible Loads in Parallel and Distributed Systems (John Wiley & Sons, 1996). Google Scholar
    • 8. M. Drozdowski, Scheduling for Parallel Processing (Springer, 2009). CrossrefGoogle Scholar
    • 9. H. Casanova, A. Legrand and Y. Robert, Parallel Algorithms (Chapman and Hall/CRC, 2008). CrossrefGoogle Scholar
    • 10. J. Sohn and T. G. Robertazzi, Optimal divisible job load sharing for bus networks, IEEE Transactions on Aerospace and Electronic Systems 32(1) (1996) 34–40. Crossref, ISIGoogle Scholar
    • 11. H. M. Wong, D. Yu, B. Veeravalli and T. G. Robertazzi, 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. L. Marchal, Y. Yang, H. Casanova and Y. Robert, 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. CrossrefGoogle Scholar
    • 13. T. Lammie and G. Thomas, A linear daisy chain with two divisible load sources, Conference Information Science and Systems (2005). Google Scholar
    • 14. T. G. Robertazzi and D. Yu, Multi-source grid scheduling for divisible loads, in Proceedings of the 40th Annual Conference on Information Sciences and Systems (2006), pp. 188–191. CrossrefGoogle Scholar
    • 15. A. Okabe, B. Boots, K. Sugihara and S. N. Chiu, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams (John Wiley & Sons, 2009). Google Scholar
    • 16. I. Stojmenovic, A. P. Ruhil and D. Lobiyal, Voronoi diagram and convex hull based geocasting and routing in wireless networks, Wireless Communications and Mobile Computing 6(2) (2006) 247–258. Crossref, ISIGoogle Scholar
    • 17. S. Meguerdichian, F. Koushanfar, G. Qu and M. Potkonjak, 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. CrossrefGoogle Scholar
    • 18. T. G. Robertazzi, Processor equivalence for daisy chain load sharing processors, IEEE Transactions on Aerospace and Electronic Systems 29(4) (1993) 1216–1221. Crossref, ISIGoogle Scholar
    • 19. X. Liu, H. Zhao and X. Li, 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. J. T. Hung and T. G. Robertazzi, Switching in sequential tree networks, IEEE Transactions on Aerospace and Electronic Systems 40(3) (2004) 968–982. Crossref, ISIGoogle Scholar
    • 23. J. Jia, B. Veeravalli and J. Weissman, Scheduling multisource divisible loads on arbitrary networks, IEEE Transactions on Parallel and Distributed Systems 21(4) (2010) 520–531. Crossref, ISIGoogle Scholar
    • 24. F. Chin and C. A. Wang, 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, ISIGoogle Scholar
    • 25. J. Błażewicz and M. Drozdowski, 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. M. Drozdowski and P. Wolniewicz, Performance limits of divisible load processing in systems with limited communication buffers, Journal of Parallel and Distributed Computing 64(8) (2004) 960–973. Crossref, ISIGoogle Scholar
    • 27. W. Głazek, A multistage load distribution strategy for three-dimensional meshes, Cluster Computing 6(1) (2003) 31–39. CrossrefGoogle Scholar