Abstract:
Arbitration requests are received that belong to respective bus types. Each of the types is associated with a programmed value representing a potential number of times that requests of that type may win arbitration events that occur in a given time period. For at least some arbitration events that occur in the given time period, the invention updates a counter value for at least some of the types, the counter value for each of the types being set initially to the programmed value, and chooses a winning type in each of the arbitration events based on at least some of the counter values of the types of requests that are contending in the arbitration event.

Description:
BACKGROUND 
     This invention relates to arbitrating requests on computer buses. 
     Computer buses carry data from one part of a computer to another. As shown in FIG. 1, input/output (I/O) buses  12  carry data from I/O units  10  such as keyboards, disk drives, and graphics devices. The I/O bus  12 , e.g., a peripheral component interconnect (PCI) bus, carries the data through a bridge  14  to a system bus  16 . The system bus  16  carries data and processing requests to and from the central processing unit (CPU)  18  and random access memory (RAM)  20 . 
     Instead of traveling on an I/O bus  12 , graphics data and processing requests may travel on a special channel, e.g., an accelerated graphics port (AGP)  22 . AGP  22  carries data and processing requests, in the order it receives it, from a graphics device  24  directly to the CPU  18 . 
     SUMMARY 
     In general, in one aspect, the invention features receiving arbitration requests belonging to respective bus types and associating with each of the types a programmed value representing a potential number of times that requests of that type may win arbitration events that occur in a given time period. For at least some arbitration events that occur in the given time period, the invention updates a counter value for at least some of the types, the counter value for each of the types being set initially to the programmed value, and chooses a winning type in each of the arbitration events based on at least some of the counter values of the types of requests that are contending in the arbitration event. 
     Other advantages and features will become apparent from the following description and from the claims. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of a computer system. 
     FIG. 2 is a diagram of an arbitration system in accordance with an implementation of the invention. 
     FIG. 3 is a timeline of an arbitration system. 
     FIG. 4 is a chart of results from an arbitration system. 
     FIG. 5 is a block diagram of a computer system. 
     FIG. 6 is a table of registers. 
    
    
     DESCRIPTION 
     In a specific example shown in FIG. 2, an arbitration scheme  30  helps set the order in which various streams of I/O unit processing requests  46   a-f  associated with respective arbiter control registers  32   a-f  are permitted to gain access to a buffer unit (B-unit)  44  through which the requests are served by a processor  48 . The arbiter control registers  32   a-f  hold integer weight values which indicate the potential number of times that requests belonging to their respective streams of requests  46   a-f  may gain access to the B-unit  44  in a given time period. As shown in FIG. 3, in each of a sequence of arbitration events  50 , the scheme  30  chooses one arbiter control register  32   a-f  associated with an active type of request  46   a-f . A type of request  46   a-f  is active if there is at least one request of that type that needs processing. An active request  46   a-f  of the type associated with the winning arbiter control register  32   a-f  is put in a pipeline in the arbiter  30  to await access to the B-unit  44 , where it may be processed. 
     As shown in FIG. 4, the arbitration scheme  30  randomly chooses one arbiter control register  32   a-f  in each arbitration event  50   a ,  50   b ,  50   c , etc. The winner is denoted by an “X” in a “Winner” row  76  for each column (each arbitration event  50 ) in each time slice  52   a ,  52   b ,  52   c , etc. The winner of each arbitration event  50  is associated with a type of active request  46   a-f , as indicated in “Requests Remaining” rows  68 . 
     For example, if no eligible arbiter control register  32   a-f  has a non-zero current weight value, shown in “Current Weight Value” rows  70 , the arbiter control register  32   a-f  ranked highest in a fixed or programmed priority scheme wins arbitration. A preferred fixed priority scheme is, from highest to lowest priority, Hublink_A Isochronous (register  32   f ), AGP High Priority (register  32   b ), Hublink_B Asynchronous (register  32   e ), AGP Low Priority (register  32   c ), Hublink_A Asynchronous (register  32   d ), and AGP PCI (register  32   a ). For example, in arbitration events  50   a-d , the winning arbiter control registers  32   a-f  each held a weight value of zero, shown in their respective rows  70 , but won arbitration under this preferred priority scheme. 
     The B-unit  44  may reject the request  46   a-f  it receives from the pipeline in a skipping action  38 , thereby skipping that request  46   a-f  entirely or swapping it with the next request  46   a-f  in the pipeline. Swapping can occur only if the two requests  46   a-f  are of different types. After each time slice, the current weight values (in rows  70 ) in the arbiter control registers  32   a-f  are reset to their pre-programmed values (in rows  72 ), the time slice value (in row  74 ) in the time slice register  36  resets to zero, and the next time slice begins. Any requests  46   a-f  remaining in rows  68  at the end of a time slice, e.g., time slice  52   a , carry over to the next time slice, e.g., time slice  52   b , and are added to any new requests  46   a-f.    
     As shown in FIG. 5, the arbitration scheme  30  is part of an arbiter  34  located in a chipset  54 , e.g., a graphics device  24  (FIG.  1 ). Generally, the chipset  54  provides the processor  48  (e.g., the CPU  18  via the B-unit  44 ) with data and processing requests traveling on buses such as the system bus  16 , the PCI bus  56 , and the AGP  22 . The chipset  54  includes three hubs (connection points between devices)  58 ,  60 ,  62 . The memory controller hub (MCH)  58  provides an interface for the processor  48 , system memory  20 , and graphics data on the AGP  22 . The I/O controller hub (ICH)  60  handles data and processing requests coming from the I/O units  10 . A hub interface A  64  connects the MCH  58  and the ICH  60 . The firmware hub (FWH)  62  stores system and video BIOS (basic I/O system) software containing instructions on how to perform I/O functions and a random number generator (hardware that generates random numbers for use in, for example, encryption). 
     The arbiter  34  includes one thirty-two bit register, seen in FIG. 6, containing the three-bit or four-bit arbiter control registers  32   a-f  in the read/write bits zero to eighteen. Bits zero to two contain arbiter control register  32   a , the AGP/PCI register, holding the weight value for requests  46   a , requests from the AGP  22  using PCI  56  semantics. Bits three to five contain arbiter control register  32   d , the Hub_Interface_A Asynchronous register, holding the weight value for requests  46   e , asynchronous requests (ones not occurring at regular intervals) on the hub interface A  64 . Bits six to eight contain arbiter control register  32   c , the AGP Low Priority register, holding the weight value for requests  46   c , low priority requests on the AGP  22 . Bits nine to eleven contain arbiter control register  32   e , the Hub_Interface_B Asynchronous register, holding the weight value for requests  46   e , asynchronous requests from the MCH  58 . Bits twelve to fourteen contain arbiter control register  32   f , the Hub_Interface_A Isochronous register, holding the weight value for requests  46   f , isochronous requests (ones occurring at regular intervals) on the hub interface A  64 . Bits fifteen to eighteen contain arbiter control register  32   b , the AGP High Priority register, holding the weight value for requests  46   b , high priority requests on the AGP  22 . Read/write bits nineteen to twenty-four contain a time slice register  36 , holding a value equal to the total number of arbitration events  50  that have occurred in the instant time slice. That number is the sum of the weight values in the arbiter control registers  32   a-f  (the total number of arbitration events  50  dedicated for I/O units  10 ). Bits twenty-five to thirty-one are read-only reserved bits. 
     Before arbitration begins (e.g., at time slice  52   a ), each arbiter control register  32   a-f  is pre-programmed with an integer weight value in its three-bit or four-bit field (multiple registers may have the same value). For example, arbiter control register  32   f  could be given a value of seven by programming “ 111 ” into its field. In the example in FIG. 4, arbiter control register  32   a  has a pre-programmed weight value of zero, arbiter control registers  32   c-d  each have a pre-programmed weight value of one, arbiter control register  32   e  has a pre-programmed weight value of two, and arbiter control registers  32   b  and  32   f  each have a pre-programmed weight value of three, for a total of ten arbitration events  50  per time slice. The pre-programmed weight values in the arbiter control registers  32   a-f  represent their (and their associated requests  46   a-f ) potential winning percentages in each time slice. So in the FIG. 4 example, arbiter control registers  32   c-d  each potentially have a one-tenth chance of winning an arbitration event  50  in each time slice. Not all arbiter control registers  32   a-f  may be associated with active requests  46   a-f  in every arbitration event  50 , so their actual winning percentages may be higher or lower since each arbitration event  50  always chooses one arbiter control register  32   a-f . For example, in time slice  52   b , register  32   c  won three arbitration events  50  despite its pre-programmed weight value of two (row  72 ), while register  32   e  won no arbitration events  50  despite its pre-programmed weight value of one (row  72 ). 
     During arbitration, the current weight values of arbiter control registers  32   a-f  are used because weight values can change from one arbitration event  50  to the next. Each arbiter control register  32   a-f  begins at its pre-programmed weight value. The value in time slice register  36  begins at zero, incrementing by one after each arbitration event  50 . When the value in time slice register  36  reaches the sum of all the pre-programmed weight values in arbiter control registers  32   a-f , the current time slice expires. At the end of each arbitration event  50 , the current weight value in the winning arbiter control register  32   a-f  decreases by one, never falling below zero, indicating its win and decreasing its chances of winning future arbitration events  50  during the same time slice. 
     Other embodiments are within the scope of the following claims.