GB2216368A - Bus arbitration method and apparatus - Google Patents

Description

16368 BUS ARBITRATION METHOD AND APPARATUS

BACKGROUND OF THE TNVENTTON

1. Field of the Invention.

This invention relates to the field of methods for controlling access to a system bus by a number of 5 requesters in a computer system.

2. Prior Art.

Computer systems typically comprise several resources such as processor units, input/output controllers, memories, etc. which all share a common system bus for purposes of communication with one another. It is necessary to control access to the system bus to avoid allowing more than one resource access to the bus at one time.

In general, two techniques for controlling access to the system bus are known. In a first technique, a central point of control is utilized to control all system bus requests. A second technique distributes control of system bus requests, for example allowing resources on a single board to all be controlled by a single controller. In such a distributed system, all controllers must cooperate in granting access to avoid collisions on the bus.

In either case, a system bus arbitration scheme is designed to satisfy one or more of the following objectives: (1) minimize the amount of time required to service a request, (2) reduce use of system bus resources, and (3) allow for flexible priorities in servicing of system bus reqVests.

In one known method for controlling access to a system bus, the requester is allowed to make a request irregardless of whether the requested resource is busy. If the resource is busy, the system bus is tied up with the request until it can be serviced. Such a method consumes system bus resources while waiting for the request to be serviced.

One known alternative is to queue requests at the responders, thus freeing up the system bus. However, such a method requires additional circuitry at each resource to allow for storing request information in the queue and further suffers from finite queue sizes.

Therefore, it is desired to design a bus arbitration scheme which satisfies each of the above objectives and overcomes the problems of the prior art.

Known distributed systems for sharing a bus resource suffer from one or more problems when handing off the bus from one resource to another. Due to a variety of causes, systems suffer from clocks controlling access to system buses or other devices having some degree of clock skew between various ports. As such, several known systems allow the bus to be unused for a clock cycle between the bus being released -by one resource and being used by another. This insures bus contention will not occur between the two resources. However, such a method underutilizes the bus resource by allowing it to go unused for a clock cycle during the handoff from one resource to the next.

Another known method for dealing with bus contention in a distributed system is to design the 3 system such that clock skew is minimized between resources. Contention, to the extent it occurs is then ignored in these systems. However, such a method adds complexity to the design of the system circuitry.

A third known method of controlling bus contention utilizes multiple clocks on the bus which are skewed by a precise amount. One clock may be used for enabling and another clock is used for disabling. Such a method introduces problems of controlling multiple clocks with precise skews.

SUMMARY OF THE TNVENTTQN

The present invention discloses a bus arbitration scheme in which requesters request a resource only after detecting the resource is not busy. In the preferred embodiment of the present invention there are eighteen resources, sixteen memory resources, one 1/0 resource and one graphics resource. Each resource has associated with it a signal on the system bus denoting whether or not the resource is busy. The system comprises a plurality of arbiters, each coupled with one or two requesters. The requesters may determine from the signal whether or not a resource they wish to utilize is busy.

After a requester determines a resourcf! it wishes to request is not busy, the requester must then arbitrate for use of the bus. A request for the bus is made in one clock cycle to use the bus in the cycle following successful arbitration. If the request is not granted the requester continues to ask for the required bus until it is granted. In the preferred embodiment, arbitration is divided into two levels; global and local. Local arbitration determines which requester on a board has access to the local buses. Global arbitration determines which board has access to the system bus.

After a requester determines whether a resource is available for a transaction, the requester asserts a bus request. The arbiter determines which requester receives the local bus based on a set of priority rules.

In parallel with this determination a bus request is asserted on the system bus. The arbiter then samples all active system bus requests and determines whether the priority of its requester is highest over all active requests. If its requester does have the highest priority, the arbiter asserts a system bus grant to the requester. At the same time a busy signal is asserted by the arbiter for the requested resource until the resource is able to assert its own busy signal. This prevents other requesters from requesting the resource in the next clock cycles.

