Blocks 初探與 multithreading 應用

近日由於個人一項工作的緣故, 為了能在短時間內能夠加速複雜程式的運作
因此現學現賣地採用了 OpenMP 做快速的優化實作, 最後得到 3倍左右的加速

儘管 OpenMP 表現不俗, 然而在 Android 上的實作必須仰賴已經被 deprecated 的 GCC
讓現今預設使用 clang 的環境必須特別撰寫 makefile
而儘管亦能夠使用先前撰文介紹的 Grand Central Dispatch 作為方案
然而一方面 libdispatch 的 Android port 已經過舊
而官方版必須限定 Android API-level 21 外 (另外現在編譯也有問題)
另一個問題是 GCD 的實作規模不可以說小

由於 Blocks 的使用其簡潔與動態的特性對於個人而言是充滿魅力的
基於如此的動機便開始構思結合 thread pool 與 Blocks 的方式
以此來簡化 multi-threading 程式的撰寫, 並且得到能夠有效修改的實作
為此目的必須先去了解 Blocks 是如何運作的
儘管 clang 提供了 "Language Specification for Blocks" 的頁面
然而個人認為 Apple 的 Blocks Programming - Introduction 撰寫的比較淺顯易懂

基本上 Blocks 提供了將 C/C++ 的大括號內的 code 區塊轉化作為類似下列型別作為"變數"的能力

void (*func)(void);

而 Blocks 中最有趣以及最為實用的功能是對於使用 global/local variable 上數值的"擷取"
以 local variable 為例, 一般的 serial code 毫無疑問會在 stack memory 中
若使用了 Blocks 並於 Blocks 中使用了該 Block 區間外的 global/local variable
這時的流程會產生了類似 process fork 的分歧, 理解上應為未明確寫出的 call by value
Blocks 中對於外部的 global/local variable 本身的修改是不具有寫回的效果
除此之外型別為 Blocks 的變數在使用上的概念其實與一般變數無異
程式撰寫的過程中同樣地必須考量與處理 variable lifetime 的問題
這時就必須藉由使用 Block_copy/Block_release 來手動複製與釋放 Blocks 所含的內容
對於程式中 local/global variable 處理概念上的不同是 OpenMP 與 Blocks 最大差異
而兩者所使用的方式, 在應用上來說真的是各有優缺

透過閱讀上述的參考資料建立概念後
接著就動手來做類似於 GCD 的 Blocks dispatching 的功能

首先是建立等同於 GCD 中使用來作為 task dispatch 的 dispatch_block_t 的型別
接著就是增加 thread pool 的 dispatch function
基本上是將原本的介面的參數自 function pointer 與型別為 (void *) 的 argument
改為直接使用 Block 型別
可不用再撰寫型別為 void* func(void*) 的 pthread glue code 的好處不用再多說了

在建立概念之後, 動手實作上就簡單多了
為了快速而採用了現成的 thread pool 實作 - C-Thread-Pool
而 Blocks 的操作是基於 BlocksRuntime (提供了 Block_copy / Block_release)
而初步的成果我暫且名為 gunshot
請 git clone 後記得 git submodule init/update

修改的 example.c 中, 嘗試比較填入一個 buffer 數值

    for(int pidx = 0; pidx < TEST_DEPTH; pidx++){
        int *plane = buf0 + pidx*TEST_W*TEST_H;
        for(int yidx = 0; yidx < TEST_H; yidx++){
            for(int xidx = 0; xidx < TEST_W; xidx++){
                plane[yidx*TEST_W + xidx] = pidx*4096 + (yidx + xidx);
            }
        }
    }

而 thread pool + Blocks 的版本可以寫為

    for(int pidx = 0; pidx < TEST_DEPTH; pidx++){
        int *plane = buf1 + pidx*TEST_W*TEST_H;
        thpool_add_block(thpool, ^{
            for(int yidx = 0; yidx < TEST_H; yidx++){
                for(int xidx = 0; xidx < TEST_W; xidx++){
                    plane[yidx*TEST_W + xidx] = pidx*4096 + (yidx + xidx);
                }
            }
        });
    }

在個人使用的 Quad-Core A8-5545M 平台得到了以下結果
single thread - 34832 us
4 threads - 13129 us

得到了 2.65 倍的加速

從 Helio X20 分享 HMP (Heterogeneous Multiple Processor) 心得

此篇為 2015年 8月 臉書的貼文, 對於 Helio X20 與 HMP 的一些看法
HelioX20 面市已滿一年, 也適合檢視看法的正確性
=====

