Mathematical Modeling of Flow Control Mechanism in Wireless Network-on-Chip
Subject Areas : Wireless Network
Fardad Rad
1
,
Marzieh Gerami
2
1 - Department of Computer Engineering, Yasooj Branch, Islamic Azad University, Yasooj, Iran
2 - Department of Computer Engineering, Shahrekord Branch, Islamic Azad University, Shahrekord, Iran
Keywords: Wireless network-on-chip, Flow control mechanism, Optimization, Gradient projection method, Utility function.,
Abstract :
Network-on-chip (NoC) is an effective interconnection solution of multicore chips. In recent years, wireless interfaces (WIs) are used in NoCs to reduce the delay and power consumption between long-distance cores. This new communication structure is called wireless network-on-chip (WiNoC). Compared to the wired links, demand to use the shared wireless links leads to congestion in WiNoCs. This problem increases the average packet latency as well as the network latency. However, using an efficient control mechanism will have a great impact on the efficiency and performance of the WiNoCs. In this paper, a mathematical modeling-based flow control mechanism in WiNoCs has been investigated. At first, the flow control problem has been modeled as a utility-based optimization problem with the wireless bandwidth capacity constraints and flow rate of processing cores. Next, the initial problem has been transformed into a dual problem without limitations and the best solution of the dual problem is obtained by the gradient projection method. Finally, an iterative algorithm is proposed in a WiNoC to control the flow rate of each core. The simulation results of synthetic traffic patterns show that the proposed algorithm can control and regulate the flow rate of each core with an acceptable convergence. Hence, the network throughput will be significantly improved.
[1] International Technology Roadmap for Semiconductors. Available: http://www.itrs.net.
[2] A. Ben Achballah, S. Ben Othman and S. Ben Saoud, “Problems and challenges of emerging technology networks−on−chip: A review”, Microprocessors and Microsystems, vol 53, pp. 1-20, 2017.
[3] J. Lin Jr, H.-T. Wu, Y. Su, L. Gao, A. Sugavanam, and J. E. Brewer, "Communication using antennas fabricated in silicon integrated circuits," Solid-State Circuits, IEEE Journal of, vol. 42, pp. 1678-1687, 2007.
[4] S. Deb, A. Ganguly, P. P. Pande, B. Belzer, and D. Heo, "Wireless NoC as interconnection backbone for multicore chips: Promises and challenges," Emerging and Selected Topics in Circuits and Systems, IEEE Journal on, vol. 2, pp. 228-239, 2012.
[5] D. Zhao and Y. Wang, "SD-MAC: Design and synthesis of a hardware-efficient collision-free QoS-aware MAC protocol for wireless network-on-chip," Computers, IEEE Transactions on, vol. 57, pp. 1230-1245, 2008.
[6] S.-B. Lee, S.-W. Tam, I. Pefkianakis, S. Lu, M. F. Chang, and C. Guo, "A scalable micro wireless interconnect structure for CMPs," in Proceedings of the 15th annual international conference on Mobile computing and networking, pp. 217-228, 2009.
[7] K. Kempa, J. Rybczynski, Z. Huang, K. Gregorczyk, A. Vidan and B. Kimball, "Carbon nanotubes as optical antennae," Advanced Materials, vol. 19, pp. 421-426, 2007.
[8] Abadal, S., Llatser, I., Mestres, A., Solé-Pareta, J., Alarcón, E. and Cabellos-Aparicio, “Fundamentals of Graphene-Enabled Wireless On-Chip Networking,” In Modeling, Methodologies, and Tools for Molecular and Nano-scale Communications, pp. 293-317, 2017.
[9] K. Chang, S. Deb, A. Ganguly, X. Yu, S. P. Sa,h and P. P. Pande, "Performance evaluation and design trade-offs for wireless network-on-chip architectures," ACM Journal on Emerging Technologies in Computing Systems (JETC), vol. 8, p. 23, 2012.
[10] M. Palesi, M. Collotta, A. Mineo, and V. Catania, "An Efficient Radio Access Control Mechanism for Wireless Network-On-Chip Architectures," Journal of Low Power Electronics and Applications, vol. 5, pp. 38-56, 2015.
[11] Dehghani, A. and Jamshidi, K.,” A fault-tolerant hierarchical hybrid mesh-based wireless network-on-chip architecture for multicore platforms,” The Journal of Supercomputing, vol. 71, no. 8, pp. 3116-3148, 2015.
[12] U. Y. Ogras and R. Marculescu, “It’s a small world after all": NoC performance optimization via long-range link insertion," Very Large-Scale Integration (VLSI) Systems, IEEE Transactions on, vol. 14, pp. 693-706, 2006.
[13] Hu, W. H., Wang, C., and Bagherzadeh, N,” Design and analysis of a mesh-based wireless network-on-chip,” The Journal of Supercomputing, vol. 71, no. 8, pp. 2830-2846, 2015.
[14] Ogras, U. Y. and Marculescu, R,” Analysis and optimization of prediction-based flow control in networks-on-chip,” In Modeling, Analysis and Optimization of Network-on-Chip Communication Architectures, pp. 105-133, 2013.
[15] A. Pullini, F. Angiolini, D. Bertozzi, and L. Benini, "Fault tolerance overhead in network-on-chip flow control schemes," in Integrated Circuits and Systems Design, 18th Symposium on, pp. 224-229, 2005.
[16] J. W. van den Brand, C. Ciordas, K. Goossens, and T. Basten, "Congestion-controlled best-effort communication for networks-on-chip," in Proceedings of the conference on Design, automation, and test in Europe, pp. 948-953, 2007. [17] A. Rezaei, M. Daneshtalab and D. Zhao,” CAP-W: Congestion-Aware Platform for Wireless-based Network-on-Chip in Many-Core Era,” Microprocessors and Microsystems, vol. 52, pp. 23-33, 2017. [18] T. Marescaux, A. Rangevall, V. Nollet, A. Bartic, and H. Corporaal, "Distributed Congestion Control for Packet-Switched Networks on Chip," in ParCo, pp. 761-768, 2005. [19] F. Jafari, M. S. Talebi, A. Khonsari, and M. Yaghmaee, "A Novel Congestion Control Scheme in Network-on-Chip Based on Best Effort Delay-Sum Optimization," in Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 191-196, 2008. [20] Talebi, M. S., Jafari, F., Khonsari, A. and Yaghmaee, M. H,” Proportionally fair flow control mechanism for best-effort traffic in network-on-chip architectures”, International Journal of Parallel, Emergent, and Distributed Systems, vol. 25, no. 4, pp. 345-362, 2010. [21] Durand, Y., Bernard, C. and Clermidy, F,” Distributed Dynamic Rate Adaptation on a Network on Chip with Traffic Distortion,” In Embedded Multicore/Many-core Systems-on-Chip (MCSoC), pp. 225-232, 2016. [22] Y. Wang and D. Zhao, "Distributed flow control and buffer management for Wireless Network-on-Chip," in Circuits and Systems, 2009. ISCAS 2009. IEEE International Symposium on, pp. 1353-1356, 2009.
[23] C. Wang, W.-H. Hu, and N. Bagherzadeh, "A wireless network-on-chip design for multicore platforms," in Parallel, Distributed and Network-Based Processing (PDP), 19th Euromicro International Conference on, pp. 409-416, 2011.
[24] D. Zhao and R. Wu, "Overlaid mesh topology design and deadlock-free routing in wireless network-on-chip," in Networks on Chip (NoCs), Sixth IEEE/ACM International Symposium on, pp. 27-34, 2012. [25] S. H. Low and D. E. Lapsley, "Optimization flow control—I: basic algorithm and convergence," IEEE/ACM Transactions on Networking (TON), vol. 7, pp. 861-874, 1999. [26] F. P. Kelly, A. K. Maulloo, and D. K. Tan, "Rate control for communication networks: shadow prices, proportional fairness and stability," Journal of the Operational Research Society, pp. 237-252, 1998.
[27] S. Boyd and L. Vandenberghe, Convex optimization: Cambridge university press, 2004.
[28] S. Boyd, "Convex Optimization II Lecture Notes," Ed: Stanford University, 2006.
[29] M. Grant, S. Boyd, and Y. Ye, "CVX: Matlab software for disciplined convex programming," ed, 2008.
[30] Mohtavipour, S. M., Mollajafari, M. and Naseri, A, ‘‘a novel packet exchanging strategy for preventing HoL-blocking in fat trees,’’ Cluster Computing, pp: 1-22, 2019.
[31] Mortazavi, H., Akbar, R., Safaei, F. and Rezaei. A., ‘‘a fault-tolerant and congestion-aware architecture for wireless networks-on-chip,’’ Wireless Networks, vol. 25, no. 6, pp. 3675-3687, 2019.
[32] Yazdanpanah, F., AfsharMazayejani, R., Alaei, M., Rezaei, A. and Daneshtalab, M., “An energy-efficient partition-based XYZ-planar routing algorithm for a wireless network-on-chip”, The Journal of Supercomputing, vol. 75, no. 2, pp. 837–861, 2019.
[33] Rezaei, A., Daneshtalab, M., Zhao and D. CAP-W, “Congestionaware platform for wireless-based network-on-chip in many-core era”, Microprocessors and Microsystems, vol. 52, pp. 23–33, 2017. [34] S. M. Mamaghani and M. A. J. Jamali, ‘‘A load-balanced congestion-aware routing algorithm based on time interval in wireless network-on-chip,’’ Journal of Ambient Intelligence and Humanized Computing, vol. 10, no. 7, pp. 2869-2882, 2019.
