Abstract:
A bandwidth allocator to allocate in real time shared resources of a network on-chip is disclosed. The bandwidth allocator routes data packets between elements of the network in response to requests to access the shared resources. The bandwidth allocator could include a plurality of network interfaces to process the data packets to be routed within the network and a plurality of routers for routing the data packets through the network. A processor, distributed within the routers, controls the routers and the transmission of each data of the data packets through the routers to provide a bandwidth for each data flow. The network interfaces is adapted to fill a header field of each data packet with header field information depending on a requested bandwidth. The processor controls the transmission of the data packets through the routers as a function of the value of the header field information of each data packet.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
   The present application is related to European Patent Application No. 06 290 854.6, filed May 29, 2006, entitled “ON-CHIP BANDWIDTH ALLOCATOR”. European Patent Application No. 06 290 854.6 is assigned to the assignee of the present application and is hereby incorporated by reference into the present disclosure as if fully set forth herein. The present application hereby claims priority under 35 U.S.C. §119(a) to European Patent Application No. 06 290 854.6. 
   TECHNICAL FIELD 
   The present disclosure relates in general to packet forwarding operations in on-chip communication networks and, in particular, to a bandwidth allocator for allocating in real-time shared resources of an on-chip network for routing data packets between elements of the network, such as a calculating means and a memory means. 
   BACKGROUND 
   An on-chip network, or Network on Chip (NoC) is based on packet-based communication and relies on a layered definition of the communication. NoCs generally replace buses which tend to be limited in terms of scalability, wire efficiency and performance. 
   Different fundamental approaches may be followed when building a network core for routing data. Networks based on reservation of connections imply arrangements which are rather complicated and are not appropriate for allocating resources within a low cost arrangement. On the other hand, in packet switched networks, the resources are not reserved. Packets use the resources on demand, and as a consequence, may have not to wait for access to communication link. 
   Conventional methods and apparatuses for controlling data routing use an arbitration logic. A conventional arbitration controller typically includes a plurality of inputs that receive one or more transactions from a plurality of resources. For example, a conventional arbitration controller typically arbitrates requests for access to shared resources among the plurality of blocks of functionality by implementing an arbitration policy for allowing data packets to be transferred with a requested quality of service (QoS), in particular a requested bandwidth. Accordingly, the arbitration logic is based on sorting the priority bits written in the data packets to be transferred. Accordingly, the shared resources are allocated to the packets according to the value of the priority bit. 
   Most conventional systems are used to transfer data on bus architectures and are not intended for allocating shared resources in a NOC. In addition, conventional communication systems, the value of the priority bit is allocated to data flow only when the priority is to be changed. Groups of packets are identified by tagging the beginning and/or the end. 
   In other words, all data having the same level of priority are not tagged with the information bit. Thus, problems may arise when bits of data flows previously sprayed in the network have to be gathered together. Moreover, each time more flows are concentrated, the tagging must follow composition rules not trivial to implement. 
   In addition, with conventional resource allocation methods, it is not possible to use any kind of arbitration method, such as WRR (“Weighted Round Robin”) or priority or other possible schemes. 
   There is therefore a need for a bandwidth allocator for allocating in real-time shared resources in an on-chip network of a simple architecture, and in which any kind of allocating strategies may be used. 
   SUMMARY 
   The present disclosure provides a real-time bandwidth allocator for allocating shared resources of a network on-chip (NOC). The bandwidth allocator routes data packets between elements of the network in response to requests for accessing the shared resources. 
   In one embodiment, the present disclosure provides a real-time bandwidth allocator to allocate time-shared resources of a network on-chip (NOC). The allocator includes a network interface to process data packets to be routed within the network. The network interface also populates a header field of at least one of the data packets with header field information depending on a requested bandwidth. The allocator could also include routers to route the packets through the network and a processor to control the routers. The processor could also control the transmission of data within each of the data packets through the routers according to a function of a value of the header field information of each data packet. 
   In another embodiment, the present disclosure provides a method of allocating shared resources of a network on-chip in real time. The method could include populating a header field of data packets with header field information depending on a requested bandwidth. The method could also include controlling transmission of the data packets through routers as a function of the value of the header field information of each data packet. 
   In still another embodiment, the present disclosure provides a bandwidth allocator to allocate in real time shared resources of a network on-chip. The bandwidth allocator routes data packets between elements of the network in response to requests to access the shared resources. The bandwidth allocator could include a plurality of network interfaces to process the data packets to be routed within the network. The bandwidth allocator could also include a plurality of routers for routing the data packets through the network. The bandwidth allocator could further include a processor distributed within the routers to control the routers and the transmission of each data of the data packets through the routers to provide a bandwidth for each data flow. The network interfaces is adapted to fill a header field of each data packet with header field information depending on a requested bandwidth. The processor controls the transmission of the data packets through the routers as a function of the value of the header field information of each data packet. 
   Other technical features may be readily apparent to one skilled in the art from the following figures, descriptions and claims. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     For a more complete understanding of this disclosure and its features, reference is now made to the following description, taken in conjunction with the accompanying drawings, in which: 
       FIG. 1  is a somewhat simplified schematic of a routing strategy for data packets according to one embodiment of the present disclosure; 
       FIG. 2  is a block diagram of a routing means according to one embodiment of the present disclosure; and 
       FIG. 3  is a somewhat simplified block diagram of a routing means and, in particular, of the arbitration controller to elaborate the priority value according to one embodiment of the present disclosure. 
   

   DETAILED DESCRIPTION 
   Reference will now be made to  FIGS. 1 and 2  which illustrate a bandwidth allocator according to the invention. One embodiment of the allocator is intended to provide a flexible, scalable and low cost management for allocating variable bandwidth for data packets to be routed within an on-chip network. 
     FIG. 1  is a somewhat simplified illustration of network  100 . Network  100  includes a set of routers (R)  102  connected to respective network interfaces (NI 1 , NI 2  and NI 3 )  104   a ,  104   b  and  104   c  (sometimes collectively referred to herein as network interfaces  104 ) in which data packets to be transferred are entered. In the embodiment shown in  FIG. 1 , the network of routers (R)  102  receives packets of data from the network interfaces (NI 1  NI 2  and NI 3 )  104 . Access to shared resources is controlled by arbitration means  200  included in each router  102  as shown in  FIG. 2 . 
   More particularly, within each router  102  output links are shared resources. Arbitration means  200 , depicted in  FIG. 2 , included in each router  102  arbitrates the resources such that data packets from the network interfaces (NI 1 , NI 2  or NI 3 )  104  are arbitrated through the routers  102  they are going to cross accordingly to priority policy. 
   Each packet, denoted A, B or C, is associated with a weighting factor, for example 3, 2 or 4 such that, after routed by a corresponding router, the data packets are transmitted according to the value of the weighting factor. For example, if data packets A, B and C are allocated with weighting factors 3, 2, 4 respectively, the transmitted word of packets will be, in one embodiment, ABC ABC ACC. But the sequence can be different in another embodiment depending on the arbitration scheme used within the word of packets, for instance AAA BB CCCC. 
   As illustrated in  FIG. 2 , arbitration means  200  of each router  102  are used to grant or not access to the shared resources for each request (req- 1 , req- 2  or req- 3 ), to access said resource, by setting the value of a grant signal (gnt- 1 , gnt- 2  or gnt- 3 ) associated with each request input. 
   As also illustrated, arbitration means  200  of each router  102  comprises a priority arbiter (PA)  202  intended to grant or not access to the shared resources and an arbitration controller (CTRL)  204  which elaborates and allocates priority values to each data packet entered to the router  102 , with a view to schedule transmission of each data packet to allow a higher priority (PR- 1 , PR- 2  or PR- 3 ) to one of the request (req- 1 , req- 2  or req- 3 ) to access shared resources of the network  100  inputted in the router  102 . 
   The execution strategy is based on the use of priority information introduced within the header filled of injected packets. In particular, the network interfaces (NI 1 , NI 2  and NI 3 )  104  are provided with means and are dully programmed for filling the header QoS field for each injected packet with the following bits: PK-faction-id, PK-priority and PK-priority-FBA. 
   The header field information, PK-faction-id, corresponds to the priority information associated to each packet and, for example, may have two values, namely “one” or “zero”. 
   The packet priority information, PK-priority, is the priority specified for each packet within a set of packets having the same PK-faction-id and is used, in one embodiment of the present disclosure, to allocate particular priority to each of these packets having a same header field information. 
   The third information value, PK-priority-FBA, is written in each header field and is used to allocate priority for each data packet not transferred or, in other words, to the least recently served packets. 
   This information is entered within the arbitration controller (CTRL)  204  to schedule priority and allocate the shared resources ( FIG. 2 ). 
   Accordingly, as illustrated in  FIG. 2 , when each data packet is entered within the on-chip network, the packets are first tagged with the information PK-faction-id- 1 , PK-faction-id- 2  or PK-faction-id- 3  depending on a requested bandwidth and the packets from different sources are transferred, at each router of the network R, such that packets having the same priority information PK-faction-id-i are grouped to move together. 
   For example, the header field information PK-faction-id-i and the third information value PK-priority-FBA-i are to prioritize packets least served and are coded using one bit, whereas the packet priority information PK-priority-i is coded using two bits. However, this packet priority information may be coded, if needed, using a different number of bits (n) greater than 2. 
   It should be noted that a requested bandwidth is expressed in bytes and corresponds to the global amount of data transferred, computed from the opcode size, by a considered one network interface in a given round during which the packets are transferred using a same information PK-faction-id, at a specific target. 
   The round at the specific target is a given number of variable accesses. The size of bytes read or written in that round represents the percentage of variable bandwidth demanded by this initiator flow. 
   As previously indicated, the priority information PK-faction-id-i may have two values, namely one or zero, depending on the requested bandwidth for reaching a specific target. 
   In addition, the data packets that have to be transferred together are tagged by the same PK-faction-id-i. For that purpose, each network interface (NIi)  104  accumulates the opcode size associated to each packet and tags with the same priority information all the packets until the threshold value is reached. Then, the priority information is switched, and the data transfer size is once again accumulated until the threshold is reached again. In one embodiment, the threshold can be fixed and in another embodiment it can vary dynamically with specific hardware of software means to control its value. Accordingly, the arbitration controller (CTRL)  104  gives high priority (PR-i) to packets which have the same header field information. The thus labeled data packets are transferred first. 
   The data packets having the same priority information PK-faction-id, the arbitration controller (CTRL)  204  may, as indicated above, use a known arbitration strategy, for example, of the type RR (“Round Robin”), WRR (“Weighted Round Robin”) or LRU (“Least Recently used”). However, it should be understood that any other suitable strategies may also be used. 
   According to another embodiment, specific priority may be allocated to each data packet having a same priority information PK-faction-id-i using the packet priority information PK-priority- 1 , PK-priority- 2  or PK-priority- 3  such that the router  102  transfers first the data packets having the higher packet priority information. 
   As previously indicated, the data packets are transferred by the routers  102  according to the value of the priority information. In particular, the arbitration controller (CTRL)  204  stores, within a register, the current value of the priority information PK-faction-id of transferred data packets. 
   For that purpose, the header field information included within the QoS header of each incident packet is compared with the current value stored within the register. When the value of this information corresponds to that of the current information stored within the register, the packet is tagged with a high priority in order to be transferred together with the data packets having the same priority information. 
   As illustrated by  FIG. 3 , the arbitration controller  200  is, for that purpose, realized using a simple logic circuitry  300 . For example, in one embodiment, this logic circuitry  300  comprises a first logic gate  302  realizing the logical function “NOT (XOR)” between the header field information PK-faction-id-i and the current header field information. A second logical gate  304  realizes the logical function “OR” between the third information allocating for each data packet not transferred a priority PK-priority-FBA-i, locally tagged or previously written at a previously reached router and a corresponding information PK-priority-FBA-int-i computed internally by the arbitration controller associated with a present router  102 . 
   Finally, another priority information is elaborated using the PK-priority data. Otherwise, as previously indicated, a conventional arbitration strategy block  306  may be used to elaborate priority information for data packets having the same header field information. 
   Each information provided by the logical elements  302  and  304  or by the block  306  are used to elaborate a priority word the most significant bit (MSB) of which corresponds to the output of the first logical gate  302 , whereas the two least significant bits (LSB) correspond to the priority information provided by the third block  306 . 
   Accordingly, the most significant bit MSB is set to one when the priority information provided by a logical gate  302  is equal to the corresponding information stored within the register of the arbitration controller. This means that the current packet belongs to the current information value and must have highest priority. 
   The two least significant bits correspond to the field of the packet header previously called PK-priority or is generated by the RR or WRR logic or by the LRU logic in block  308 . 
   Finally, the bit issued by the second logical block  304  is used to set a high or a low priority to packets that have not been transferred or that have been transferred in a previous round. This reduces latency because flows that miss a round will be prioritized in the following round. This bit can be constituted by a value reported in the header or computed internally by the arbitration controller unit (CTL)  204  as result of the last round local to this router. 
   The information PK-priority-FBA-int is updated when the priority information changes. In such a case, this data PK-priority-FBA-int is set for each input not served in previous rounds and is copied within the header of each packet arising from the same entry. 
   Finally, as concerns the current priority information stored within the register of the arbitration controller, this value is maintained when an incident packet has the same information data value or when no packet arrives. On the contrary, this value is changed when there is no packet having this priority information value. For that purpose, bits of the header PK-faction-id, which are allowed to pass, are simply sampled to determine the value of the internal priority value. 
   It should at last be noted that there are numerous benefits of the bandwidth allocator according to the present disclosure. For example, the bandwidth allocator is only requested to program the network interface with the requested bandwidth value. In addition, the routers have no register to be programmed and thus their behavior is fixed. 
   Furthermore, the quality of service (QoS) is not explicitly linked to the path of flow through the routers, but only to the injection point, namely the network interface. For instance, routing can be changed without any effort to re-compute the path followed by the flow and the consequent QoS parameters along this new path. One embodiment of the present disclosure is good to support hierarchical multi-hop distributed interconnected such as the network on chip. 
   Another benefit of one embodiment of the present disclosure is that bandwidth can be proportionally allocated, but flows can be prioritized in a round using any available standard arbitration scheme or a per-packet priority scheme. Least recently used packets can be automatically and dynamically prioritized through the entire network to limit maximum latency. Finally, the router implements a simple arbiter, without any need of counter or slow complex logic. 
   It may be advantageous to set forth definitions of certain words and phrases used in this patent document. The term “couple” and its derivatives refer to any direct or indirect communication between two or more elements, whether or not those elements are in physical contact with one another. The terms “include” and “comprise,” as well as derivatives thereof, mean inclusion without limitation. The term “or” is inclusive, meaning and/or. The phrases “associated with” and “associated therewith,” as well as derivatives thereof, may mean to include, be included within, interconnect with, contain, be contained within, connect to or with, couple to or with, be communicable with, cooperate with, interleave, juxtapose, be proximate to, be bound to or with, have, have a property of, or the like. 
   While this disclosure has described certain embodiments and generally associated methods, alterations and permutations of these embodiments and methods will be apparent to those skilled in the art. Accordingly, the above description of example embodiments does not define or constrain this disclosure. Other changes, substitutions, and alterations are also possible without departing from the spirit and scope of this disclosure, as defined by the following claims.