解析 Qualcomm Hexagon 680 架構 I - V6x 架構

Qualcomm S835 於不久前發佈
其中內建了強大的 Hexagon 682 DSP
雖然在 S835 的發佈宣傳文中僅說明了新增了對於 TensorFlow 與 Halide Language 的支援
但是還是有發佈專文說明 Hexagon 682 DSP 即便與 Adreno 540 GPU 相較下
在 TensorFlow 與 Machine Learing 方面的效能與功耗效率的其表現出色
儘管 DSP 處理器這字眼對於程式工作人員並不陌生
但除了特定領域面向的工作者外, 有機會接觸者並不多
這與應用平台的可見度與普及性
以及各家 DSP 相關的軟硬體在架構與軟體資訊較為封閉有關

Qualcomm 自 S820 加入的 Hexagon 680 這顆運算性能強大的 DSP
(事實上先前即有 V5 的 DSP,  但是 HVX 讓 V6 增色不少)
相關文件與 SDK 皆有公開釋出, 所以是個很好的說明範例
而 Hexagon 682 應該與 680 相去不遠
因此這裡以系列短文介紹探討這顆 DSP 的架構

探討的內容為 Qualcomm 官網內的一份簡報與兩分文件 (需註冊帳號, 免費)
1. Architecture of the Hexagon 680 DSP for Mobile Image and Computer Vision
2. Hexagon V60/V61 Programmer's Reference Manual
3. Hexagon V60 HVX Programmer's Reference Manual

Hexagon 68x 為 Hexagon V6x 架構的處理器
而 HVX 為 Hexagon Vector Extension 的縮寫, 以 Coprocessor 的方式與 V6x DSP 整合運作
下圖取自官方文件 3. 的系統 blocks diagram

首先讓我們先以上圖來討論 Hexagon V6x DSP
Hexagon DSP 主要由 5 個部分所組成, 其中各個 block 意義如下:

• D$ - Data Cache
• RF - Register File
• I$ - Instruction Cache
• XU - eXecution Unit
• MMU - Memory Management Unit

另外有3個對外的控制介面, 分別是:

• AXI, AHB 對外的 Bus 與 Host 端系統整合
• 256b-wide L2-cache port
• Co-Processor Instruction Port 控制 Hexagon VX Co-processor

其中值得注意的地方是 AXI/AHB 以及 L2-cache port 中, V6x 內部中以 L2 Control 與 cache state/tag table 的 function block 連接著, 整個 Hexagon DSP 的資料, 都仰賴著 V6x processor 統一對外透過 AXI/AHB 而取得, 若了存入 L2-cache, 相關資訊則會以 L2 state/tag 紀錄, V6x processor 本身即能夠完全掌握系統中 L1 與 L2 一致性控制的管理. 而 HVX co-processor 即是在 V6x processor 控制流程與 data control 的方式下, 以兩個 512b-wide L2-cache port 存取資料來運作. 即便 HVX 所需資料發生 cache miss, 負責處理這問題的是 V6x proccessor 本身.

首先是 Cache Size, MMU 的相關資訊:

這樣的設計方式與其他 DSP 不同的地方在於它的 instruction 處理部分, 預設是採用 I-Cache 的方式, 以架構來說,  缺乏 I-TCM 的方式對於一些 hard realtime 的應用稍有不利的地方, 但是其支援了 hardware instruction prefetch 的能力彌補來這部分. 而 MMU 部分提供了 4GB 的定址空間, 作為 DSP 的 Virtual Address 與 Physical Address 間著轉換. 由於對於 ARMv8 系統都提供了 > 4GB 定址空間, 因此對於 V6x DSP 使用的記憶體區間應有軟體上或硬體上的限制.

接著來探討 V6x 的剩下的 XU 與 RF, 讓我們用官方的 architecture 圖來說明

透過官方架構圖, 可以看到需要探究的東西增加了, Control Registers 基本上是控制流程(Loop Regs, Predicate Regs)與提供流程相關(Status Regs, Program Counter)資訊的用途, 這裡就捨去不談, 這裡主要談 XU 衍生的 Sequencer + S0 ~ S3 以及 RF 所代表的 General Registers R0 ~ R31

對於 S0 ~ S3 來說, S 代表的是 Slot 的意思, 看到這個字眼稍有敏銳的人就知道接著要說的是 Very Large Instruction Word (VLIW), V6x processor 本身即為 VLIW 架構, 許多的 DSP 都採用這樣的方式, 其優點是:

• 簡化硬體設計: 對於 DSP 來說若採用 SuperScalar 架構會增加面積在 hardware instruction scheduler 的實作上, 除了增加成本外也增加 power/thermal 的風險
• 可精確分析與預期效能: 由於 VLIW 的指令排程是透過 compiler 來完成, 而硬體上來說的處理相對簡單, 因此執行上的時間, 若以 single loop iteration 而言 compiler 即能提供資訊, runtime 所需時間, 透過 simulator/emulator 就能得到很精確的時間估測

對於 VLIW 而言, 弄清楚每個 slot 能夠處理的指令是一個重點, 以下為 V6x 的 Slot-Instruction 配置說明:

可以看出, 除了共通的 ALU32 指令外, 每個 Slot  都有著其所被賦予的任務:

• Slot 0, 1: 主要負責記憶體的 load & store, 其中 Slot 0 更負責了 cache 維護, maintenance 與匯流排的操作.
• Slot 2, 3: 負責主要的負責數理運算, 以及 Vector 相關指令, 程式內部的流程控制 (J/JR/CR)

到這邊可能會有人想喊 "等等!!! Vector 運算 !?"
是的, V6x 本身即支援了初步的 64b-wide Vector 運算, 下圖為官方的指令範例:

