Abstract:
A modification of rank priority arbitration for access to computer system resources through a shared pipeline that provides more equitable arbitration by allowing a higher ranked request access to the shared resource ahead of a lower ranked requester only one time. If multiple requests are active at the same time, the rank priority will first select the highest priority active request and grant it access to the resource. It will also set a ‘blocking latch’ to prevent that higher priority request from re-gaining access to the resource until the rest of the outstanding lower priority active requesters have had a chance to access the resource.

Description:
FIELD AND BACKGROUND OF INVENTION  
       [0001]    This invention related to a computer system design and particularly to shared pipeline request fairness algorithms. 
         [0002]    Cycle time in high end multiprocessor systems continues to decrease as technology advances. However, the number of requests sharing a resource is increasing because today&#39;s systems are including higher numbers of active processors and IO requestors. Additionally, more and more logic is being moved onto a single chip. This combination requires new priority mechanisms that take up less physical space, consume less power, simply design and chip wiring and that minimize the number of critical timing paths, while maintaining a sufficiently robust priority mechanism to handle an increased number of requesters. 
         [0003]    Traditionally, the least physically demanding scheme has been basic rank priority. In this scheme, all the requestors waiting to use a resource are assigned a rank order, and are only allowed access to the resource if no higher ranking requests are present. While the basic rank priority scheme is efficient from a physical design point of view (it uses fewer latches and less silicon) than more complicated schemes, logically it is not a very fair algorithm. The lower ranked requesters may be continually and indefinitely blocked by a plurality of higher ranked requesters. The Least Recently Used (LRU) priority scheme is a more ‘fair’ algorithm, but it requires many latches and increases the number of critical paths and priority latency. One prior art priority scheme is taught in Shefer et al U.S. Pat. No. 6,119,188, to which the interested reader is referred should more detailed information be desired. 
       SUMMARY OF THE INVENTION 
       [0004]    The shortcomings of the prior art are overcome and additional advantages are provided through the provision of an arbitration scheme that fairly prioritizes requests for use of a shared resource whole minimizing the amount of latches, combinational logic and critical timing paths. This invention is a modification of rank priority that provides more equitable arbitration by allowing a higher ranked request access to the shared resource ahead of a lower ranked requester only one time. If multiple requests are active at the same time, the rank priority will first select the highest priority active request and grant it access to the resource. It will also set a ‘blocking latch’ to prevent that higher priority request from regaining access to the resource until the rest of the outstanding lower priority active requesters have had a chance to access the resource. 
         [0005]    In addition, it solves the problem of having to meet cycle time with arbitration among a large number of requesters in one cycle by distributing the prioritizing logic across two cycles while maintaining the integrity of the arbitration. 
         [0006]    System and computer program products corresponding to the above-summarized methods are also described and claimed herein. 
         [0007]    Additional features and advantages are realized through the techniques of the present invention. Other Embodiments and aspects of the invention are described in detail herein and are considered a part of the claimed invention. For a better understanding of the invention with advantages and features, refer to the description and to the drawings. 
     
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         [0008]    Some of the purposes of the invention have being stated, others will appear as the description proceeds, when taken in connection with the accompanying drawings, in which: 
           [0009]      FIG. 1  illustrates the gate-level implementation of the blocking rank scheme&#39;s first cycle; 
           [0010]      FIG. 2  illustrates the gate-level implementation of the blocking rank scheme&#39;s second cycle; 
           [0011]      FIG. 3  illustrates an example of the present invention, showing the priority selection method with three independent requestors, focusing specifically on the setting and resetting of the block latches; 
           [0012]      FIG. 4  illustrates the timing of the blocking rank latch settings in relation to a resource grant; and 
           [0013]      FIG. 5  illustrates a computer readable media bearing program instructions implementing the present invention. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0014]    While the present invention will be described more fully hereinafter with reference to the accompanying drawings, in which a preferred embodiment of the present invention is shown, it is to be understood at the outset of the description which follows that persons of skill in the appropriate arts may modify the invention here described while still achieving the favorable results of the invention. Accordingly, the description which follows is to be understood as being a broad, teaching disclosure directed to persons of skill in the appropriate arts, and not as limiting upon the present invention. 
         [0015]    Turning now to the drawings in greater detail,  FIG. 1  and  FIG. 2  show how a large number of requestors can be divided into a number of groups with a smaller number of requesters within each group. Additionally, these two figures show how the arbitration logic is performed across two logical cycles.  FIG. 1  shows the ‘first level’ portion of the arbitration logic, which takes place in the first logical cycle.  FIG. 2  shows the second ‘second level’ portion of the arbitration which takes place in the second logical cycle. 
         [0016]      FIG. 1  shows the first level blocking rank arbitration taking place in parallel for a variable number of requester groups  170 ,  171 ,  172  with each group having a variable number of requesters  101 ,  102 ,  103 ,  104 . This is the within-group arbitration. All the within-group takes place in parallel to all the other groups&#39; within group arbitration. 
         [0017]    There is one blocking rank latch for each requester latch. The blocking latches are all set to ‘0’ initially. In  FIG. 1 , blocking rank latch Block A  111  is the blocking rank latch for Request A  101 . Before being presented to the rest of the arbitration logic  140 , the request signal  101  is gated with the block signal  111  as shown by the logic gates in block  121 . In this way, the request will not appear active to the remaining arbitration logic  140  if the block latch  111  is active. This gating scheme is repeated for the other requests in the same first level arbitration group. Requests  102 ,  103 , and  104  are grated with blocking rank latches  112 ,  113 , and  114 , respectively and provide inputs to the downstream priority logic  140  of  122 ,  123 ,  124 , respectively. Hence, when all the blocking rank latches are set to ‘0’ the logic behaves like basic rank priority. 
         [0018]    When one or more first cycle requests become active, the rank priority will select a request to be presented to the second level of priority. The priority logic also outputs a set of mutually exclusive select lines  131 ,  132 ,  133 ,  134 , one select output corresponding to each requester input and a first level request signal which is active if any of the requests gated with the blocking latch are active. As  140  shows,  101  is the highest ranking requester, thus if its block latch  111  is not active, its first level select latch  131  will be set. Request  102  is the second highest ranking requester, thus if its block latch is not active and there is no gated higher ranking request active from  121 , the corresponding first level select latch  122  will be set. Similarly, request  103  is the third highest ranking requester, thus if its block latch  113  is not active and there is not gated higher ranking request from  121  or  122 , the corresponding first level select latch  123  will be set. 
         [0019]    This scheme continues for as many requesters as there are in the group, with the lowest ranked requester  104  only having it&#39;s select latch  124  set if no higher number gated requests are active. Due to the ‘OR’ function that takes place across all the select lines  150 , if any of the output lines from the request gating logic  121 ,  122 ,  123 , or  124  are active, the Group 1 request latch  151  will be set. This latch will be active in the following cycle  160 . Each parallel first level priority group&#39;s  170 ,  171 ,  172  winning request is latched  151  and presented to the second level blocking rank priority logic in the next cycle  150 . The select lines are used to multiplex the data accompanying the request and stage this data to the next cycle for presentation to the second level priority mutliplexing. 
         [0020]      FIG. 2  shows the second level blocking rank arbitration taking place for a variable number or requesters. At the second level, the winning request from each first level priority station  201 ,  202 ,  203 ,  204  vies for priority to access the shared pipeline  251 . Similar to the first level priority arbitration, there is one blocking rank latch for each second level requester, and all the blocking rank latches are set to ‘0’ initially.  FIG. 2 , blocking rank latch  211  is the block rank latch for request  201 . Before presented to the rest of the arbitration logic  240 , the request signal  201  is gated with the block signal  211  as shown by the logic gates in block  221 . In this way, the request will not appear active to the remaining arbitration  240  if the block latch  211  is active. This gating scheme is repeated for the other second level priority requesters: requests  202 ,  203  and  204  are gated with blocking rank latches  212 ,  213  and  214 , respectively and provide inputs to the downstream priority logic  240  of  222 ,  223 ,  224 , respectively. 
         [0021]    When one or more gated second cycle requests become active  221 ,  222 ,  223  or  224 , the rank priority  240  will select a request to be presented to the shared pipeline. The second level priority logic outputs a set of mutually exclusive select lines  231 ,  232 ,  233 ,  234 , one select output corresponding to each requester input and a final request signal which is active if any of the second level requests gated with the blocking latch  221 ,  222 ,  223  or  224  are active. The arbitration scheme at the second level is identical to that at the first level, although the actual number of requesters may vary. 
         [0022]    This scheme continues for as many requesters for as many requesters as there are in the group, with the lowest ranked requester  204  only having it&#39;s select latch  224  set if no higher number gated requests  221 ,  222  or  223  are active. Due to the ‘OR’ function that takes place across all the select lines  250 , if any of the output lines from the request gating logic  221 ,  222 ,  223  or  224  are active, the final request latch  251  will be set. The select lines are used to multiplex the data accompanying the request and present this data to the shared pipeline. 
         [0023]      FIG. 3  is an example showing the priority selection method for the first level of priority with three independent requesters and the controls for setting and resetting of the blocking latches. The priority selection is done in the same manner as shown in  FIG. 1  at  140 . If the request is selected by the second level of priority, this is reported back to the first level via a grant signal  350 . When the grant signal is asserted indicating the request was accepted by the second level of the priority logic, the selected request is gated with the grant  351 ,  352 ,  353  and will then set its block indication  111 ,  112 ,  113 . If this is the second stage of priority, then there is no external grant signal and the select signals  131 ,  132 ,  133  may be used to directly set the block indication  111 ,  112 ,  113 . After this point, future requests by the selected requester will be blocked from being included in the priority selection  121 ,  122 ,  123 , thus creating an opportunity for lower ranked requests to be selected by the priority logic. As long as a request exists for the priority logic to select  330 , the block indication for previously granted requests must be held  361 ,  362 ,  262  to allow lower ranked requests to be selected. When there are no longer any requests available to be selected  121 ,  122 ,  123 , all requesters had the opportunity to be satisfied, and all blocking  111 ,  112 ,  113  may be released. 
         [0024]      FIG. 4  demonstrates the timing relationship between an initial request to the first level of the arbitration logic  400  and the block indication being set due to successfully gaining access to the shared resource  405 . The request to the first level of arbitration is selected  400  and then staged to the second level  401 . When the second level of arbitration the selects the request  402 , it then causes a blocking indication for the second level  403  to be set, which prevents the same request from being selected multiple times. The results of the second level of arbitration are forwarded to the first level one cycle later  404 , and this indication is used to set the first level arbitration block  405 . 
         [0025]    The capabilities of the present invention can be implemented in software, firmware, hardware or some combination thereof. 
         [0026]    As one example, one or more aspects of the present invention can be included in an article of manufacture (e.g., one or more computer program products) having, for instance, computer usable media. The media has embodied therein, for instance, computer readable program code means for providing and facilitating the capabilities of the present invention. The article of manufacture can be included as a part of a computer system or sold separately. Additionally, at least one program storage device readable by a machine, tangibly embodying at least one program of instructions executable by the machine to perform the capabilities of the present invention can be provided. 
         [0027]      FIG. 5  shows a computer readable medium, in the form of an optical disk  500 , which carries computer executable code stored on the media accessibly to and executable on a computer system for implementing this invention. While here shown for purposes of illustration, it will be appreciated that the media may be an optical disk, a magnetic disk, a signal passed to the system, or some other form know to those of skill in the art. What is significant is that the appropriate instructions are produced and then provided to be deployed to and executed on a computer system which has a plurality of priority setting logic elements which controllably pass requests for access to computer system resources to a shared pipeline as contemplated here. 
         [0028]    The flow diagrams depicted herein are just examples. There may be many variations to these diagrams or the steps (or operations) described therein without departing from the spirit of the invention. For instance, the steps may be performed in a differing order, or steps may be added, deleted or modified. All of these variations are considered a part of the claimed invention. 
         [0029]    While the preferred embodiment to the invention has been described, it will be understood that those skilled in the art, both now and in the future, may make various improvements and enhancements which fall within the scope of the claims which follow. Although specific terms are used, the description thus given uses terminology in a generic and descriptive sense only and not for purposes of limitation.