Mediatek 的 Helio X20 有著 Luffy 般的神技"三檔"已不是新聞, 身為一個小螺絲釘, 對於一些人執著於 Antutu 等測試軟體分數感到近乎偏執的程度(GPU 配置真的弱很久...). 但是對於這樣的極端 HMP 的平台系統(CA72 2.5Ghz X2, CA53 2.0Ghz X4, CA53 1.4Ghz X4), 只延續以往 CorePilot 將其擴充到"三檔", 仍是一個以 system (total DMIPs) performance 與 power 間做考量的 scheduling system, 但問題是對於軟體應用這樣的方案是否足夠?

各位若有興趣而且有機會的話能以 #MT6595 平台(CA17 X4, CA7 X4)實驗, 就可一窺這樣系統的問題: 一個單以系統提供的 total computation throughput 嘗試對應系統負載程度做 system-level scheduling 是不足的. 軟體上會經常碰到的問題是一個應用程式中的 threads 獲得的 computation throughput 會因為 HMP, DVFS, thermal control 而變得與 SMP 架構相較有著較大的變異性, 不公平性與不確定性. 平均分割的 task, 常因為長跑於 little 核心上的 thread 而無法顯示具有大核的效能優勢.

八月中在思考&探討軟體因應HMP策略的同時, 忽然有個念頭, 如果能針對 per-core 的情況, 在計算架構上能考慮到公平性(fairness)這件事情, 似乎問題就解決大半了, 第一時間的發想是將 CPU 做類似 HyperThreading 中 logical core 與 physical core 的 decouple, 多個 logical core 透過切換底層多個 physical core 的對應, 達到 OS scheduling 時間單位級(通常是 1~10ms)內的更細的 core switching, 而這樣的行為對軟體具有 transparent 特性, 也就是 software 完全不會意識到這樣的切換, 以為自己持續是在同一 core 上運作, 而這是 logical core 介面所造成軟體的假象. 以此方式達到底層是 HMP 但是軟體可以視為 SMP 的架構

這樣的想法, 在這個月與其他同仁討論, 但是因為實在不是在唸書時期, 也因為工作而無暇於找出這樣架構的相關研究 ...

而因為另一件事在看近日結束的 Hotchips 2015 的資料, 昨日翻著 slides 看到了這篇 poster - Under 100-cycle Thread Migration Latency in a Single-ISA Heterogeneous Multi-core Processor

儘管方向不同, 但是我快速地理解到這是不同面向, 但是目的完全相同的事情. (reference 中的第一篇是 2003 的論文, 但幾乎是這方向的經典)

有了 references 與 keywords, 花了點時間就找到了一些有趣的東西

1. Fairness-Aware Scheduling on Single-ISA Heterogeneous Multi-Cores

這篇是 2013 年的論文，主要以學理分析, 以實驗點出我開頭提到的問題, 並透過不同的大小核數量配置, 分析 throughput, runtime, fairness, 結論是透過 equal-time, equal-progress 的方式有助於軟體於 HMP 架構上的效能. 其中注意到 Hardware vs. software scheduling 這節 "By doing so, the hardware would be able to provide the abstraction to software of homogeneous hardware, while dynamically rescheduling threads among the cores in a heterogeneous multi-core within an OS time slice." 這即與我一開始的想法契合.

2. Multitasking Workload Scheduling on Flexible-Core Chip

Multiprocessors

這篇也是切分為 logical & physical core, 但是做的事情是 reverse HyperThreading

3. MIT Execution Migration Engine ( link-1, link-2)

一個支援 low-overhead thread migration 的 stack-based 計算架構

4. Dynamic Thread Mapping for High-Performance, Power-Efficient Heterogeneous Many-core Systems

這是以學理探討 threads 與 HMP core 動態對應的關係.

5. Hardware Round-Robin Scheduler for Single-ISA Asymmetric Multi-core

這篇與我原始想法幾乎一樣, 很可惜的是沒有做的很深入..

Put It Altogether! : Matrix Multiplication with libdispatch + Clang SIMD optimization

先前介紹過 Clang OpenCL vector 與 libdispatch
這裡以 Matrix Multiplication 為例將這兩者結合, 來顯示這樣作法的強大

相關程式碼可以透過 github 取得

git clone https://github.com/champyen/gcd_vector.git 

首先在 matmul8x8.h 中我們定義了需要 Matrix Multiplication 8x8 tiling 的介面

void matmul8x8(float *m1, int p1, float *m2, int p2, float *mo); 

其中 m1, m2 為需要相乘的兩個 8x8 矩陣, 而 mo 為 output
而 p1 為 m1 的 pitch size, p2 為 m2 的 pitch size

