Multiprocessing system including a shared cache

• US 4,445,174 A
• Filed: 03/31/1981
• Issued: 04/24/1984
• Est. Priority Date: 03/31/1981
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Fletcher, Robert P.
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): Niessen, William G.
• Application Number:
  US06/249,526
• Time in Patent Office: 1,120 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/134
• US Class Current: 711/121
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/084 with a shared cache

Abstract

A control system for interlocking processors in a multiprocessing organization. Each processor has its own high speed store in buffer (SIB) cache and each processor shares a common cache with the other processors. The control system insures that all processors access the most up-to-date copy of memory information with a minimal performance impact. The design allows read only copies of the same shared memory block (line) to exist simultaneously in all private caches. Lines that are both shared and changed are stored in the common shared cache, which each processor can directly fetch from and store into. The shared cache system dynamically detects and moves lines, which are both shared and changed, to the common shared cache and moves lines from the shared cache once sharing has ceased.

Claims

1. In a multiprocessor system, the combination comprising:

at least first and second processors;

a main storage means for storing a plurality of pieces of information at main storage addressable locations;

at least first and second private cache storage means operative with said at least first and second processors, respectively, in which a given number of pieces of information previously transferred from said main storage means are stored, including means for directly accessing said private cache storage means;

a shared cache storage means, including means for directly accessing said shared cache storage means by each of said at least first and second processors, in which a number of pieces of information, previously transferred from at least one of said at least first and second private cache storage means, are stored;

means for interrogating said private cache of said first processor to determine if information stored at a given main memory addressable location is stored therein, and if so, including means for accessing said information for use by said first processor; and

if not

means for interrogating said shared cache to determine if said information is stored therein, and if so, including means for accessing said information for use by said first processor; and

if not

means for interrogating said private cache of said second processor to determine if said information is stored therein, and if so, including means for determining if the information has been changed with respect to the main storage copy of the information, and if the information has been changed, including means for transferring said information to said shared cache for immediate access by said first and second processors, and if the information has not been changed, including means for fetching said information to said first processor'"'"'s private cache from said main storage means; and

if said information is not stored in said private cache of said second processor,

means for fetching said information to said private cache of said first processor from said main storage means.

2. A data processing system comprising:

a main storage means for storing a plurality of pieces of information at addressable locations;

including a directory means for identifying where each of said plurality of pieces of information are stored;

a plurality of processing means;

each of said processing means including a private high speed storage means associated therewith for storing a predetermined number of said pieces of information previously transferred from said main storage means to said private high speed storage means, including means for directly accessing said private high speed storage means by its associated processor;

each of said private high speed storage means including a directory means for identifying pieces of information in said private storage means for immediate access by its associated processing means;

a shared high speed storage means, including means for directly accessing said shared high speed storage means by each of said plurality of processing means, for storing a number of pieces of information previously transferred from said main storage means to at least one of said private high speed storage means, and subsequently transferred to said shared high speed storage means from said one private high speed storage means, following said number of pieces of information being changed with respect to the main storage copy of the information, by the processor associated with said one high speed private storage means, and then subsequently being requested by another processing means;

a directory means operable with said shared high speed storage means for identifying pieces of information in said shared high speed storage means for immediate access by each of said plurality of processing means;

storage control means, including copies of each of the directory means of each of the private high speed storage means, interconnected between said main storage means and each of the private and shared high speed storage means and their directory means for controlling the transfer of said pieces of information between the respective storage means; and

each of said processing means including means for providing a local address signal identifying a piece of information in said main storage means, with said local address signal being provided by a given processing means in a predetermined sequence to;

(a) said directory means of said private high speed storage means of said given processing means,

(b) said directory means of said shared high speed storage means,

(c) said copy in said storage control means of the directory means of the private high speed storage means of the other processing means, and

(d) said directory means of said main storage means, with said given processing means including means for determining the first directory means in the predetermined sequence that indicates the storage means associated therewith has the identified piece of information stored therein, and

means for accessing said identified piece of information by said given processing means.

3. A data processing system comprising:

