Shared Memory Concurrency Roadmap

05-25

過去很多年, 單核處理器性能基本沿摩爾定律的預測不斷提速. 然而, 設計上越來越複雜, 也越來越接近物理極限, 引起了生產成本和功耗的增大, 性價比降低. 2005年前後, CPU製造商, 開始從原來提升單核處理器的ILP(instruction-level parallelism), 轉向在單個晶元上增加核數, 挖掘multicore processor的性能[1].

目前, 市面上, 商用廉價或高端伺服器, 一般都採用shared memory multicore multiprocessor. 高端伺服器有幾十~幾百core, 幾百GB甚至上TB的內存. 例如: Intel? Xeon? Processor E7-8894 v4支持8 socket * 24 core, 3.07TB內存[2]. 伺服器提供了強大處理的能力, 可將系統dataset(比如in-memory database)可以全駐於內存, 採用multi-threaded編程, 共享地址空間, 提升計算性能[3][4].

shared memory concurrency涉及三個方面: parallelism, performance和correctnesss.

並行(Parallelism)

並行可加速計算. 通常採用兩種方式[5]:

partitioning: 將數據分割為若干由不同worker管理的partition, 可並行處理不同的partition.
pipelining: 將任務分為若干彼此銜接的stage, 構成pipeline; stage之間通過共享存儲或消息傳遞的方式傳遞中間結果. 多個任務不同stage可活躍於pipeline的不同stage, 獲得inter-stage parallelism; 每個stage的輸入數據或者消息分成若干partition, 由一組計算節點處理, 可獲得intra-stage parallelism.

partitioning和pipelining都可以採用共享存儲的方式, 對數據分而治之, 利用計算節點和數據之間的親俯性(affinity), 提升計算性能.

例子比比皆是, 如:

MapReduce[6]
Apache Storm[7]
Apache Spark[8]
SEDA[9]
h-store[10]
intra-operator/inter-operator parallelism[11].

主要的關切點由:

pipelining採用message passing還是shared storage[12][13]?
intra-stage的多個worker是否需要barrier同步[14][15]?
pipelining採用command-driven dataflow還是data-driven dataflow[16]?

總之並行處理, 普遍存在於不同的計算層級中(集群, 機器, 多處理器, 多核, 指令流水)普遍採用, 不同的應用場景中(AP, TP, ETL), 不同的workload中. 並行化能夠更加有效地利用計算資源, 提升負載, 縮短延遲和提升吞吐.

本文提到的並行處理, 是指在shared memory multiprocessors結構中, 利用多核的並行處理能力, 採用多線程編程, 訪問相同地址空間中的in-memory數據結構.

性能(Performance)

性能

可以三個方面來分析性能:

speedup[1]: 多線程執行相對於單線程執行的加速比, speedup越接近core數越好, 但實際上很難做到.
CPI(cycles per instruction)[1][17]: 執行一條指令花費的CPU周期數, 越少越好.
scalability[3][4]: 吞吐隨著線程/core數目增加而提升, 越接近線性擴展越好.

性能影響因素有:

串列執行: 代碼中critical section和contention point數目很多, critical section所轄粒度太大, 採用了heavy-weight synchronization primitives[3][4].
cache顛簸: CPU分支預測失敗, cache miss頻繁, 反覆invalidate cache等因素導致CPU stall[17].
線程數目增大, 負載上升導致線程間的競爭更加激烈, 影響scale-out能力[3][4].

解決方法:

減少甚至消除critical section, 減少contention point, 採用輕量級的atomic variable或者memory fence進行inter-thread synchronization[18][19].
設計cache friendly演算法[20].

正確性(Correctness)

程序員能夠寫出符合預期結果的程序, 能夠直觀地推知程序的行為.
使用輕量級的同步原語和細粒度的設計, 比重量級和粗粒度鎖要複雜, 容易出錯.
編譯層面的優化可能是基於對單線程的data/control dependency分析, 會冒進地reorder語句.
為了hide store/load latency, 系統可能採用relaxed consistency model. 影響store和load指令program order和write atomicity.
處理器的out-of-order schedule, multiple issue和speculative execution會影響program order.

總之, 有諸多因素破壞了program order和write atomicity[1][18].

解決方法

線程之間通過原子變數進行同步.
插入編程語言或者操作系統提供的{memory, load, store} fence指令以阻止reorder.

總結

程序使用輕量級的同步操作, 設計cache-friendly演算法, 減少contention和CPU stall, 盡最大可能提高speedup和降低CPI, 並且具有線性的scale-out能力.

Speedup和Amdahls Law[1]

Amdahls Law:

一個程序分為若干fraction: F1, F2, …, Fn; 表示執行時間的佔比.

每個fraction的並行度為P1, P2,…,Pn; 表示可並行執行的core數.

speedup為:

speedup = 1 / (F1/P1 + F2/P2 + ... + Fn/Pn)

如果串列執行佔比為f, 則:

speedup < 1/f, (f ≠ 0)

用Amdahls Law可以估算性能提升.

