Multiple-Writer Distributed MemoryThe Sequential Consistency Memory ModelThis ClassMotivation for Weaker OrderingsWeak OrderingWeak Ordering ExampleMultiple Writer ProtocolTreadmarks 101Lazy Release ConsistencyOrdering of Events in TreadmarksVector Timestamps in TreadmarksLRC ProtocolWrite NoticesOrdering Conflicting UpdatesMore slidesCapturing Updates (Write Collection)Lazy Interval/Diff CreationTreadmarks Page State TransitionsOrdering Conflicting Updates (2)Page Based DSM: Pros and ConsMultiple-Writer Distributed MemoryMultiple-Writer Distributed MemoryThe Sequential Consistency Memory ModelThe Sequential Consistency Memory ModelP1 P2P3switch randomly setafter each memory opensures some serialorder among all operationssequential processorsissue memory opsin program orderMemoryEasily implemented with shared bus.[Lebeck]This ClassThis ClassSpend time at the start to discuss Haifeng Yu’s notion of a continuum of consistency quality for distributed systems.Understand why weakening consistency can improve performance or availability.But what does it really mean to weaken consistency? How much can the application tolerate?We discuss one notion of weak consistency for distributed shared memory (DSM), using mechanisms similar to Bayou. The background for DSM was covered previously and is in the CDK text chapter 16.Motivation for Weaker OrderingsMotivation for Weaker Orderings1. Sequential consistency is sufficient (but not necessary) for shared-memory parallel computations to execute correctly.2. Sequential consistency is slow for paged DSM systems.Processors cannot observe memory bus traffic in other nodes.Even if they could, no shared bus to serialize accesses.Protection granularity (pages) is too coarse.3. Basic problem: the need for exclusive access to cache lines (pages) leads to false sharing.Causes a “ping-pong effect” if multiple writers to the same page.4. Solution: allow multiple writers to a page if their writes are “nonconflicting”.Weak OrderingWeak OrderingCareful access ordering only matters when data is shared.Shared data should be synchronized.Classify memory operations as data or synchronizationCan reorder data operations between synchronization operationsForces consistent view at all synchronization pointsVisible synchronization operation, can flush write buffer and obtain ACKS for all previous memory operationsCannot let synch operation complete until previous operations complete (e.g., ACK all invalidations)[Lebeck]Weak Ordering ExampleWeak Ordering ExampleRead / Write…Read/WriteRead / Write…Read/WriteRead / Write…Read/WriteSynchSynchA B(x = y = 0;)if (y > x) loop { panic(“ouch”); x = x + 1; y = y + 1;}Aacquire();if (y > x) panic(“ouch”);release();Bloop() { acquire(); x = x + 1; y = y + 1; release();}[Lebeck]Multiple Writer ProtocolMultiple Writer Protocolx & y on same page P1 writes x, P2 writes yDon’t want delays associated with constraint of exclusive accessAllow each processor to modify its local copy of a page between synchronization pointsMake things consistent at synchronization point[Lebeck]Treadmarks 101Treadmarks 101Goa l: implement the “laziest” software DSM system.•Eliminate false sharing by multiple-writer protocol.Capture page updates at a fine grain by “diffing”.Propagate just the modified bytes (deltas).Allows merging of concurrent nonconflicting updates.•Propagate updates only when needed, i.e., when program uses shared locks to force consistency.Assume program is fully synchronized.•lazy release consistency (LRC)A need not be aware of B’s updates except when needed to preserve potential causality......with respect to shared synchronization accesses.Lazy Release ConsistencyLazy Release ConsistencyPiggyback write notices with acquire operations.•guarantee updates are visible on acquirelazier than Munin, which propagates updates on release•implementation propagates invalidations rather than updatesP0P1P2acq w(x) relr(y)r(y)acqlockgrant+ inv.w(x)relacqlockgrant+ inv.r(x)relupdates to xupdates to xX & Y on same pageOrdering of Events in TreadmarksOrdering of Events in TreadmarksABCLRC is not linearizable: there is no fixed global ordering of events.There is a partial order on synchronization events and the intervals they define.Acquire(x)Release(x)Release(x)Acquire(x)Release(x)Acquire(x)Vector Timestamps in TreadmarksVector Timestamps in TreadmarksTo maintain the partial order on intervals, each node maintains a current vector timestamp (CVT).•Intervals on each node are numbered 0, 1, 2...•CVT is a vector of length N, the number of nodes.•CVT[i] is number of the last preceding interval on node i.Vector timestamps are updated on lock acquire.•CVT is passed with lock acquire request...•compared with the holder’s CVT...•pairwise maximum CVT is returned with the lock.LRC ProtocolLRC ProtocolABCAcquire(x)Release(x)Acquire(x)Release(x)Acquire(x)receive write noticesgenerate write noticesCVTB write noticesfor CVTA - CVTB(see text below)reference to page with pending write noticedelta requestdeltalistwrite noticesWhat does A send to B on the red arrow (pass with lock token)? - a list of intervals known to A but not to B (CVTA - CVTB) - for each interval in the list: - the origin node i and interval number n- i’s vector clock CVTi during that interval n on node i- a list of pages dirtied by i during that interval n- these dirty page notifications are called write noticesWrite NoticesWrite NoticesLRC requires that each node be aware of any updates to a shared page made during a preceding interval.•Updates are tracked as sets of write notices.A write notice is a record that a page was dirtied during an interval.•Write notices propagate with locks.When relinquishing a lock token, the holder returns all write notices for intervals “added” to the caller’s CVT.•Use page protections to collect and process write notices.“First” store to each page is trapped...write notice created.Pages for received write notices are invalidated on acquire.Ordering Conflicting UpdatesOrdering Conflicting UpdatesBCDWrite notices must include origin node and CVT.Compare CVTs to order the updates.A(x)R(x)A(x)R(x)A(x)AA(y)R(y)R(y)A(y)B2 (j = 0, i = 0)C1 (i = 1)A1 (j = 1)D2 (i == ?, j == ?)0210B2: j=0, i=0A1: j=1032Variables i and j are on the same page, under control of locks X and Y.C1: i =1 A(y)412(j == 0)(i == 0){B2, A1}{C1}B2 < A1, B2 < C1More slidesMore slidesThe following slides were not