The present invention further discloses a method for controlling access to a bus when handing off access from one resource to another in a system using distributed control of the bus resource and a technique for preventing linked conflicts. It is an objective of the invention to prevent contention on the system bus while fully utilizing all available clock cycles on the bus. 20 In the preferred embodiment, a resource may utilize the system bus only when its bus enable signal (BMINE) is asserted. The BMINE signal may be asserted or deasserted only when a central enable line is deasserted. Access to the bus is controlled such that the bus may not be accessed by a resource unless both the BMINE and central enable lines are asserted.

RRTEF DESCRTPTTON OP THE DRAWINGS Figure I is a flow chart illustrating an arbitration method as may be utilized by the present invention.

Figure 2 is a timing diagram illustrating timing of bus requests and grants as may be utilized by the present invention.

Figure 3 is a block diagram illustrating an arbitration gate array as may be utilized by the present invention.

Figure 4 is a block diagram illustrating boards and arbitration gate arrays accessing a system bus as may be utilized by the present invention.

Figure 5 is a timing diagram illustrating timing signals for enabling bus access as may be utilized by the present invention.

Figure 6 is a schematic illustration of circuitry which may be utilized for controlling access to the bus by the present invention.

DETATT, QF.-Sr-RTPTTQN OF THE PRESENT TNVENTTON A bus arbitration method and apparatus is described. In the following description, numerous specific details are set forth such as pin numbers, priority levels, etc., in order to provide a thorough understanding of the present invention. It will be obvious, however., to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well known circuits, structures, and techniques have not been shown in detail in order not to unnecessarily obscure the present invention.

The present invention discloses a method and apparatus for sharing a common bus coupled with a plurality of resources by a plurality of requesters for those resources. 'In the preferred embodiment, there are eighteen resources: sixteen memory resources, one 1/0 resource and one graphics resource. The sixteen memory resources comprise sixteen interleaved memories (e.g., separate memories which may operate in parallel). It will, however, be obvious to one of ordinary skill in the art that other resource configurations may be supported without departing from the spirit of the present invention. For example, a system with multiple 1/0 resources or multiple graphics resources may be employed.

In the present invention, a requester requests a resource only when the resource is not busy. The requester is able to determine whether or not a resource 8 is busy by examining a busy signal associated with each resource. The signals for identifying whether a resource is busy in the preferred embodiment will be described in more detail in connection with Figure 3.

After a requester determines whether a particular resource is free, the requester arbitrates for use of a bus to communicate with the resource. The method used by the preferred embodiment for arbitrating use of buses is described by Figure 1.

10. First, a requester asserts a request to its arbitration gate array (AGA), block 10. The arbitration gate array is associated with a bus and may provide arbitration for one or two requesters. The arbitration gate array supports arbitration for both the system bus and, where necessary, arbitration for a local bus which may feed the system bus.

The arbitration gate array then accepts the request from the requester, block 11 and determines whether the requested resource will be available in two clock cycles, block 12. As will be seen in conjunction with Figure 2, if a request is made in the current clock cycle the earliest the resource will be required is in two clock cycles, one for arbitration and one for the bus transfer. Each resource negates its busy signal two clock cycles before it is ready to receive another request.

Assuming the resource will be available, the AGA determines which requester receives access to the local bus and generates a local bus grant signal to that requester, block 13. This is significant where multiple requesters share a local bus and two or more of them make a request in the same clock cycle. In parallel, a bus request is asserted on the system bus, block 14.

The AGA then samples all active system bus requests, block 15. Each AGA in the system is responsible for monitoring all active system bus requests in the same manner. The AGA which determines that its requester has the highest priority of any requester requesting the system bus is selected to receive the system bus in the next clock cycle, block 16.

The selected AGA then asserts a system bus grant to its requester, block 17. At the same time a busy signal is asserted by the AGA for the selected resource for the present clock cycle plus two clock cycles, block 18. This insures the resource appears busy to other requesters until such time as the resource is able to assert its own busy.

Figure 2 illustrates a timing diagram as may be representative of several signals of interest utilized by the present invention. The timing diagram illustrates a clock signal 26, a request signal from a requester 27, a local bus grant signal 28, a system bus grant signal 29, a bus enable (BMINE) signal 36, a local address bus signal 37, and a system bus address signal 38.