a main storage means for storing a plurality of pieces of information at addressable locations, including a directory means for identifying where each of said plurality of pieces of information are stored;

at least first and second processing means;

said first and second processing means each including a private high speed storage means associated therewith for storing a predetermined number of said pieces of information previously transferred from said main storage means to said private high speed storage means, including means for directly accessing said private high speed storage means by its associated processor;

each of said private high speed storage means including a directory means for identifying said pieces of information in said private storage means for immediate access by its associated processing means;

a shared high speed storage means which is operative with and directly accessible by each of said at least first and second processors, and in which is stored at addressable locations pieces of information which have been changed, with respect to the main storage copy of the information, by one processor and are subsequently requested by the other processor, and following the request are transferred from said one processor'"'"'s private high speed storage means to said shared high speed storage means, including means for directly accessing said shared high speed storage means by each processor;

a directory means operable with said shared high speed storage means for identifying pieces of information in said shared high speed storage means for immediate access by each of said first and second processing means;

storage control means, including copies of each of the directory means of each of the private high speed storage means, interconnected between said main storage means and each of the private and shared high speed storage means and their directory means for controlling the transfer of said pieces of information between the respective storage means; and

each of said processing means including means for providing a local address signal identifying a piece of information in said main storage means, with said local address signal being provided by one of said first and second processing means in a predetermined sequence to;

(a) said directory means of said private high speed storage means of one of said first and second processing means;

(b) said directory means of said shared high speed storage means;

(c) said copy in said storage control means of the directory means of the private high speed storage means of the other one of said first and second processing means;

(d) said directory means of said main storage means; and

means operative with said means for providing a local address signal, to determine the first directory means in the sequence that indicates the storage means associated therewith which has the identified piece of information stored therein.

4. A data processing system comprising:

a main storage means for storing a plurality of instructions and operands at addressable locations;

at least first and second processing means;

said first and second processing means each including a private high speed storage means associated therewith for storing a predetermined number of instructions only, previously transferred from said main storage means to said private high speed storage means, including means for directly accessing said private high speed storage means by its associated processor;

a shared directly accessible high speed storage means, associated with each of said first and second processing means, for storing a predetermined number of instructions and operands previously transferred from said main storage to said shared high speed storage means, including means for directly accessing said shared high speed storage means by each processor.

each of said processing means including means for providing a local address signal identifying an instruction or operand in said main storage means, with said local address signal being provided by one of said first and second processing means in a predetermined sequence to;

(a) said private high speed storage means of one of said first and second processing means directly if the local address signal identifies an instruction,

(b) said shared high speed storage means directly if the local address signal identifies an instruction or operand,

(c) said main storage if the local address signal identifies an instruction or operand, and including means operative with said means for providing a local address signal to determine the first storage means in the sequence that indicates the identified instruction or operand is stored therein, with the identified instruction or operand being fetched from said first storage means in the sequence to the processing means which provided said local address signal.

5. A data processing system comprising:

a main storage means for storing a plurality of instructions and operands at addressable locations;

including a directory means for identifying where each of said plurality of instructions and operands are stored;

a plurality of processing means;

each of said processing means including a directly accessible private high speed storage means for storing a predetermined number of instructions previously transferred from said main storage means to said private high speed storage means, including means for directly accessing said private high speed storage means by its associated processor;

each of said private high speed storage means including a directory means for identifying instructions in said private storage means for immediate access by its associated processing means;

a shared high speed storage means, including means for directly accessing said shared high speed storage means by each of said plurality of processing means, for storing therein a number of instructions and operands previously stored in at least one of said private high speed storage means, with said instructions and operands being changed with respect to the main storage means copy thereof by said one private high speed storage means and then subsequently being requested by another processor, and following the request being transferred to said shared high speed storage means;

a directory means operable with said shared high speed storage means for identifying instructions and operands in said shared high speed storage means for immediate access by each of said plurality of processing means;

each of said processing means including means for providing a local address signal identifying an instruction or operand in said main storage means, with said local address signal being provided by a given processing means in a predetermined sequence to;

