Parallel Thinking

動機

平行的思考

Concurrent computing & Parallel computing & Distributed computing

其實就共用資源、與各個計算單元之間要溝通這件事而言，他們其實差不多

但如果還是要分的話 Parallelism: 多個core同時跑 Concurrency: 因為同時/交互執行/節點失敗/節點不可靠所造成的效果(non-determinacy)

Parallel computing & Distributed computing

其實就共用資源、與各個計算單元之間要溝通這件事而言，他們其實差不多

但Distributed computing更重視HA的部分

平行化就是在 => Coordination

Communication: 傳送結果到其他點
Load Balancing: 工作量不能差太大
Synchronization: 要等其他點到一定程度

用一般演算法的話來說就是D&Q，所以怎麼divide?

Task-parallelism & Data-parallelism

Task-parallelism: 各種任務(像新年大掃除有掃廁所、清廚房…)，不同core做 Data-parallelism: 不同core做類似的任務，像多段下載

目前沒有一個好的方式把serial prog轉成Parallel prog 所以要自己寫!!

因為task吃題目，所以這裡只看Data-parallelism

2 parallel models (+ 1 model)

model的要素

Control
- 如何達成平行化
- operation之間的怎麼協調執行順序
Data
- 那些資料是 private 是 shared
- 怎麼存取shraed data
Synchronization
- 有哪些operation
- 那些是atomic
Cost
- 有什麼成本

Shared Memory

Control
- 如何達成平行化
  - thread當成抽象的processor
  - 可以自由地創thread
- operation之間的怎麼協調執行順序
  - 讀寫shared memory
  - 透過Synchronization做協調(coordinate)
Data
- 那些資料是 private 是 shared
  - private: 在thread內的
  - shared: 在thread外的
- 怎麼存取shraed data
  - 直接讀寫mem
Synchronization
- 有哪些operation
  - Synchronization
    - semaphore
    - mutex
    - busy-waiting
  - 協調
    - condition variable
- 那些是atomic
  - 就是atomic與thread操作
Cost
- 有什麼成本
  - 創thread
  - context switch

Race Condition

每次跑，結果可能會不同

優缺點

優點
- 溝通方式簡單
  - mem讀寫
缺點
- 需要Synchronization機制
- 不好scale
- 處理cache很頭痛 (cache Coherence)

Message passing

Control
- 如何達成平行化
  - 有許多獨立的processor
- operation之間的怎麼協調執行順序
  - send/receive pairs
    - 在溝通時剛好完成協調
Data
- 那些資料是 private 是 shared
  - private: processor內的資料
- 怎麼存取shraed data
  - 沒有shared data，要透過send/receive pairs
Synchronization
- 有哪些operation
  - 不用
- 那些是atomic
  - 不用
Cost
- 有什麼成本
  - 溝通時的delay
    - 溝通的方式: 網路, mem
    - 怎麼接收: poll, interrupt

優缺點

優點
- 明確溝通
- 不用特別為cache頭痛
缺點
- 溝通的成本很高
- 不好寫 (??)

Shared Memory & Message passing

communication Turing complete
- 彼此可以互相實作對方的模型

除了divide，還可以一次處理多一點: Data Parallel

像是array不是一次處理一個，或是讓thread分別處理每個段

現在是直接處理整個array!!

Parallel Algo的手法

把任務切出來，讓其他人去做 (Divide-and-conquer)
讓一次處理的資料變多 (對array之類的collection操作)
Contraction (縮點、上rank)
Randomization
Identifying independent sets
Pointer jumping

parallel primitives

map
reduce: reduce, min, max, sum, …
scan: prefix sum
filter
- 其實是由 map, scan, map構成
  - map給的predicate
  - scan做prefix sum (counting sort)
  - 利用第1步與第2步的array去生array

從FP來的，在mapreduce後廣為人知

Parallel Algo的BigO

work: sequential 跑的時間複雜度 (只有一顆core)
span: 如果有很多core跑時，最長的時間複雜度 (有很多顆core)
- 怎麼樣叫Parallel，怎麼樣叫Sequential
  - fully Sequential: for (i : range(A)) A[i] = f(A[i-1])
    - 這個span是A
  - fully Parallel: for (i : range(A)) A[i] = f(A[i])
    - 這個span是1
  - partially Parallel: for (i : range(A)) A[i] = f(A[i-sqrt(len(A))])
    - 這個span是sqrt(A)
speed-up: work/span