假如在某in-memory OLTP database, 已經通過micro-benchmark得知:

事務平均延遲為1μs;
時間戳分配需100ns並且串列執行;
其餘部分都可以並行執行.

串列執行部分佔比為10%, 採用16 socket * 16 core 機器, speedup為:

speedup = 1 / (0.9 / 16*16 + 0.1) = 9.66使用256core, 性能最多提升9.66倍.

下面兩幅圖, 可說明

只有在串列執行佔比較小的前提下, 增加處理器數量才能顯著提高性能(near-linear scalability).

在圖"Speedup scales over # of cores"中, 串列佔比越大(如10%和50%), near-linear scale的階段越早結束, 隨著core數目上升, speedup迅速收斂(10%, 50%分別對應10, 2). 而佔比1%的曲線, 依然強勁增長. 可以得出結論, speedup收斂之後, 增加核數無法顯著提高speedup.

在圖"Speedup scales over serial fraction"中, 隨著串列佔比增加, speedup開始下降. 當串列佔比較小時(<2%), 則增加核數, 能夠提升性能; 而串列佔比較大時(>8%), 增加核數沒有顯著收益.

Cache miss對性能的影響[1]

CPU速度比main memory訪問速度快; 而且隨著硬體的發展, 速度差異越來越明顯. 比如基本CPI為0.2 cycle. 而存取內存需要100 cycle. 兩者之間增加多級cache以彌補速度差距. cache造價和功耗較高, 相比於內存, 容量較小. cache失效(未命中)時, 訪問memory會造成CPU stall.

a 100% busy CPU could be 95% memory stalled[21].

Cache miss分為四類(4C):

compulsory miss: cache初始時無數據, 需要warmup.
capacity miss: 容量有限, 裝滿之後, 載入其他block, 需要evict掉老數據.
conflict miss: 一個block只能載入到cache的一個set中, set如果滿了, 需要evict掉老數據.
coherence miss: 執行store操作, 廢除其他處理器的cache中的copy.

Cache miss對CPI

CPI = BasicCPI + MemoryAccessPerInstruction *(HitTime + MissRate * MissPenalty) cache的fetch以block為單位, 取指令和存取數的次數平攤到每條指令, 按照MemoryAccessPerInstruction計算.假設: BasicCPI = 0.2 cycle, HitTime = 1 cycle, MissRate = 3%, MissPenalty = 100 cycle, MemoryAccessPerInstruction = 0.3.則: CPI = 1.4 cycle, CPI是原來的7倍.實際上, 如果系統採用L1~L3 cache, 則:CPI = BasicCPI + MemoryAccessPerInstruction * (L1_HitTime + L1_MissRate * (L2_HitTime+ L2_MissRate* (L3_HitTime + L3_MissRate * MemoryAcessTime)))

編譯器生產目標代碼時, 會對寄存器分配進行優化, 減少從內存中存取中間結果.

分支預測失敗, 處理器會排空指令隊里, 重新取指. GCC中用__builtin_expect可以提示編譯器, 將執行頻率高的分支順序執行.

JIT執行器, 也可根據分支執行頻率, 調整機器指令的分支順序.

文獻[20]提到, 在L2 cache顛簸比較嚴重的情況下, 也會對L1 instruction cache造成顯著影響, 需要花費更久的時間從L3或者memory中取指令.

用cache-friendly設計降低cache miss rate

對cache-friendly設計而言, 期望:

clusering: 數據按訪問次序, 聚集在cache line上, 有效利用cache line的大小.
affinity: core/thread親附內存的某一地址範圍.
exclusive: core修改私有exclusive copy, 然後安裝到共享數據結構中. 修改exclusive copy能夠很好地利用latency-hiding技術. 將修改全局數據結構的同步代價平攤到exclusive copy的修改中.

數據如何聚集, 取決於workload. 以資料庫的storage model為例:

NSM (Slotted-page structure)[22]: tuple的欄位存在一起, 利tuple materialization, 不利projection.
DSM (Decomposition Storage Model)[23]: columnar store, 不利tuple materialization, 利projection.
PAX (Partition Attributes Across)[20]: 混合NSM和DSM
Fractured Mirrors[24]: 混合NSM和DSM

skiplist/btree[25]

對in-memory key-value系統而言, skiplist和btree比較, 後者對cache更友好. 通常, 在skiplist, 一個key-value pair佔據小塊內存, 塊的大小取決於payload大小和next指針的數目(隨機高度). 小塊散布, 用指針相連. 搜尋數據時, 指針隨機跳轉. btree中, 可以將多個key-value pair聚集存儲在cache line (64B)中.

hash table

顯然採用數組+二次探測的方法對cache不友好. 可以採用bucket方法, 每個bucket由若干塊組成, 塊的大小採用cache line的整數倍.

affinity[1][4]

