2016q3 Homework2 (phonebook-concurrent)

# 2016q3 Homework2 (phonebook-concurrent) contributed by <`jkrvivian`> ## 預期目標 * 學習第二週提及的 [concurrency](/s/H10MXXoT) 程式設計 * 學習 POSIX Thread * 學習效能分析工具 * code refactoring 練習 * 探索 clz 的應用 ## 資料閱讀 ### Concurrency 系列 * multithread底下有問題，常是因執行順序的不確定性 * **Sequenced-before**: 對 **==同一個==** thread下求值的描述 * evaluation(求值) * value computation (如:left-to-right associativity) * side effect (修改記憶體的值呼叫Library) A is not sequenced-before B and B is not sequenced-before A ==>執行順序不一定，求值時可能會重疊，優化後的執行順序會交錯 * 雖然訂定了許多evaluation order，但仍有一些未定義的行為 * i = i++ ### [concurrency系列(二)](http://enginechang.logdown.com/posts/788206-concurrency-series-2-starting-from-sequenced-before) value computation V.S. side effect > 有點混亂了@@ > i++這類的後置運算子，value computation會先於side effect >>對於assignment operator而言(=, +=, -=之類的)，會先進行運算元的value computation，之後才是assigment的side effect, 最後是整個assigment expression的value computation[color=red] * **happens-before** : 前一個操作的效果在後一個操作執行之前必須要 **可見** * 執行順序不一定就如程式所撰寫的順序一樣 * A happens-before B != A happening before B * 執行順序不一定是A在前 * 只要A在B執行前可見就好 * 同一個thread內sequenced-before就是happen-before * C++定義能夠建立跨thread間的happens-before * 1) A synchronizes-with B (A和B有適當的同步) * 2) A is dependency-ordered before B (A和B有相依的順序關係) * 3) A synchronizes-with some evaluation X, and X is sequenced-before B * 4) A is sequenced-before some evaluation X, and X inter-thread happens-before B * 5) A inter-thread happens-before some evaluation X, and X inter-thread happens-before B * **synchornized-with** :兩個不同thread間的同步行為，當A synchronized-with B的時，代表A對記憶體操作的效果，對於B是可見的。而A和B是兩個不同的thread的某個操作 * ***跨thread版本的happens-before*** * `synchronized` in java * mutual exclusive * 只允許一個thread使用 * 建立happens before關係 * 確保每次對物件的修改都會對接下來的thread可見 * `volatile` in java * 不同thread對變數的讀寫是atomic * 都會讀到最新的值 * **memory consistency models**: 系統要想辦法在保證 **正確** 的情況下，盡可能的最佳化，讓程式跑的又快又好 * 只是一種 **幻象約定** 只要結果跟約定好的定義相同就好，改變執行順序也沒關係 * sequential consistency: * 對於每個獨立的處理單元，執行時都維持程式的順序(Program Order) * 整個程式以某種順序在所有處理器上執行 * cache architecture 與 sequential consistency * cache coherence:確保不同處理器上的cache在系統中保持一致 * detecting the completion of write operations * maintaining the illusion of atomicity for writes ### 冼鏡光的並行計算投影片 * 平行(parallel)：兩件事齊頭並行 * 並行(concurrent)：兩件事中交錯執行、但每一瞬間每件事都有點進展 ==> 一般電腦就是一個並行系統 ### Concurrency (並行) vs. Parallelism (平行) * 影片 * **concurrent** : a composition of independently process(executing things) ==> typically functions * ***dealing*** a lot of things at once * goal: good structure * 不一定要平行 * **parallel** : a simultaniously execution of multiple things * ***doing*** a lot of things at once parallelism can come from better expression of concurrent problem ### Process vs. Thread vs. Coroutines * **Process**: 包括了一個執行中的程式，和一些他所需的系統資源，諸如檔案描述表和位址空間等 * **Threads**: 一個程式計數器、一個堆疊再加上一組暫存器,掌握了所有的執行活動,『共享』系統資源 * **coroutines**: 多工實做技術，合作式多工過往接觸過的： A每次呼叫B或C都是從兩人的最開始執行到最後再回到A ![](https://i.imgur.com/CvRbSYw.png) coroutines: 每次都是回到ABC三者的中斷點再接續執行，而不是從頭開始 ![](https://i.imgur.com/XyzGTbW.png) :::warning 若有使用到local變數，那執行結果可能就不如預期了 >解決辦法：allocate **separate** stack space for each function that is running as a thread[color=red] ::: * 讀[Jserv老師的部落格](http://blog.linux.org.tw/~jserv/archives/001848.html)還有文中提到的經典文章[coroutines in C](http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html)，完全不知道switch可以這樣用(跪)，還沒完全看懂，研讀中~ * 用switch其實就是goto的效果！ >a case statement is still legal within a sub-block of its matching switch statement ### POSIX Threads #### [Getting Started With POSIX Threads 宋振華](http://www.csie.ntu.edu.tw/~r92094/c++/pthread.txt) * thread同步問題 * POSIX 提供 * **mutex**: 控制共享資源存取的一組函數 * **condition variable**: 能夠做到讓某一個 thread 能暫停，並等待另一個 thread 的信號（signal）,當信號來了，thread 就醒過來，然後將相關的mutex lock 起來，為mutex功能的延伸 * **semaphore**: 透過整數運算，所有semaphore的初始值為1 * wait(),decrement直到為0時block * post(),increment :::warning pthread_create 之前定義或在其所呼叫的函數中定義的變數來完成其工作，並將他的成果經由整體變數合併。對這些大家都可以存取的變數，我們必須加以控制。 >回想之前實作raytracing使用omp進行優化時，就是因此才需要使用`private()`保護變數[color=orange] ::: * 檢查thread函式是否正確執行是必要的，若失敗大多數都回傳-1 * [condition varaible](https://www.cs.mtu.edu/~shene/NSF-3/e-Book/MONITOR/CV.html) * **critical section**: * **reentrant**: * **mutual exclusion**: ## 驗證程式碼正確性及效能 ### opt效能 * **Thread_num = 4** ``` size of entry : 24 bytes execution time of append() : 0.009720 sec execution time of findName() : 0.004989 sec ``` * cache misses約49.5% ``` Performance counter stats for './phonebook_opt' (100 runs): 774,269 cache-misses # 49.546 % of all cache refs ( +- 1.73% ) 1,562,737 cache-references ( +- 1.64% ) 225,877,891 instructions # 1.25 insns per cycle ( +- 0.04% ) 181,307,063 cycles ( +- 1.23% ) 0.129546375 seconds time elapsed ( +- 6.50% ) ``` * plot * 圖中可以明顯看見findName()的時間與orig版本差異不大，append()下降許多 * 應想辦法降低findName()時間 ==> 雖然使用hash function可以大大降低，但這樣append()的時間又會拉高@@ ![](https://i.imgur.com/2bpNQd8.png) ### 正確性 * `phonebook_opt.c`中已有個`show_entry()`的function可以列出所有entry中的last name，因此可以與原有的`words.txt`比對 * 打開opt版本的字典檔發現與原本的`words.txt`不同 :::warning 直接看是不對的啊！因為輸出檔沒有排序，直接看下來當然會不同@@ ::: * 執行`diff`指令發現多處不同，其一原因是`phonebook_opt`的output並沒有sort，因此先執行`sort`指令排序 * 執行結果：發現少了前4組 ``` 0a1,4 > aaaa > aaaaa > aaaaaa > aaaaaaa ``` * 修正 ```C== for (int i = 0; i < THREAD_NUM; i++) { if (i == 0) { pHead = app[i]->pHead->pNext; dprintf("Connect %d head string %s %p\n", i, app[i]->pHead->pNext->lastName, app[i]->ptr); } else { etmp->pNext = app[i]->pHead->pNext; dprintf("Connect %d head string %s %p\n", i, app[i]->pHead->pNext->lastName, app[i]->ptr); } etmp = app[i]->pLast; dprintf("Connect %d tail string %s %p\n", i, app[i]->pLast->lastName, app[i]->ptr); dprintf("round %d\n", i); } ``` 把`pHead = app[i]->pHead->pNext`和`etmp->pNext = app[i]->pHead->pNext`裡的`pNext`拿掉就對了 ## mmap * creates a new mapping in the virtual address space of the calling process. ```C== #include <sys/mman.h> void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset); ``` ## Code Refactoring refactoring（重構）的定義：「在不改變軟體的外在行為之下，改善既有軟體的內部設計」 [甚麼是refactoring](http://teddy-chen-tw.blogspot.tw/2014/04/refactoring.html)有提到22種壞味道 * `main.c`58行開始及77行include和define搬到最前面，個人習慣，看起來比較整齊 ```C== #ifndef OPT #include "file.c" #include "debug.h" #include <fcntl.h> #ifndef THREAD_NUM #define THREAD_NUM 4 #define ALIGN_FILE "align.txt" #endif ``` * Line48 與 Line95 `struct timespec mid`雖然有`gettime()`，但之後完全沒有用到，所以直接刪除 * `struct timespec mid`刪除後就可以合併前後的`#ifndef OPT`內的程式碼，並把`struct timespec start, end`搬到外面 ```C== #ifndef OPT FILE *fp; int i = 0; char line[MAX_LAST_NAME_SIZE]; struct timespec start, end; double cpu_time1, cpu_time2; /* check file opening */ fp = fopen(DICT_FILE, "r"); if (!fp) { printf("cannot open the file\n"); return -1; } #else file_align(DICT_FILE, ALIGN_FILE, MAX_LAST_NAME_SIZE); int fd = open(ALIGN_FILE, O_RDONLY | O_NONBLOCK); off_t fs = fsize(ALIGN_FILE); #endif ``` * Line92的兩個for回圈可以合併 ```C== for (int i = 0; i < THREAD_NUM; i++) { app[i] = new_append_a(map + MAX_LAST_NAME_SIZE * i, map + fs, i, THREAD_NUM, entry_pool + i); pthread_create( &tid[i], NULL, (void *) &append, (void *) app[i]); } ``` ## 參考資料 [課程指定材料](https://hackmd.io/s/H10MXXoT#process-vs-thread-vs-coroutines) [吳彥寬學長共筆](https://hackmd.io/s/BkN1JNQp#2016q3-homework1-phonebook) [mmap](http://welkinchen.pixnet.net/blog/post/41312211-%E8%A8%98%E6%86%B6%E9%AB%94%E6%98%A0%E5%B0%84%E5%87%BD%E6%95%B8-mmap-%E7%9A%84%E4%BD%BF%E7%94%A8%E6%96%B9%E6%B3%95) ###### tags: `system embedded` `HW 2`

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.