但 V6x 有一點是特別的, 就是它的 Register File
主要是它將 General Register 與 Vector Register 整合在一起:

在操作上亦提供了便利的 32/64b Register Notation

對於 V6x 就以此簡短的介紹, 有興趣者可以再透過官方文件深入
下一篇會介紹讓 Hexagon V6x 大幅提升計算能力的 HVX

SIMD 加速的實例 - NEON acceleration of tiling in VC4 of RPi3

今日增加了 Matrix Multiplication 對於 GCC 的支援, 與相關效能數字後
(基本上 GCC 的 Vector 優化較 Clang 差)
一則關於NEON的新聞引起了我的注意
主要是 Broadcom 的開發者在OSS Driver 中使用 NEON 加速
其部分 Blog 原文引述如下:
"My first hope was that I could load a full cacheline with NEON's VLD.  VLD1 only loads up to 1 "quadword" (16 bytes) at a time, so that doesn't seem like much help.  VLD4 can load 64 bytes like we want, but it also turns AOS data into SOA in the process, and there's no corresponding "SOA-back-to-AOS store 8 or 16 bytes at a time" like we need to do to get things back into the CPU's strided representation.  I tried VLD4+VST4 into a temporary, then doing my old untiling path on the cached temporary, but that still left me a few percent slower on loads than not doing any of this work at all.

Finally, I hit on using the VLDM instruction.  It seems to be intended for stack loads/stores, but we can also use it to get 64 bytes of data in from memory untouched into NEON registers, and then I can use 4 (32bpp) or 8 (8 or 16bpp) VST1s to store it to the CPU side.  With this, we get a 208.256% +/- 7.07029% (n=10) improvement to GetTexImage performance at 1024x1024.  Doing the same NEON code for stores gave a 41.2371% +/- 3.52799% (n=10) improvement, probably mostly due to not calling into memcpy and having it go through its size/alignment-based memcpy path choosing process."

由於 NEON 中的 Vector load 指令 VLD1 "只能"一次讀入16bytes, 因此原本計劃採用了 VLD4 期望來一次大量的讀入資料, 但 VLD4 這個指令會做類似 AOS(Array of Structure) 轉 SOA (Structure of Array) 的動作(其實是 de-interleave), 而且並沒有一次 SOA轉回 AOS 的指令, 該開發者嘗試過 VLD4+VST4 然後再利用原有非 tiling 的作法, 但是還是比慢上了許多. (其實這樣使用 VLD4 的作法, 基本上有 register spilling 的疑慮, 再者 VLD4 基本上還是透過 L/S unit, 基本上由於 ARM 的 NEON unit 的實作, 基本上並不會比 VLD1 好)

最後他採用了 VLDM 指令(這個指令可以參考這篇), 基本上這指令帶來的好處是不用會 touch 到 NEON registers, 並且能夠處理的長度也較長, 最終該開發者在讀取的 GetTexImage 得到了 208.256% 的效能改善,  並且在寫入獲得了 41.2371% 的改善. 開發者認為這或許歸功於避免直接呼叫 memcpy, 並採取 size/alignment-based 的對應流程.

從 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

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

CLTK - OpenCL ToolKit

臉書原始貼文
這是個 2016年8月 開始的個人專案
對於 OpenCL 有興趣者歡迎 feedback 討論
==
兩年多前, 寫了第一個關於 OpenCL 名為 clscript 的 github 專案
但連自己都缺乏感動, 妥協的設計也沒有動力去維護
近日工作上因為一件關於 OpenCL 的事情帶來一點成就感
儘管手邊的案子已經 run 了十個多月
這個案子技術上的特殊性造成 GL 不適用
當時為了方便與簡化 CL 帶來流程複雜性
給自己寫了一套 OpenCL 的 toolkit 使用
無情的是功能需求上只要客戶不買單, 那就沒有什麼好說的
因此目前還在持續努力 review 與改進之中
而加上由於類似的應用功能並不是第一個面市
相關時間與效果的要求變得很嚴苛
實作特性上客戶要求去 align 對手方案是難以避免的

而這兩週演算部門被要快速提出類似演算與整合
但要求的時間很短, 演算開發者很快也發現之前他們寫的 GL routine 不適用
由於之前知道個人有實作類似功能而詢問我
麻煩的地方是手邊的事情也蠻趕的
只好請演算開發負責人看一下我的 flow
轉寫時幫忙依樣畫葫蘆寫手機上的 code
而 CL 的 GPU kernel code 我便會抽空負責幫忙改一份適用的
在接到演算部門的code 後,
昨日上午只花了兩個小時就把事情完成了
這比我預期的短非常多
其實不管別人如何想, 一旦把事情做對做好
必要時它也會對你回報
受到了這件事的激勵
加上一直有個想實作的東西, 而類似的東西亦是必要的
於是這兩晚就以相關經驗從無到有再重新設計與撰寫
產生了這第二個 github project - OpenCL ToolKit
比起第一個 clscript, 新實作的 CLTK 個人認為實用許多

https://github.com/champyen/cltk

CLTK 有個基本精神, 希望使用 .cl 檔案能像是以 dlopen 方式使用 C 的 .so 檔
另一個 CLTK 與其他類似工具最大的不同點在於:
參數傳遞上大幅簡化
除了dimension(類似 loop 有幾層) 與 workitem 的 size (類似 for-loop 的 size)之外
使用上只要知道 kernel function 的宣告, 參數就只要如同呼叫 C function 般地將參數傳入
無需如以往地針對不同 kernel function 各自撰寫一份用以呼叫特定 function 的 glue code
code 的雜亂度會大幅降低, 能更著重於整體流程結構與在 GPU 上執行的 .cl code 的撰寫

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 頁面上