工作線程親附cache或者內存的一段連續的地址區間, 能夠減少cache miss. 當使用NUMA或者NUCA結構的機器時, 尤為重要. 工作線程之間盡量彼此獨立, 降低contention. 比如h-store實現, 將內存中的數據結構分成若干partition, 每個partition有一個worker認領. 單個partition的事務, 也無需同步. 修改私有的副本, 也能夠減少coherence開銷.

bw-tree[26]

bw-tree是用cas實現的latch-free B+Tree. 樹結點之間的層級關係用logical pointer(i.e. 結點編號)維護, 通過mapping table, 可以將logical pointer轉為為physical pointer(i.e. 內存地址). 查詢時, 先將root結點的編號轉化為內存地址, 然後訪問root結點, 挑一個子節點的logical pointer, 如此往複… insert/update/delete不原地修改, 而是創建delte塊, 將delta塊通過physical pointer指向old page, 然後用cas修改mapping table中的響應的physical pointer值. 樹的結點由若干delta塊和一個old page組成, 可以採用某種策略對樹的結點進行compaction, 將delta 應用於old page中, 採用垃圾回收釋放已經廢棄的塊.

delta塊為線程私有, 在安裝到mapping table之前, 對其他線程不可見, 因此對delta的寫入操作屬於cas的前置操作, 可以屏蔽掉. (引文中說可以減少cache invalidation, 未必使然).

TLB

TLB miss對性能影響, 後續再研究.

文獻[21]提到, 採用pagesize=4KB, TLB容量是64 entries, 當數據結構的大小超過256KB, TLB miss對性能有明顯的影響.

根據[1], TLB也可以採用多級cache.

shared-memory concurrency涉及的面比較廣, 要說清楚問題, 可能需要一本書的篇幅. 本文主要的目的, 是給出深入學習的roadmap. 可以把整個學校研究的過程看成是拼圖, roadmap能夠說明缺失的圖塊.

Roadmap

roadmap給出了軟體, 系統結構和微結構三個層面的需要考量的問題, 並進一步對每個層面進行了細分.

#1. in-memory OLTP database

面向OLTP的內存資料庫是shared memory concurrency的典型應用領域.

TP和AP相比較, 前者一般無需保存過多的歷史記錄和豐富維度信息, 雖然dataset規模適中, 可全駐內存. 強大的多核計算能力和內存訪問速度, 能夠滿足事務處理的低延遲, 高吞吐的需求. 比如Hekaton[27], Silo[4], TicToc[3]等.

一般地, in-memory database, 也會將系統分為事務處理層和存儲層, 兩者都會用到輕量級同步方法.

存儲層通常採用in-memory concurrent data structure.

#2. shared-memory concurrent data structure

採用並發skiplist, btree或者hash table, 可高效修改,查詢key-value.

concurrent data structure採用prefetch, batch write, multiversion, SIMD, version validation和RCU等方法[4].

concurrent數據結構有: MassTree[28], Fractal Tree[29]和Bw-Tree[30] etc.

#3. software abstract

在實現數據結構的時候, 用已被操作系統或編程語言分裝過的抽象介面, 比依賴處理器的hardware primitives要方便, 前者便於代碼移植, 屏蔽了底層硬體實現細節, 降低了程序員的心智負擔.

比如:

C++ STL: #include<atomic>
Linux: https://www.kernel.org/doc/Documentation/memory-barriers.txt
RCU: https://lwn.net/Articles/262464/

#4. language memory model

編程語言層面, 也會定義多線程訪問共享變數的行為: reordering, atomic operation, visiable side-effect.

C++: http://en.cppreference.com/w/cpp/atomic/memory_order
Go: https://golang.org/ref/mem
Java: https://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4

#5. compile optimization/JIT optimization

不管是編譯執行還是解釋執行, 編譯器和解釋器可能會對最終生成的機器指令, 進行優化. 改變程序的執行順序.

GCC: 可用asm volatile("" ::: "memory")語句避免重排.
JIT: JIT必然會重排和優化代碼, 但是否需要程序員限制過於冒進的優化, 有待進一步學習.

#6. hardware primitives

處理器的指令集提供原子操作和memory fence. 比如x86[31]:

lfencesfencemfencexchgcmpxchglock

其他處理器, 請參考[19]

也可搜索Linux源碼樹:

ag #define.*mb.*asmtools/arch/alpha/include/asm/barrier.h4:#define mb() __asm__ __volatile__("mb": : :"memory")5:#define rmb() __asm__ __volatile__("mb": : :"memory")6:#define wmb() __asm__ __volatile__("wmb": : :"memory")tools/lguest/lguest.c242:#define wmb() __asm__ __volatile__("" : : : "memory")243:#define rmb() __asm__ __volatile__("lock; addl $0,0(%%esp)" : : : "memory")244:#define mb() __asm__ __volatile__("lock; addl $0,0(%%esp)" : : : "memory")tools/arch/powerpc/include/asm/barrier.h25:#define mb() __asm__ __volatile__ ("sync" : : : "memory")26:#define rmb() __asm__ __volatile__ ("sync" : : : "memory")27:#define wmb() __asm__ __volatile__ ("sync" : : : "memory")tools/arch/tile/include/asm/barrier.h11:#define mb() asm volatile ("mf" ::: "memory")tools/arch/x86/include/asm/barrier.h19:#define mb() asm volatile("lock; addl $0,0(%%esp)" ::: "memory")20:#define rmb() asm volatile("lock; addl $0,0(%%esp)" ::: "memory")21:#define wmb() asm volatile("lock; addl $0,0(%%esp)" ::: "memory")23:#define mb() asm volatile("mfence":::"memory")24:#define rmb() asm volatile("lfence":::"memory")25:#define wmb() asm volatile("sfence" ::: "memory")tools/arch/mips/include/asm/barrier.h10:#define mb() asm volatile( ools/arch/arm64/include/asm/barrier.h12:#define mb() asm volatile("dmb ish" ::: "memory")13:#define wmb() asm volatile("dmb ishst" ::: "memory")14:#define rmb() asm volatile("dmb ishld" ::: "memory")tools/arch/sh/include/asm/barrier.h25:#define mb() __asm__ __volatile__ ("synco": : :"memory")tools/arch/s390/include/asm/barrier.h25:#define mb() do { asm volatile(__ASM_BARRIER : : : "memory"); } while (0)tools/arch/xtensa/include/asm/barrier.h14:#define mb() ({ __asm__ __volatile__("memw" : : : "memory"); })tools/arch/sparc/include/asm/barrier_64.h39:#define rmb() __asm__ __volatile__("":::"memory")40:#define wmb() __asm__ __volatile__("":::"memory")tools/testing/selftests/powerpc/dscr/dscr.h39:#define rmb() asm volatile("lwsync":::"memory")40:#define wmb() asm volatile("lwsync":::"memory")tools/testing/selftests/powerpc/include/reg.h19:#define mb() asm volatile("sync" : : : "memory");arch/alpha/include/asm/barrier.h6:#define mb() __asm__ __volatile__("mb": : :"memory")7:#define rmb() __asm__ __volatile__("mb": : :"memory")8:#define wmb() __asm__ __volatile__("wmb": : :"memory")arch/frv/include/asm/barrier.h17:#define mb() asm volatile ("membar" : : :"memory")18:#define rmb() asm volatile ("membar" : : :"memory")19:#define wmb() asm volatile ("membar" : : :"memory")arch/frv/include/asm/io.h43://#define __iormb() asm volatile("membar")44://#define __iowmb() asm volatile("membar")arch/powerpc/include/asm/barrier.h33:#define mb() __asm__ __volatile__ ("sync" : : : "memory")34:#define rmb() __asm__ __volatile__ ("sync" : : : "memory")35:#define wmb() __asm__ __volatile__ ("sync" : : : "memory")45:#define dma_wmb() __asm__ __volatile__ (stringify_in_c(SMPWMB) : : :"memory")51:#define __smp_wmb() __asm__ __volatile__ (stringify_in_c(SMPWMB) : : :"memory")arch/arm/include/asm/barrier.h18:#define dmb(option) __asm__ __volatile__ ("dmb " #option : : : "memory")24:#define dmb(x) __asm__ __volatile__ ("mcr p15, 0, %0, c7, c10, 5" 31:#define dmb(x) __asm__ __volatile__ ("" : : : "memory")36:#define dmb(x) __asm__ __volatile__ ("" : : : "memory")arch/arc/include/asm/barrier.h29:#define mb() asm volatile("dmb 3 " : : : "memory")30:#define rmb() asm volatile("dmb 1 " : : : "memory")31:#define wmb() asm volatile("dmb 2 " : : : "memory")41:#define mb() asm volatile("sync " : : : "memory")47:#define mb() asm volatile (".word %0" : : "i"(CTOP_INST_SCHD_RW) : "memory")48:#define rmb() asm volatile (".word %0" : : "i"(CTOP_INST_SCHD_RD) : "memory")arch/x86/um/asm/barrier.h26:#define mb() asm volatile("mfence" : : : "memory")27:#define rmb() asm volatile("lfence" : : : "memory")28:#define wmb() asm volatile("sfence" : : : "memory")arch/x86/include/asm/barrier.h14:#define mb() asm volatile(ALTERNATIVE("lock; addl $0,0(%%esp)", "mfence", 16:#define rmb() asm volatile(ALTERNATIVE("lock; addl $0,0(%%esp)", "lfence", 18:#define wmb() asm volatile(ALTERNATIVE("lock; addl $0,0(%%esp)", "sfence", 21:#define mb() asm volatile("mfence":::"memory")22:#define rmb() asm volatile("lfence":::"memory")23:#define wmb() asm volatile("sfence" ::: "memory")arch/sh/include/asm/barrier.h27:#define mb() __asm__ __volatile__ ("synco": : :"memory")33:#define __smp_mb() do { int tmp = 0; __asm__ __volatile__ ("cas.l %0,%0,@%1" : "+r"(tmp) : "z"(&tmp) : "memory", "t"); } while(0)arch/mips/include/asm/barrier.h206:#define smp_llsc_mb() __asm__ __volatile__(__WEAK_LLSC_MB : : :"memory")arch/arm64/include/asm/atomic_ll_sc.h58:#define ATOMIC_OP_RETURN(name, mb, acq, rel, cl, op, asm_op) 80:#define ATOMIC_FETCH_OP(name, mb, acq, rel, cl, op, asm_op) 152:#define ATOMIC64_OP_RETURN(name, mb, acq, rel, cl, op, asm_op) 174:#define ATOMIC64_FETCH_OP(name, mb, acq, rel, cl, op, asm_op) arch/arm64/include/asm/barrier.h31:#define dmb(opt) asm volatile("dmb " #opt : : : "memory")arch/arm64/include/asm/atomic_lse.h49:#define ATOMIC_FETCH_OP(name, mb, op, asm_op, cl...) 246:#define ATOMIC64_FETCH_OP(name, mb, op, asm_op, cl...) arch/xtensa/include/asm/barrier.h12:#define mb() ({ __asm__ __volatile__("memw" : : : "memory"); })arch/unicore32/include/asm/barrier.h15:#define dmb() __asm__ __volatile__ ("" : : : "memory")arch/s390/include/asm/barrier.h23:#define mb() do { asm volatile(__ASM_BARRIER : : : "memory"); } while (0)arch/sparc/include/asm/barrier_64.h37:#define rmb() __asm__ __volatile__("":::"memory")38:#define wmb() __asm__ __volatile__("":::"memory")

