Memory reference control in a multiprocessor

• US 4,745,545 A
• Filed: 06/28/1985
• Issued: 05/17/1988
• Est. Priority Date: 06/28/1985
• Status: Expired due to Term

• Current Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Original Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Inventors: Schiffleger, Alan J.
• Primary Examiner(s): Heckler, Thomas M.
• Application Number:
  US06/750,099
• Time in Patent Office: 1,054 Days
• Field of Search: 364/200 MS File
• US Class Current: 711/150
• CPC Class Codes: G06F 13/1663 Access to shared memory
• CPC Class Codes: G06F 15/167 using a common memory, e.g. mailbox

Abstract

A memory interface and conflict resolution network for a multiprocessor system. The memory is multisectional and each section of memory has a plurality of individually addressable memory banks organized in an interleaved fashion and a section level conflict resolution network. Each processor in the system includes several ports and a gating network such that each port may access any section of memory, but access is restricted to no more than one reference per processor per clock period to each section of memory. References generated from different ports of the same processor are automatically synchronized. Each processor has a conflict resolution circuit to resolve conflicts between different ports seeking access to the same section of memory. Conflict resolution is achieved in two clock periods with conflicts between different ports of a processor resolved in the first clock period and conflicts between different processors seeking access to the same banks of any particular section of memory resolved in the second clock period.

Claims

1. In a multiprocessor computer system including a main memory organized into a plurality of sections each consisting of a plurality of individually addressable memory banks, and wherein each processor includes a plurality of reference generating ports which may generate memory references to any one of said sections and banks, a memory reference interface between said processors and said sections comprising:

section level bank conflict resolution means, one for each of said sections of memory, each for receiving reference requests and resolving conflicts between said reference requests;

port level gating means, one associated with each of said processors, each for receiving reference requests from each of the ports associated with its respective processor and gating said reference requests to the associated one of said section level bank conflict resolution means in accordance with the bank to which the request is directed, said port level gating means permitting only one reference per memory section to be gated at a time;

port level section conflict resolution means, one associated with each of said processors, each for monitoring reference requests generated by the ports of its respective processor and detecting whether conflicts between reference requests to the same section of memory exist, and if conflicts are detected, determining which one reference request may proceed to each section of memory through said port level gating means and causing the other conflicting reference requests to be held by the port that generated them;

each of said section level bank conflict resolution means comprising;

a plurality of input gating means, one associated with each processor, each for selectively gating either a reference request gated through said port level gating means or a resubmitted reference request previously gated therethrough but which could not proceed to the memory due to a conflict;

bank busy means for monitoring each bank in the associated memory section and generating a set of busy signals each one indicative of the activity status of a particular bank in said associated memory section;

a plurality of bank conflict checking means each receiving the reference requests gated through a respective one of said input gating means and said set of busy signals for determining the availability of the bank required for a received reference request and generating a bank busy conflict signal indicative of whether or not the checked reference request may proceed;

simultaneous bank conflict checking means receiving all reference requests gated through said input gating means simultaneously for determining if any of said simultaneous reference requests are directed to the same bank and for generating a set of simultaneous request conflict indicating signals each one corresponding to a respective one of said received simultaneous references; and

means receiving said bank busy and simultaneous request conflict indicating signals for resolving conflicts between reference requests submitted to said section level bank conflict resolution means, determining which reference requests may proceed to the memory, causing permissible reference requests to be issued to the memory, causing conflicting impermissible reference requests to be resubmitted to their associated input gating means, and causing the port level section conflict resolution means and associated processor to hold the procession of subsequent reference requests when a reference request associated therewith cannot proceed.

2. A multiprocessor computer system comprising:

a main memory organized into a plurality of sections each consisting of a plurality of individually addressable memory banks;

a plurality of processors each including a plurality of reference generating ports which may generate memory references to any one of said sections and banks;

section level bank conflict resolution means, one for each of said sections of memory, each for receiving reference requests and resolving conflicts between said reference requests;

port level gating means, one associated with each of said processors, each for receiving reference requests from each of the ports associated with its respective processor and gating said reference requests to the associated one of said section level bank conflict resolution means in accordance with the bank to which the request is directed, said port level gating means permitting only one reference per memory section to be gated at a time;

port level section conflict resolution means, one associated with each of said processors, each for monitoring reference requests generated by the ports of its respective processor and detecting whether conflicts between reference requests to the same section of memory exist, and if conflicts are detected, determining which one reference request may proceed to each section of memory through said port level gating means and causing the other conflicting reference requests to be held by the port that generated them;