所以實際的時間複雜度 (Tp)，一定介於兩者之間 work <= Tp <= span

之後有個神奇公式，可以求漸近的Tp，P是核心數， Tp = O(work/P + span)

這邊可以配合後面的測量指標(尤其是Amdahl’s Law) 一起看

例子: findMin on Tree

def findMin(root):
    if not root:
        return float('-inf')
    else:
        return min(root.data, findMin(root.left), findMin(root.right))

work:

if n = 1
    O(1)
else
    O(left) + O(right) + O(1)

span:

if n = 1
    O(1)
else
    max(O(left) + O(right)) + O(1)

所以需要知道實際的input，才知道實際的複雜度

Degenerate Tree(就是list)
- work: O(n)
- span: O(n)
Perfect Tree(平衡樹)
- work: O(n)
- span: O(log n)

測量指標

speedup: serial執行的時間對上Parallel執行的時間的比率
- 線性speedup
  - speedup 剛好等於核心數
  - 也就是隨著核心數上去速度就會上去
efficiency: speedup的比率除上核心數，也就是每個核心促進了多少進步
scalability: 資料量上升，核心數上升就能讓efficiency不變
- Strongly scalable
  - 核心數上升，資料量不變，efficiency不變
- Weakly scalable
  - 核心數上升，資料量上升，efficiency不變

隨著核心數上升，performance可以提升到多少?

performance有兩個面向，latency與throughput

s是serial的比例(就是1-p)，p是parallel的比例(就是1-s)，n是核心數

兩個面向關注的點不同，

一個是關注能減少多少時間
- Amdahl’s Law
  - speedup = (s+p) / (s+(p/n)) = 1 / (s+(p/n))
    - n帶無限，可以得到1/s
  - 假設
    - 溝通時沒有成本
    - 問題大小固定
一個看能多處理多少工作
- Gustafson’s Law
  - (s+n*p) / (s+p) = (1-p)+n*np = 1+(n-1)*p
  - 假設
    - 處理時間固定

到處都是平行化

processor

Instruction Level Parallelism (ILP)

讓一次處理的資料變多
- 指令 (把指令想像成一條長帶子)
  - 把帶子空隙填滿: 總throughput不變，latency變小
    - Out of Order Execution
      - stall時跑指令
      - Out-of-order execution => out-of-order completion
    - Pipelining
      - 把工作流程分段
      - 各種harzard
        Structural hazards: 同時想用同一個phase
        Data hazards
        Read-after-write: 完成寫入前讀值
        沒辦法在不犧牲latency的方式下處理
        處理方式
        stall
        Write-after-read: 完成讀值前寫入
        Write-after-write: 完成第一個寫入前寫入
        處理方式
        ooo execution
        register renaming
        forwarding (cps)
        Control hazards
        猜、猜、猜
        Speculative Execution
        猜分支、指令相依性、數字
        猜錯要整個重來
  - 把帶子疊到帶子上(1 x n到2 x 0.5n): 總throughput變大，latency變小
    - Superscalar: 可以同時跑很多指令
      - 原本是scalar，也就是只操作一條指令/資料單位
    - VLIW (Very Long Instruction Word): 把沒有相關的指令包在一起跑
      - 由compiler指定什麼指令可以一起跑
- 資料
  - Vector Processing/SIMD (Single Instruction Multiple Data)
    - 以array為單位去操作了 (原本是一次一個，做好幾次)
    - programmer要自己寫，compiler或是cpu不會自己轉換
    - Multimedia Extensions
      - 把一部分的reg當成array
        像把32 bits的reg當成兩個16 bits的array

Superscalar & VLIW

與Superscalar差在compiler的輸出，一個是parralel，一個是serial code

所以VLIW compiler需要做binder把call分配到下面的執行單元，Superscalar是留給硬體

Thread-Level Parallelism (TLP)

thread origin
- real processor
  - Hardware
- illusion: 在某個時間後就切到另一個thread
  - Hardware
  - OS
  - user-level (PL的library)
thread creation
- cobegin/coend: 這塊(procedure)可以平行的跑
- fork/join: fork出去的(procedure或function)會平行的跑
- future: 這段code(expression)會平行的跑
thread Scheduling
- 底層決定他什麼時候跑 (thread switch)
  - fine grain: thread主動交棒
  - coarse grain: thread stall, 其他thread可以跑等等
- 可以指定affinity
- 或是用user-level thread
too many thread!
- 創thread要$$
  - mem
  - cpu的cycle