# 7.memory consistency model[1][5][19]

多個processor訪問多個shared memory location必須遵守的規則.

處理器訪問私有memory location (local scoped變數和TLS), 編譯器和處理器優化能夠保持data dependency/control dependency[1].

多處理器在保證control/data dependency的前提下, 容許單個處理器對不同memory location的操作進行重排, 可能產生不一致的結果.

例如: 下面代碼中, 直觀上(x,y)可取(1,1), (0, 1)和(1, 0); 但也可能取到(0, 0).

a = 0;b = 0;x = 0;y = 0;processor1: a = 1; x = b;processor2: b = 1; y = a;

處理器其實難以區分, 存取指令所謂訪問的memory location是私有還是共享. 對於uniprocessor, 重排是可接受的; 對於multiprocessor, 重排會出現非預期的結果.

在談到memory consistency model時, SC(sequential consistency)[32][33][34]首先會被提及. SC有很多等價的表述方法.

SC除了單個處理器保證control/data dependency之外, 還需要添加兩個條件:

program order requirement: 單處理器訪問不同memory location, 需要保證program order.
write atomicity requirement: 多處理器訪問相同memory location, 要等待outstanding write操作完成後進行.

後面的所有討論, 都假定cache採用write-back方式.

當多個處理器在私有cache中有數據的shared copy時, 其中一個處理器修改數據, 其他處理器如果不等待該處理器完成而讀取stale的結果, 會產生不一致的結果.

SC和Linearizability[34]不同的時, 操作不必在invocation和reponse之間生效. 操作生效時間點可以延遲到reponse之後, 但依然需要滿足:

操作是逐個生效的.
單個處理器的操作是按照program order的順序生效的.

這就說明, 可以採用一些hide store/load latency的技術, 提前返回, 插入一些修改私有數據的存取指令或者非訪存的指令執行.

SC是程序正確性的保證, 但是究竟哪些存取指令需要遵從SC呢? 這是一個值得商榷的問題.

其實, 只要保證存取共享的memory location的SC即可.

如果把存取共享的memory location的操作分為兩類: data operation和synchronization operation. 假如採用的synchronization operation為smp_mb, smp_wmb和smp_rmb.

smp_wmb之前代碼不能挪到smp_wmb之後執行.
smp_rmb之後代碼不能挪到smp_wmb之後執行.
smp_mb相當於smp_wmb+smp_rmb的效果.

顯然單處理器上的synchronization operation的執行按照program order, data operation相對於synchronization operation的執行順序也按照program order, 但是相鄰的data operation操作可以reorder, 而且smp_wmb之後的代碼也容許挪到smp_wmb之前, smp_rmb之前的代碼, 也可以挪到smp_rmb之後.

這樣一來, 並非所有存取指令需遵從SC. 可以放寬program order requirement和write atomicity requirement. relaxed memory model就是指這兩個條件的放寬[5].

結論

uniprocessor的指令調度保證data/control dependency,

multiprocessor通過synchronization保證先後次序,

uniprocessor的data operation和synchronization operation要保證相對的program order,

processor提供atomic operation和memory fence用於synchronization,

programmer決定atomic operation和memory fence插入的位置.

容許相鄰的data operation在保證data/control dependency的前提下, 重排.

比如[5]:

TSO (Total Store Ordering): 容許W-R重排.

PSO (Partial Store Ordering): 容許W-R, W-W重排.

WO (Weak Ordering): 容許W-R, W-W, R-W, R-R重排.

#8.hide store/load latency[1][19]