During a first clock cycle a request 20 is asserted by a requester. In this case, the AGA accepts the request and determines if the requested resource will be free in two clock cycles. The AGA also determines that 10 this requester is to receive the local bus either as a result of it having the highest priority of any requesters on the same board or it being the only requester on the board requesting the bus. The AGA then signals a local bus grant 21 for this request and asserts a system bus request (not shown). In this particular case, the system bus request is successful and a system bus grant signal is asserted 22. At the same time, address information is placed on the local bus 23 as a result of the local bus grant 21. As a result of the system bus grant, a BMINE signal is asserted by the AGA 24. The BMINE signal is used as one input to a tristate circuit for the requester. When the BMINE signal is asserted and a central enable (not shown) is asserted the resource has access to the system bus. The resource then puts address information on the system address bus 25.

Request number 5 illustrates a request in which a local bus grant is given to a request, however, the system bus grant is not given for several clock cycles. This may be due to the system bus being busy servicing other requesters which have higher priorities. A request 30 is asserted and local bus grants are given 31, 32 and 33. Requests 31 and 32 did not yield a system bus grant. Therefore, the AGA reasserts the system bus request until a system bus grant is obtained 34.

Request 6 illustrates a request which does not receive a local bus grant or a system bus grant on the first attempt. Request 40 and request 41 did not receive a local bus grant and were reasserted by the requester. Request 42 receives a local bus grant 43. However, the corresponding system bus request does not yield a system bus grant. Therefore, the system bus request is reasserted and a system bus grant 45 is received. A BMINE 46 is then asserted to the requester.

Figure 3 illustrates a arbitration gate array (AGA) 50 as may be utilized by the present invention. 54 pins of the arbitration gate array 50 are illustrated, however, the preferred embodiment of the present invention, in fact, utilizes a 100 pin array. It will be appreciated by one skilled in the art that the remaining pins comprise such pins as reset, Vec, clock and other pins which are not critical to an understanding of the present invention.

When a requester in the system intends to arbitrate for access to the system bus it asserts its local bus request pin, 60 and 68. Each AGA in the preferred embodiment may service up to two requesters. As illustrated by Figure 3, local bus request pin 60 is associated with requester 0 and local bus request pin 68 is associated with requester 1. A signal on local bus request pins 60 and 68 indicates a valid request is being asserted by requester 0 and requester 1, respectively.

A requester requests access to the buses by asserting its request type on the request type pins 48 and 54. Each requester requires separate request type pins. As illustrated by Figure 3, pins 48 are associated with requester 0 and pins 54 are associated - 12 with requester 1. There are three request type pins 48 and 54 associated with each requester. Their signals are interpreted as shown in the table below.

Request Type Type 0 0 0 NONE 0 0 1 GRAPHICS 1 0 1/0 0 1 1 MEMORY 1 0 0 TEST 1 0 1 RESERVED 1 1 0 LOCAL 1 1 1 RETURN If the request type is a memory request (request type = 011) the requester also provides an address for the particular memory interleave address pins 49 and 58.

The preferred embodiment of the present invention utilizes a memory with sixteen interleaves. There are four address pins 49 and 58 associated with each requester to allow for addressing of the sixteen interleaves.

Read request pin 47 and 53 specifies if the access is a read or write access. In the preferred embodiment if this pin is asserted by a requester, a read is being requested.

The AGA utilizes read busy pin 52 as input when determining whether the bus should be granted to a requester initiating a write request. Read busy pin 52 indicates the data bus will be busy with returning read data in two clock cycles following the cycle in which it - 13 is asserted. A requester initiating a write request will be denied access to the bus if this signal is asserted to prevent collision of data on the bus. The memory subsystem controls the signal from the read busy pin 52, forcing the 1/0 and graphics subsystems to arbitrate for the bus to return data.

The arbitration gate array determines if the resource is busy by examining the appropriate busy pin. There are 16 interleave busy pins 55 corresponding to each of the memory interleaves of the preferred embodimebt. The 1/0 busy pin 56 indicates whether the 1/0 subsystem is busy. The graphics busy pin 57 indicates whether the graphics subsystem is busy.

Each of the busy pins 55, 56 and 57 are both input and output pins. The busy pins 55, 56 and 57 are used as inputs to the AGA when the AGA determines whether a particular resource is busy. The AGA will assert (output) a signal for three clock cycles on the appropriate busy pin 55, 56 and 57 when it has arbitrated successfully for the bus. In the preferred embodiment, it is necessary for the AGA to assert the signal for three cycles as the resource will not begin asserting the signal for itself until after three cycles have elapsed.