each of said section level bank conflict resolution means comprising;

a plurality of input gating means, one associated with each processor, each for selectively gating either a reference request gated through said port level gating means or a resubmitted reference request previously gated therethrough but which could not proceed to the memory due to a conflict;

bank busy means for monitoring each bank in the associated memory section and generating a set of busy signals each one indicative of the activity status of a particular bank in said associated memory section;

a plurality of bank conflict checking means each receiving the reference requests gated through a respective one of said input gating means and said set of busy signals for determining the availability of the bank required for a received reference request and generating a bank busy conflict signal indicative of whether or not the checked reference request may proceed;

simultaneous bank conflict checking means receiving all reference requests gated through said input gating means simultaneously for determining if any of said simultaneous reference requests are directed to the same bank and for generating a set of simultaneous request conflict indicating signals each one corresponding to a respective one of said received simultaneous references; and

means receiving said bank busy and simultaneous request conflict indicating signals for resolving conflicts between reference requests submitted to said section level bank conflict resolution means, determining which reference requests may proceed to the memory, causing permissible reference requests to be issued to the memory, causing conflicting impermissible reference requests to be resubmitted to their associated input gating means, and causing the associated port level section conflict resolution means and associated processor to hold the procession of subsequent reference requests when a reference request associated therewith cannot proceed.

3. The multiprocessor computer system of claim 2 wherein the means receiving said bank busy and simultaneous request conflict indicating signals includes:

means for assigning priority between the processors on a rotating basis;

means for handling reference requests so that a reference is allowed to proceed to the requested bank if there is no bank busy conflict and no simultaneous request conflict;

means for handling simultaneous request conflicts so that the reference from the highest priority processor with no bank busy conflict is allowed to proceed to the requested bank; and

means for holding reference requests when there is a bank busy conflict or simultaneous request conflict.

4. The multiprocessor computer system of claim 2 wherein each of said port level section conflict resolution means includes:

section busy conflict means for determining for each reference request whether the memory section containing the requested bank is already being referenced by one of the ports associated with its respective processor;

means for determining whether there are simultaneous reference requests to banks within the same section of memory from more than one of the ports associated with its respective processor;

means for assigning priority between the ports associated with its respective processor, a port with a reference request having an odd address increment having priority over a port with a reference request having an even address increment and where ports have reference requests with the same increment the earliest activated port reference having priority;

means for handling reference requests so that a request is gated through said port level gating means associated with its respective processor if there is no conflict due to the memory section already being referenced and if there is no conflict due to simultaneous reference requests to banks within the same memory section; and

means for handling conflicts between simultaneous reference requests to banks within the same memory section so that the reference request from the highest priority port is gated through said port level gating means associated with its respective processor if there is no conflict due to the memory section already being referenced.

5. A multiprocessor computer system, comprising:

a main memory organized into a plurality of sections each consisting of a plurality of individually addressable memory banks, said banks organized in said sections such that each section includes groups of n consecutive banks, where n equals the number of clock periods required for a bank to perform a reference, said groups interleaved throughout said memory sections in a consecutive manner;

a plurality of processors each including a plurality of reference generating ports which may generate memory references to any one of said sections and banks;

section level bank conflict resolution means, one for each of said sections of memory, each for receiving reference requests and resolving conflicts between said reference requests;

port level gating means, one associated with each of said processors, each for receiving reference requests from each of the ports associated with its respective processor and gating said reference requests to the associated one of said section level bank conflict resolution means in accordance with the bank to which the request is directed, said port level gating means permitting only one reference per memory section to be gated at a time;

port level section conflict resolution means, one associated with each of said processors, each for monitoring reference requests generated by the ports of its respective processor and detecting whether conflicts between reference requests to the same section of memory exist, and if conflicts are detected, determining which one reference request may proceed to each section of memory through said port level gating means and causing the other conflicting reference requests to be held by the port that generated them;

each of said section level bank conflict resolution means comprising;

a plurality of input gating means, one associated with each processor, each for selectively gating either a reference request gated through said port level gating means or a resubmitted reference request previously gated therethrough but which could not proceed to the memory due to a conflict;

bank busy means for monitoring each bank in the associated memory section and generating a set of busy signals each one indicative of the activity status of a particular bank in said associated memory section;

a plurality of bank conflict checking means each receiving the reference requests gated through a respective one of said input gating means and said set of busy signals for determining the availability of the bank required for a received reference request and generating a bank busy conflict signal indicative of whether or not the checked reference request may proceed;