接著前文提及SC容許processor存取操作在生效之前返回, 存取指令可以相互overlapping.

Time-shared common bus

multiprocessor和私有cache之間通過shared bus連接, uniprocessor的存取操作需要分時互斥地持有匯流排, 直到操作完成. 此方式簡單直觀, 能夠很好地保證write atomicity, 卻性能不好.

寫操作:

processor: P0,P1和P21. P0申請並獲得匯流排2. P0修改cache line3. P0廣播invalidate msg給P1和P24. P1和P2收到invalidate msg後, 標記相應的cache line為invalid, 然後恢復ack.5. P0收到來自P1和P2的invalidate ack.6. P0釋放匯流排.

讀操作:

processor: P0,P1和P21. P1因為匯流排佔用,而持續等待, 直到匯流排空閑, 仲裁邏輯授予P1匯流排的使用權.2. P1發送地址, 讀cache line.3. 如果cache line被標記為invalid或者read miss, 則從其他下一級cache或其他處理器的私有cache獲取copy.4. P1從載入完up-to-date copy到cache line中獲取地址指定的數據.5. P1釋放匯流排.

匯流排互斥訪問的方法保證write atomicity, 會引入CPU stall.

引入store buffer(也有文獻提到write buffer)

store buffer相當於queue, 用於保存processor的store操作.

processor執行store fence指令, 標記store buffer中的現有的store操作.

可以採用計數器, 或者直觀上想像, 執行store fence指令, 就是在store buffer的隊尾插入一個barrier標記.

store buffer中, 只有當store fence的前置的操作flush到cache之後, 後置的操作才能flush.

processor只有收到其他processor的關於store操作invalidate ack之後, 才能將該store操作flush到cache中.

所以:

processor執行store fence指令, 向store buffer插入fence標記.
processor執行store指令, 如果目標cache line不處於Modified/Exclusive狀態或者store buffer中有fence標記, 則將store操作放入store buffer中.
否則, 說明目標cache為processor所獨享並且無必須前置完成的store操作, 則直接修改cache.

store fence並不是意味著清空store buffer, 而是保證fence標記前後的store操作的生效順序. 生效是指:

其他processor的cache已經感知到store操作, 並且設置cache line為invalid;
store指令的發起者將操作flush到cache中.

引入invalidate queue

收到invalidate msg的, processor將msg放入invalidate queue中, 然後及時向store操作的發起者發送ack.

processor可以後續處理invalidate msg, 將cache line置為invalid.

同樣地, processor可執行load fence在invalidate queue中插入fence標記. 當processor發起load操作時, 如果有前置的invalidate msg, 則stall直到前置的cache line被置為invalid.

處理器會通過memory fence指令, 兼具store fence和load fence的效果.

#9. cache coherence protocol

coherence和consistency有什麼區別呢?

[1]p.411: Coherence defines the behavior of reads and writes to the same memory location, while consistency defines the behavior of reads and writes with respect to accesses to other memory locations.

coherence是指multiprocessor存取同一個memory location, 所有processor感知到相同的訪問次序.

所修改的目標copy在以shared狀態載入在其他處理器中, 需要發送invalidate msg讓其失效. 其他處理器後續讀該copy時, 發現狀態為invalid, 能夠觸發read miss, 重新fetch數據.

consistency是指multiprocessor把用於synchronization operation的memory location作為data operation生效次序的參考.

如果兩個processor訪問的memory location毫無交集, 則無需同步; 即便有共享的memory location, 不關心存取操作發生的次序是否被所有processor觀察到相同次序, 也無需同步.

比如: 不同processor中成對出現的release-acquire. release修飾的store操作的結果, 被acquire修飾的load操作讀到, 則前者必然先於後者發生. 並且: (→表示happen before)

release前置操作 → release操作;

acquire操作 → acquire後置操作;

release操作 → acquire操作;

必然:

release前置操作 → acquire操作

cache coherence protocol協議分為三類:

invalidate-based protocol(snooping protocol)
directory-based protocol
update-based protocol

只有處理器的私有cache, 如L1和L2, 會擁有同一個block的各自的copy, 需保持一致. 共享cache, 如L3, 則無需考慮.

下文提到的coherence協議, 均採用write-back策略.

invalidate-based protocol

前文已多次提及.

簡言之: 發起store操作處理器, 向其他所有處理器廣播invalidation msg, 等待其他處理器設置copy為invalid狀態並回復ack msg. 所有的處理器除了需要探聽(snoop名字的由來) invalidate msg, 還需要探聽read/write miss msg, 當處理器探聽到cache miss消息後, 如果處理器自身擁有目標地址的copy已經處於Modified狀態; 需要write-back該copy到共享存儲器中, 或者直接forward該copy給cache miss的觸發者.

invalidate-based protocol有很多變種, 根據cache維護的狀態命名. 文獻[19]提到, cache實現比模型更複雜, 可能會維護數十狀態.

1. MSI (Modified, Shared, Invalid)[1]

