2017q1 Homework4 (phonebook-concurrent)

tags: embedded

contributed by <Cayonliow>

作業

• 作業說明： B07: phonebook-concurrent
• 參考資料： Toward Concurrency, 李昆憶學長的共筆 , The Free Lunch Is Over , Concurrency is not parallelism

背景知識

這張圖我在計組上課的時候有看過， 跟老師說的一樣

• 以前 CPU 增進效能的手段
  • Clock speed
  • Execution Optimization
  • Pipelining、Branch prediction
  • Out-of-order execution 還要注意不能讓原本程式崩潰 (read/write reorder)
  • Cache：盡量減少存取 Main memory 的機會

可是依上圖， Perf/Clock(ILP), Power 跟 Clock Speed 在 2000 年就出現飽和的現象， 所以增進效能的手段也跟着改變

• 現在 CPU 增進效能的手段

  • Hyperthreading: 在 single CPU 上同時執行多個 thread，但是共用 ALU、FPU
  • Multicore：多個 CPU
  • Cache

Free (performance) lunch 指的是程式設計的效能可以透過 CPU 時脈的進步而得到改善。會說 over 是因為 CPU 的時脈無法得到更進一步的增加，由於耗電和散熱的問題，所以程式設計師必須要修改程式才能改善效能

Concurrency

• 使用 Concurrency 的理由:
  1.分離可獨立運作的工作；
  2.為了效能，像是使用多核新的 CPU

• 可是並非所有的程式都合適平行化；所以程式要設計可以實行 Concurrency 是很困難的

• 如果程式的相依性太高或是太常取用共同資源則會拖慢 Concurrency 的效率

• 對軟體設計的影響

  1. 想要完全使用到 CPU 所有的資源
  2. 程式越來越有機會造成 CPU-bound。雖然主要還是 IO-bound 等，但如果 CPU 時脈無法增加，而其他存取方式速度變快，最後會發生 CPU-bound
  3. 效能優化將會越來越重要
  4. 程式語言強迫必須好好處理 concurrency

• A happends-before B ： 在 B 開始執行之前， A 的執行效果必須可見。

• A is Sequenced-Before B ： 在同一個 thread 下，A 比 B 先求值。

• A is synchronized-with B ： A 在這一個 thread 對記憶體的操作，在另一個 thread 的 B 必須可見。

• Sequential consistency ： 無論處理器實際怎麼執行，確保結果跟照程式順序執行一樣

  • Read before Write ： 在新值寫入前讀取到舊值
  • Write after Write ： 在正確值寫入後被舊值複寫 (有先後)

• Concurrency is not parallelism

  • Concurrency 是指程式架構， 將程式拆開成多個可獨立運作的工作

    • eg：drivers， 都可以獨立運作，但不需要平行化。

    • 拆開多個的工作不一定要同時運行

    • 多個工作在單核心 CPU 上運行

    • 工作可拆分成「獨立執行」的部份, 這樣「可以」讓很多事情一起做, 但是「不一定」要真的同時做。

    • 展示具有並行性，但不去同時執行

    • 並行性是種「架構程式」的概念。寫下一段程式之前, 思考問題架構時就決定好的。

  • Parallelism 是指程式執行， 同時執行多個程式. Concurrency 可能會用到 parallelism，但不一定要用 parallelism 才能實現 concurrency。

    • eg：Vector dot product
    • 程式會同時執行 (例如：分支後，同時執行，再收集結果)
    • 一個工作在多核心 CPU 上運行
    • 把規劃好， 能夠並行的程式, 分配給不同執行緒, 並讓他們同時執行。

開發記錄

一開始先 make plot 看看結果

發現 append() 的效能提升了很多， 所用的時間甚至比 findName() 來的少

然後參考 csielee 的共筆 分析 concurrent 的實作

主要是在 append() 的時候將工作分給多個 thread 一起做
並使用下面的方法，讓多個 thread 可以順利 concurrent

• 對齊
  • 利用 text_align 對齊 DICT_FILE(要讀取的名字檔案)
  • open()
    • O_RDONLY: 以只讀方式打開文件
    • O_NONBLOCK：以不可阻斷的方式打開文件，也就是無論有無數據讀取或等待，都會立即返回進程之中

    text_align(DICT_FILE, ALIGN_FILE, MAX_LAST_NAME_SIZE);
    int fd = open(ALIGN_FILE, O_RDONLY | O_NONBLOCK);
    off_t file_size = fsize(ALIGN_FILE);

• 對映
  • 把 ALIGN_FILE 的檔案內容利用 mmap() 記憶體對映到記憶體當中
  • 同時利用對齊後的檔案大小去計算出需要幾個 entry，利用一次 malloc 把需要的記憶體空間一次分配好
  • mmap()
    • PROT_READ：映射區域可被讀取
    • PROT_WRITE：映射區域可被寫入
    • MAP_PRIVATE：對應射區域的寫入操作會產生一個映射文件的複制，即私人的“寫入時復制”（copy on write）對此區域作的任何修改都不會寫回原來的文件內容 。
    • 在調用mmap（）時必須要指定MAP_SHARED或MAP_PRIVATE。

    map = mmap(NULL, file_size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
    assert(map && "mmap error");
    entry_pool = (entry *)malloc(sizeof(entry) *
                                 file_size / MAX_LAST_NAME_SIZE);
    assert(entry_pool && "entry_pool error");

• 分配
  • 最後將這些東西分配進每個 thread，這樣互相執行起來， 就可以解決同時讀取同一個檔案的檔案指標 critical 問題，跟頻繁的 malloc

for (int i = 0; i < THREAD_NUM; i++)
        // Created by malloc, remeber to free them.
        thread_args[i] = createThead_arg(map + MAX_LAST_NAME_SIZE * i, map + file_size, i,
                                         THREAD_NUM, entry_pool + i);

• merge linked list
  • 最後等每個 thread 執行完，就把每個 thread 各自產生的 linked list 合併起來

    for (int i = 0; i < THREAD_NUM; i++) {
        if (i == 0) {
            pHead = thread_args[i]->lEntry_head->pNext;
            DEBUG_LOG("Connect %d head string %s %p\n", i,
                      pHead->lastName, thread_args[i]->data_begin);
        } else {
            e->pNext = thread_args[i]->lEntry_head->pNext;
            DEBUG_LOG("Connect %d head string %s %p\n", i,
                      e->pNext->lastName, thread_args[i]->data_begin);
        }

        e = thread_args[i]->lEntry_tail;
        DEBUG_LOG("Connect %d tail string %s %p\n", i,
                  e->lastName, thread_args[i]->data_begin);