- Sol
  - thread pool或是固定thread數量
  - 復用main thread
    - before: A.fork(); B.fork(); A.join(); B.join();
    - after: A.fork(); B.run(); A.join();

TLP + ILP

把TLP的thread當成填充ILP發生stall的指令來源

summary

Memory System

與cpu相比，ram的速度太慢了!!
- Locality
  - 8/2法則: 最常用到的只有一點點
    - 從古至今，hardware依舊靠locality加速
  - Temporal Locality (Locality in Time)
    - loop
  - Spatial Locality (Locality in Space)
    - array
- Memory Hierarchy
  - 越慢的放越遠

hardware Architecture

把多個處理單元放在一起，一起處理問題

重點是?
- 資源分配
  - 有什麼處理單元? cpu? gpu?
  - 多少mem
- communication的成本
  - Data access, Communication and Synchronization
  - 從Power與latency (所有效能面向)，communication是最貴的部分
Architecture的分類
- Single-instruction single-data (SISD)
- Single-instruction multiple-data (SIMD)
- Multiple-instruction multiple-data (MIMD)
- Multiple-instruction single-data (MISD)
總的來說

Shared-memory Architectures

任何cpu都能access到任何mem
透過mem操作溝通
兩種類型
- Uniform Memory Access
  - Symmetric Multiprocessor (SMP)
  - Cache Coherence
    - 每個cpu都有自己的cache
    - 如果有人改到mem的值，其他cache怎麼辦
    - Sol: Coherence Protocol
      - 去invalidate其他cache
- Non-Uniform Memory Access
  - Distributed shared memory
    - 所以access到mem的時間會有所不同!!
      - Coherence not Enough!!
        傳輸有delay的話…
      - Sol: Memory Consistency Model
        執行某個記憶體操作，誰看的到這個改動
        Sequential Consistency
        每個指令都是atomic!!
        還有其他的，在介紹lockfree時再提

Coherence & Consistency

Coherence
- read會拿到什麼值
  - 別人寫了，(cache)拿到的值是不是對的
- behavior to same location
Consistency
- 什麼時候會拿到寫入的值
  - 寫之後，要一直read到某一次或是第一次之後才會看到
- behavior to other locations

Distributed-memory Architectures

processor有自己的mem
mem不與其他人共享

software Programming

Shared-Memory Model

變數(mem)分成shared與private
Explicit v.s. Implicit Threads Programming
- Explicit: pthread
  - 創thread
    - 用API創
    - programmer創thread與管理thread
  - 分配工作
    - programmer自己寫
  - sync (等待thread完成)
    - 手動join
- Implicit: openMP
  - 創thread
    - 用directives
    - runtime創thread與管理thread
  - 分配工作
    - 用directives
  - sync (等待thread完成)
    - 在區塊結束的地方等
Nondeterminism: race condition
- mutex
- busy-waiting
- semaphore
- Transactional memory
Thread Safety
- serial function在multi-thread能不能正常跑
- 反例: strtok
  - 他有static去存目前string處理到哪邊，如果被多thread call…

Distributed-Memory Model

process有自己的mem
mem不與其他人共享
各個process之間有rank作類似addr的功用
有另外的超能力
- Broadcast: 把val推到其他process
- Reduction: 把其他process的output整合
One-Sided Communication
- 只更新一個mem的值
  - 跟新local，from remote process
  - 跟新remote，from local process

Programming Hybrid Systems

Partitioned Global Address Space Languages
- allow the user to use some shared-memory techniques
  - for programming distributed-memory hardware
- 跨local的mem access十分慢!!

Shared memory programing

3 synchronization scenarios

critical section

多thread共同修改某一變數，就是critical section

Busy-waiting

可能是reorder的受害者

    y = f(id)
    while (flag != id) ;
    x += y
    flag++

    // order
    y = f(id)
    x += y
    while (flag != id) ;
    flag++

會把一顆cpu吃掉 (spin lock)

mutex

就是mutex，在real time可以有priority promotion處理priority inversion

Semaphore

acc就是還有多少個空位的意思

原本: acc + queue posix: acc

Semaphores vs Mutexes

Semaphore不管ownership，只要有人call semaphore，semaphore就會變

Producer-Consumer Synchronization (no critical section)

沒有critical section
- No competition synchronization
- 為了合作而synchronization (Cooperation synchronization)

barrier