除了Modified狀態外, store操作的請求者廣播invalidate msg.requestor遇到cache miss, 從下級共享存儲器傳輸數據.Modified狀態偵聽到cache miss, 要write-back到下級共享存儲器.

2. MESI (Modified, Exclusive, Shared, Invalid)[1]

Exclusive狀態是MSI中Shared狀態的一種.當processor是唯一sharer時, 則cache line處於Exclusive狀態.修改Exclusive狀態不必廣播invalidate msg.Exclusive狀態的cache line被修改後, 轉化為Modified狀態.cache miss的處理同MSI.

3. MESIF (Modified, Exclusive, Shared, Invalid, Forward)[1][35]

廣播invadidate msg的處理同MESIF.Forward是一種特殊的Shared狀態, 最多指定一個sharer為Forward狀態.如果偵聽到cache miss, 則Forward狀態的processor採用cache-to-cache傳輸數據.cache-to-cache傳輸, 比從下級共享存儲器傳輸數據要快.

4. MOESI (Modified, Owned, Exclusive, Shared, Invalid)[1][35]

Owned是特殊的Modified狀態, 表示下級共享存儲器中的數據已經out-of-date.廣播invalidate msg的處理同MESI.如果偵探到cache miss, 則Owned狀態的processor採用cache-to-cache傳輸數據.

顯然, 減少snoop代價, 採用cache-to-cache transfer可以改善性能.

snooping協議的主要問題是要向所有的處理器廣播invalidate msg, 並且所有的處理器需要偵聽cache miss/invalidate msg, 需要佔用過多interconnection network的帶寬, 所以scalability較差. 相較於directory-based protocol, 支持的處理器數目較少.

directory-based protocol[1]

directory協議也需要在store的時候, 將其他shared copy標記為invalid. 但只需要將invalidate msg發送給shared copy即可; 因此, interconnection的帶寬競爭不如invalidate激烈.

將下級共享存儲器(比如L3 cache)的block在狀態信息保存directory中, directory entry可看做bitvector, 每個bit對應一個處理器, 表示是否位於處理器的私有cache中. 顯然, 根據bitvector的信息, 結合cache line的狀態信息, 可以判斷是否需要發送invalidate msg, 以及向誰點對點的發送.

採用centralized directory, 隨著處理器的數目上升, 多處理器競爭會更加激烈. 因此, 採用distributed directory.

所以, 為了支持更多數目的處理器, 往往採用NUMA或者NUCA的系統結構. 將main memory或者L3 cache劃分給多處理器, 每個處理器本地訪問速度快於異地訪問. 存儲器分區的對應的directory entry也有同一個處理器認領.

update-based protocol

實現思路類似RSM, overhead比較高, 不再贅述, 可參考文獻[5]

#10.SMP/DSM和interconnection network [1]

處理器, 存儲模塊之間傳遞消息的媒介, 稱為interconnection network.

主要類型有:

time-shared common bus
multiport memory
crossbar switch
multistage switch
hypercube

point-to-point(除time-shared common bus)的方式, 能夠提供多個消息通路, 在設計上比bus複雜, 但可獲得更高的帶寬.

處理器, 多級cache和main memory可以組合方式有:

SMP (Symmetric Multiprocessors): centralized organization of main memory/outermost cache.
NUCA (Nonuniform Cache Access): centralized main memory, distributed outermost cache.
NUMA (Nonuniform Memory Access): distributed main memory.

SMP和NUCA, NUMA都採用shared memory, i.e. 所有的處理器可以訪問整個地址空間.

這裡的中心化/分散式的區別不在於memory的bank數量, 而是指將memory劃片後, 分給處理器. 處理器訪問自己本地分片, 只會經過自己cache; 訪問異地分片, 需要請求別的處理器forward. 所以, 訪問本地數據的延遲比異地數據要低. 上層應用可以利於處理器和本地分片的親和性, 讓處理器儘可能訪問本地數據.

#11. Instruction-Level Parallelism[1]

ILP涉及處理器的設計和實現, 從程序員的角度理解:

指令通過pipeline並行疊加執行.
能夠保證data/control dependency.
必要時, 程序員要用synchronization operation(atomic, fence)限制指令的out-of-order調度.

文獻[1]對ILP做了非常詳盡的分析.

參考文獻

[1] J. L. Hennessy and D. A. Patterson, 「Computer architecture: a quantitative approach,」 2011.

[2] https://ark.intel.com/products/96900/Intel-Xeon-Processor-E7-8894-v4-60M-Cache-2_40-GHz

[3] X. Yu, A. Pavlo, D. S. 0003, and S. Devadas, 「TicToc - Time Traveling Optimistic Concurrency Control.,」 SIGMOD Conference, pp. 1629–1642, 2016.

[4] S. Tu, W. Zheng, E. Kohler, B. Liskov, and S. Madden, 「Speedy transactions in multicore in-memory databases.,」 SOSP, pp. 18–32, 2013.

[5] S. V. Adve and K. Gharachorloo, 「Shared memory consistency models: A tutorial,」 computer, vol. 29, no. 12, pp. 66–76, 1996.