If the resource will be available, a bus request is asserted on one of pins 51. There are eight bus request pins, one for each requester on the bus in the preferred embodiment. As discussed previously, the AGA 50 asserts the appropriate busy pin after granting the resource to a requester for three clock cycles. The resource is - 14then responsible for asserting the correct busy signal until it completes the request and is available for the next request. As discussed above, the resource actually negates the busy pin two clock cycles before it is ready to receive another request since the soonest a request will arrive at the resource is in two clock cycles. This allows maximal overlap.

The arbitration gate array determines which requester is to be granted access to the local bus based on the priorities of each local requester. The requester with the highest priority is granted access to the local bus by the AGA 50 asserting the appropriate local bus grant pin 61 and 69. There are two local bus grant pins 61 and 69 on each AGA, one for each requester which may be coupled with and controlled by the AGA 50.

The AGA 50 samples all active system bus requests and determines whether its requester has the highest priority. If it does, a global bus grant is asserted on the global bus grant pin 62. A BMINE signal is also asserted on pin 63 to allow access to the system bus as discussed in conjunction with Figure 1.

In the preferred embodiment of the present invention, simultaneous requests for the system bus are handled on a priority basis. There are eight priority levels for accessing the system, each priority level associated with the bus request pins 51. The priority levels are assigned as level 8 being a spare priority, level 7 for 1/0 initiated requests, level 6 for graphics initiated requests, levels 4 and 5 for integer processor units (IPU) requests, levels 2 and 3 for floating point processors unit (FPU) request and level 1 is a spare priority.

Priority level for processors in the system may be rotated on a round robin basis. The preferred embodiment allows for two modes of round robin priority switching. The selection of a mode is controlled by round robin pin 65. If this signal 65 is asserted, priority is rotated among levels 2 through 5. If this signal 65 is deasserted, priority is toggled between level 4 and 5 and between level 2 and 3. Levels 1, 6, 7 and 8 remain at fixed priorities.

A global arbitration priority pin 83 signals round robin priority between boards. If this signal is zero, processor board 0 will have priority in arbitration. if the signal is one, processor board 1 will have priority. The global arbitration priority pin 83 is toggled every four clock cycles.

Board arbitration priority signal 84 signals priority in a round robin fashion between AGAs on the same board. The board arbitration priority signal 84 is toggled to the other whenever a request is serviced.

Internal arbitration signal 85 signals priority in a round robin fashion between two requesters controlled by the same AGA. When this signal 85 is a zero, requester 0 is higher priority, if it is a one, requester I is higher priority. The signal 85 is toggled to the other requester whenever a request is serviced.

Due to the randomness introduced by changing relative priority levels among the various requesters in - 16 the system, problems of linked conflicts are avoided. A clock signal is input to the AGA 50 as pin 66. A bus enable signal is input as pin 67. The bus enable signal 67 controls bus enables for all boards in the system and 5 is used to generate the BMINE signal for enable control.

Figure 4 illustrates a bus 70 coupled with a processor board 71, a graphics board 77, an 1/0 board 79 and a memory 81 as may be utilized by the present invention. In the preferred embodiment the processor board 71 contains four AGAs 72, 73, 74 and 75. One of the AGAs 72 may be associated with an integer processing unit (IPU) on the processor board, one of the AGAs 73 may be for a floating point processor unit store pipe and two AGAs 74 and 75 may be for floating point process unit (FPU) load pipes. The graphics board 77 has a single AGA 78. The 1/0 board 79 also has a single AGA 80.

Figures 5 and 6 disclose, in more detail, the method and apparatus for handing access to the bus from one requester to another. It is desired to hand access from one resource to another resource while preventing bus contention problems during the handoff.

Figure 5 illustrates a timing diagram showing access to the bus being handed from a first requester controlled by BMINEI signal 91 to a second requester controlled by BMINE2 signal 92. The second requester retains control of the bus for one clock cycle and control is handed back to the first requester in the next clock cycle.

- 17 A bus clock signal 90 provides timing for the bus.

