2017q1 Homework4 (mergesort-concurrent)

contributed by <tina0405>

開發環境

tina@tina-X550VB:~$ lscpu
Architecture:          x86_64
CPU 作業模式：    32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s):             1
NUMA 節點：         1
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              58
Model name:            Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz
製程：              9
CPU MHz：             1270.750
CPU max MHz:           3200.0000
CPU min MHz:           1200.0000
BogoMIPS:              5188.47
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           3072K
NUMA node0 CPU(s):     0-3

語法操作

嘗試 ./sort [thread_count] [input_file]

• 使用 $./sort 會提示我們使用方法

嘗試 uniq words.txt | sort -R > input.txt

• 幫助我們提供快速的亂序表

作業要求1

• 將 merge sort 的實做改為可接受 phonebook-concurrent 的 35 萬筆資料輸入的資料檔
  • 字典檔資料需要事先用 sort -R 處理過
  • 思考如何得到均勻分佈的亂數排列，並且設計自動測試的機制

均勻分佈 和 常態分佈

討論之前機率學的 Probability density function 和 Cumulative distribution function

• 參考均勻分佈

• PDF
  

• CDF
  

• 參考常態分佈

• PDF
  

• CDF
  

• 會想參考這些東西是因為我認為如果今天收到了35萬筆資料，一定會比較趨於現實的情況，有資料分散和不分散的問題（可由標準差去觀察），而不是只有均勻分佈那樣 f(x) 定值，我覺得這樣能更貼近真實狀況。

• 網路上剛好有實作常態分佈的公式：
  Box-Muller方法是以兩組獨立的隨機數U和V，這兩組數在(0,1]上均勻分布，用U和V生成兩組獨立的標準常態分布隨機變量X和Y

    X = − 2 ln(U)* cos( 2 π V ) 

    Y = − 2 ln ⁡(U)* sin( 2 π V ) 

作業要求2

• 研究 thread pool 管理 worker thread 的實做，提出實做層面的不足，並且參照 concurrent-ll，提出 lock-free 的實做

參考thread pool

複習一下以前OS的內容

作業要求3

• 學習 concurrent-ll (concurrent linked-list 實作) 的 scalability 分析方式，透過 gnuplot 製圖比較 merge sort 在不同執行緒數量操作的效能
  • 注意到 linked list 每個節點配置的記憶體往往是不連續，思考這對效能分析的影響
• 共筆的內容儘量用 GraphViz 製作