Highly Concurrent Cache Coherence Protocols

Abstract

We describe a family of cache coherence protocols for MIN-based multiprocessors. These protocols, called delta - cache protocols. are more highly concurrent than other directory protocols. They allow more operations to be pipelined. support multiple readers and writers to the same cache block. and allow processes to execute atomic actions on multiple shared variables without acquiring exclusive access rights to the variables. The protocols are based on the isotacll network. a network implementing a logical time system in which all operations travel at the same velocity. one switch per logical time pulse. lsotach networks are feasible. They can be implemented by applying a standard list-merge algorithm to the operations arriving on the inputs to each switch. We prove the correctness of delta-cache protocols with a new correctness criterion that integrates cache coherence with other aspects of concurrency control. We also describe a highly concurrent migration algorithm based on the isotach network. Note: Abstract extracted from PDF file via OCR