Mathematical Modeling of Flow Control Mechanism in Wireless Network-on-Chip
الموضوعات :
Fardad Rad
1
( Department of Computer Engineering, Yasooj Branch, Islamic Azad University, Yasooj, Iran)
Marzieh Gerami
2
(Department of Computer Engineering, ShahreKord Branch, Islamic Azad University, ShahreKord, Iran)
الکلمات المفتاحية: Wireless network-on-chip, Flow control mechanism, Optimization, Gradient projection method, Utility function.,
ملخص المقالة :
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.
http://jist.acecr.org ISSN 2322-1437 / EISSN:2345-2773 |
Journal of Information Systems and Telecommunication
|
Mathematical Modeling of Flow Control Mechanism in Wireless Network-on-Chip |
Farhad Rad1*, Marzieh Gerami1
|
1. Department of Computer Engineering, Yasooj Branch, Islamic Azad University, Yasooj, Iran 2. Department of Computer Engineering, ShahreKord Branch, Islamic Azad University, ShahreKord, Iran |
Received: 21 Aug 2021/ Revised: 04 Jan 2022/ Accepted: 12 Feb 2022 |
|
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.
Keywords: Wireless Network-on-Chip; Flow Control Mechanism; Optimization; Gradient Projection Method; Utility Function.
1- Introduction
One of the simplest communication structures of the components inside the chip is the bus. The main drawback of bus-based systems is the sharp decline of the system performance with the increasing number of processing cores. Increasing the number of cores integrated into a chip will transform the communication bus between the cores into a bottleneck for the system. Also, in this structure, having a mechanism as an arbitrator for control and fair access to the joint bus seems necessary. The inflexibility of this communication structure has led to a significant challenge in systems-on-chip.
The network on the chip is a communication structure between the cores within the chip that has overcome the defects and challenges of the few structures. On-chip networks, while being scalable, should provide low power consumption and adequate bandwidth for communication between tens or hundreds of processing cores within a chip. A major challenge of the network on the chip, despite the reduction in transistor dimensions in recent years, is the issue of delayed wired connections within the chip, which has grown exponentially (ITRS report) [1].
In recent years, new communication structures include 3DNoCs, photonic NoCs, and network on chip with radio (wireless) connections have been proposed [2]. Using these emerging technologies in the advanced integrated circuit industry has been able to reduce the delay and power consumption of the chip.
The design and manufacture of on-chip integrated silicon antennas were presented in the last decade. These antennas have been used with a frequency equivalent to ten to one hundred GHz inside a chip [3]. However, increasing the operating frequency of processing cores and the high bandwidth of wireless links for inter-core communication will turn these links into hotspots in the network (network congestion will increase delay and reduce network efficiency). Therefore, the existence of a mechanism to control congestion and flow control to reduce network traffic and increase chip performance is essential.
According to the studies conducted in the field of wireless networks-on-chip, the problem of modeling the flow rate control in the wireless network on the chip has not been done so far. For this purpose, in this paper, first, the flow rate control modeling in the wireless network on the chip will be examined. To formulate the problem, we have used the maximization of a utility function. Then, we solved the problem with Lagrange multipliers and gradient projection and presented an algorithm to control the flow rate of processing cores. The proposed algorithm has been able to regulate and control the flow rate of processing cores with appropriate convergence speed.
This paper consists of the following parts:
Section 2 has presented the details of the wireless network-on-chip. The network model as well as the mathematical modeling of the flow control problem along with the proposed algorithm have been presented in Section 3. The results of the implementation have been given in Section 4. Finally, the conclusion has been described in Section 5.
2- A review of Previous Works
The use of wireless in-chip connections has introduced a new structure called the wireless network on chip (WiNoC) [4]. In addition to high flexibility, this network has increased communication bandwidth and eliminated the problems of noise and power consumption of metal wires. This new structure on the chip has been generally studied in three layers. Physical layer, data link layer, and network layer. The following is a brief introduction to each section.
2-1- Physical Layer in the WiNoC:
In a WiNoC, antennas are designed according to the operating frequency of the circuits and then used in conjunction with other wireless transmission devices such as modulator circuits and telecommunication filters on the chip. Since the bit rate error in wireless on-chip transmission will have a significant effect on the reliability of the system, hence the medium of wave propagation must be completely examined. The use of different frequency boards has divided the WiNoC into four general categories. Figure 1 shows these four frequency ranges that can be used in the design of WiNoC.
Fig. 1. Division of the frequency of the WiNoC [4]
In the following, we will briefly review the work done in the field of designing antennas compatible with each of the frequency ranges:
2-1-1- Ultra-Wide Band (UWB):
Reference [5] has proposed the architecture of WiNoC based on the frequency of the ultra-wideband. In this architecture, a radio pulse transmitter-receiver with a carrier signal has been used for wireless communication. The transmitter uses an integrated, CMOS-compliant Gaussian monocycle pulse to generate low-power, low-driving pulses. The antenna used in this architecture is a 2.9mm long Meander Dipole Antenna (MDA) that can transmit data up to a radius of 1 mm. The transmission rate of this antenna is 1.16 Gbps for a channel with a frequency of 3.6 GHz.
2-1-2- Mm-Wave Band:
reference [3] has proposed the design of a metal zigzag antenna. This antenna will have little effect on the rotation (relative angle between the transmitting antenna and the receiving antenna) and the received signal strength. The millimeter frequency band was also able to provide bandwidth between ten and one hundred GHz without signal attenuation.
2-1-3- Sub-THz:
The design of small antennas with simple transceivers that could operate at frequencies between 100 and 1000 GHz has been proposed for the first time in reference [6]. These antennas can cover a communication radius of 10 to 20 mm on the chip. In this architecture, the possibility of simultaneous use of 16 non-overlapping channels with frequencies of 100 to 500 GHz for the structure of the WiNoC has been proposed.
2-1-4- THz:
by increasing the signal frequency to the THz range, one can expect much smaller antennas to be designed that can occupy less surface area on the chip. Reference [7] has proposed the design and fabrication of antennas using carbon nanotubes. The properties of carbon nanotubes make them suitable for making antennas on high-frequency chips.
In addition to the above, the design of graphene-based plasmonic antennas using electromagnetic waves up to the range of ten terahertz for wireless in-chip communication has also been introduced and has recently been considered [8]. In this paper, the authors claim that the many benefits of using graphene will bring great success in wireless in-chip communication. In the future, the design of these antennas will provide the possibility of all-broadcast and multi-broadcast on-chip communication. Figure 2 shows a view of the network-on-chip with graphene antennas.
Fig. 2. Graphene antennas in the structure of WiNoC [8]
2-2- Data Link Layer in the WiNoC:
To increase the efficiency and maximum use of the bandwidth of communication channels in the WiNoC, having a media access control mechanism (MAC) is also needed. Designing a MAC protocol on a wireless chip should be able to impose the minimum of power and consumption overhead on the system. In reference [5] a shared channel access protocol was proposed. In this design, the network is divided into several areas with the least signal interference. Hence, to access shared wireless channels a central arbitration policy is used.
In [9], a protocol has been implemented based on token flow control. In this design, any router equipped with a wireless antenna that has the token can send or receive packets on the wireless channel. After sending the packets, this token will flow in turning form for the use of other routers. By increasing the number of wireless cores in the NoC, this mechanism leads to an increase in token flow time between cores and a decrease in network performance.
Reference [10] has proposed an access control mechanism called RACM for WiNoC. In this design, each radio hub (wireless router) has been connected to a processing core on a ring-shaped structure. This mechanism dynamically splits the token capture time in a router that has no data to send between all stations that have used their maximum time to send data. The simulation results show a 30% reduction in communication delay and a 25% improvement in stored energy in this design.
2-3- Network Layer in the WiNoC:
For maximum performance in the WiNoC, it is necessary to have deadlock-free and fault-tolerant routing algorithms. A fully adaptive fault-tolerant routing algorithm (FAFTR) has been proposed and investigated in reference [11]. In addition to finding the shortest path, the proposed distributed algorithm can be free of deadlocks. In this algorithm, the deadlock has been prevented by applying rotation restrictions.
A deadlock-free routing algorithm based on the static routing table and the XY algorithm, with a sub-THz frequency band in the mesh structure, has been also presented in the reference [12]. Reference [13] has presented an algorithm that uses the buffer state of wireless routers to decide on the shortest path. This algorithm has been able to prevent traffic in wireless routers.
The use of routing algorithms along with Media Access Control (MAC) mechanisms as well as core flow rate control solutions can provide better network performance in the WiNoC while properly distributing traffic throughout the network.
Transmitter flow control algorithms can also manage the competitive conditions created between cores for shared resources (such as channel bandwidth or buffers) and provide fair resource allocation. Hence, two types of flow control in the NoC can be considered:
2-3-1- Switch-to-Switch (Router) Mechanisms:
in this design, control signals between adjacent routers have been used locally to regulate the flow rate of traffic. Examples include credit-based flow control, on-off flow control, acknowledgment/non-acknowledgment protocol, and handshaking signal-based flow control. These methods do not require direct communication between the transmitter and receiver to exchange control signals and do not impose much control overhead on the system. However, as the number of cores increases and the size of the network increases, before the path congestion information in the form of control signals can reach the origin at the appropriate time, the packets sent by the transmitter will inevitably increase the network congestion [14].
2-3-2- End-to-End Flow Control Mechanisms:
in this mechanism, the transmitter cores will be responsible for the rate of production and injection of their flows into the network. This method eliminates packet overload and network congestion. In the network on chip, unlike computer networks, it is not possible to delete and lose packets, therefore, there is no need for confirmation signals to send and receive packets safely. Therefore, end-to-end flow control methods will not impose much control overhead on the system and each core will be independently responsible for controlling and regulating the transmitted flow rate [15].
In the following, we will first review the works done on the problem of congestion control/flow control in the NoC. Then, the works done on the flow rate control in the WiNoC have been presented. Reference [14] has proposed a prediction-based congestion control algorithm. In this design, each router decides on the congestion that may occur in the future based on the size and status of its gateway buffer. This design regulates the number of packets in the network by controlling the flow rate of injection of packets into the network.
In reference [16], link utilization has been used as a measure of congestion. A controller determines the appropriate workload for the current transmitters at best.
In the reference [17] of the CAP-W algorithm, a combined routing algorithm has been used to solve the problem of local congestion in the hierarchical wired and wireless structure. The proposed routing algorithm has tried to control congestion in the area by distributing traffic throughout the network by changing the status of a deterministic routing to adaptive routing and also proposing mapping tasks to freer cores.
Distributed congestion control method has been proposed in the reference [18]. To detect congestion, the number of packets in the queue buffers has been used. The main disadvantage of this method is that due to the limited space of the buffer of each router, it is possible to detect the fault, especially when the network congestion is relatively high.
A congestion control mechanism based on the flow rate utility function and the total delay was presented in references [19-21].
In a WiNoC, two types of competitive flow have been proposed [22-23]. The authors have presented a distributed flow control mechanism with a buffer management strategy to improve network performance on the wireless chip. In [23] the buffer information of each wireless router is used to prevent congestion. On the other hand, using the deterministic routing algorithms lead to Head-of-Line (HoL) blocking when load traffic is high [30-32]. Hence, some studies used congestion control mechanisms to eliminate HoL and reduce congestion in the wireless routers congestion-aware routing algorithms [33-34].
3- Mathematical Modeling of Flow Rate Control in WiNoC
In this section, we will first describe the network model used and then the flow rate control problem has been modeled.
3-1- Model of WiNoC
The NoC is based on a two-dimensional mesh connection with several routers equipped with a wireless antenna in the center of each 3 × 3 sections. Figure 3 shows a view of this structure.
Fig. 3. Graphic structure of the proposed network
The wireless structure is based on a mechanism of Frequency Division Multiple Access (FDMA) and wireless single-hop transmission. Each wireless router can access the other routers in the adjacent subdivision using a single hop. In this structure, the bandwidth of wireless channels has been assumed to be fixed and without bit error. All wireless routers (red nodes) are in direct view of each other and each pair of them operates in a separate frequency band (channel) from the other pairs. The switching method is wormhole switching. The X-Y routing algorithm is used to route packets (first the packet moves in the X direction and then in the Y direction) which is a deadlock-free algorithm. Routing between each transmitter and receiver pair located in 3 × 3 areas is performed using the X-Y routing algorithm. If the transmitter and receiver are not in a 3 × 3 section, then a combination of the X-Y algorithm and wireless links are used to send packets between the source and destination. A matrix A has been established by using this routing pattern. This matrix will show the routing pattern between the transmitter and receiver. In the implemented structure, the size of matrix A is 64 × 36 (64 rows and 36 columns for 6 × 6 networks). Since one of the features of routing algorithms of the NoC is to prevent deadlocks, therefore, to prevent this phenomenon, the octagon turn model [24] has been used in the proposed method. This model uses four clockwise rotations and four counterclockwise rotations to prevent deadlock and create cycles. The rules of this model have been stated as follows:
• The flit of a package will not be allowed to turn in the following four clockwise directions:
W→SE, N→SW, E→NW, and S→NE
• The flits of a package will not be allowed to turn in the following four counterclockwise directions:
NE→S, NW→E, SW→N, and SE→W
Figure 4 shows the eight ports (directions in which the flits of a packet can be sent or received) from a router equipped with a wireless antenna. Table 1 also shows the symbols used in the proposed modeling.
Table 1. Symbols used in the proposed model
Symbol | Definition |
| Core set |
| A set of wired and wireless links |
| Injection rate per core |
| The bandwidth of each link |
| A set of links through which the core flow passes |
| A set of cores that pass through link l |
| Traffic pattern matrix |
Fig. 4. Wireless router with eight transmission and receiving directions
3-2- Flow Control Modeling Problem
In this section, the flow control problem in the WiNoC has been formulated using mathematical modeling. To control and regulate flow rates, the problem has been written in a utility-based function based on the limited bandwidth capacity of links as well as flow rates. This method aims to maximize the flow rate of all processing cores taking into account the mentioned limitations. The concept of utility function was inspired by economics science and shows the degree of satisfaction a consumer or seller of a product at his disposal. In the proposed model, a utility function called U is defined for each transmitter (k) based on the flow rate (x). The purpose of modeling is to maximize the sum of all rates of in-chip cores to achieve maximum optimum chip performance. The function has been considered as an incremental, derivative, and concave function [25]. Figure 5 shows the steps of modeling operations.
Fig. 5. Steps of flow control problem modeling
Equation 1 has shown that the sum of the flow rates through a link cannot be greater than the bandwidth capacity of the link. The symbol A is the link traffic pattern matrix written by the routing algorithm implemented in the target network.
(1)
Now, to control the flow rate of the cores to maximize total flow rates, the following relationships can be written:
subject to:
(3)
(4)
To solve the written nonlinear optimization problem, Lagrange multipliers can be used to rewrite the problem:
: The total cost of links through which the same flow passes. (The cost that a core must pay to pass its flow through these links [26]).
According to the dual theory, for any problem, dual convex optimization can also be written. The dual form of Equation 2 has been written in the following form [27]:
where
Considering the concavity and derivability of the utility function, the final and global value of the flow rate can be obtained from the following equation:
In this case, it 
is the optimal value of the written dual function, 
which can also be considered as the optimal of the initial function. The gradient projection method has been used to solve the dual problem. In this method, the value 
is set in the opposite direction of the gradient
.
(14)
in Equation 16 represents the value of the convergence hop. This parameter is an important factor in the convergence speed of the proposed algorithm. The selection of the value of this parameter in the implementation is based on the values mentioned in the reference [28]. When the sum of the costs of using link l is more than the bandwidth of link l, in other words, when the value of the relationship 
is positive, the link cost will increase in the next hop (line 2 in the pseudo-code of the proposed algorithm). The pseudo-code of the proposed algorithm for the flow control problem in the form of an iterative algorithm has been shown in Figure7.
4- Numerical Simulation of the Proposed Algorithm
Implementation of the proposed algorithm on the WiNoC with 36 processing cores (four wireless routers (yellow nodes) and 32 wireless routers (0 blue nodes)) and 64 links (four wireless links (dotted links) and 60 wired links) organized in a 6 × 6 mesh structure (Figure 6) have been investigated using the CVX tool [29]. The bandwidth of wired links at 1 Gbps and wireless channels at 2 Gbps have been considered. The traffic pattern generated by the cores is uniform. In this pattern, each core can send or receive packets from all cores in the network.
This implementation also shows the flow rate convergence of cores to an equilibrium point. The transmitter of each flow also prevents congestion in the network by adjusting the rate of the transmitted flow, while using the available bandwidth of the links more effectively. Figure 8 has shown that the proposed algorithm with the step size length 
has converged the flow rates of all cores to the optimum point after 60 iterations. Baseline routers equipped with wireless antennas can have a higher flow rate at the beginning of work. However, after the 30th iteration, the flow rate of the desired nodes is also decreased because all packets forward to distant destinations must be sent through wireless routers. This problem will cause congestion at wireless routers. Therefore, the flow rate of cores has decreased significantly compared to the initial time. Also, with the step size length 
, the proposed algorithm can converge the flow rate of cores to the final equilibrium point after 91 iterations (Figure 9). The flow rates at 50, 100, and 150 iterations for two scenarios are shown in the proposed algorithm.
Figure 10 shows that the rate of flows overlap approximately after the 93rd iteration and remain unchanged. While for , rates are unchanged from the 50th iteration. This problem will prove the rapid convergence rate of the proposed algorithm (Figure 11).
Figure 12 shows the network throughput under uniform and Bit-Complement traffic patterns. As it can be seen, the use of the proposed method has been able to improve the operational capacity of the network. Controlling and adjusting the flow rate of each core according to the capacity of each link can reduce the congestion traffic at each link. Hence, congestion in routers is reduced and the throughput of the network is increased.
Fig. 6. Network-on-chip with 36 nodes in mesh networks
Initialization:
1. Initialize Cl of all links. 2. Set link price vector to zero.
Main loop Do Until
Link Price Update: 1) Received rates 2) Update price by
3) Send
Rate Adaption: Received link prices from all links 1) Calculate 2) Adjust rate by
3) Send |
Fig. 7. Pseudo code of the proposed algorithm to control the flow rate of WiNoC
Fig. 8. Core flow rate with uniform hop length of and uniform traffic pattern
Fig. 9. Core flow rate with uniform hop length of and uniform traffic pattern
Fig. 10. The convergence of the rates at the iterations 50, 100, and 150 in a uniform, hop-by-hop traffic pattern
Fig. 11. The convergence of the rates at the iterations 50, 100, and 150 with Bit-Complement traffic pattern and hop length of
Fig. 12. Network throughput in uniform and Bit-Complement traffic patterns
5- Conclusion
In recent years, the development of the integrated circuit industry will promise to increase the number of in-chip processing cores. In multicore chips, NoC is an effective structure for exchanging data packets among cores. However, due to the communication delay between long-distance cores, congestion is occurring. Therefore, providing an interconnection network with less delay and power consumption will play a key role in improving the performance of multicore systems.
Using the shared wireless links with higher bandwidth on NoCs can reduce the data packet transmission delay. However, the wireless routers on these chips are converted to hot spots because of increasing the demand for data packets forwarding from one area to another through wireless links. Therefore, improving the quality of service and efficient use of resources in WiNoCs cannot be obtained without the presence of mechanisms for flow control or congestion control. In this paper, the flow rate control mechanism in a wireless NoC is introduced as a utility maximization problem. The solution to this problem is done by writing a dual problem of the primary problem and using the gradient projection method by considering a utility function. Hence, an iterative algorithm is proposed to regulate and control the flow rate of cores. The simulation results of the proposed algorithm under traffic patterns show that the proposed algorithm can regulate the flow rate of processing cores and the network throughput at an acceptable speed and level. As well, the convergence speed of the proposed method under the amount of step size is shown in the proposed algorithm.
References
[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.
* Farhad Rad
Fa.rad@iau.ac.ir