(a) said directory means of said private high speed storage means of said given processing means in the local address signal identifies an instruction,

(b) said directory means of said shared high speed storage means if the local address signal identifies an instruction or operand, and

(c) said directory means of said main storage means, if the local address signal identifies an instruction or operand; and

means operative with said means for providing a local address signal to determine the first directory means in the sequence that indicates the storage means associated therewith has the identified instruction or operand stored therein, with the identified instruction or operand being accessed in said associated storage means by said given processing means.

6. A method of operating a multiprocessor system comprised of at least first and second processors, a private cache storage device associated with each processor, which is directly accessible by its associated processor, a shared cache storage device which is shared by each processor, which is directly accessible by each processor, and a main memory storage device which is shared by each processor, with information being referenced with respect to addressable locations in said main memory storage device, said method comprising the steps of:

storing slected pieces of information from said main memory storage device in each of said private cache storage devices;

transferring pieces of information, that have been or are about to be updated with respect to the main memory storage copy of the information in the private cache storage device of one of said first and second processors, and is subsequently requested by the other one of said first and second processors, to said shared cache storage device for storage therein, and

accessing a selected piece of information by a given processor in response to interrogating each of said private cache directly, said shared cache directly and said main memory storage device in a predetermined sequence.

7. A method of operating a multiprocessor system comprised of at least first and second processors, a private cache storage device associated with each processor, which is directly accessible by its associated processor, a shared cache storage device which is shared by each processor, which is directly accessible by each processor and a main memory storage device which is shared by each processor, with information being stored at addressable locations in said main memory storage device, with selected pieces of information being stored in said private cache storage devices device for immediate access by each processor following said information being updated, with respect to the main memory copy of the information, by one processor and subsequently being requested by another processor, said method comprising the steps of:

interrogating in a predetermined sequence by said first processor;

(a) said private cache storge device of said first processor directly,

(b) said shared cache storage device directly,

(c) said private cache storage device of said second processor directly, and

(d) said main memory storage device,

to determine if a given piece of information is stored therein; and

accessing said given piece of information from a given storage device by said first processor in response to said given storage device in the sequence indicating that said piece of information is stored therein.

8. A method of operating a multiprocessor system comprised of at least first and second processors, a private cache associated with each processor, which is directly accessible by its associated processor, a shared cache which is shared by each processor, which is directly accessible by each processor, and a main memory, with information stored in the system being referenced with respect to addressable locations in said main memory, with selected pieces of information being stored in said private caches and said shared cache for immediate access by each processor, said method comprising the steps of:

interrogating said private cache of said first processor directly to determine if information stored at a given main memory addressable location is stored therein, and if so directly accessing said information for use by said first processor; and

if not

interrogating said shared cache directly to determine if said information is stored therein, and if so directly accessing said information for use by said first processor; and

if not

interrogating said private cache of said second processor directly to determine if said information is stored therein, and if so determining if the information has been changed with respect to the main memory copy of the information, and if the information has been changed, transferring said information to said shared cache for immediate access by said first and second processors, and if the information has not been changed fetching said information to said first processors cache from main memory; and

if said information is not stored in said private cache of said second processor;

fetching said information to said private cache of said first processor from said main memory.

9. The method of claim 8, following the direct interrogation of said second processors private cache and finding that said information is stored therein and has not been changed, with said information being fetched from said main memory to said private cache of said processor, including the step of:

marking said information read only in said private cache of said first and second processors.

10. A method of operating a multiprocessor system comprised of at least first and second processors, at least first and second private cache storage devices associated with said first and second processors, respectively, which store instructions only and is directly accessible by its associated processor, a shared cache storage device which is shared by each processor, which stores instructions and operands and which is directly accessible by each processor, and a main memory storage device which is shared by each processor, which stores instructions and operands, with information being stored with respect to addressable locations in said main memory storage device, with selected instructions being stored in said private cache storage devices, and selected instructions and operands being stored in said shared cahce storage device for immediate access by each processor, with each processor including means for providing a local address signal identifying an instruction or operand in said main memory storage device which is a given processor desires to access, said method comprising the steps of:

interrogating by a given processor by providing said local address signal in a predetermined sequence to;

(a) said private cache storage device of said given processor directly if said local address signal identifies an instruction,

(b) said shared cache storage device directly if said local address signal identifies an instruction or operand,

(c) said main memory storage device if said local address signal identifies an instruction or operand, and

accessing said instruction or operand from a given storage device by said given processor in response to said given storage device in the sequence indicating that said instruction or operand is stored therein.

11. A method of operating a multiprocessor system comprised of at least first and second processors, a private cache storage device associated with each processor, which is directly accessible by its associated processor, a shared cache storage device which is shared by each processor and is directly accessible by each processor and a main memory storge device which is shared by each processor, with instructions and operands being referenced with respect to addressable locations in said main memory storage device, said method comprising the steps of:

storing selected instructions only in each of said private cache storage devices;

storing instructions and operands in said shared cache storage device; and

accessing a selected instruction or operand by a given processor in response to selectively interrogating said private cache directly, said shared cache directly and said main memory storage device in a sequence predetermined by whether an instruction or operand is to be accessed.

12. In a multiprocessor system, the combination comprising:

a main storage means for storing a plurality of pieces of information at addressable locations;

at least first and second processors;

at least first and second private high speed storage means which are operative with and directly accessible by said at least first and second processors, respectively, and in which a number of pieces of information transferred from said main storge means are stored at addressable locations, including means for directly accessing said private high speed storage means by its associated processor; and

a shared high speed storage means which is operative with and directly accessible by each of said at least first and second processors, and in which is stored at addressable locations pieces of information which have been changed, with respect to the main storage means copy of the information;

by one processor and are subsequently requested by the other processor, and following the request are transferred from said one processor'"'"'s private high speed storage means to said shared high speed storage means, including means for directly accessing said shared high speed storage means by each processor.

13. In a multiprocessor system, the combination comprising:

a main memory for storing a plurality of pieces of information at addressable locations;

at least first and second processors;

at least first and second private cache memories which are operative with and directly accessible by said at least first and second processors, respectively, and in which a number of pieces of information transferred from said main memory are stored at addressable locations, including means for directly accessing said first and second private cache memories by their associated processor; and

a shared cache memory which is operative with and directly accessible by each of said at least first and second processors, and in which is stored at addressable locations pieces of information which have been stored in the first private cache memory and have been updated with respect to the main memory copy of the information, and are subsequently requested by the second processor, or are stored in the second private cache memory and have been updated with respect to the main memory copy of the information and are subsequently requested by the first processor, and following said request are transferred from one of said first and second private cache memories to said shared cache memory, including means for directly accessing said shared cache memory by each of said at least first and second processors.

14. In a multiprocessor system, the combination comprising:

a main storage means for storing a plurality of pieces of information at addressable locations;

at least first and second processors;

at least first and second private high speed storage means which are operative with and directly accessible by said at least first and second processors, respectively, and in which a number of instructions only, previously transferred from said main storage means, are stored at addressable locations, including means for directly accessing said at least first and second private high speed storage means by their associated processor; and

a shared high speed storage means which is operative with and directly accessible by each of said at least first and second processors, and in which is stored, at addressable locations, a number of instructions and operands previously transferred from said main storage means to said shared high speed storge means, including means for directly accessing said shared high speed storage means by each of said at least first and second processors.

15. A method of operating a multiprocessor system comprised of, at least first and second processors, a directly accessible private cache memory associated with each processor, a shared cache memory which is shared and directly accessible by each processor, and a main memory which is shared by each processor, with information being referenced with respect to addressable locations in said main memory, said method comprising the steps of:

storing selected pieces of information, transferred from said main memory, in each of said private cache memories; and

transferring pieces of information that have been or are about to be changed, with respect to the main memory copy of the information, in the private cache memory of one of said first and second processors, and is subsequently requested by the other one of said first and second processors, to said shared cache memory for storage therein, and subsequent direct access by each of said first and second processors; and

means for directly accessing said shared cache memory and said private cache memories by said processors.