Method and apparatus for dynamic cache line sectoring in multiprocessor systems

In a computer system which includes a shared main memory, a system control element, and at least two processors, each processor having a respective private cache memory holding lines of memory words, apparatus for managing access to the words in the cache memories, said apparatus comprising:

• means for identifying a line in one of the cache memories that has been referenced by two of the processors, such that each work in said line has been reference by at most one of the processors;
• means for providing exclusive control to each processor over any words which have been modified by that processor within a copy of said identified line in the private cache memory of that processor, at least two respective processors being provided exclusive control over respectively different words in said identified line simultaneously;
• means for invalidating those words in each private cache memory that have been modified by a processor other than that to which the cache is private;
• and
• means for providing read-only access to all processors for those words which have not been modified by any processor since being made resident in any of the cache memories.

In a computer system including a plurality of processors, a shared main memory and a system control element, wherein each processor has a respective cache memory and each cache memory holds lines of memory words, apparatus for managing access to the memory words comprising:

• first identification means, coupled to each processor, for identifying data lines in the cache memories that have been modified by the processor;
• second identification means, coupled to each processor, for identifying each data line in each cache memory that contains a first word which has been modified by a first one of said processors and a second word which has been accessed by a second one of said processors;
• first control means, coupled to said system control element and responsive to a request from one of said processors to gain access to a word in a line of one of said cache memories, for determining, from said first identification means, whether said line contains a word to which another one of said processors has been given access and has modified said word;
• and
• second control means, responsive to the determination by the first control means, for transferring the line from the first identification means to the second identification means and for preventing two processors from gaining simultaneous access to any one word in the line when one of the two processors has write access to the word, said second control means including means for providing simultaneous write access tot he two processors, the respective processors accessing respectively different data words in respective copies of the line residing in respectively different cache memories.

In a system, including a plurality of processors, a shared main memory and a system control element, where each processor has a cache memory which holds lines of memory words, apparatus for managing access to data in cache memories comprising:

• modified line identification means for identifying data words which have been changed since the lines which contain the words were made resident in one of said cache memories;
• sectoring means for marking a line in which a first word has been modified by one processor and a second word has been referenced by at least one other processor since being made resident in the cache;
• sectored line directory means, responsive to said sectoring means, for identifying individual words within a line marked by the sectoring means as being under exclusive control, being under read-only control of a given processor or being invalid;
• and
• shared exclusive control means for allowing each processor to store information into words within the marked lines only if thy are under said exclusive control of the given processor, and to fetch information only from words in said marked lines which are marked as being under exclusive or read-only control, said shared exclusive control means including means for providing the respective processors simultaneous write access to respectively different data words in respective copies of the marked lines, each respective copy residing in a respectively different cache memory.

In a system, including a plurality of processors, a shared main memory, a system control element and a shared cache memory, where each processor has a respective private cache memory which holds lines of memory words, apparatus for managing access to data in cache memories comprising:

• identification means for identifying a data line in a private cache memory that has been referenced by at least two of the processors while resident in at least one private cache memory, such that each data word in said data line has been referenced by at most one of the processors;
• control means, responsive to said identification means, for providing simultaneous write access to the processors which have accessed data words in the identified line, each respective processor accessing a respectively different word in a respective copy of the identified line in the respective private cache memory of that processor;
• further identification means for marking as shared a data line in cache memory which has been referenced by at least two of the processors while resident in a private cache memory, such that at least one data word in said data line has been referenced by at least two of the processors;
• and
• further control means, responsive to said further identification means, for storing said data line marked as shared by said further identification means into the shared cache memory, and for invalidating all copes of said data line marked as shared in the private cache memories.

In a computer system which includes a shared main memory, a system control element, and at least two processors, each processor having a respective private cache memory, a method for managing access to data in cache memories said method comprising the steps of:

• identifying a data line in cache memory that has been referenced by at least two of the processors, such that each data word in said data line has been referenced by at most one of the processors;
• providing simultaneous write access, for writing to respectively different words in the identified line, tot he processors which have accessed data words in the identified line, each respective processor accessing a respective copy of the identified line in the respective private cache memory of that processor;
• and
• preventing more than one processor from gaining simultaneous write access to any one word in said data line.

