Method and apparatus for avoiding data bus grant starvation in a non-fair, prioritized arbiter for a split bus system with independent address and data bus grants

• US 6,535,941 B1
• Filed: 11/08/1999
• Issued: 03/18/2003
• Est. Priority Date: 11/08/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kruse, Robert Earl
• Primary Examiner(s): Wong, Peter
• Assistant Examiner(s): King, Justin
• Application Number:
  US09/436,200
• Time in Patent Office: 1,226 Days
• Field of Search: 710/241, 710/113, 710/116
• US Class Current: 710/241
• CPC Class Codes: G06F 13/1605 based on arbitration arbitration in handling access to a common bus or bus system G06F13/36
• CPC Class Codes: G06F 13/362 with centralised access control

Abstract

A distributed system structure for a large-way, symmetric multiprocessor system using a bus-based cache-coherence protocol is provided. The distributed system structure contains an address switch, multiple memory subsystems, and multiple master devices, either processors, I/O agents, or coherent memory adapters, organized into a set of nodes supported by a node controller. The node controller receives transactions from a master device, communicates with a master device as another master device or as a slave device, and queues transactions received from a master device. Since the achievement of coherency is distributed in time and space, the node controller helps to maintain cache coherency. In order to reduce the delays in giving address bus grants, a bus arbiter for a bus connected to a processor and a particular port of the node controller parks the address bus towards the processor. A history of address bus grants is kept to determine whether any of the previous address bus grants could be used to satisfy an address bus request associated with a data bus request. If one of them qualifies, the data bus grant is given immediately, speeding up the data bus grant process by anywhere from one to many cycles depending on the requests for the address bus from the higher priority node controller.

Claims

1. A method for controlling data transfer between memory controller and a master device by a bus arbiter in a multiprocessor system wherein memory controller has higher priority that the master device, the method comprising the steps of:

granting an unrequested address bus grant to the master device;

in response to receiving an address bus request from the memory controller and an address bus request and data bus request from the master device, rescinding the unrequested address bus grant; and

if the unrequested address bus grant occurred within a predetermined length of time before the data bus request, granting the data bus request to the master device wherein the unrequested address bus grant is converted to a requested address bus grant for the master device.

2. The method of claim 1 further comprising:

maintaining a grant history of unrequested address bus grants.

3. The method of claim 2, wherein the grant history has a length of a predefined number of cycles equal to a number of latches through which bus grants pass between the master device and the bus arbiter.

4. The method of claim 3 further comprising:

receiving a data bus request from the master device;

checking the grant history for an unrequested address bus grant within the previous predefined number of cycles; and

in response to a determination that an unrequested address bus grant has been granted within the previous predefined number of cycles, granting immediately a data bus grant to the master device.

5. The method of claim 4 further comprising:

in response to a determination that an unrequested address bus grant has been granted within the previous predefined number of cycles, clearing a record of the unrequested address bus grant from the grant history.

6. The method of claim 1, wherein the bus arbiter is in a node controller.

7. The method of claim 6 wherein the multiprocessor system comprises:

the node controller;

a plurality of master devices; and

a plurality of bidirectional master device buses, wherein a master device bus connects one or more master devices within a node to a port of the node controller.

8. The method of claim 7 wherein a node controller comprises:

a plurality of master device ports, wherein each master device port connects to a master device bus;

a pair of address switch ports, wherein each address switch port connects to one of a pair of unidirectional address switch buses, wherein one of the pair of address switch buses conveys an address from the node controller to the address switch and one of the pair of address switch buses conveys an address from the address switch to the node controller; and

a plurality of memory subsystem ports, wherein each memory subsystem port connects to a bidirectional memory subsystem bus, wherein a memory subsystem bus conveys data between the node controller and one of the memory subsystems.

9. An apparatus for controlling data transfer between a memory controller and a master device by a bus arbiter in a multiprocessor system, wherein memory controller has higher priority that the master device, the apparatus comprising the steps of:

granting means for granting an unrequested address bus grant to the master device;

rescinding means for rescinding, in response to receiving an address bus request from the memory controller and an address bus request and data bus request from the master device, the unrequested address bus grant, and

granting means for granting the data bus request to the master device if the unrequested address bus grant occurred within a predetermined length of time before the data bus request wherein the unrequested address bus grant is converted to a requested address bus grant for the master device.

10. The apparatus of claim 9 further comprising:

maintaining means for maintaining a grant history of unrequested address bus grants.

11. The apparatus of claim 10, wherein the grant history has a length of a predefined number of cycles equal to a number of latches through which bus grants pass between the master device and the bus arbiter.

12. The apparatus of claim 11 further comprising:

receiving means for receiving a data bus request from the master device;

checking means for checking the grant history for an unrequested address bus grant within the previous predefined number of cycles; and

granting means for granting, in response to a determination that an unrequested address bus grant has been granted within the previous predefined number of cycles, immediately a data bus grant to the master device.

13. The apparatus of claim 12 further comprising:

clearing means for clearing, in response to a determination that an unrequested address bus grant has been granted within the previous predefined number of cycles, a record of the unrequested address bus grant from the grant history.

14. The apparatus of claim 9, wherein the bus arbiter is in a node controller.

15. The apparatus of claim 14 wherein the multiprocessor system comprises:

the node controller;

a plurality of master devices; and

a plurality of bidirectional master device buses, wherein a master device bus connects one or more master devices within a node to a port of the node controller.

16. The apparatus of claim 15 wherein a node controller comprises:

a plurality of master device ports, wherein each master device port connects to a master device bus;

a pair of address switch ports, wherein each address switch port connects to one of a pair of unidirectional address switch buses, wherein one of the pair of address switch buses conveys an address from the node controller to the address switch and one of the pair of address switch buses conveys an address from the address switch to the node controller; and

a plurality of memory subsystem ports, wherein each memory subsystem port connects to a bidirectional memory subsystem bus, wherein a memory subsystem bus conveys data between the node controller and one of the memory subsystems.

17. The apparatus of claim 16, wherein the node controller comprises a plurality of interrupt arbiters, and wherein each interrupt arbiter is uniquely associated with a master device port.

18. A computer program product in a computer-readable medium for controlling data transfer between a memory controller and a master device by a bus arbiter in a multiprocessor system, wherein memory controller has higher priority that the master device, the computer program product comprising:

instructions for granting an unrequested address bus grant to the master device;

instructions for rescinding, in response to receiving an address bus request from the memory controller and an address bus request and data bus request from the master device, the unrequested address bus grant; and

instructions for granting the data bus request to the master device if the unrequested address bus grant occurred within a predetermined length of time before the data bus request wherein the unrequested address bus grant is converted to a requested address bus grant for the master device.

19. The computer program product of claim 18 further comprising:

instructions for maintaining a grant history of unrequested address bus grants.

20. The computer program product of claim 19, wherein the grant history has a length of a predefined number of cycles equal to a number of latches through which bus grants pass between the master device and the bus arbiter.

21. The computer program product of claim 20 further comprising:

instructions for receiving a data bus request from the master device;

checking the grant history for an unrequested address bus grant within the previous predefined number of cycles; and

instructions for immediately granting, in response to a determination that an unrequested address bus grant has been granted within the previous predefined number of cycles, a data bus grant to the master device.

22. The computer program product of claim 21 further comprising:

instructions for clearing in response to a determination that an unrequested address bus grant has been granted within the previous predefined number of cycles, a record of the unrequested address bus grant from the grant history.

23. The computer program product of claim 18, wherein the bus arbiter is in a node controller.

24. The computer program product of claim 23 wherein the multiprocessor system comprises:

the node controller;

a plurality of master devices; and

a plurality of bidirectional master device buses, wherein a master device bus connects one or more master devices within a node to a port of the node controller.

25. The computer program product of claim 24 wherein a node controller comprises:

a plurality of master device ports, wherein each master device port connects to a master device bus;

a pair of address switch ports, wherein each address switch port connects to one of a pair of unidirectional address switch buses, wherein one of the pair of address switch buses conveys an address from the node controller to the address switch and one of the pair of address switch buses conveys an address from the address switch to the node controller; and

a plurality of memory subsystem ports, wherein each memory subsystem port connects to a bidirectional memory subsystem bus, wherein a memory subsystem bus conveys data between the node controller and one of the memory subsystems.

26. A system for controlling data access between a memory controller and a master device by a bus arbiter in a multiprocessor system, wherein the memory controller has higher priority than the master device, the system comprising:

a bus arbiter for a bus connected to a master device and a node controller, wherein the bus arbiter parks the bus toward the master device;

a history of address bus grants;

wherein the history is used to determine whether one of a plurality of previous address bus grants within predetermined length of time can be used to satisfy an address bus request associated with a data bus request by the master device; and

wherein if a previous address bus grant of the plurality can be used to satisfy the address bus request associated with the data bus request, giving the data bus grant immediately.

27. A method of arbitrating bus access between a memory controller and a master device, wherein the memory controller has higher priority tan the master device, comprising the steps of:

granting an unrequested address bus grant to the master device;

in response to receiving an address bus request from the memory controller, rescinding the unrequested address bus grant; and

if the unrequested address bus grant existed within a predetermined amount of time prior to receiving a data bus request from the mast device, granting the data bus to the master device wherein the unrequested address bus grant is converted to a requested address bus grant for the master device.

28. The method of claim 27, wherein a history of unrequested address bus grants to the master device is retained.

29. The method of claim 28, wherein the history is retained for a number of clock cycles equal to one less than the number of latches rough which requests and grants must pass.

30. A method of controlling data transfer between a memory controller and a master device by a bus arbiter, wherein the memory controller has higher priority than the master device, comprising the steps of:

storing a history of unrequested address bus grants;

when an unrequested address bus grant is given within a preconfigured number of cycles prior to a coupled address and data bus request satisfying the address bus request portion of the coupled address and data bus request by using the unrequested address bus grant.