# 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](https://github.com/sysprog21/phonebook-concurrent) 的 35 萬筆資料輸入的資料檔
* 字典檔資料需要事先用 `sort -R` 處理過
* 思考如何得到均勻分佈的亂數排列，並且設計自動測試的機制

### 均勻分佈 和 常態分佈

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

* 參考[均勻分佈](https://en.wikipedia.org/wiki/Uniform_distribution_%28continuous%29)
* PDF

* CDF

* 參考[常態分佈](https://en.wikipedia.org/wiki/Normal_distribution)
* 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](https://github.com/jserv/concurrent-ll)，提出 lock-free 的實做

參考[thread pool](http://columns.chicken-house.net/2007/12/14/threadpool-%e5%af%a6%e4%bd%9c-1-%e5%9f%ba%e6%9c%ac%e6%a6%82%e5%bf%b5/)

複習一下以前OS的內容

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