[6] J. Dean and S. Ghemawat, 「MapReduce: simplified data processing on large clusters,」 Communications of the ACM, vol. 51, no. 1, pp. 107–113, 2008.

[7] http://storm.apache.org/releases/2.0.0-SNAPSHOT/index.html

[8] M. Zaharia, R. S. Xin, P. Wendell, T. Das, M. Armbrust, A. Dave, X. Meng, J. Rosen, S. Venkataraman, and M. J. Franklin, 「Apache spark: a unified engine for big data processing,」 Communications of the ACM, vol. 59, no. 11, pp. 56–65, 2016.

[9] M. Welsh, D. Culler, and E. Brewer, 「SEDA: an architecture for well-conditioned, scalable internet services,」 vol. 35, no. 5, pp. 230–243, 2001.

[10] M. Stonebraker, S. Madden, D. J. Abadi, S. Harizopoulos, N. Hachem, and P. Helland, The end of an architectural era: (its time for a complete rewrite). VLDB Endowment, 2007, pp. 1150–1160.

[11] http://15721.courses.cs.cmu.edu/spring2016/slides/10.pdf

[12] D. Peng, F. D. OSDI, 2010, 「Large-scale Incremental Processing Using Distributed Transactions and Notifications.,」 http://usenix.org.

[13] O. Shacham, F. Perez-Sorrosal, E. B. P. O. T. 15th, 2017, 「Omid, reloaded: scalable and highly-available transaction processing,」 http://usenix.org.

[14] https://en.wikipedia.org/wiki/Bulksynchronousparallel

[15] G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski, 「Pregel: a system for large-scale graph processing,」 pp. 135–146, 2010.

[16] G. Graefe, Volcano: An Extensible and Parallel Query Evaluation System. 1989.

[17] B. Gregg, 「Systems performance: enterprise and the cloud,」 2013.

[18] S. V. Adve and K. Gharachorloo, 「Shared memory consistency models: A tutorial,」 computer, vol. 29, no. 12, pp. 66–76, 1996.

[19] P. E. McKenney, 「Memory barriers: a hardware view for software hackers,」 Linux Technology Center, IBM Beaverton, 2010.

[20] A. Ailamaki, D. J. DeWitt, M. D. Hill, M. S. VLDB, 2001, 「Weaving Relations for Cache Performance.,」 http://vldb.org.

[21] P. A. Boncz, M. L. Kersten, and S. Manegold, 「Breaking the memory wall in MonetDB,」 Communications of the ACM, vol. 51, no. 12, pp. 77–85, 2008.

[22] A. Silberschatz, H. F. Korth, and S. Sudarshan, Database System Concepts. McGraw-Hill Education, 2011.

[23] D. J. Abadi, S. R. Madden, N. H. P. O. T. 2. ACM, 2008, 「Column-stores vs. row-stores: how different are they really?,」 http://dl.acm.org.

[24] R. Ramamurthy, D. J. DeWitt, Q. S. T. V. Journal, 2003, 「A case for fractured mirrors,」 Springer.

[25] http://15721.courses.cs.cmu.edu/spring2016/slides/06.pdf

[26] http://15721.courses.cs.cmu.edu/spring2016/slides/07.pdf

[27] P.-?. Larson, S. Blanas, C. Diaconu, C. Freedman, J. M. Patel, and M. Zwilling, 「High-Performance Concurrency Control Mechanisms for Main-Memory Databases,」 http://arXiv.org, vol. cs.DB. 31-Dec-2011.

[28] Y. Mao, E. Kohler, and R. T. Morris, 「Cache craftiness for fast multicore key-value storage,」 EuroSys 12, pp. 183–196, 2012.

[29] M. A. Bender, M. Farach-Colton, J. T. Fineman, Y. R. Fogel, B. C. Kuszmaul, and J. Nelson, 「Cache-oblivious streaming B-trees,」 pp. 81–92, 2007.

[30] J. J. Levandoski, D. B. Lomet, and S. Sengupta, 「The Bw-Tree: A B-tree for new hardware platforms,」 pp. 302–313, 2013.

[31] Intel Corporation, 「Intel? 64 and IA-32 Architectures Software Developer』s Manual Volume 2 (2A, 2B, 2C & 2D): Instruction Set Reference, A-Z,」 pp. 1–2226, Mar. 2018.

[32] H. Attiya, J. W. A. T. O. C. S. TOCS, 1994, 「Sequential consistency versus linearizability,」 http://dl.acm.org.

[33] L. L. I. T. O. computers1979, 「How to make a multiprocessor computer that correctly executes multiprocess progranm,」 http://ieeexplore.ieee.org.

[34] M. P. Herlihy, J. W. A. T. O. P. Languages, 1990, 「Linearizability: A correctness condition for concurrent objects,」 http://dl.acm.org.

[35] https://en.wikipedia.org/wiki/MESIF_protocol

[36] https://en.wikipedia.org/wiki/MOESI_protocol