simultaneous bank conflict checking means receiving all reference requests gated through said input gating means simultaneously for determining if any of said simultaneous reference requests are directed to the same bank and for generating a set of simultaneous request conflict indicating signals each one corresponding to a respective one of said received simultaneous references; and

means receiving said bank busy and simultaneous request conflict indicating signals for resolving conflicts between reference requests submitted to said section level bank conflict resolution means, determining which reference requests may proceed to the memory, causing permissible reference requests to be issued to the memory, causing conflicting impermissible reference requests to be resubmitted to their associated input gating means, and causing the port level section conflict resolution means and associated processor to hold the procession of subsequent reference requests when a reference request associated therewith cannot proceed.

6. A multiprocessor computer system comprising:

a main memory organized into a plurality of sections each consisting of a plurality of individually addressable memory banks;

a plurality of processors each including a plurality of reference generating ports which may generate memory references to any one of said sections and banks;

section level bank conflict resolution means, one for each of said sections of memory, each for receiving reference requests and selectively conveying reference requests to its associated memory section;

port level gating means, one associated with each of said processors, each for receiving reference requests from each of the ports associated with its respective processor and gating said reference requests to the associated one of said section level bank conflict resolution means in accordance with the bank to which the request is directed;

port level section conflict resolution means, one associated with each of said processors, each for monitoring reference requests generated by the ports of its respective processor and controlling the gating of requests through the port level gating means associated with its respective processor, each of said port level section conflict resolution means comprising;

bank detection means for determining which of said memory banks within the main memory has been requested;

section busy conflict means for determining for each reference request whether the memory section containing the requested bank is already being referenced by one of the ports associated with its respective processor;

means for determining whether there are simultaneous reference requests to banks within the same section of memory from more than one of the ports associated with its respective processor; and

means for resolving section busy conflicts and conflicts between simultaneous reference requests to banks within the same memory section so that only one reference request to any one memory section is gated through said port level gating means associated with its respective processor at any one time;

each of said section level bank conflict resolution means comprising;

bank busy conflict means for determining for each reference request whether the requested memory bank is ready to be referenced or whether said bank is busy;

means for comparing all of the received reference requests to determine if there are any simultaneous reference requests to the same bank from different processors;

means for resolving bank busy conflicts and conflicts between simultaneous reference requests to the same bank so that only one reference to any one memory bank is allowed at one time and only one memory reference to the memory section associated with said section level bank conflict resolution means from any one processor is allowed at one time.

7. The multiprocessor memory system of claim 6 wherein each of said port level section conflict resolution means further includes:

means for signalling the ports associated with its respective processor that have a reference being held at said port level section conflict resolution means so that said ports do not generate another reference request, and wherein said section level bank conflict resolution means further includes;

means for signalling the port level section conflict resolution means associated with the processors that have a reference being held at said section level bank conflict resolution means so that the ports associated with said processors do not generate another reference request.

8. A method of conveying memory references from the processors to the main memory and resolving memory reference conflicts in a multiprocessor computer system, said system including:

a main memory organized into a plurality of sections each consisting of a plurality of individually addressable memory banks;

a plurality of processors each including a plurality of reference generating ports which may generate memory references to any one of said sections and banks;

section level bank conflict resolution circuits, one for each of said sections of memory, each for receiving reference requests and selectively conveying reference requests to its associated memory section;

port level gating circuits, one associated with each of said processors, each for receiving reference requests from each of the ports associated with its respective processor and gating said reference requests to the associated one of said section level bank conflict resolution circuits in accordance with the bank to which the request is directed, each of said port level gating circuits permitting only one reference per memory section to be gated at a time;

port level section conflict resolution circuits, one associated with each of said processors, each for monitoring reference requests generated by the ports of its respective processor and controlling the gating of reference requests through the port level gating circuit associated with its respective processor;

within a port level section conflict resolution circuit, said method comprising the steps of;

(a) monitoring reference requests from said ports associated with its respective processor;

(b) determining for each reference request which of said memory banks within the main memory has been requested;

(c) determining for each reference request whether the memory section containing the requested bank is already being referenced by one of the ports associated with its respective processor;

(d) determining whether there are simultaneous reference requests to banks within the same section of memory from more than one of the ports associated with its respective processor;

(e) assigning priority between the ports associated with its respective processor, a port with a reference request having an odd address increment having priority over a port with a reference request having an even address increment and where the ports have reference requests with the same increment the earliest activated port reference having priority;