因此在 test.c 中, 我們透過這介面實作了Matrix Multiplication 的主 flow

    for(int y = 0; y < H1; y+=8){
        for(int x = 0; x < W2; x+=8){
            matmul8x8(m1+y*W1, W1, m2+x, W2, mo+y*W2+x);
        }
    }

接著實作了三個版本, 分別是 naive, tile 與 vec
naive.c: 這個版本單純是直接計算出 mo 於該位置的 output

void matmul8x8(float *m1, int p1, float *m2, int p2, float *mo)
{
    for(int y = 0; y < 8; y++){
        for(int x = 0; x < 8; x++){
            float val = 0.0f;
            for(int idx = 0; idx < p1; idx++){
                val += (*(m1+y*p1+idx)) * (*(m2+idx*p2+x));
            }
            *(mo+y*p2+x) = val;
        }
    }
}

tile.c: 這個版本中, 以 8x8 矩陣相乘為單位的方式累加出 mo 的結果

void matmul8x8(float *m1, int p1, float *m2, int p2, float *mo)
{
    for(int y = 0; y < 8; y++){
        for(int x = 0; x < 8; x++){
            *(mo+y*p2+x) = 0.0f;
        }
    }

    for(int idx = 0; idx < p1; idx+= 8){
        for(int y = 0; y < 8; y++){
            for(int x = 0; x < 8; x++){
                for(int idx2 = 0; idx2 < 8; idx2++){
                    *(mo+y*p2+x) += (*(m1+y*p1+(idx+idx2))) * (*(m2+(idx+idx2)*p2+x));
                }
            }
        }
    }
}

 vec.c: 這是個 tile.c 再加上使用 Clang OpenCL vector

typedef float float8 __attribute__((ext_vector_type(8)));

#define PF_DIST 8
void matmul8x8(float *m1, int p1, float *m2, int p2, float *mo)
{
    float8 vrow[8];
    for(int y = 0; y < 8; y++){
        vrow[y] = (float8)0.0f;
    }

    for(int idx = 0; idx < p1; idx+= 8){
        float8 vm2[8];
        int ofs = idx*p2;
        int ofs2 = PF_DIST*p2;
        for(int y = 0; y < 8; y++, ofs+=p2){
            vm2[y] = *((float8*)(m2+ofs));
            __builtin_prefetch(m2+ofs+ofs2);
        }
        ofs = 0;
        for(int y = 0; y < 8; y++, ofs+=p1){
            float8 vm1 = *((float8*)(m1+ofs+idx));
            __builtin_prefetch(m1+ofs+idx+PF_DIST);
            for(int idx2 = 0; idx2 < 8; idx2++)
                vrow[y] += vm1[idx2]*vm2[idx2];
        }
    }
    int ofs = 0;
    for(int y = 0; y < 8; y++, ofs+=p2){
        *((float8*)(mo+ofs)) = vrow[y];
    }
}

接著我們導入使用 libdispatch 來做多核運算加速
於 test_gcd 中我們改寫了矩陣相乘的 flow

    for(int y = 0; y < H1; y+=8){
        for(int x = 0; x < W2; x+=8){
            dispatch_group_async(
                group,
                queue,
               ^{
                    matmul8x8(m1+y*W1, W1, m2+x, W2, mo+y*W2+x);
                }
            );
        }
    }
    dispatch_group_wait(group, DISPATCH_TIME_FOREVER);

最後是實際的測試, 這裡測試的是兩個 512x512 矩陣相乘
由於 libdispatch 與 Clang OpenCL vector 的可移植性, 所以我們能夠在多樣的平台上測試
於 Raspberry Pi 3 上, 透過 SIMD + GCD 甚至可以得到超過百倍的加速而架構間的數據倍率差異, 也很值得去思考結果為何如此

Raspberry Pi 3: 114X

• test 18700284 us
• test_tile 2160980 us
• test_vec 358326 us
• test_gcd 6778646 us
• test_gcd_tile 1085776 us
• test_gcd_vec 164121 us

A8-5545m: 15X

• test 446682 us
• test_tile 2613739 us
• test_vec 48856 us
• test_gcd 239297 us
• test_gcd_tile 2638397 us
• test_gcd_vec 29957 us

i7-3612QM: 23.4X

• test 275879 us
• test_tile 224157 us
• test_vec 31457 us
• test_gcd 112845 us
• test_gcd_tile 92521 us
• test_gcd_vec 11808 us

20170116 UPDATED:
後續加入了 GCC 的支援, 相關數字已更新於 github 頁面上