Multiprocessor coherent cache system including two level shared cache with separately allocated processor storage locations and inter-level duplicate entry replacement

A data processing system comprising:

• a pair of independently operated processing units, each processing unit being operative to generate memory request for data, each request including an address having first and second address portions;
• and
• a cache memory subsystem coupled to said pair of processing units for receiving said requests, said cache memory subsystem comprising:
• a first stage including a directory store being divided equally into first and second pluralities of levels, said first and second pluralities of levels, each plurality containing groups of storage locations, each location for storing said first address portion of a memory request generated by each of said processing units allocated said first and second plurality of levels and each different group of locations within said plurality of directory store levels being defined by a different one of said second address portions;
• a second stage including a data store being divided equally into the same first and second plurality of levels as said directory store and each different group of locations within said data store levels being accessed by a different one of said second address portions;
• first and second accounting means being associated with said first and second pluralities of levels of said cache store respectively, each accounting means containing said first plurality of levels for storing information establishing the order of replacing locations within said levels on the basis of usage;
• multiple allocation memory (MAM) means including said first plurality of levels of said groups of locations and each different group of locations being accessed by said second address portion;
• and,
• selector means coupled to said MAM means and to said first and second accounting means;
• and,
• decode and control means coupled to said directory store, to said MAM means, said decode and control means being operative during each allocation cycle to generate signals for indicating when the same first address portion stored in a location defined by said second address portion of one of said first levels allocated to one processing unit being written into a location defined by the same second address portion in one of said plurality of levels allocated to the other processing unit resulting in a duplicate directory entry;
• and
• said MAM means being conditioned by said decode and control means to store signals specifying the directory store level of a predetermined one of said pair of processing units and a multiple allocation memory (MAM) signal indicating the occurrence of a multiple allocation, said MAM means in response to the same second address portion during a next allocation cycle in which a location specified by the same second address is being allocated in another one of said first or second pluralities levels, reading out said stored level and MAM allocation signals, said selector means being conditioned to specify said stored level from said MAM means as a replacement location eliminating said duplicate entry ensuring that coherent data is maintained in said cache store.

A system comprising a number of data processing subsystems and at least one main memory subsystem coupled in common to an asynchronous system bus, at least one of said data processing subsystems including a pair of processing units, each processing unit being operative to generate memory requests for data, each request including an address having first and second address portions;

• and
• a pipelined cache memory subsystem coupled to each of said processing units for receiving said data requests, said cache subsystem comprising:
• input selection means for selecting a request address from one of said processing units during an allocated time slot interval;
• a first pipeline cache stage coupled to said input selection means, said pipeline stage including a directory store divided into the same number of levels Xo through Xn and Yo through Yn containing groups of storage locations, each location for storing said first address portion of a memory read request generated by one of said processing units during said allocated time slot interval and each different group of locations within said directory store levels being accessed by a different one of said second address portions;
• a second cache pipeline stage including a data store divided into the same number of levels Xo through Xn and Yo through Yn of said groups of locations as in said directory store and each different group of locations within said data store levels being accessible by a different one of said second address portions during a succeeding time slot interval for transfer of the date contents to the requesting one of said processing units;
• first and second accounting means being associated with said levels Xo through Xn and Yo through Yn of said cache store respectively, each accounting means containing said first plurality of levels for storing information establishing the order of replacing locations within said levels on the basis of usage;
• multiple allocation memory (MAM) means including the same number of levels of said groups of locations as levels Xo through Xn and Yo through Yn and each different group of locations being accessed by said second address portion;
• and,
• selector means coupled to said MAM means and to said first and second accounting means;
• and,
• decode and control means coupled to said directory store, to said MAM means, said decode and control means being operative during each allocation cycle to generate signals for indicating when the same first address portion stored in a location defined by said second address portion of one of said levels Xo through Xn allocated to one processing unit having a higher priority is being written into a location defined by the same second address portion in one of said plurality of levels Yo through Yn allocated to the other processing unit resulting in a duplicate directory entry;
• and
• said MAM means being conditioned by said decode and control means to store signals specifying one of the directory store levels Yo through Yn and a multiple allocation memory (MAM) signal indicating the occurrence of a multiple allocation, said MAM means in response to the same second address portion during a next allocation cycle in which a location specified by the same second address is being allocated in another one of said first or second pluralities levels, reading out said stored level and MAM allocation signals, said selector means being conditioned to specify said stored level from said MAM means as a replacement location eliminating said duplicate entry ensuring that coherent data is maintained in said cache store.