(f) handling reference requests so that a request is gated through said port level gating circuit associated with its respective processor if the memory section requested is not already being referenced by one of the ports associated with its respective processor and if there are no simultaneous reference requests to banks within the same memory section by another of the ports associated with its respective processor;

(g) handling simultaneous reference requests to the same section of memory from more than one of the ports associated with its respective processor so that the reference request from the highest priority port is gated through said port level gating circuit associated with its respective processor if the memory section containing the bank requested by the highest priority port is not already being referenced;

(h) holding reference requests when the memory section containing the requested bank is already being referenced and when the request has a conflict with a request from a higher priority port;

within a section level bank conflict circuit, said method comprising the steps of;

(i) receiving reference requests from said port level gating circuits;

(j) monitoring each bank in the associated memory section and generating a set of busy signals each one indicative of the activity status of a particular bank in said associated memory section;

(k) comparing all of the received reference requests to said set of busy signals to determine the availability of the requested memory banks;

(l) comparing all of the received reference requests to determine if there are any simultaneous reference requests to the same bank from different processors;

(m) assigning priority between the processors on a rotating basis;

(n) handling reference requests so that a request is allowed to proceed to the requested bank if there is no bank busy conflict and no simultaneous reference request to the same bank from a different processor;

(o) handling conflicts between simultaneous reference requests from different processors so that the reference from the highest priority processor with no bank busy conflict is allowed to proceed to the requested bank; and

(p) holding reference requests when the requested bank is busy or when there is a conflict with a higher priority processor.

9. The method of claim 8 further comprising within a port level section conflict resolution circuit the step of:

(a) sending a signal to all of the ports associated with its respective processor that have a reference being held at said port level section conflict resolution circuit so that said ports do not generate another reference request.

10. The method of claim 8 further comprising within a section level bank conflict resolution circuit the step of:

(a) sending a signal to the port level section conflict resolution circuits associated with the processors that have a reference being held at said section level bank conflict resolution circuit so that the ports associated with said processors do not generate another reference request.

11. The method of claim 8 further comprising within a section level bank conflict resolution circuit the steps of:

(a) resubmitting held reference requests; and

(b) for each processor, selecting either a reference request received from the port level gating circuit associated with said processor or a resubmitted reference request from said processor.

12. The method of claim 8 further comprising between different section level bank conflict resolution circuits the step of:

(a) sending a hold signal to all of the section level bank conflict resolution circuits that have received a reference request from a processor issued subsequent to a held reference generated by that processor so that reference requests from the ports of that processor are kept in the order generated.

13. A method of conveying memory reference from the processors to the main memory and resolving memory reference conflicts in a multiprocessor computer system, said system including:

a main memory organized into a plurality of sections each consisting of a plurality of individually addressable memory banks;

a plurality of processors each including a plurality of reference generating ports which may generate memory references to any one of said sections and banks;

section level bank conflict resolution circuits, one for each of said sections of memory, each for receiving reference requests and selectively conveying reference requests to its associated memory section;

port level gating circuits, one associated with each of said processors, each for receiving reference requests from each of the ports associated with its respective processor and gating said reference requests to the associated one of said section level bank conflict resolution circuits in accordance with the bank to which the request is directed; and

port level section conflict resolution circuits, one associated with each of said processors, each for monitoring reference requests generated by the ports of its respective processor and controlling the gating of requests through the port level gating circuit associated with its respective processor;

within a port level section conflict resolution circuit, said method comprising the steps of;

(a) monitoring reference requests from said ports associated with its respective processor;

(b) determining for each reference request which of said memory banks within the main memory has been requested;

(c) determining for each reference request whether the memory section containing the requested bank is already being referenced by one of the ports associated with its respective processor;

(d) determining whether there are simultaneous reference requests to banks within the same section of memory from more than one of the ports associated with its respective processor;

(e) resolving conflicts due to the requested memory section already being referenced and conflicts between simultaneous reference requests to banks within the same memory section so that only one reference request to any one memory section is gated through said port level gating circuit associated with its respective processor at any one time;

within a section level bank conflict resolution circuit, said method comprising the steps of;

(f) receiving reference requests from said port level gating circuits;

(g) checking the status of each requested memory bank to determine whether said bank is ready to be referenced or whether said bank is busy;

(h) comparing all of the received reference requests to determine if there are any simultaneous reference requests to the same bank from different processors.

(i) resolving bank busy conflicts and conflicts between simultaneous reference requests to the same bank so that only one reference to any one memory bank is allowed at one time and only one memory reference to the memory section associated with said section level bank conflict resolution circuit from any one processor is allowed at one time.