Try   HackMD

2016q3 Homework3 (mergesort-concurrent)

contributed by <FZzzz>

預期目標

主要開發環境

Distribution: Ubuntu 16.04 LTS

Architecture:          x86_64
CPU 作業模式：    32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                8
On-line CPU(s) list:   0-7
每核心執行緒數：2
每通訊端核心數：4
Socket(s):             1
NUMA 節點：         1
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              60
Model name:            Intel(R) Xeon(R) CPU E3-1231 v3 @ 3.40GHz
製程：              3
CPU MHz：             3748.632
CPU max MHz:           3800.0000
CPU min MHz:           800.0000
BogoMIPS:              6784.07
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           8192K

最近筆電剛弄好環境，有可能也會在上面測，如果有需要附上我再貼　`chenyi`

TODO

  • Git hooks
  • 打亂字典檔（運用sort -R處理）
  • 閱讀程式脈絡並做一些修改
  • 提出實作層面不足
  • lock-free實作
  • 分析

閱讀程式脈絡並思考改進

原本的程式使用了若干個mutexes

(目前數下來是兩個，mutrace看是3個)
`fzzzz`

  • data_contex_mutex
  • task_queue_mutex

task執行區塊

static void *task_run(void *data)
{
    (void) data;
    while (1) {
        task_t *_task = tqueue_pop(pool->queue);
        if (_task) {
            if (!_task->func) {
                tqueue_push(pool->queue, _task);
                break;
            } else {
                _task->func(_task->arg);//call function and run
                free(_task);
            }
        }
    }
    pthread_exit(NULL);
}

task在開始前會被放入共用的work queue中，在tpool_init(pool, thread_count, task_run)中

for (uint32_t i = 0; i < tcount; ++i)
        pthread_create(&(the_pool->threads[i]), &attr, func, NULL);

放入task_run的讓各個thread從task queue撈工作，直到撈出來的 task == null。

可以先算完會用至少幾個thread，再開幾個給他就好

不過這樣就不符題意了XD `fzzzz`

為何要說「假設多開很多thread，會造成浪費」呢？你當然要先作空間複雜度分析，然後透過預先保留適當的資源和調整 thread pool 即可。再一次可見數學分析的重要。 jserv

超酷的比對方式XD

llist_t *small = (llist_t *)
                 ((intptr_t) a * (a->head->data <= b->head->data) +
                 (intptr_t) b * (a->head->data > b->head->data));
  • 可能改進方向
  • condition variable在整支程式裡似乎沒被用到(init卻不使用)，然後沒有destroy
  • 沒做到平衡地分配工作
    `fzzzz`

修正test case給予方式

  • 給予正確且平均的亂數分佈
    • rand() and srand()
  • 能接受phonebook作業裡的資料
    • 利用strcmp()

自動化測試(Makefile)

for i in 1 2 4 8 16 32 64 128 256; do ./sort $$i input.txt; done

字串比對

llist_t* small = (strcmp(a->head->data , b->head->data) <= 0) ? a:b;

原版時間測試

利用clock_gettime()來作為量測時間的方法，這邊主要想放一下各個thread數目的效能比較

等等補圖 正在更改成可比對字串中

比對字串版

太少筆了不好看

為什麼會振盪？
應該不是clock_gettime()的問題，肉眼在看程式執行時間就可以看到的差異
清理cache
`fzzzz`
可以嘗試對特定的N-threads做多次，來看實驗數據分佈的狀況
cheng hung lin

可以看出趨勢是thread數目愈多，花費時間就愈多

References

tags fzzzz sysprog
Last changed by 
 
Yi Chen
0
993
Published on HackMD