Directory-based coherence

<h2 id="history">History</h2>
The idea of directory-based cache coherence systems began long ago. The idea of DASH (Directory Architecture for SHared-memory) was first proposed by C.K. Tang<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> in the mid 1970s. However, applying it to cache coherence was proposed a few years later in 1978, when researchers at <a href="/facts/Stanford_University/JEQeF9z2">Stanford University</a> proposed the first version of this coherence systems called <a href="/facts/Stanford_DASH/heeBY2cT">Stanford DASH</a>, in a paper<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> that described the system with the difficulties and improvements associated with such designs. Beside this approach, several attempts were done to provide a scalable systems. For instance, <a href="/facts/BBN_Butterfly/kDvAPTeT">BBN Butterfly</a><a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> which was introduced in 1985, and IBM PR3<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> which was introduced in 1987, are some examples of scalable <a href="/facts/Multiprocessor_system-on-chip/s5jssTDl">multiprocessor systems</a>. However, both of these systems have a drawback; For example, BBN Butterfly does not have caches. Similarly, IBM PR3 does not provide hardware cache coherence, which limits the performance of both of these designs, especially when employing high performance processors.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>
The limitations of other competitors made it easier for DASH based systems to get chosen when designing cache coherence systems and other systems needing scalability in cache-based nodes. In 1985, James Archibald<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> and <a href="/facts/Jean-Loup_Baer/6l3F3yeB">Jean-Loup Baer</a> from the <a href="/facts/University_of_Washington/36PG6qkG">University of Washington</a> published a paper<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> that proposes a more economical, expandable, and modular variation of the "global directory" approach in the term of hardware use in the design.
In 1992, Daniel Lenoski from Stanford university published a paper<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> proposing advances in cache coherence protocols for directory-based systems. In a 1996 paper,<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> he introduced the design of the <a href="/facts/SGI_Origin_2000/VWwb0NRH">SGI Origin 2000</a>, a family of server computers employing directory based cache coherence. The subsequent <a href="/facts/Origin_3000/PWWqRwzf">Origin 3000</a><a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> was introduced in July 2000.

<h2 id="protocols">Protocols</h2>
Unlike <a href="/facts/Snoopy_cache/NUxKS0mb">snoopy</a> coherence protocols, in a directory based coherence approach, the information about which caches have a copy of a block is maintained in a structure called directory. In a directory based scheme, participating caches do not broadcast requests to all other sharing caches of the block in order to locate cached copies, instead it queries the directory to retrieve the information about which block have cached copies and sends only to those particular processors and hence traffic saving compared to a snoopy protocol is large. In well optimized applications, most data sharing is only for data that is read only, and there is little sharing for data that is frequently read and written. A directory approach can result in a substantial traffic saving compared to broadcast/snoopy approach in such applications.

As shown in the data flow diagram, the actors involved in a distributed shared memory system implementing directory based coherence protocol are:

<ul><li>Requestor Node: This node is the processor who is requesting for a read/write of a memory block.</li>
<li>Directory Node: This node maintains the information of the state of each cache block in the system and requestor directs its requests to the directory node.</li>
<li>Owner Node: An owner node owns the most recent state of the cache block, note that directory might not be always up to date with latest data.</li>
<li>Sharer Node: One or many node which are sharing a copy of the cache block.</li></ul>

Requestor and Owner nodes maintain their state transition similar to a snoopy coherence protocols like <a href="/facts/MESI_protocol/BUCBWvtS">MESI protocol</a>. However, unlike a bus based implementation where nodes communicate using a common bus, directory based implementation uses <a href="/facts/Message_Passing_Interface/BEuBgDpm">message passing</a> model to exchange information required for maintaining <a href="/facts/Cache_coherence/MhUD576q">cache coherence</a>.
Directory node acts as a serializing point and all communications are directed through this node to maintain correctness.

<h2 id="directory-node">Directory node</h2>
A directory node keeps track of the overall state of a cache block in the entire cache system for all processors. It can be in three states :

<ul><li>Uncached (U): No processor has data cached, memory up-to-date .</li>
<li>Shared (S): one or more processors have data cached, memory up-to-date. In this state directory and sharers have clean copy of the cached block.</li>
<li>Exclusive/Modified (EM): one processor (owner) has data cached; memory out-of-date. Note that directory cannot distinguish a block cached in an exclusive or modified state at the processor, as processors can transition from an exclusive state to modified state without any bus transaction.</li></ul>
Explanation of the directory state transition <a href="/facts/Finite-state_machine/GMusWd0a">finite-state machine</a> (refer image 1) is captured below in the table:

<table><tbody><tr><th>Initial State</th><th>Bus Request</th><th>Response/ Action</th><th>New State</th></tr><tr><td>U</td><td>BusRd orBusRdX</td><td><ul><li>Fetch block from memory as the directory is having the updated copy of the block.</li><li>send the memory block to requestor using the message (ReplyD).</li><li>if there are no sharers: requestor = first sharer, directory transitions into EM state.</li></ul></td><td>EM</td></tr><tr><td>EM</td><td>BusRd</td><td><ul><li>Send intervention(Int) to the owner</li></ul></td><td>S</td></tr><tr><td></td><td>BusRdX</td><td><ul><li>Send Invalidation(Inv) to the current owner.</li></ul></td><td>-</td></tr><tr><td>S</td><td>BusRd</td><td><ul><li>Reply to the requestor with the memory block (ReplyD)</li></ul></td><td>-</td></tr><tr><td></td><td>BusRdX</td><td><ul><li>Reply to the requestor with the memory block (ReplyD)</li><li>Invalidate(Inv) all sharers.</li></ul></td><td>EM</td></tr><tr><td></td><td>BusUpgr</td><td><ul><li>Invalidate(Inv) all sharers.</li><li>Reply to the requestor that he can upgrade. (Reply)</li></ul></td><td>EM</td></tr></tbody></table>
In addition to cache state, a directory must track which processors have data when in the shared state. This is required for sending invalidation and intervention requests to the individual processor caches which have the cache block in shared state. Few of the popular implementation approaches are: 

<ul><li>Full bit-vector: A bit field for each processor at the directory node are maintained. The storage overhead scales with the number of processors.</li>
<li>Limited pointer: In this approach directory information of limited number of blocks is kept at the directory to reduce storage overhead.</li></ul>
The protocol described above is the basic implementation and <a href="/facts/Race_condition/bvNpgy4F">race conditions</a> can occur due to the fact that directory can be out of sync with the caches and also messages between processors can be overlapping. More complex implementations are available like <a href="/facts/Scalable_Coherent_Interface/QvMJHpge">Scalable Coherent Interface</a> which have multiple states.
DASH<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> cache coherence protocol is another protocol that uses directory-based coherence scheme. DASH protocol uses a clustered approach, where processors inside a cluster are kept coherent using bus based snooping scheme, while the clusters are connected in a directory approach. Even though various protocols use different implementations for tracking cache blocks, however the concept of directory remains same.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Coherence_protocol/MhUD576q">Coherence protocol</a></li>
<li><a href="/facts/MSI_protocol/YjNNNoGU">MSI protocol</a></li>
<li><a href="/facts/Bit_array/PAfzTEHB">Bit array</a></li>
<li><a href="/facts/Distributed_shared_memory/IboHJvt6">Distributed shared memory</a></li>
<li><a href="/facts/Snoopy_cache/NUxKS0mb">Snoopy cache</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Solihin, Yan (2009). Fundamentals of parallel computer architecture. pp. 319–360. <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Solihin, Yan (2009). Fundamentals of parallel computer architecture. pp. 319–360. <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Tang, C.K. "Cache system design in the tightly coupled multiprocessor system". AFIPS '76 Proceedings of the June 7–10, 1976, National Computer Conference and Exposition. <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">"The Directory-Based Cache Coherence Protocol for the DASH Multiprocessor" (PDF). Computer Systems Laboratory. <a href="http://people.eecs.berkeley.edu/~kubitron/cs258/handouts/papers/p148-lenoski.pdf" target="_blank">http://people.eecs.berkeley.edu/~kubitron/cs258/handouts/papers/p148-lenoski.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Schmidt, G.E. "The Butterfly Parallel Processor". In Proc. Of ICS. <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">"The IBM research parallel processor prototype PR3: Introduction and architicture". In Proceeding of the 1985 International Conference of Parallel Processing. <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">"Design of Scalable Shared-Memory Multiprocessors: The DASH approach". Computer System Laboratory, Stanford University. <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">"James Archibald". ece.byu.edu. Archived from the original on 2017-08-02. Retrieved 2016-11-15. <a href="https://web.archive.org/web/20170802134914/http://ece.byu.edu/faculty/jka" target="_blank">https://web.archive.org/web/20170802134914/http://ece.byu.edu/faculty/jka</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">"An economical solution to the cache coherence problem". ISCA '84 Proceedings of the 11th Annual International Symposium on Computer Architecture. <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Lenoski, Daniel; Laudon, James; Gharachorloo, Kourosh; Weber, Wolf-Dietrich; Gupta, Anoop; Hennessy, John; Horowitz, Mark; Lam, Monica S. (1992-03-01). "The Stanford Dash Multiprocessor". Computer. 25 (3): 63–79. doi:10.1109/2.121510. ISSN 0018-9162. S2CID 9731523. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Laudon, James; Lenoski, Daniel (1997-01-01). "The SGI Origin". Proceedings of the 24th annual international symposium on Computer architecture - ISCA '97. New York, NY, USA: ACM. pp. 241–251. doi:10.1145/264107.264206. ISBN 978-0897919012. S2CID 692050. <a href="978-0897919012" target="_blank">978-0897919012</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Corp., Silicon Graphics International. "Support Home Page". support1-sgi.custhelp.com. Archived from the original on 2018-04-13. Retrieved 2016-11-16. <a href="https://web.archive.org/web/20180413084346/https://support1-sgi.custhelp.com/" target="_blank">https://web.archive.org/web/20180413084346/https://support1-sgi.custhelp.com/</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">"The Directory-Based Cache Coherence Protocol for the DASH Multiprocessor" (PDF). Computer Systems Laboratory. <a href="http://people.eecs.berkeley.edu/~kubitron/cs258/handouts/papers/p148-lenoski.pdf" target="_blank">http://people.eecs.berkeley.edu/~kubitron/cs258/handouts/papers/p148-lenoski.pdf</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
</ol>

Directory-based coherence open-in-new

Directory-based coherence