contributed by <zmke
、petermouse
、 tina0405
、heathcliffYang
>
在原始的版本中,會將輸入的 list 分割給每個 thread 去做 merge ,而最後 thread 之間 list 的 merge 則是一個不能並行執行的部分,無法隨著 thread 數增加而提高執行效率,是增加 scalability 會遇到的瓶頸。
這讓我們想到一個在計組教過的 Amdahl's law
不能並行的部分則讓核心數增加帶來的加速效果存在極限。
所以我們把其中一個目標放在 thread 之間 list 的 merge 也要讓它可以並行處理,實作方法在下面的部分會詳細介紹。
另外,在與新夥伴溝通時,發現他們參考 Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms 嘗試過 lock-free threadpool。
以下 2 、 3 版本都有包含 lock-free threadpool,且都是以 ./sort 16 test_data/input.txt
進行測驗。
Original
原版在最後 thread 之間的 list 做 merge 時,因為工作不能多執行緒一起執行,所以其他 thread 會持續要求工作直到結束。
Condition variable
這個版本是 lock-free thread pool 與 condition variable 一起的實作,而 condition variable 則會在 monitor 的部分做介紹。
因為 condition variable 的關係,當 queue 裡面沒有工作時,空閒的 thread 不會佔用到 CPU 的時間,tqueue_pop
的次數有減少,但花費時間卻增加了。
此外,lock-free thread pool 會導致在 thread 多時,跑不完。
Condition variable + merge concurrent
這個版本是 lock-free thread pool 與 condition variable ,再加上 thread 之間的 list 做 merge 的工作是 concurrent。
tqueue_pop
的次數減少一半,後期 merge 的工作已可以允許多個 thread 一起執行;其中工作可以容納的 thread 數有限制: arg->task_cnt = arg->source->size / local_size * 2
,這部分需要再思考如何訂定最有效益的辦法;這是初版的 concurrent merge ,改變了所有 list 的資料結構,同時也可以看到 list_search 與 list_insert 有相當的成本,也是一個可以考慮改進的方向。
這張圖忘記改 label 了
讓 thread 可以保持 mutual exclution 並等待直到特定的 condition 成立
monitor 包含 mutex 和 conditional variable
pthread_cond_wait(cond, mutex)
pthread_cond_signal(cond)
pthread_cond_broadcast(cond)
當 thread 被喚醒之後,應該要重新評估是否該繼續執行或是再等待一次,所以 condition wait 常被實作在 while loop 內,來確保執行的安全性
原本的程式在 task queue 沒東西的時候,也會一直嘗試 tqueue_pop() ,造成 CPU time 的浪費,尤其是在 thread 數量多的時候影響會更大
我們想要利用 condition variable 讓空閒的 thread 在 task queue 裡面沒有東西的時候 sleep ,等到有 task push 到 task queue 裡面之後,再喚醒他們起來要工作,希望減少 pop 空的 task queue 造成的浪費
一開始就拿 mutex ,之後檢查 task queue 內是否是空的,如果是空的就等待並釋放 mutex ,被喚醒之後會拿到 mutex 但是 pool->queue->size 可能已經被改變,所以要再檢查一次,如果沒問題就釋放 mutex ,否則就是再等待一次
在 push 的最後加上 pthread_cond_signal() ,藉此通知被 block 的 thread 已經有工作可以拿
Lock-free linkedlist implementation of Harris' algorithm
原本的數字串如下:
如果想要 insert Node_20 , 我們會這樣做:
如果想要 delete Node_10 , 我們會這樣做:
但如果現在 insert Node_20 和 delete Node_10 同時發生,就有可能出現以下情況:
但我們不樂見,因為我們希望他會走訪 Node_20
解決方法:
步驟1:左邊的圖是先將刪除點 mark 起來
步驟2:右邊的圖是真的刪掉 node_10
logically deleted : 完成步驟1
phisically deleted : 完成步驟2
好處:
一開始本來對,如果要序列: 1,4 中間同時插入 2 跟 3 的話可能會發生,兩個 2 跟 3 同時指到4,此時序列就不是我們要的 1,2,3,4 了 ,但以下程式碼用 CAS 插入做了檢查的動作:
證明的想法:
We will take a fairly direct approach to outlining the linearizability of the operations by identifying particular instants during their execution at which the complete operation appears to occur atomically
對於右節點的標記狀態,通過前3個回傳條件都是true後,觀察兩個返回路徑都要確認右結點未被標記,而右結點從未變成 unmarked ,我們推斷起初右節點沒有標記。
CAS 指令 C1 成功後,通過從 list 中 unlinking 標記的節點
這裡是在說明 op(i,m) 是和操作次數 (m) , processor 數 (i) 有關,也就是,在i個 processor 下,執行m次的表現
而 d(i,m) 則是執行時 search 在後置條件被滿足時的 final real-time
我們一直希望利用多執行緒下去做的排序,如果 thread 愈多理論上是愈快
如果能成功算得 d(i,m),就表示我們右節點沒有被 mark 且包含 search_key
如果利用 Find(k) 去搜尋,發現在 search_key 右半部的nodes 的 key 是嚴格遞減,左半部的nodes 的 key 是嚴格遞增,可證其正確性。
merge sort 在最後會將兩個已經排序好的資料重新 merge ,合併成一筆排序好的資料,但是如果兩筆資料量很大時,只有一個 thread 去處理會相當得慢。
因此我們想要將這部份以多個 thread 下去 lock-free 的方式處理,在看了論文之後,我們的想法大概是這樣:
head
) 尋找,每個 thread 會紀錄上一次的插入位置,等取得下一個 node 時,直接從上一次的插入位置尋找參考了原本的論文實作出類似的架構
list_pop()
從 source 取出一個 nodelist_insert()
, list_insert()
會使用 list_search()
協助找尋插入點以上的操作比起論文還要來的單純,一加一減的 linked list 使得我們不用去考慮 marked 以及 unmarked 的問題
這是 concurrent merge 所需的參數,除了上述提到的 source
以及 dest
,還加入了 task_cnt
作為 counter,最後會遞減至 0 ,代表所有 thread 已經做完
這不代表一定要所有 thread 進入才開始,只要有一個 thread 進入就開始 merge 的動作,但一定會有task_cnt
初始值的 thread 進入,即使資料已經處理完也會先進入爾後離開
在每個 thread 排序完自身的 linked list 時會丟入 tmp_list
,或是因為 tmp_list
已有 list 存在開啟新的 task ,設定好相關的參數,決定應進入 thread 數量,開啟等量的 task ,並行 merge
每個 thread 的工作就是不斷地
拿取 node >> 插入 node
當再也 pop 不出任何東西時,會去將 task_cnt
減 1 離開,當最後一個 thread 也準備離開時(line 13: if (old_cnt == 1)
):
其實要
list_pop
list_insert
就即時更新了 … :sweat_smile:
list_pop
、 list_insert
、 list_push
上面沒有提到的問題點是關於 linked list 的資料結構,因為論文的資料結構與原本的不一樣, 所以需要一些改變
原本 list 的資料結構,且初始化 head 指向 NULL
但現在新增了 tail
且 head
與 tail
會各指向一個不會使用到、配置空間的 node (這個 node 稱為 sentinel node) 來使演算法正確運作
這樣的改動連帶牽扯了其他相關的 function 都要修正
包含 mergesort.c
中的 split_n_merge()
與 sort_n_merge()
main.c
中的 build_list_from_file()
與 cut_local_list()
有些 function 需要頻繁的使用 list_get
來取得最後一個 node ,也就是說整個 list 都遍歷了
…結果這樣使得效率整個降低
1 個 thread,純修改資料結構的結果
光是如此已經在時間上拉出差距
因為調整資料結構對於 merge sort 帶來的衝擊很大,最後是不改變原始的資料結構,只有當有需要的時候再改變
為此當要並行 merge 時,我們需要 sentinel nodes,我們在執行前加入了 sentinel head
至於 sentinal tail 是不一定要的:在我們的程式碼中所有的 list->tail
都可以用 NULL
取代
merge_thread_list()
第 13、14 行針對 src 與 dest 做這樣的處理,再丟入 task 中執行 concurrent_merge()
concurrent_merge()
的最後一個 thread 再把 dest 的 sentinel head 移除 (第 17 行)
因為 lock-free 很容易爆炸,這邊以維持 mutex 做測試
時間確實有下降一點!不過當 thread 數目變多,時間會再往上增長,主要原因是因為
這是決定 thread 參與數量的方式, local_size
代表 thread 當初分割的local linked list 資料量 ,也就是使用與處理這些資料同等數量的 thread 做 merge ,但是每個 thread 的參與需要遍歷整個 linked list , thread 多於核心數等於過度浪費時間在 list_search()
上,反而降低效益
最後將能夠參與的數量限制在核心數,這裡使用到了 get_nprocs()
執行環境在雙核且支援 hyper-threading 的 intel 處理器,get_nprocs()
回傳了 4
文中有特別指出這個 function 成本昂貴,因為要去開啟 /sys 底下的檔案解析,因此只使用一次存下來
我們的目標是要改善程式碼的 scalability,但可以由上述的比較圖看出,程式在 thread 數為 4 的時候表現最佳,thread 數繼續變多的時候,無法更快甚至有變慢的情形。所以我們決定驗證這個現象的原因。
我們歸納出的原因有兩個,第一個是程式本身不夠好,concurrent merge 的機制不夠好,因為愈多個 thread 要一起 merge ,
每個 thread 都要拜訪 list 的所有 node ,或者是 thread pool 的機制也尚待改進;第二個是 thread 之間的 context switch 所花的時間,若 context switch 所花的時間遠小於我們程式碼所花的時間,就代表 scalability 還有增加的空間。
以下數據以 64 threads 的 case 來比較
436 ms >> 1519 * 830.7 ns ~ 1 ms
老師提到可以在 merge 的過程中重新建立記憶體連續的資料 (array)
context switch 時間 : https://github.com/jserv/lmbench-next
Quantifying The Cost of Context Switch∗
附上原版 github
CFS 相較於 2.6 版本以前的 kernel
參考文件中提到
一種 system benchmark
sort_n_merge
著手連續的記憶體結構可以使 cache-miss 有機會降低
在排序 local linked list 的過程中 ,嘗試在 merge 的時候先分配一塊準備要塞排序好的資料空間,當作是一個陣列的資料結構來 merge,但內部還是存在 linked list 的結構,所以 next 單純指向下一個陣列元素,方便在之後可以 concurrent merge 時有幫助
實驗結果
目前時間還沒有顯著差異
concurrent_merge
先前 concurrent_merge
會使得每個 merge 的 thread 幾乎遍歷過整個 linked list 來找尋適合插入的點並插入 node
但是現在建立在連續記憶體的結構下,我們可以
待補
to be continued…