要所有thread在同一時間啟動(或是停在同一個點)

像是debug或是計時會用到

用busy-waiting與mutex

mutex.lock()
acc += 1
mutex.unlock()
while acc < cnt_of_threads:
    pass

吃爆cpu(busy waiting)
怎麼做第2個barrier?
- reset acc? 要考慮有沒有reset acc對

用Semaphores

一個數有幾個process (count_sem, 1) (其實應該可以用atomic)

一個數負責停下process (barrier_sem, 0)

sem_wait(&count_sem);
if (counter == thread_count−1) {
    counter = 0;
    sem_post(&count_sem);
    for (j = 0; j < thread_count−1; j++)
        sem_post(&barrier_sem);
} else {
    counter++;
    sem_post(&count_sem);
    sem_wait(&barrier_sem);
}

用condition variable

pthread_mutex_lock(&mutex);
counter++;
if (counter == thread_count) {
    counter = 0;
    pthread_cond_broadcast(&cond_var);
} else {
    pthread_cond_wait(&cond_var, &mutex) ;
}
pthread_mutex_unlock(&mutex);

lock其實很貴

假設要做一個multi-thread的linked list

所有動作用lock包
- 那根本就是serial
每個node放lock
- lock要空間!!
- 實作十分複雜
- 明明只要read卻還要跟別人搶lock!?
  - 所以這個效能是所有case中最爛的
read-write lock
- 可以與1一樣但是read的成本變小了
  - write多，總體效果與1一樣
  - read多，效果比1好
- 還可以保護write

關於cache

cache miss

void *Pth_mat_vect(void* rank) {
    ...
    for (i = my_first_row; i <= my_last_row; i++) {
        y[i] = 0.0; // HERE
        for (j = 0; j < n; j++)
            y[i] += A[i*n+j]*x[j]; // HERE
    }
    return NULL;
} /* Pth_mat_vect */

cacheline是64 bytes

如果y的範圍太大，寫入會失敗 (write-misses)
如果x的範圍太大，寫入會失敗 (read-misses)

假設上面程式的y，剛好可以都放入cacheline，但是只要cacheline的值被某個thread改變，其他thread要access資料時cacheline就要重拿資料(Cache Coherence)，而這邊明明都是y，如果一直有thread寫資料…

所以可以想見，cacheline會一直重拿，但是明明大部分的cache(y)是對的!!

另一個情況是task上編號(rank)，這樣在shared mem中就不會衝突，但因為false sharing就算把thread加上去，效能也沒有隨之變好

加padding把cacheline塞滿
- sum[id][pad]
用syncronization包成一個變數!!
- atomic_int sum

Reordering Memory

再一次，memory consistency model
- sequentially consistent
  - program order == code order == commit order
- Relaxed Consistency
  - 把指令分成
    - data(write, read)
      - 不保證順序
    - sync (mem barrier, volatile, atomic, fork/join…)
      - 保證順序!!
        S -> S
        S -> W/R
        W/R -> S
      - mem barrier (在openMP叫flush)
        flush之前的變數(在flush有用到的部分)會被commit (所以flush中一定看的到)
        read mem barrier
        flush之後的變數(在flush有用到的部分)，會看到在flush中做出的結果
        write mem barrier
        flush中不會reorder

單論Synchronization

我們的敵人
- race condition: 泛指跑好幾次可能出現不同的結果
  - data race: 對同一個變數修改
- reorder (講義叫Bad interleavings)
  - a = 1; b = 2 與 b = 2; a = 1;
    - 在compiler或是cpu眼中是可以reorder的!!
      - 看arch的規定
工具
- 保持Atomicity (critical section)
  - mutex，但有很多細節
新的敵人
- deadlock
  - Dining Philosophers (為lock上順序!!)
- Time-Of-Check-To-Time-Of-Use
  - if (checkA()) { execA(); }
  - 有人在checkA成功後，到執行execA之前，被其他thread做到事的話…
    - 換言之，if的block中，不能信任有確認過的條件了
解法
- Thread-Local Memory
  - 不用share的資料就copy
- Immutable Memory
  - 沒有write，沒有race condition或是data race
