2016q3 Homework3（mergesort-concurrent)
===
contributed by <`RayPan`>
## 開發環境
* OS: Ubuntu 16.04 LTS
* CPU：Intel® Core™ i5-4200H CPU @ 2.80GHz × 4
* L1d cache: 32K
* L1i cache: 32K
* L2 cache: 256K
* L3 cache: 3072K
* Memory: 7.7 GiB
---
## 開發目標
* 將 merge sort 的實做改為可接受 phonebook-concurrent 的 35 萬筆資料輸入的資料檔
* 字典檔資料需要事先用 sort -R 處理過
* 思考如何得到均勻分佈的亂數排列，並且設計自動測試的機制
* 研究 thread pool 管理 worker thread 的實做，提出實做層面的不足，並且參照 concurrent-ll，提出 lock-free 的實做
* 學習 concurrent-ll (concurrent linked-list 實作) 的 scalability 分析方式，透過 gnuplot 製圖比較 merge sort 在不同執行緒數量操作的效能
* 注意到 linked list 每個節點配置的記憶體往往是不連續，思考這對效能分析的影響
## Graphviz
參考資料：[Graphviz - 用指令來畫關係圖吧！](http://www.openfoundry.org/tw/foss-programs/8820-graphviz-)、[Graphviz Gallery](http://www.graphviz.org/Gallery.php)
* 簡介
是一個運用廣泛的命令行繪圖軟體，提供一套語言能直接陳述圖片上的節點、邊、方向等性質。之後，由它來產生整張「關係圖」，且HackMD 已經支援 GraphViz。
* 使用

1  # Graphviz
2  ＞＜cmd＞ ＜inputfile＞ -T ＜format＞ -o ＜outputfile＞
3 
4  # 舉例：輸出 png
5  ＞ dot input.dot -T png -o output.png
6  # 舉例：一樣是輸出 png，只不過檔名是 txt
7  ＞ dot input.dot -T png -o output.txt

* 實例

digraph G {

	subgraph cluster_0 {
		style=filled;
		color=lightgrey;
		node [style=filled,color=white];
		a0 -> a1 -> a2 -> a3;
		label = "process #1";
	}

	subgraph cluster_1 {
		node [style=filled];
		b0 -> b1 -> b2 -> b3;
		label = "process #2";
		color=blue
	}
	start -> a0;
	start -> b0;
	a1 -> b3;
	b2 -> a3;
	a3 -> a0;
	a3 -> end;
	b3 -> end;

	start [shape=Mdiamond];
	end [shape=Msquare];
}

/* courtesy Ian Darwin and Geoff Collyer, Softquad Inc. */
digraph unix {
	size="6,6";
	node [color=lightblue2, style=filled];
	"5th Edition" -> "6th Edition";
	"5th Edition" -> "PWB 1.0";
	"6th Edition" -> "LSX";
	"6th Edition" -> "1 BSD";
	"6th Edition" -> "Mini Unix";
	"6th Edition" -> "Wollongong";
	"6th Edition" -> "Interdata";
	"Interdata" -> "Unix/TS 3.0";
	"Interdata" -> "PWB 2.0";
	"Interdata" -> "7th Edition";
	"7th Edition" -> "8th Edition";
	"7th Edition" -> "32V";
	"7th Edition" -> "V7M";
	"7th Edition" -> "Ultrix-11";
	"7th Edition" -> "Xenix";
	"7th Edition" -> "UniPlus+";
	"V7M" -> "Ultrix-11";
	"8th Edition" -> "9th Edition";
	"1 BSD" -> "2 BSD";
	"2 BSD" -> "2.8 BSD";
	"2.8 BSD" -> "Ultrix-11";
	"2.8 BSD" -> "2.9 BSD";
	"32V" -> "3 BSD";
	"3 BSD" -> "4 BSD";
	"4 BSD" -> "4.1 BSD";
	"4.1 BSD" -> "4.2 BSD";
	"4.1 BSD" -> "2.8 BSD";
	"4.1 BSD" -> "8th Edition";
	"4.2 BSD" -> "4.3 BSD";
	"4.2 BSD" -> "Ultrix-32";
	"PWB 1.0" -> "PWB 1.2";
	"PWB 1.0" -> "USG 1.0";
	"PWB 1.2" -> "PWB 2.0";
	"USG 1.0" -> "CB Unix 1";
	"USG 1.0" -> "USG 2.0";
	"CB Unix 1" -> "CB Unix 2";
	"CB Unix 2" -> "CB Unix 3";
	"CB Unix 3" -> "Unix/TS++";
	"CB Unix 3" -> "PDP-11 Sys V";
	"USG 2.0" -> "USG 3.0";
	"USG 3.0" -> "Unix/TS 3.0";
	"PWB 2.0" -> "Unix/TS 3.0";
	"Unix/TS 1.0" -> "Unix/TS 3.0";
	"Unix/TS 3.0" -> "TS 4.0";
	"Unix/TS++" -> "TS 4.0";
	"CB Unix 3" -> "TS 4.0";
	"TS 4.0" -> "System V.0";
	"System V.0" -> "System V.2";
	"System V.2" -> "System V.3";
}

---
## 研讀BASH
參考資料：[第十章、認識與學習BASH](http://linux.vbird.org/linux_basic/0320bash.php)
* bash 就是 linux 預設的 shell
### Shell 的變數功能
* 變數: 以一組文字或符號，取代一些設定或一串保留的資料。
* 變數取用: `echo $變數名稱` or `echo {$變數名稱}`
* 變數設定: `變數名稱 = 變數內容`
* 取消變數: `unset 變數名稱`
* 命令別名: `alias 別名='指令 選項'...`

---
## 程式理解

### Makefile
參考資料：[GNU make: Flavors](https://www.gnu.org/software/make/manual/html_node/Flavors.html), [Makefile](http://kezeodsnx.pixnet.net/blog/post/25125766-makefile)

* `.PHONY`
無條件執行，避免rule與檔案名稱重複，被make誤判為該target已經存在而沒有執行。若有個檔案叫clean，在執行make clean時，clean已經存在，則不執行。但若使用.PHONY: clean，則該rule無條件執行。
* GNU有兩種定義變數的方式：
* 遞迴展開變數(Recursively Expanded Variable)
用`=`或`define`定義，如果變數的定義引用了其它的變數，那麼引用會一直展開下去，直到找到最新的定義，並以此作為變數的值返回。
* 簡單擴展變數(Simply Expanded Variables)
用`:=`定義，用這種方式定義的變數會在變數的定義點，按照被引用的變數的目前值進行展開。

兩者差異在於變數assign的時機。前者是用到時才給值，後者是執行時就給值。
範例：
1.
`var1=hello`
`var2=$(var1) world` //使用遞迴展開變數
`var1=hi`
`echo $(var2)` → var2為 hi world
2.
`var1=hello`
`var2:=$(var1) world` //使用簡單擴展變數，此時已將var1當時的值assign給var2
`var1=hi`
`echo $(var2)` → var2為 hello world
* `-rdynamic`
指示linker把所有label（不僅只是程序已使用到的外部label）都添加到動態符號表（即.dynsym表）裡，以便dlopen或backtrace等函數使用；

* ``

### `main.c`

* `max_cut`為做merge_sort前分群時的切割次數， 取thread_num和data_count兩者之間較小者的數值再減1

	max_cut = thread_count * (thread_count <= data_count) +
          	  data_count * (thread_count > data_count) - 1; 

* 對於動態分配的互斥量, 在申請內存(malloc)之後, 通過pthread_mutex_init進行初始化,
並建立thread pool

    pthread_mutex_init(&(data_context.mutex), NULL);
    data_context.cut_thread_count = 0;
    tmp_list = NULL;
    pool = (tpool_t *) malloc(sizeof(tpool_t));
    tpool_init(pool, thread_count, task_run);

* 建立第一個task，遞迴使用cut_func切割the_list

task_t *_task = (task_t *) malloc(sizeof(task_t));
    _task->func = cut_func;
    _task->arg = the_list;
    tqueue_push(pool->queue, _task);

參考資料：
merge_sort: [Comparison Sorting Algorithms](http://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html)
[Linux 中程式同步處理- 互斥量（Mutex） ](http://www.linuxeden.com/html/develop/20071119/37340.html)

###

### `list.c`

node_t *node_new(val_t val, node_t *next); //建立新的節點

llist_t *list_new(); //建立新的list物件

int list_add(llist_t *list, val_t val); //插入給定資料val到輸入的list中

node_t *list_nth(llist_t *list, uint32_t idx); //回傳一個指到list中第idx

void list_print(llist_t *list); //逐一印出list內容

---
作業詳細資訊：[A07: mergesort-concurrent](https://hackmd.io/s/rJ-GWtJ0)

###### tags `RayPan` `A07:Mergesort-Concurrent`