A scalable coherent cache system with fuzzy directory state

We describe a directory based coherent cache system which can be scaled. Our scheme is an interpolation between the complete directory state solution of Censier and Feautrier, where the memory controller knows the disposition of the line for every cache, and the minimal state solution due to Archibald and Baer which requires broadcasts for all state transitions. By interpolating between these solutions we can limit the negative performance impact of broadcasts to caches which do not have a copy of the line. In our scheme, the N caches in the system are divided into N/G subgroups, where G is the group size, and a state bit is used to reflect occupancy information for each subgroup. The number of state bits required for each line can be scaled by appropriately selecting the group size. Multicasts of invalidate requests are limited to subgroups of caches which have one or more copies of the line. Our interconnection network efficiently supports multicasts to subgroups of caches, and combines the responses from these multicasts, to optimize performance. 10 refs., 3 figs.