- 但我真的需要改 (要用mutex了qq)
  - Use Consistent Locking
    - 用同樣的lock到所有有關的地方
    - 好好記錄為什麼需要這個lock
    - 用lock去割出 shared-and-mutable locations
      - lock-oriented
  - Start With Fewer Locks (Coarse-Grained)
    - 除非contention太嚴重才讓lock變多 (Fine-Grained)
  - Keep Critical Sections Small
    - Critical Sections太長: 效能差
    - Critical Sections太短: race condition (可以看到中間狀態)
  - Think About Atomicity
    - 想想什麼動作應該放在一起
      - 像Time-Of-Check-To-Time-Of-Use
      - 不是data race也不是race condition
      - 但就是出事，所以應該把if與動作綁在一起
  - Use Libraries

Message passing programing

Point to Point Communication

Communication透過recv與send執行

message會傳

sender的rank
receiver的rank
communicator (MPI的網路)
tag: 使用者指定的tag
data

下面是standard 的傳送方式 sender buf --{copy}--> system buffer --{network}--> system buffer --{copy}--> receiver buf

communication modes

blocking

blocking的理由是

等handshake
- Synchronous
等copy
- 所有類型都要等
- 從sender buffer 到 receiver buffer
  - Synchronous
  - Ready
- 從sender buffer 到對面的system buffer 到 receiver buffer
  - Standard(資料小)
- 從sender buffer 到自己指定的 buffer 到 receiver buffer
  - Buffered
沒copy到別的buffer (sender buf => receiver buf)
- Synchronous: 一般的tcp
  1. ssend送msg到recv說我要傳，之後等
  2. recv送msg，之後等
  3. handshake好了，可以送了，兩邊等到完成
- Ready: 類似reverse tunnel
  1. recv送msg，之後等
  2. rsend看有沒有recv的msg，有，開送，兩邊等到完成；沒有，報錯退出
copy到別的buffer
- Buffered: 先copy到自己指定的mem (in sender)
  1. bsend把資料copy到自己指定的mem，copy完退出
  2. 收到recv的msg，開送
- Standard:
  - 資料小: copy到system buffer (in receiver)
    1. send把資料送到對面的system buffer，等到送完
    2. recv直接從system buffer copy到receiver buf，等到copy完
  - 資料大: 就變成Synchronous

non-blocking

isend會開始送，但是不會等，馬上return
- 用test看目前狀態，wait去等他完成
irecv如果好了就會收，但是不會等，馬上return
- 用test看目前狀態，wait去等他完成

剩下就是Standard(資料小)

可以想像成傳資料時開thread!!

deadlock (對，還是有)

send 與 recv 要成對出現

if (rank == 0) {
    err = MPI_Send(sendbuf, count, datatype, 1, tag, comm);
    err = MPI_Recv(recvbuf, count, datatype, 1, tag, comm, &status);
}else {
    err = MPI_Send(sendbuf, count, datatype, 0, tag, comm);
    err = MPI_Recv(recvbuf, count, datatype, 0, tag, comm, &status);
}

解法: swap

if (rank == 0) {
    err = MPI_Send(sendbuf, count, datatype, 1, tag, comm);
    err = MPI_Recv(recvbuf, count, datatype, 1, tag, comm, &status);
}else {
    err = MPI_Recv(recvbuf, count, datatype, 0, tag, comm, &status);
    err = MPI_Send(sendbuf, count, datatype, 0, tag, comm);
}

解法: non-blocking

if (rank == 0) {
    err = MPI_Isend(sendbuf, count, datatype, 1, tag, comm, &req);
    err = MPI_Irecv(recvbuf, count, datatype, 1, tag, comm);
    err = MPI_Wait(req, &status);
}else {
    err = MPI_Isend(sendbuf, count, datatype, 0, tag, comm, &req);
    err = MPI_Irecv(recvbuf, count, datatype, 0, tag, comm);
    err = MPI_Wait(req, &status);
}

CUDA

cpu vs gpu

cpu: Latency
- 大cache
  - 降低mem延遲
- 複雜的control邏輯
  - branch prediction
  - data forwarding
- 計算能力(ALU)強
  - 降低operation延遲
- 在sequential code快
gpu: Throughput
- 小cache
  - 增加mem的throughput
- 簡易的control邏輯
  - NO branch prediction
  - NO data forwarding
- 計算能力(ALU)弱(省能源)
  - 延遲高，但是可以pipeline達成高throughput
    - 所以有很多thread
- 在parallel code快

gpu

下面是gpu在arch上的特點

CUDA: Parallel Computing Platform

CUDA: Heterogeneous Programming

gpu叫device 控制的cpu叫host 各自有自己的mem，而跑在device上的function(thread)叫kernel

Thread Hierarchies