An enable signal 93 is deasserted at time 97 in response to the leading edge of the clock signal which occurred at time 96. BMINEI 91 is deasserted at time 98 and BMINE2 92 is asserted at time 99. The BMINE signals 91 and 92 only change states after the enable signal 93 is deassqrted. Enable signal 93 is reasserted at time 100.

Eable signal 93 is provided to all boards in the system and is controlled by a central clock generation circuit. It is generated to be deasserted after the leading edge of the bus clock and is asserted after allowing for enough time to compensate for clock skew in the system.

At time 101, a second leading edge of clock signal 90 is generated. The enable signal 93 is deasserted at time 102. At time 103 BMINE1 signal 91 is asserted.

Between time 102 and-103, both BMINE1 signal 91 and BMINE2 signal 92 are asserted. Therefore during this time period, both requester 1 and requester 2 may access the system bus absent some additional control. As described above, all access to the system bus is disallowed during time periods when enable signal 93 is deasserted, providing such additional control.

At time 103 BMINE2 signal 92 is deasserted and at time 104 enable signal 105 is asserted. By utilizing a central enable control signal 93, bus contention is avoided during time period 102 to 103.

Figure 6 further illustrates circuitry utilized to control access to the system bus. BMINE signal line 110 and enable signal line 111 are AND'ed together by - 18 circuit 115. only when both BMINE signal line 110 and enable signal line 111 are high will tristate circuit 113 allow line 114 to access bus 112.

Thus, a bus arbitration method and apparatus is disclosed which allows requesters to detect whether a resolirce is busy bifore making a request and allows sing16 cycle arbitration of a bus.

1 CLATMS I 1. A method for controlling access to resources in a computer system comprising the steps of: a requester asserting a request for service by a resource; a determination being made whether said resource is available for said request; if said resource is available, said requester being given access to said resource; whereby, said requester receives access to said resource only if said resource is available to service said request.

Claims (1)

