Cache coherency protocol for allowing parallel data fetches and eviction to the same addressable index

A computer program product for enabling concurrent cache line replacement operations to a plurality of cache line sets of a congruence class, the computer program product comprising:

• a non-transitory tangible storage medium readable by a cache controller, wherein a cache is operatively connected to the cache controller, the cache comprising congruence classes where each of the congruence classes has its own addressable index;
• wherein a cache directory has status indications for each memory element in the cache;
• wherein the congruence classes are rows in the cache;
• wherein sets are columns in the cache, such that each of the sets is included in each of the congruence classes;
• the non-transitory tangible storage medium storing instructions for execution by the cache controller for performing a method comprising:
• when there is a cache miss to a given congruence class having a given addressable index in the cache, placing a lock on the given congruence class to prevent access to the given congruence class as a whole while at least one set in the given congruence class is in a process of being marked by adding a marked bit in a status indication for the at least one set in the cache directory;
• wherein the at least one set and other sets are in the given congruence class having the given addressable index, such that the at least one set and the other sets are on a same row defined by the given congruence class;
• marking, by the cache controller, the at least one set of the given congruence class as a marked set by adding the marked bit into the status indication for the at least one set, the marked bit indicating that the marked set is unavailable while replacement operations are being performed on the marked set;
• removing the lock on the given congruence class as a whole once the at least one set has been marked with the marked bit, such that the marked bit blocks access only to the marked set in the given congruence class while allowing access to the other sets in the given congruence class;
• selecting, by the cache controller, the other sets of the given congruence class without marked bits in their status indications in order to permit new replacement operations to be performed on the unmarked sets while the marked bit still blocks access only to the marked set in the given the congruence class on the same row having the given addressable index;
• wherein the at least one set is unmarked based on the replacement operations being complete for the at least one set.