Arbitration protocol for a bidirectional bus for handling access requests to a logically divided memory in a multiprocessor system

• US 5,594,876 A
• Filed: 07/27/1995
• Issued: 01/14/1997
• Est. Priority Date: 06/24/1992
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Getzlaff, Klaus J., Wille, Udo
• Primary Examiner(s): Harvey, Jack B.
• Assistant Examiner(s): WILEY, DAVID ARMAND
• Application Number:
  US08/514,355
• Time in Patent Office: 537 Days
• Field of Search: 395/425, 395/280, 395/725
• US Class Current: 710/113
• CPC Class Codes: G06F 13/18 based on priority control G06F13/1605 takes precedence
• CPC Class Codes: G06F 13/368 with decentralised access control

Abstract

The invention concerns a multiprocessor system comprising processors PU0 to PUn and a common main memory. The memory is logically divided into at least two banks M0 and M1 and is interconnected with the processors by a bus 110. By means of control lines 111 to 118 a bus protocol is established so that one of said memory banks is accessed while another one of said banks is still busy.

Claims

1. A multiprocessor system comprising:

a plurality of processors;

storage means for storing information, said storage means being logically divided into a plurality of banks;

a bus interconnecting each of said processors for communication between said processors and interconnecting said processors and said storage means for transmitting said information from said processors to said storage means and from said storage means to said processors;

arbitration means for granting to said processors accesses to said bus in response to requests from said processors to access said banks, wherein a first one of said accesses to said bus is granted to a first one of said processors in response to a request from said first one of said processors to access a first one of said banks, and a second one of said accesses to said bus is granted to a second one of said processors in response to a request from said second one of said processors to access a second one of said banks, said second one of said accesses to said bus granted to said second one of said processors and said second one of said processors issuing an access command to said second one of said banks over said bus during a time when said first one of said banks is carrying out an access command from said first one of said processors;

wherein said processors each have a predetermined ranking and said banks each have a corresponding queue, and wherein said arbitration means comprises means for storing processor requests to access one of said banks in a queue corresponding to said one of said banks, said processor request to access one of said banks queued in a corresponding queue if one of the following conditions is fulfilled;

(a) a request of a higher ranking processor is already queued in said corresponding queue, or

(b) condition (a) is not fulfilled and a request from a lower ranking processor is not already queued in said corresponding queue; and

wherein said arbitration means grants an access to said bus to a processor whose request to access one of said banks is queued in one of said corresponding queues and

(A) there is no request from a higher ranking processor queued in said one of said corresponding queues, and

(B) one of the following conditions are fulfilled additionally;

(1) a last access to said bus was granted due to a processor request to access another one of said banks, or

(2) if (1) is not fulfilled, there is no request queued in another one of said corresponding queues, and

(C) one of the following conditions are fulfilled additionally;

(1) said one of said banks is not busy, or

(2) if (1) is not fulfilled, said queued request is not a request to access the memory of said one of said banks and wherein if condition (2) is fulfilled, access to said bus is granted to allow said bus to be used for communication between said processors during a time when one of said banks is carrying out an access command from one of said processors.

2. The multiprocessor system according to claim 1, wherein a number of said banks are assigned to corresponding processors, and wherein said arbitration means is distributed so that each of said corresponding processors has an arbiter for each of said banks assigned to said corresponding processors.

3. The multiprocessor system according to claim 1, wherein said processors each comprise:

a first level of cache memory assigned thereto; and

a corresponding first level cache directory, whereby an access to said bus granted to one of said processors is preceded by a bus snooping operation of all other processors to check their cache memory for a cache match in order to maintain data consistency.

4. The multiprocessor system according to claim 1, wherein said multiprocessor system further comprises a direct memory access unit, said direct memory access unit having a highest ranking so that direct memory access unit requests to access one of said banks have priority over said requests from said processors to access said banks.

5. The multiprocessor system according to claim 1, wherein a processor request to access one of said banks is granted in the same machine cycle during which said processor request to access one of said banks was issued.

6. The multiprocessor system according to claim 1, wherein a third one of said accesses to said bus is granted to a third one of said processors in response to a request from said third one of said processors to access a third one of said banks, said third one of said accesses to said bus granted to said third one of said processors and said third one of said processors issuing an access command to said third one of said banks over said bus during a time when said first one of said banks and said second one of said banks are carrying out said access command from said first one of said processors and said access command to said second one of said banks, respectively.

7. The multiprocessor system according to claim 1, wherein at least one other of said accesses to said bus is granted to at least one other of said processors in response to a request from said at least one other of said processors to access at least one other of said banks, said at least one other of said accesses to said bus granted to said at least one other of said processors and said at least one other of said processors issuing an access command to said at least one other of said banks over said bus during a time when said first one of said banks and said second one of said banks are carrying out said access command from said first one of said processors and said access command to said second one of said banks, respectively.

8. The multiprocessor system according to claim 1, wherein a processor request to access one of said banks is granted in the same machine cycle during which an access request from another processor is dropped.

9. A method for granting to processors access to a common bus means in a multiprocessor system, said common bus means coupled to the processors and to storage means, said common bus means adapted to transmit information between the processors and between the processors and the storage means, said storage means logically divided into a plurality of banks, said method comprising the steps of:

a) assigning a rank to each of said processors such that a rank of any one processor is either higher or lower in relation to a rank of any one other processor,

b) queuing a request from one of said processors to access one of said banks in a queue, if the following conditions are fulfilled;

A) a request from a higher ranking processor is already queued in said queue, or

B) condition A) is not fulfilled and a request from a lower ranking processor is not already queued in said queue, and

c) granting access to said bus means in response to said request from said one of said processors if;

(A) there is no said request from a higher ranking processors queued in said queue, and

(B) one of the following conditions are fulfilled additionally;

(1) a last access to said bus means was granted due to a request to access another one of said banks, or

(2) if (1) is not fulfilled, there is no request queued in another queue, and

(C) one of the following conditions are fulfilled additionally;

(1) said one of said banks is not busy, or

(2) if (1) is not fulfilled, said queued request is not a request to access the memory of said one of said banks and wherein if condition (2) is fulfilled, access to said bus is granted to allow said bus to be used for communication between said processors during a time when one of said banks is already carrying out an access command from one of said processors.