The authors describe and analyze two algorithms for maintaining cache coherence in multiprocessor systems with parallel communication channels and many processors. A distributed link-list relates all cache frames representing the same main memory block. Messages traverse the list to maintain list integrity, exclusive ownership, and consistent values. Memory access semantics are equivalent to a shared memory system without caches. Reference latency, efficiency of memory use, and hardware complexity are moderate and well-bounded. A brief comparison with the Scalable Coherent Interface illustrates some of the design tradeoffs associated with distributed directory algorithms.>

We discuss the translation lookaside buffer (TLB) consistency problem for multiprocessors, and introduce the Mach shootdown algorithm for maintaining TLB consistency in software. This algorithm has been implemented on several multiprocessors, and is in regular production use. Performance evaluations establish the basic costs of the algorithm and show that it has minimal impact on application performance. As a result, TLB consistency does not pose an insurmountable obstacle to multiprocessors with several hundred processors. We also discuss hardware support options for TLB consistency ranging from a minor interrupt structure modification to complete hardware implementations. Features are identified in current hardware that compound the TLB consistency problem; removal or correction of these features can simplify and/or reduce the overhead of maintaining TLB consistency in software.