Patent Publication Number: US-9906467-B2

Title: Inverse weighted arbitration

Description:
RELATED APPLICATIONS 
     This application claims the benefit of the Jun. 13, 2014 priority date of U.S. provisional application 62/012,027, the contents of which are herein incorporated by reference. 
    
    
     FIELD OF INVENTION 
     This application relates to resource allocation, and in particular, to equitable allocation of computing resources among competing entities. 
     BACKGROUND 
     In many computer systems, entities compete for use of a particular resource. A goal in some such systems is to provide equality of service among the competing entities. 
     A known way to allocate a resource among such competing entities is to provide each entity with equal time using the resource. This may result in locally fair arbitration of the resource. However, locally fair arbitration can result in unfairness at the global level. 
     A known way to overcome this difficulty is to dynamically observe demands made by the competing entities and to adjust resource allocation accordingly. Another known way is to allocate a resource on the basis of waiting times associated with each competing entity. However, these schemes introduce additional overhead. 
     SUMMARY 
     In one aspect, the invention features an apparatus for data communication. Such an apparatus includes a router, a plurality of packet producers, each of which is directly connected to the router, and a penalizer. Although there can be any number of packet producers, the invention is best understood, without loss of generality, by considering the operation with a first packet producer and a second packet producer, or with first, second, and third packet producers. The penalizer assesses a first penalty against the first packet producer when the router services the first packet producer. Similarly, it assesses a second penalty against the second packet producer when the router services the second packet producer. The first and second penalties have values that depend at least in part on expected extents to which the first and second packet producers require service. The penalizer then combines the penalty assessed against the first packet producer with an accumulated penalty for the first packet producer. Similarly, the penalizer combines the penalty assessed against the second packet producer with an accumulated penalty for the second packet producer. The invention is described herein in terms of only a few packet producers for ease of exposition. The operation and structure would be the same for any number of packet producers, or, more generally, any number of entities that seek access to a finite resource. 
     Some embodiments also include a network in which the data communication takes place. Among these are embodiments in which the entire network is integrated into a chip, those in which the entire network is distributed across, and integrated into, plural chips, those in which parts of the network are integrated into one or more chips, and those in which the network is not integrated at all. 
     Some embodiments include an arbiter that is configured to award priority to a packet producer based at least in part on the accumulated penalty for the first packet producer and on the accumulated penalty for the second packet producer. Among these are embodiments in which the arbiter is configured to cause penalty values that are greater than a threshold to become less than the threshold when a request has been received from a producer having a penalty accumulator whose value is above the threshold but no request has concurrently been received from a producer having a penalty accumulator whose value is below the threshold. 
     Also among the embodiments that include such an arbiter are those in which the packet producers are divided among upper and lower rungs of a penalty ladder that can have two or more rungs. In these embodiments, packet producers are placed on rungs based on their accumulated penalties. For example, a packet producer is on the upper rung if an accumulated penalty associated with the producer is in excess of a threshold. Conversely, a packet producer is on the lower rung if an accumulated penalty associated with the producer is less than the threshold. The arbiter is programmed or otherwise configured to award priority to a producer on the lower rung when possible. A variety of methods can be used to select a particular packet producer from those on the lower rung. In one particular embodiment, the arbiter does so by using round-robin arbitration. 
     As noted above, the penalty ladder is not restricted to two rungs. For example, the penalty ladder can have three or more rungs, each one of which is associated with a range of penalty values. In these embodiments, the packet producers are divided among the rungs based on their accumulated penalties. In particular, a packet producer is on a particular rung if an accumulated penalty associated with the producer is within a range of penalty values associated with the particular rung. In these embodiments, the arbiter preferentially services penalty accumulators in the lowest rung that has penalty accumulators in it, and then services penalty accumulators in each of the next highest occupied rung, an occupied rung being one that has at least one penalty accumulator in it. The arbiter does so in order from the lowest occupied rung to the highest occupied rung. In these embodiments, the arbiter uses any number of schemes for selecting a particular producer within a rung. In some embodiments, it uses round-robin arbitration to select a particular producer from among a plurality of producers on one of the rungs. Also among these embodiments are those in which each rung has an associated threshold, and the arbiter uses round-robin arbitration to select a particular producer from among a plurality of producers on a rung that, among all rungs that have associated producers, has the lowest associated threshold. 
     Among those embodiments that feature an arbiter are those in which the arbiter responds to a dynamically changing relationship between a threshold and the penalty values and causes a change in that the relationship in response to the occurrence of a condition that depends on the relationship. In these embodiments, packet producers are divided among upper and lower rungs of a penalty ladder, with each rung having an associated threshold. Among these are embodiments in which the arbiter causes penalty values that are greater than the threshold to become less than the threshold. In some embodiments, this is carried out by causing penalty values that are greater than the threshold to become less than the threshold by increasing the threshold, or alternatively, by subtracting a value from the penalty values. Subtraction can be carried out in various ways. For example, when each penalty value is represented in binary by a fixed number of bits, the arbiter can subtract a value by clearing the most significant bit in the string of bits. As another example, the arbiter subtracts a selected value, such as the threshold itself, from the penalty values. In other examples the selected value is a value other than the threshold. 
     In some embodiments, the packet producers are dynamically divided among rungs of a penalty ladder based on accumulated penalties of each of the packet producers. These embodiments include circuitry for identifying a next packet producer to be serviced. Such circuitry includes a set of first fixed-priority arbiters and a second fixed-priority arbiter. The second fixed-priority arbiter includes a plurality of inputs. Each of the first fixed-priority arbiters corresponds to one of the inputs. These embodiments include those in which the number of inputs is one more than the number of rungs in the penalty ladder, as well as those in which the number of inputs is less than or equal to twice the number of rungs in the penalty ladder. 
     Alternative embodiments that include an arbiter are those in which the arbiter allocates service among packet producers based on a load ratio. In these embodiments, the first and second packet producers have corresponding average loads. A ratio of these loads defines a load ratio. The arbiter then allocates service between the first and second packet producers based on this load ratio. In particular, the arbiter allocates service between the first and second packet producers such that a ratio of service provided between the first and second packet producers is the same as the load ratio. 
     In other embodiments that include an arbiter, the first and second packet producers have corresponding first and second designated service levels. These service levels define a service ratio. The arbiter allocates service between the first and second packet producers such that a ratio of service provided between the first and second packet producers is the same as the service ratio. 
     In another embodiment, the penalty value assessed against the first packet producer is inversely proportional to an expected extent to which the first packet producer requires service. Similarly, the penalty value assessed against the second packet producer is inversely proportional to an expected extent to which the second packet producer requires service. In another embodiment, packet producers that require the most service incur the smallest penalty values. 
     Other embodiments feature first and second penalty accumulators corresponding to the first and second packet producers. In these embodiments, the penalizer is configured to accumulate penalties for the first and second packet producers in the corresponding first and second penalty accumulators. 
     In other embodiments, the penalizer assesses a penalty value against the first packet producer. This penalty value depends at least in part on a traffic pattern associated with a data packet associated with the first packet producer. Among these embodiments are those in which the penalizer inspects a data packet and determines, based on information in the data packet, a traffic pattern associated with the data packet. 
     Also among the embodiments are those in which the router has at least one output port and the penalizer is associated with this output port. 
     In another aspect, the invention features an apparatus comprising a data communication system that comprises a set of competitors, and a finite resource that provides a service that is required by the competitors for carrying out data communication. The data-communication system allocates this finite resource among the competitors. Each competitor comprises a source of data that is to be communicated using the finite resource. Each competitor also has a corresponding expectation. This expectation indicates an extent to which the competitor is expected to require service from the resource. The system further includes an arbiter, a penalizer, and a plurality of penalty accumulators, each of which corresponds to one of the competitors. The arbiter schedules the competitors for receiving service from the resource. The penalizer penalizes a competitor for requesting access to the resource. In particular, in response to receiving a request from a particular competitor for service by the finite resource, the penalizer assesses a penalty. The extent of that penalty is inversely related to the expectation. For each competitor, the penalizer accumulates penalties for that competitor in that competitor&#39;s corresponding penalty accumulator. The penalty accumulators are dynamically assigned to rungs of the penalty ladder. Each rung has an assigned range of accumulated penalty values. The penalty accumulators transition among the rungs based on changes to accumulated penalty values stored therein. The arbiter services competitors assigned to a lower rung before servicing competitors on a higher rung. Within a rung that is being serviced, the arbiter executes a round robin to service competitors assigned to the rung. 
     In some embodiments, the competitors comprise sources of units of information. Among these are embodiments in which the units of information comprise data packets and those in which they comprise datagrams. 
     In those embodiments in which the competitors comprise sources of information units, the sources can include routers, computational elements, and/or communication channels. 
     Some embodiments also include a router that has at least one output port. In these embodiments, the finite resource is that output port. 
     Also among the embodiments are those in which the resource and the competitors are implemented on a common chip, and those in which the resource and the competitors are implemented on plural chips. 
     Yet other embodiments include hardware configured to implement a molecular-dynamics simulation system for simulating states of bodies in a simulation volume that is divided into a plurality of simulation regions. Such hardware includes a plurality of nodes, and an off-chip network that interconnects the nodes. Each node simulates states of bodies within a particular simulation region of the simulation volume. Each node includes a chip that has multiple cores and an on-chip network that interconnects the multiple cores. The on-chip network includes a plurality of on-chip routers, each of which has at least one output port. The arbiter, penalizer, penalty accumulator, and penalty ladder are associated with an output port of one of these on-chip routers. 
     An advantage of one or more embodiments is that the arbitration approach at a router can be implemented with relatively simple hardware, for example, without the complexity of monitoring backlogs of packets, because the target number or rate of packets to pass through via the router are known in advance. 
    
    
     
       DESCRIPTION OF THE FIGURES 
       These and other features of the invention will be apparent from the following detailed description and the accompanying figures, in which: 
         FIG. 1  shows information producers connected to a router; 
         FIG. 2  shows an arbiter corresponding to one of the output ports in the router shown in  FIG. 1 ; 
         FIG. 3  shows a two-rung penalty ladder; 
         FIG. 4  shows a three-rung penalty ladder; and 
         FIG. 5  shows a molecular-dynamics simulation system having nodes, each of which implements inverse-weighted arbitration using arbiters as shown in  FIG. 2 . 
     
    
    
     DETAILED DESCRIPTION 
     The invention concerns the management of competition by several entities for a particular finite resource. In certain embodiments described herein, the finite resource is access to a particular one of the one or more output ports of a router. However, the subject matter described herein is applicable to competition for any finite resource, including, without limitation, competition for memory locations, competition for ports used to read from and write to memory locations, and competition for inter-router channels. 
     The competing entities are producers of data packets. Each competing entity would like to provide a sequence of these packets to the router, where the sequence of packets can include one or more data packets. Ideally, as each packet from a sequence arrives, the router would immediately forward that packet to a particular output port of the router. Unfortunately for the competing entity, there may be many other competing entities, all of which are providing packets to the router for further delivery through the designated port. 
     The packet producers can be, without limitation, other routers, computational elements, or communication channels, whether they are implemented on the same chip or on different chips. Common to all such producers is that they produce units of information, such as data packets, that need routing to a destination. 
       FIG. 1  shows a router  14  having a plurality of input ports  16   a ,  16   b ,  16   c  and a plurality of output ports  18   a ,  18   b ,  18   c . Although only three input ports and three output ports are shown, it is understood that this is only by way of example, and that in general a router can have m input ports and n output ports, where m and n are positive integers. 
     Three producers  20   a ,  20   b ,  20   c  are in data communication with the router  14 . Although three producers are shown, it is understood that this is only by way of example, and that in general there can be k producers, where k is a positive integer greater than 1. For ease of exposition, and without loss of generality, the invention as shown in  FIG. 1  will be described for the case in which k=3. However, the principles described herein are easily extended to other values of k. 
     When traffic is light, there is no backlog of packets waiting to pass through the router  14 . In that case, when the router  14  receives a packet from a producer  20   a - 20   c , it inspects the packet to see where it is going. Having done so, it then forwards it immediately out the correct output port  18   a - 18   c.    
     However, sometimes a router  14  develops a backlog of packets to be delivered. In that case, to the extent the producers  20   a - 20   c  each provide packets that are ultimately to be forwarded through a particular router output (for example, output port  18   b ), they become competing entities. The resource being competed for is the access to that output port  18   b . The router  14  must therefore somehow determine, for instance, an order in which it should forward packets from the producers  20   a - 20   c.    
     In some applications, the router  14  is part of a network that is used in connection with one or more known computational tasks. Each such computational task gives rise to a characteristic data traffic pattern that is known in advance, for example by having been simulated. 
     For example, in one embodiment, which involves a simulation of molecular dynamics, different processing elements are assigned to carry out computations associated with different volumes of space. These processing elements must sometimes communicate with each other, generally through a network having routers, such as the router  14  shown in  FIG. 1 . 
     However, because the types of interactions are known in advance in such an embodiment, it is possible to predict traffic patterns among processing elements, and hence between the producers  20   a - 20   c  and the router  14 , with reasonable accuracy once the particular computational task is known. For example, the total number of packets, or an average rate of packets per unit time, that a router will receive from each producer  20   a - 20   c  connected to its input ports  16   a - 16   c  is known or approximately known for each of the computation tasks. 
     Advance knowledge of this characteristic data traffic pattern can be exploited for allocation of the particular router&#39;s attention among the competing producers  20   a - 20   c.    
       FIG. 2  shows circuitry  22  associated with a particular output port  18   b  for managing the way access to the output port  18   b  is shared among producers  20   a - 20   c . The remaining output ports  18   a ,  18   c  have similar circuitry that operates in the same way. Accordingly, only the circuitry for the particular output port  18   b  is described in detail. 
     An interconnector  17  mediates communication with the producers  20   a - 20   c  and updates a penalizer  26  that tracks the service history of each producer  20   a - 20   c . To do so, the penalizer  26  maintains penalty accumulators  28   a - 28   c  for each producer  20   a - 20   c  that is capable of using the port  18   b . Each penalty accumulator  28   a - 28   c  has a value indicative of an extent to which its corresponding producer  20   a - 20   c  has received attention. Thus, for example, each time a producer  20   a  provides a data packet to be routed through the output port  18   b , the penalizer  26  updates the penalty accumulator  28   b  for that producer  20   a.    
     As a result, at any instant, an arbiter  30  associated with a particular output port  18   b  can determine, for example, which of the producers  20   a - 20   c  has received the most or the least attention. To decide which producer  20   a - 20   c  to service next, the arbiter  30  inspects its penalty accumulators  28   a - 28   c  and identifies a penalty accumulator  28   c  that, at that instant, has a lower penalty value than other penalty accumulators. 
     In one embodiment, the arbiter  30  identifies the penalty accumulator  28   a - 28   c  having the lowest penalty value and then preferentially services the producer  20   a - 20   c  corresponding to that penalty accumulator  28   a - 28   c.    
     In another embodiment, shown in  FIG. 3 , the arbiter  30  defines what is referred to herein as a penalty ladder  32  having a lower rung  34  and an upper rung  36 . In these embodiments, the arbiter  30  moves penalty accumulators  28   a - 28   c  between the lower rung  34  and the upper rung  36  dynamically, based on a current penalty value in the penalty accumulator  28   a - 28   c . Each rung  34 ,  36  represents a particular priority level. As a result, a penalty accumulator  28   c  in the upper rung  36  currently has a penalty value above some threshold, and penalty accumulators  28   a ,  28   b  in the lower rung  34  are those that currently have a penalty value below that threshold. The arbiter  30  preferentially services producers  20   a ,  20   b  that have penalty accumulators  28   a ,  28   b  in the lower rung  34 . 
     Thus, in the embodiment illustrated in  FIG. 3 , the arbiter  30  services the needs of first and second producers  20   a ,  20   b  before servicing the needs of the third producer  20   c  because the third producer  20   c  has already had its share of attention from the arbiter  30 , as evidenced by the fact that its associated penalty accumulator  28   c  is on the upper rung  36  of the penalty ladder  32 . Within a particular rung  34 , the arbiter  30  uses round-robin arbitration to service the producers  20   a ,  20   b  that have penalty accumulators  28   a ,  28   b  on that rung  34 . 
     In yet another embodiment, shown in  FIG. 4 , the arbiter  30  defines a “penalty ladder”  32  having a plurality of rungs  34 ,  36 ,  38  each of which corresponds to one of a corresponding plurality of thresholds. The arbiter  30  then moves penalty accumulators  28   a - 28   c  between these rungs  34 ,  36 ,  38  dynamically based on a current penalty value in the penalty accumulator  28   a - 28   c . As a result, penalty accumulators  28   a - 28   b  on a particular rung  34  will be those that have a penalty value that is within the range of penalty values associated with that rung  34 . 
     The thresholds associated with the penalty ladder  32  are strictly increasing, meaning that the penalty values associated with the lowest rung  34  of the plurality of rungs  34 ,  36 ,  38  are the smallest, the penalty values associated with the next lowest rung  36  are the second smallest, and so on, through the uppermost rung  38 , which has the highest penalty values associated with it. 
     In the illustrated embodiment, there are three such rungs  34 ,  36 ,  38 . In this embodiment, the arbiter  30  preferentially services producers  20   a ,  20   b  whose corresponding penalty accumulators  28   a ,  28   b  are on the rung  34  that has the lowest penalty value among those rungs  34 ,  36 . 
     Embodiments in which penalty accumulators  28   a - 28   c  are distributed among rungs  34 ,  36 ,  38  of a penalty ladder  32 , as described above, and in which a round-robin arbitration scheme is applied within one or more of those rungs  34 ,  36 ,  38 , are particularly advantageous because it is expensive to implement hardware that can find the actual lowest penalty value among all penalty accumulators  28   a - 28   c.    
     In the case of the two-rung penalty ladder  32  shown in  FIG. 3 , the arbiter  30  preferentially services those producers  20   a ,  20   b  that have their associated penalty accumulators  28   a ,  28   b  in the lower rung  34 . One way to do this is to implement round-robin arbitration among the producers  20   a ,  20   b , and to service producers  28   c  that have their penalty accumulators in the upper rung (also using round-robin arbitration among the corresponding producers) only when there are no service requests from producers  20   a ,  20   b  having their penalty accumulators  28   a ,  28   b  in the lower rung  34 . 
     In the case in which the penalty ladder has three or more rungs, the arbiter  30  preferentially services penalty accumulators in the lowest rung that has penalty accumulators in it, and then services penalty accumulators in each of the next highest rungs with penalty accumulators in them in order of lowest rung to highest rung. When there are no requests from producers corresponding to penalty accumulators in a particular rung of the penalty ladder, the arbiter  30  then proceeds to the rung immediately above the particular rung. For example, if the arbiter  30  has determined that there are no requests from producers having penalty accumulators at rung n, it proceeds to rung n+1. Having arrived at rung n+1, the arbiter determines whether there are any requests for service. If the answer is “yes,” the arbiter  30  proceeds to service them. If the answer is “no,” the arbiter  30  proceeds to the next higher rung, which would be rung n+2, and repeats the procedure. In this way, the arbiter  30  climbs the penalty ladder  32  and services requests from producers as it encounters penalty accumulators associated with those producers on its climb. 
     It should be noted that every time a producer  20   a - 20   c  submits a data packet to be routed, its corresponding penalty accumulator  28   a - 28   c  receives some penalty. Therefore, in the long run, as long as its associated producer remains active by continuing to submit data packets, every penalty accumulator  28   a - 28   c  will eventually climb out of the lowest rung. This means that, in the long run, the particular router  14  will have serviced all active producers  20   a - 20   c  connected to it for long enough so that the penalty values stored in the penalty accumulators  28   a - 28   c  associated with these producers  20   a - 20   c  have all risen above a maximum penalty value associated with the lowest rung. In response, the arbiter  30  increases the value of the threshold associated with each of the active producers  20   a - 20   c . In another embodiment, which is preferable since the number space is finite, the arbiter  30  subtracts the threshold value from each of the penalty values associated with each of the active producers  20   a - 20   c . However, the penalty values associated with non-active producers remain unchanged. 
     In either case, the effect is the same. The arbiter  30  causes a change in the relationship between the threshold value and the penalty values associated with the active producers  20   a - 20   c . When a request is received from an active producer  20   a , the arbiter  30  checks for the presence of any active producers in a rung that is lower than the rung of the active producer  20   a . In particular, the arbiter  30  checks to see if there are any requests from any producers that are in a rung that is lower than the rung of the active producer  20   a  from which the request has been received. If there are no such producers, then a fixed amount is subtracted from all penalty values associated with producers in the rung of the active producer, and all penalty values associated with producers in all higher rungs. Penalty values associated with producers in lower rungs are left unchanged. For certain choices of the fixed amount to subtract and the thresholds of the rungs, this has the effect of moving all active producers to the next lower rung. In this manner, penalty values are prevented from growing beyond the threshold of the uppermost rung. 
     Subtraction can be carried out in several ways. In some embodiments, when the penalty values are represented as unsigned (n+1)-bit integers, and the maximum penalty value of the lower rung is 2 n −1, a particularly efficient way to carry out the subtraction is to simply clear the most significant bit of each penalty value, regardless of whether the penalty value is in the upper rung or the lower rung. 
     As noted above, it is particularly desirable to keep penalty values associated with less active producers unchanged. Ordinarily, one might expect that if the same operation is applied to all penalty values, then all penalty values will be affected in some way. However in this case, the operation affects only those penalty values in the upper rung. There is no effect on penalty values in the lower rung. 
     For those penalty values that are in the upper rung, clearing the most significant bit amounts to subtracting 2 n  from each penalty value, thus bringing those penalty values into the lower rung. However, for those penalty values that are in the lower rung, the most significant bit is already zero. Therefore, clearing the most significant bit has no effect on those penalty values. This method is particularly advantageous because clearing the most significant bit in a way that does not discriminate based what rung the penalty value is on is easily implemented in hardware and can be executed rapidly. 
     In other embodiments, one can use a hardware subtraction module to subtract any number. A suitable choice of number for subtraction is the lowest threshold in the ladder, since all penalty accumulators that have climbed out of the lowest rung will have a penalty value greater than this threshold. 
     The penalizer  26  associated with a particular output port  18   b  updates a penalty accumulator  28   a - 28   c  by incrementing the penalty value by a known penalty each time the particular router  14  services that penalty accumulator&#39;s corresponding producer  20   a - 20   c . The penalty, however, is not necessarily the same for all penalty accumulators  28   a - 28   c . In general, the penalty used for incrementing a value in a penalty accumulator  28   a - 28   c  depends on an expected number of packets that are to pass from that penalty accumulator&#39;s associated producer  20   a - 20   c . This expected load can be obtained in advance by a variety of methods, of which one example is off-line simulation of traffic patterns. 
     Thus, a producer  20   a  that is expected to be busy receives only a small penalty whenever the particular router  14  services it. A producer  20   c  that is not expected to be so busy receives a bigger penalty whenever the particular router  14  services it. 
     In one embodiment, the penalizer  26  assesses, against a producer  20   b , a penalty that is inversely proportional to the expected usage by that producer  20   b  under an incumbent traffic pattern. In that case, the penalty value stored in the penalty accumulator  28   b  at any time would be the total number of packets received from that producer  20   b  divided by the average load for that producer  20   b . In particular, the penalty value A i (t) that is stored in the penalty accumulator  28   b  associated with the i th  producer  20   b  at time t is given by S i (t)/γ i , where S i (t) is the total number of packets serviced by the router  14  on behalf of the i th  producer  20   b  at or before time t, and γ i  is the average load resulting from the i th  producer  20   b.    
     In such a case, the ratio of service provided between any two producers  20   a ,  20   b  will be the same as the ratio of their average loads γ i /γ j . 
     The foregoing description assumes that the traffic patterns are static. In other words, the various computational elements are simply doing the same thing over and over again. As a result, the traffic pattern never changes. 
     In some embodiments, the computational elements that use the network described herein will switch between different computational tasks, each of which has its own characteristic traffic pattern. A change to a different computational task thus results in a change to the traffic pattern. This means the traffic pattern changes with time. As a result, a first producer  20   b  that was the busiest producer during one computational task may find itself less busy, and a second producer  20   c  that was formerly somewhat idle may find itself working much harder. In that case, it would not be fair for the penalizer  26  to continue to assess a high penalty for the second producer  20   c  and a lower penalty for the first producer  20   b.    
     To address this unfairness, it is useful for the penalizer  26  to assess a penalty based not only on the identity of the producer  20   a - 20   c  but also on the particular traffic pattern associated with data packets provided by that producer  20   a - 20   c.    
     To implement this, it is useful to provide the penalizer  26  with information concerning the particular traffic pattern associated with a data packet from a producer  20   a - 20   c.    
     One way to do this is to include such information in data packets received by the router  14 . The penalizer  26  can then inspect a data packet to determine not only the associated producer  20   a - 20   c  but the particular task, and hence the traffic pattern, associated with that data packet. 
     In some embodiments, multiple traffic patterns are present at the same time rather than at different times. In such cases, the approach of applying traffic-pattern-dependent penalties continues to provide the desired result of fairness for each of the traffic patterns. 
     When multiple traffic patterns are concurrently present, the value of a penalty accumulator  28   b  at any time would be the total number of packets serviced on behalf of a particular producer  20   b  under a first traffic pattern divided by the average load associated with that producer  20   b  in that first traffic pattern added to the total number of packets serviced on behalf of that producer  20   b  under a second traffic pattern divided by the average load associated with that producer  20   b  in that second traffic pattern. In particular, the penalty value A i (t) that is stored in the penalty accumulator  28   b  associated with the i th  producer  20   b  at time t is given by: 
                   A   i     ⁡     (   t   )       =       ∑     n   =   0       N   -   1       ⁢         s     i   ,   n       ⁡     (   t   )       /     γ     i   ,   n             ,         