1. 2. The method, as recited by Claim 1, further comprising the step of

   determining which of a plurality of requesters is to be granted access to said resource.

   3. A method, as recited by Claim 2, wherein said determination is based on predetermined priorities assigned to said requesters.

   4. The method, as recited by Claim 3, wherein said requesters comprise input/output (1/0) processors, graphics processors, and central processing units.

   -il 5. The method, as recited by Claim 4, wherein said resources comprise an I/0 processor, a graphics processor and a plurality of memory interleaves.

   6. The method, as recited by Claim 5, wherein: said requester asserts said request to an arbitration circuit responsible for determining whether said resource is available for servicing said request and for determining whether said requester has the highest priority.

   7. A method, as recited by Claim 6, wherein access is granted to a requester by a bus grant signal being asserted by said arbitration circuit.

   8. A method for controlling access to a bus in a computer system, comprising the steps of:

   a request being asserted by a requester for service by a resource; an arbitration circuit associated with said requester receiving said request; said arbitration circuit determining whether said resource is available to service said request; if said resource is available for said request:

   (a) said arbitration circuit asserting a bus request; (b) said arbitration circuit sampling all active bus requests in said computer system to determine if its requesters priority is the highest of all active requests; I (c) said arbitration circuit granting access to said requester to use a system bus if said requester has the highest priority; whereby, said requester receives access to said resource only if said resource is available to service said request and said requester has the highest priority of all active requests in the computer system.

   9. A method, as recited by Claim 8, wherein said requesters comprise an 1/0 processor, a graphics processor and a plurality of central processing units.

   10. The method, as recited by Claim 9, wherein said resources comprise an 1/0 processor, a graphics processor and a plurality of interleaved memories.

   11. A method, as recited by Claim 8, wherein said computer system comprises a plurality of arbitration circuits.

   12. A method, as recited in Claim 11, wherein each of said arbitration circuits may arbitrate for a plurality of requesters.

   13. A method, as recited in Claim 12, further comprising the step of each of said arbitration circuits determining which requester associated with said arbitration circuit has the highest priority..

   14. A method, as recited by Claim 13, further comprising the step of rotating priority levels among requesters assigned to an arbitration circuit after each successful arbitration for a resource.

   15. An apparatus for controlling access to resources in a computer system, comprising:

   a resource; a plurality of requesters for requesting services from said resource; first means for determining whether said resource is available to service a request coupled with said resource and said requesters; whereby, said requesters may assert requests be serviced by said resource when said resource is available to service said request.

   16. An apparatus, as recited by Claim 15, further comprising at least one second means for arbitrating which requester may assert its request, said second means coupled with each of said requesters.

   17. An apparatus, as recited by Claim 16, wherein each of said second means may be coupled with a plurality of requesters.

   18. An apparatus, as recited by Claim 17, wherein said re'source may be one of an input/output (1/0) multiple processor, a multiple graphics processor or a memory interleave.

   23 19. An apparatus, as recited by Claim 18, wherein said requester may be one of an 1/0 processor, a graphics processor, a central processing unit or a floating point processor unit.

   20. An apparatus, as recited by Claim 19, further comprising a bus for coupling said resource with said requesters.

   21. In an apparatus for controlling access to resources in a computer system, said computer system comprising at least one resource and a plurality of requesters, an improvement comprising:

   a first means coupled with said resource and said requesters for determining whether said resource is available to service said request; at least one second means coupled with each of said requesters for arbitrating which of said requesters may assert its request; whereby said requesters may only assert requests to be serviced by said resource when said resource is available to service said request.

   22. An improvement, as recited by Claim 21, further comprising a bus for coupling said resource with said requesters.

   23. An improvement, as recited by Claim 21, wherein source may be one of an input/output (1/0) 24 processor, a graphics processor, a central processing unit or a floating point processor unit.

   24. An improvement, as recited by Claim 21, wherein said requester may be one of an 1/0 processor, a graphics processor, a central processing unit or a floating point processor unit.

   25. A circuit for controlling access to a bus by a plurality of requesters in a computer system, comprising: a first signal means for controlling access to said bus, said first signal means coupled with a first of said plurality of requesters; a second signal means, said second signal means coupled with each of said plurality of requesters for providing common control signal for accessing said bus; a circuit means for allowing said first of said plurality of requesters to access said bus, said circuit means coupled with said first signal means and said second signal means said circuit means allowing access to said bus when a signal is asserted on both said first signal means and said second signal means, said circuit. means not allowing access to said bus when a signal is not asserted on said first signal means or a signal is not asserted on said second signal means; whereby, access to a bus is controlled by a local and a global control signal.

   - 26. A circuit, as recited by claim 25, wherein said first signal means may only change state when said second signal means is deasserted.

   27. A circuit, as recited by Claim 26, further comprising a timing signal means, said timing signals means providing clock pulses, wherein said second signal means is deasserted for a predetermined period of time after the leading edge of each clock pulse prevents bus conflict.

   28. A method for controlling access to a bus by a plurality of requesters in a computer system comprising the steps of: determining which of said plurality of requesters shall be granted access to said bus; granting access to a selected requester; causing a change in state of a first signal means, said first signal means being supplied to each of said plurality of requesters; causing a change in state of a second signal means, said change in state of said second signal means occurring after said change in state of said first signal means; resuming the original state of said first signal means; said selected requester accessing said bus after said resuming the original state of said first signal means.

   29. In a computer system comprising a plurality of resources and a plurality of requesters for requesting service from said resources, a method comprising the steps of:

   a first of said plurality of requesters asserting a first request for service by a first of said resources; a determination being made whether said resource is available for said first request, said determination based on a priority assigned to said first requester:

   - if said resource is available, said requester being given access to said resource; said first requester's priority being changed under a set of predetermined conditions.

   30. The method, as recited by Claim 30, wherein said priority is changed after a predetermined number of clock cycles.

   31. The method, as recited by Claim 31, wherein said predetermined number is four.

   32. A method for controlling access to resources in a c(nputer system substantially as hereinbefore described.

   33. An apparatus for controlling access to resources in a canputer system substantially as hereinbefore described with reference to the accanpanying drawings.

   Published 1989 atThe Patent Offioe, State House, 68,71 High Holborn, London WC1R 4TP. Further copies maybe obtainedfrom The Patentom". Sales Branch, St Mary Cray, Orpington, Kent BP-5 3RD. Printed by Multiplex techniques ltd, St Mary Cray, Kent, Con. 1/87