In a computer system which includes a shared main memory, a system control element, and at least two processors, each processor having a respective private cache memory holding lines of memory words, a method for managing access to the words in the cache memories, said method comprising the steps of:

• identifying a line in one of the cache memories that has been referenced by two of the processors, such that each word in said line has been referenced by at most one of the processors;
• providing exclusive control simultaneously to each processor over any words which have been modified by that processor within said line referenced by two processors, each respective processor accessing a respectively different word in a respective copy of the line in its respective private cache memory;
• invalidating those words in each private cache memory that have been modified by another processor;
• providing read-only access to all processors for those words which have not been modified by any processor since being made resident in any of the cache memories.

In a computer system which includes a shared main memory, a system control element, and at least two processors, each processor having a private cache memory for holding lines of memory words, a method for managing access to data in cache memories, said method comprising the steps of:

• identifying data words which have been changed since the lines containing said data words were made resident in said cache memories;
• identifying as sectored each line which has been changed by one of the processors and referenced by at least one other processor since being placed in cache, and for which no single word in said line has been referenced by more than one of the processors;
• identifying the control status of individual words within said sectored lines, each word being under exclusive control of one of said processors, being under read-only control of one of said processors, or being invalid;
• enabling each processor to store into words within said sectored lines only if said words are identified as being under the exclusive control of the processor, and to fetch only from those words within said sectored lines which are identified as being under exclusive or read-only control of the processor;
• and
• enabling at least two respective processors to simultaneously store into respectively different words in respective copies of the sectored lines, the respective copies of the sectored lines residing in the respective private cache memories of said two processors.

In a computer system which includes a shared main memory, a system control element, and at least two processors, each processor having a private cache memory which holds lines of memory words, a method for managing access to the memory words in the cache memories, said method comprising the steps of:

• a) recording the addresses of lines which have been caged since being made resident in the cache memory of each processor;
• b) recording the location of each data work which has been changed within the lines with said recorded addresses;
• c) setting a status flag to identify as sectored a line which has been changed by one processor and referenced by at least one other processor since being placed in the cache, and for which no single word in said line has been referenced by more than one processor, the system control element performing the setting of the status flag;
• d) recording access restriction for the individual words within each of the lines which have been identified as sectored, said access restrictions indicating that each word is under exclusive control of one of said processors, is under read-only control of one of said processors, or is invalid;
• and
• e) enabling each respective processor to store into words within said sectored lines only if the access restrictions indicate that the words are under the exclusive control of the respective processor performing a store operation, and to fetch from words within said sectored lines only if the access restrictions indicate that the words are under exclusive or read-only control of the respective processor performing a fetch operation;
• f) enabling on of said processors to receive exclusive control of a word in one of said sectored lines which is held in the cache memory of another processor without invalidating the entire line in the cache memory of said other processor, while said other processor simultaneously retains exclusive control over a further word in said one sectored line, said further word being different from said word;
• and
• g) invalidating the word in the cache memory of the other processor, using the system control element, in response tot he request for exclusive control by the one processor.

In a computer system which includes a shared main memory, a shared cache memory, a system control element, and a plurality of processors, each processor having a private cache memory for holding lines of memory words, a method for managing access to the words in the cache memories, said method comprising the steps of:

• identifying which data lines in private cache memory have been referenced by two of the plurality of processors while resident in at least one private cache memory, such that each data word in said identified data lines has been referenced by only one of the plurality of processors;
• providing, for the two processors, simultaneous access to respective copies of one of said data lines referenced by the two processors, said respective copies being stored in the respective private cache memories of said processors, wherein each data word in said one data line has been referenced by only one processor;
• marking as shared those data lines in cache memory which have been referenced by two of the plurality of processors while resident in private cache memory, such that at least one data word in each of said data lines has been referenced by the two processors;
• and
• storing into shared cache memory said data lines marked as shared;
• and
• invalidating all copies of said data lines marked as shared in private cache memories.