where the summation is carried out over all N traffic patterns, s i,n (t) is the total number of packets serviced on behalf of the i th  producer under the n th  traffic pattern at or before time t, and γ i,n  is the average load associated with the i th  producer under the n th  traffic pattern.
 
     The result is an effective traffic pattern formed by blending two or more traffic patterns with the weights associated with each traffic pattern in the blended mixture being proportional to the extent to which the system  10  engages in the computational task associated with that traffic pattern. This is summarized by the following equation for the effective load associated with the i th  producer. 
                   γ   _     i     =       ∑     n   =   0       N   -   1       ⁢       α   n     ⁢     γ     i   ,   n             ,         
where the α n  are mixing coefficients that sum to unity and that describe the fraction of traffic belonging to each traffic pattern, and γ i,n  is the average load associated with the i th  producer under the n th  traffic pattern.
 
     With K producers, some of which have requests, and N priority levels, or penalty rungs as used herein, where lower rungs have higher priority, a goal is to select a producer with a request at the highest possible priority level, using round-robin arbitration within a priority level when there are multiple producers with requests at that priority level. One way to implement this is to define P[k] as the priority level of the k th  producer, to define R[k] as 1 if the k th  producer has a request and 0 otherwise, and to define r as a round-robin pointer indicating that, within a priority level, the producers are given preference in the order r, r+1, r+2, . . . , K−1, 0, 1, . . . , r−1. With these definitions in place, a producer can be chosen as follows: 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 For n = N−1, ..., 0 
               
            
           
           
               
               
            
               
                   
                 For k=r, ... K−1 
               
            
           
           
               
               
            
               
                   
                 if P[k] == n and R[k]==1 then 
               
            
           
           
               
               
            
               
                   
                 pick k 
               
               
                   
                 goto Done 
               
            
           
           
               
               
            
               
                   
                 For k=0,...r−1 
               
            
           
           
               
               
            
               
                   
                 if P[k] == n and R[k]==1 then 
               
            
           
           
               
               
            
               
                   
                 pick k 
               
               
                   
                 goto Done 
               
            
           
           
               
               
            
               
                   
                 Done: 
               
               
                   
                   
               
            
           
         
       
     
     This can be implemented using a priority encoding approach using K-bit vectors, V1 and V2, in which the 0 th  bit is at the far left and the (K−1) th  bit is at the far right: 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 For n = N−1, ..., 0 
               
            
           
           
               
               
            
               
                   
                 V1[k] = 1 if k&gt;=r &amp;&amp; P[k] == n and R[k] 
               
               
                   
                 V1[k]=0 otherwise 
               
               
                   
                 If V1&lt;&gt; 0 then 
               
            
           
           
               
               
            
               
                   
                 pick k as leftmost bit position of a 1 in 
               
               
                   
                  V1, i.e. the smallest k such that V1[k] = 1 
               
               
                   
                 goto Done 
               
            
           
           
               
               
            
               
                   
                 V2[k] = 1 if k&lt;r &amp;&amp; P[k] == n and R[k] 
               
               
                   
                 V2[k]=0 otherwise 
               
               
                   
                 If V2 &lt;&gt; 0 then 
               
            
           
           
               
               
            
               
                   
                 pick k as leftmost bit position of a 1 
               
               
                   
                 in V2, i.e. the smallest k such that 
               
               
                   
                 V2[k] = 1 
               
               
                   
                 goto Done 
               
            
           
           
               
               
            
               
                   
                 Done: 
               
               
                   
                   
               
            
           
         
       
     
     Each of the “Pick k” operations is implemented using a fixed-priority arbiter. Using the above method requires N operations for the first conditional statement and another N operations for the second conditional statement. As a result, the foregoing implementation requires 2N operations. A hardware implementation of the foregoing method would therefore require circuitry for 2N fixed-priority arbiters. 
     In addition, the “goto Done” operation is implemented using another fixed-priority arbiter. As a result, the hardware implementation requires circuitry for a 2N-input fixed-priority arbiter to select among the results of the fixed-priority arbiters. 
     An equivalent operation requires only (N+1) operations instead of 2N operations. This equivalent operation can be expressed using a K-bit vector V as 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 V[k] = 1 if k&gt;=r &amp;&amp; P[k] == N−1 and R[k] 
               
               
                   
                 V[k] = 0 otherwise 
               
               
                   
                 If V&lt;&gt; 0 then 
               
            
           
           
               
               
            
               
                   
                 pick k as leftmost bit position of a 1 in V 
               
               
                   
                 goto Done 
               
            
           
           
               
               
            
               
                   
                 For = N−2, ..., 0 
               
            
           
           
               
               
            
               
                   
                 V[k] = 1 if k&lt;r &amp;&amp; P[k] == (n+1) and R[k] 
               
               
                   
                 V[k] = 1 if k&gt;=r &amp;&amp; P[k] == n and R[k] 
               
               
                   
                 V[k] = 0 otherwise 
               
               
                   
                 If V&lt;&gt; 0 then 
               
            
           
           
               
               
            
               
                   
                 pick k as leftmost bit position of a 1 in V 
               
               
                   
                 goto Done 
               
            
           
           
               
               
            
               
                   
                 V[k] = 1 if k&lt;r &amp;&amp; P[k] == 0 and R[k] 
               
               
                   
                 V[k] = 0 otherwise 
               
               
                   
                 If V&lt;&gt; 0 then 
               
            
           
           
               
               
            
               
                   
                 pick k as leftmost bit position of a 1 in V 
               
               
                   
                 goto Done 
               
            
           
           
               
               
            
               
                   
                 Done: 
               
               
                   
                   
               
            
           
         
       
     
     In the foregoing implementation, the for-loop requires N−1 operations. Finding the leftmost set-bit in the vector then requires two additional operations. This results in only N+1 operations. The hardware implementation of the foregoing procedure results in only (N+1) fixed-priority arbiters and one (N+1)-input fixed-priority arbiter. 
     An inverse weighted arbiter as described above is particularly useful in a massively parallel special-purpose supercomputer formed from a network of nodes, each of which has multiple cores on one chip that are linked by a high-performance tightly-coupled on-chip network. Such a data processing system, which can be used, for example, for simulation of molecular dynamics, is effectively a network of networks. 
       FIG. 5  shows a simulation volume  40  that is partitioned into simulation regions  42 , each of which contains a distribution of bodies, such as atoms or molecules. A molecular dynamics simulator  44  includes a network  46  that interconnects a large number of nodes  48 . Each node  48  is responsible for simulation of changes in position and velocity of bodies in a particular simulation region  42 . Such a simulator  44  is an example of a massively parallel special-purpose supercomputer as described above. In this example, a router  14  is associated with each one of the nodes  48 . Nodes adjacent to a particular node  48  would then correspond to some producers  20   a - c . Each node contains within it multiple cores an on-chip network interconnecting the cores. Thus, producers  20   a - c  can also correspond to neighboring cores on the on-chip network.