grid有很多block，block(wrap)有很多thread，block中的thread可以共享資料，也同時啟動(迴避掉sync的問題)，跑同一個指令

不同block的thread不能合作，同時以wrap為單位做schedule

At any time, only one of the warps is executed by SM

Thread Synchronization

可以用 __syncthreads創barrier
atomic

Memory Model

lockfree

無論當前處於什麼狀態，只要運行足夠長的時間，至少有一個 process 能取得進展或完成其操作像是Real-time的狀況，有mutex就有可能發生priority inversion

或是說，絕對不可能會有deadlock程式，也就是沒有lock的程式

作法

如果不能lock，就只能busy-waiting(或是cpu有特別指令)

做test-and-set，fetch-and-add，compare-and-swap，來確認改之前與改之後的值一不一樣，一樣就寫，不一樣繼續等

少了lock之後

lock有一個很重要的性質，他是memory model的sync指令，所以不會被reorder

但現在不能用lock，所以要注意兩個東西

cpu的memory model
- 不同架構的cpu在不同case會做reorder的case不一樣
- Weak vs. Strong Memory Models
怎麼下memory barrier (Acquire and Release Semantics)
- 得自己把不能reorder的範圍畫出來
- Acquire and Release Semantics
  - 有些programming language有提供memory model!!
    - 可以不用直接調用memory barrier，改用volatile
      - 謝謝JAVA
      - 我之前的記憶體模型筆記
    - The Happens-Before Relation
    - The Synchronizes-With Relation

ABA問題

前面是看值一樣就當成沒改，但這是把資料與時間兩件式混在一起，所以有了ABA，也就是看起來沒換，但其實被人換過，只是資料剛好長的一樣

所以要多一個變數紀錄時間，有改就要遞增；與read-write lock一樣

wait-free

就前面看到的，lockfree可能讓process無限的等(飢餓)，但是wait-free可以在有限的次數讓process動但超難，pass

Wait-Free Queues With Multiple Enqueuers and Dequeuers

TODO

wait-free
Algorithms Sequential & Parallel: A Unified Approach
- 這我不確定，但是因為他比較新就放這裡
An introduction to parallel algorithms (jaja)
- 這裡面提到 Parallel Algo的手法中提到的與沒有提到的手法

Ref

An Introduction to Parallel Programming, Morgan Kaufmann Parallel Thinking Analysis of Parallel Programs More Parallel Primitives and Parallel Sorting Synchronization Some Sequential Algorithms are Almost Always Parallel An Introduction to Lock-Free Programming

動機#

Concurrent computing & Parallel computing & Distributed computing#

Parallel computing & Distributed computing#

平行化就是在 => Coordination#

Task-parallelism & Data-parallelism#

2 parallel models (+ 1 model)#

Shared Memory#

Race Condition#

優缺點#

Message passing#

優缺點#

Shared Memory & Message passing#

除了divide，還可以一次處理多一點: Data Parallel#

Parallel Algo的手法#

parallel primitives#

Parallel Algo的BigO#

例子: findMin on Tree#

測量指標#

隨著核心數上升，performance可以提升到多少?#

到處都是平行化#

processor#

Instruction Level Parallelism (ILP)#

Superscalar & VLIW#

Thread-Level Parallelism (TLP)#

TLP + ILP#

summary#

Memory System#

hardware Architecture#

Shared-memory Architectures#

Coherence & Consistency#

Distributed-memory Architectures#

software Programming#

Shared-Memory Model#

Distributed-Memory Model#

Programming Hybrid Systems#

Shared memory programing#

3 synchronization scenarios#

critical section#

Busy-waiting#

mutex#

Semaphore#

Semaphores vs Mutexes#

Producer-Consumer Synchronization (no critical section)#

barrier#

用busy-waiting與mutex#

用Semaphores#

用condition variable#

lock其實很貴#

關於cache#

cache miss#

false sharing#

Reordering Memory#

單論Synchronization#

Message passing programing#

Point to Point Communication#

communication modes#

blocking#

non-blocking#

deadlock (對，還是有)#

解法: swap#

解法: non-blocking#

CUDA#

cpu vs gpu#

gpu#

CUDA: Parallel Computing Platform#

CUDA: Heterogeneous Programming#

Thread Hierarchies#

Thread Synchronization#

Memory Model#

lockfree#

作法#

少了lock之後#

ABA問題#

wait-free#

TODO#

Ref#

動機