2017年2月11日 星期六

OpenCL Programming for Intel FPGA 初探 - III

這篇主題進入到了 OpeCL Programming for FPGA 的優化
內容主要圍繞在官方文件 - Intel FPGA SDK for OpenCL Best Practices Guide

首先必須要知道在 FPGA 上程式撰寫的快慢與計算的多寡並無直接關係
其重點在於計算間是否存在 dependency
儘管計算煩雜, 但是多數能夠平行運作, 在 FPGA 上就能更快的計算
對於 OpenCL for FPGA 的思考在於 pipeline stage 的長度與使用的 resource
下圖為官方所使用的一個簡單的範例:
儘管例子中使用了 5個運算, 但是實際的運算方式會是如上圖
而再透過 pipeline 的處理即可達到 II =1 (initiation interval) 的情況:

如上圖所示, 這麼一來即如同於 5 instruction per cycle, 能夠這樣做的原因在於對於一般的處理器而言, 僅有著有限的 register, 因此 processor 必須透過 DRAM access 來達到處理較多的資料, 而甚至因為變數數目的關係, register spilling 效應會讓 processor 為了暫存資訊更頻繁的讀寫 DRAM, 因而造成程式效能的惡化. 但是 FPGA 可藉由 Flip-Flops (FF) 來在 pipeline 的 stages 中存放這些資訊.

但是由於 FPGA 這樣的特性, 在 Kernel 之間傳遞資料也需要更好更有效率的方式, 因此 Pipe/Channel 的使用是很重要的, 碰到演算上因記憶體頻寬限制所造成的效能問題, 基本上的處理原則即是將演算再切分為多個 kernel, 並且將 memory access 部分改以如下圖的方式使用 pipe/channel, 藉此來處理.


在 Kernel 中的 loop 處理上, 必須透過優化讓 loop 的 initiation interval 達到 1, 下圖為官方文件所提供的 optimization 策略的決策圖:

至於而何為 initiation interval, 為何它這麼的重要? 下圖凸顯了若 II 不為 1 時的差異, 主要在於 loop 若非 pipelined, 效率上的 throughput 會呈倍數差異.

上述的資訊,在 Intel FPGA SDK 環境中有提供 Loop Analysis Report, 能夠以此觀察 loop 優化的情況.
從上圖得知從 Loop Analysis Report 中可以得知 unrolled 程度, 是否 pipelined, II 以及 Bottleneck 的點, 對於 Loop 撰寫的優化有很大的幫助.

除此之外, SDK 中還提供了 Area Report, 以下為一個例子
在 Area Report 上面可以觀察到下列幾點的欄位, 也就是在系列文 II 中為何要了解 FPGA Architecture.
  • ALUTs : 即為 LE 中的 用以實作 4-input 任意函數的 LUT
  • FFs : 這部分是 Flip-Flop, 也屬於 LE 中, 通常消耗在 pipeline stage 中的 register
  • RAMs : 這是 memory load/store 的行為
  • DSPs : 這是使用到的 DSP block 數量
對於在 FPGA 平台上 OpenCL Kernel 上的撰寫除了 pipe/channel 與 loop 外的其他考量即是圍繞在上述幾個點, 因此官方以 Matrix Multiplication 為例子, 提供了優化的過程的 code 與對應使用的方式, 下圖為 Matrix Multiplication 優化中的上述幾個點的變化過程:

這裡並不做細部的探討, 有興趣者請閱讀官方文件章節 1.4.2 ~ 1.4.5 , 但是對於各版本中使用的優化技巧, 簡述如下:
  • v1 : 使用 local memory 方式降低 memory access
  • v2 : 以 loop counter + 條件計算 row 值, 減少使用 % 運算. 這運算同除法會消耗大量 ALUTs/FFs
  • v3 : 對於 offset 的計算改以在 loop 中累加的方式, 取代以乘法計算, 如此可降低 DSPs 的使用量
  • v4 : 使用 per-colume 的累加方式, 最後在計算, 來降低因 data dependency 造成的 II 為 8 的 loop (增加了一個 loop 與多使用了變數, 因此 ALUTs/FFs 增加了, 但是效能變好)

對於 local memory 的使用也並不是直接使用了就沒問題, 對於 local memory 除了需要指定大小外, 還有 bank 的相關參數來避免 access stall 的發生, 若沒有足夠的資訊的話 compiler 會產生 local memory LSU 的邏輯線路來控制與管理 local memory access, 然而 LSU 的使用可能導致效率的降低.
此外 local memory 的大小使用由於 FPGA 的 memory block 的因素, 使用的大小會 rounding 為相關大小的倍數, 因此在使用的精算中必須考量到這點.

在官方文件中後續 1.6 ~ 1.9 又詳述了針對下列幾個面向的 Optimization Strategy:
  1. Single-WorkItem: 這階段為 Optimization 的根本,  因此文件除了列出的三點也提供了下圖詳盡的 workflow:
    • 依照 analysis report 來改進
    • 移除 loop 間的因 memory access 造成的 dependency
    • 良好的設計練習 
  2. NDRange
    • 限定最大的 WorkGroup 大小, 或是要求特定的 WorkGroup 大小
    • Kernel Vectorization
    • 產生多個 Compute Unit
    • Kernel Vectorization + 多個 Compute Unit
    • 依照 resource 的使用面向來優化
  3. 改進 memory access 效率
    • 優化 Global Memory Access
    • 使用 constant, local, private memory 來做計算
    • 將變數存入 private memory array
  4. 優化 FPGA Area 的使用
    • compilation 的參數
    • memory access 的考量
    • 運算上的考量
    • 資料型別上的考量
除了上述依照 compilation report 的 optimization, 在 runtime 上可能還需要使用 profiling tool 觀察實際運作的情況, 官方文件 1.5 的部分即是介紹 profiling 相關的功能如何使用, 以及提供了哪些數據.

2017年2月10日 星期五

OpenCL Programming for Intel FPGA 初探 - II

在進入針對 OpenCL for FPGA 的優化過程之前
人們必須先了解 FPGA 是如何的裝置, 與 CPU 與 GPU 在本質上的不同之處

Architecture Overview

若以低階的 Altera Cyclone V 來看的, 我們可以從其 Handbook Volume 1 看到其架構組成
由上圖可以看出 FPGA 的主體主要由三種 block 組成
  • CoreLogic Fabric and MLABs : 主要為邏輯與簡易計算的 blocks, MLAB (memory logic array block) 基本上是通用的 SRAM array, 亦可以被設定作為 RAM/ROM 的用途
  • M10K internal Memory Blocks : dual port 的記憶體 blocks, 可以存放 processor code, 用以實作查表設計, 與實作較大的記憶體應用. (像是 OpenCL 中的 local_memory)
  • Variable-Precision DSP Blocks : 可變精準度的 DSP blocks, 透過使用數量不等的區塊可以串聯出整數/浮點數精準度不同的乘法與運算單元.

與 CPU 不同的是, FPGA 的性能主要取決於上述三種 resource 的數量, 另外應用上使用的 resource 若無法壓低, 可能無法塞入 FPGA 上執行, 這是要注意的事情, 所以應用的選擇上必須注意規格, 下圖即為 Cyclone V SE SoC 內 FPGA resource 的表格:
從上途中可以觀察出一些數字是彼此相關的, 像是 18x18 multiplier 的數目與 DSP blocks 是直接成倍數關係的, M10K memory 大小 與 M10 memory blocks 數目也是如此, 這兩個部分分別對應了三種區塊的 M10K memory 與 DSP blocks, 然而第一項的 CoreLogic Fabric 呢?

Logic Elements

這部分需要從 LEs 這個數字解釋起, LE為 Logic Elements 的縮寫, 從 Altera 的解釋, LE 為其 邏輯部分的最小單位, 提供了下列功能:
  •  4 組輸入的 lookup-table(LUT) 功能, 可以實作任何 4 變數的函數
  • 可程式的 registers
  • carry chain connection
  • register chain connection
  • 多種功能的 interconnection
  • register packing, feedback
而上述的部分必須又必須從 Adaptive Logic Module(ALM) 來解釋, 下圖為 ALM 的 block diagram:

對於 ALM 官方文件是這麼描述的 "The ALM uses an 8-input fracturable look-up table (LUT) with four dedicated registers to help improve timing closure in register-rich designs and achieve even higher design packing capability than previous generations.", 而 LE 官方文件的說明為 4 組輸入, 由此可得知 ALM 為 > 2 LE 的組合, 這推斷也與官方提供的表格數字間符合.

DSP blocks

在程式中所使用到的乘法與浮點運算必須使用到 DSP blocks, 因此對於 FPGA 而言是相當重要的運算資源, DSP 提供了18b 與高精準的兩種運算模式:
此外亦單一 DSP block 提供了單精準浮點數運算以及串連4個 DSP block 形成倍精準浮點數運算

了解這些 FPGA 內部資源與用途與後續的 optimization 有很大的關聯

2017年2月5日 星期日

OpenCL Programming for Intel FPGA 初探 - I

前一陣子許多新聞都提到使用 Intel FPGA 搭配 OpenCL 來加速應用的開發
像是中興電訊(ZTE)  透過 Intel FPGA 來開發人臉識別的加速
其實 Altera 相當早就開始將 OpenCL 導入到 FPGA Programming 這塊
在 2011 年 Altera 的簡報是這樣類比的 - VHDL/Verilog 很類似"組合語言"程式設計
而 OpenCL 讓軟體開發者能夠利用硬體加速

由於這些日子來的一些例子也令我有不同的思考
開始讓個人非常想了解這樣的 Programming Model 的不同, 以及其特性與優缺點為何
因此開始投入 Intel FPGA OpenCL Programming 的探索

現今相關的軟體 Intel 都有提供在網路上, 硬體上取決於規格價格落差也不小
台灣的友晶科技有販售相關的平台, 可以自行了解與選購
但目前先單以 Intel 提供的官方文件來討論 OpenCL Programming for Intel FPGA

Programming Overview

Intel FPGA SDK for OpenCL - Getting Starting Guide: 其中對於了解階段最重要的地方在於
它圖示了整個流程的 overview
可以看出 .cl 的 kernel 透過 SDK 分兩階段編譯為不同的 .aocx, 一者為 emulation 所使用, 另一為實質在板子上的運作時所使用, 而這文件其他篇幅著墨在環境的建立上. 一方面也可以了解, OpenCL for Intel SDK 應不俱備 Online Compiler 的方式, 可能皆以 Offline Compilation 方式開發.

Intel SDK for OpenCL - Programming Guide:

Schematic Diagram

這篇文件在流程上延伸了上述的圖, 提供了 host, kernel 與 custom part 的流程
在 Getting Start 的那張圖示, 其實在解說中間 "Kernel Code Path" 在不同開發時期的產生方式, 而這張圖是講述完整的開發流程中, Host/Kernel/Custom 相關的各部分是屬於從何而來. 這張圖也揭示了, 開發過程僅有 Offline Compiler.

文件中提供了以 PC + FPGA 卡的角度來看待這個流程:
這張凸顯了, 能夠搭配多張 FPGA 卡來負責不同的部分, 透過載入不同的 FPGA binary 就可以將功能的不同部分在不同的卡上運作.

Channel and Pipe

為了 mapping FPGA 的運作方式到 OpenCL, 提供了特別的方式: Channel 與 Pipe.
事實上兩者性質很類似, 但是 Channel 為 1.x 時針對 FPGA 部分, Altera 所提出的 extension, 而 Pipe 是 OpenCL 2.0 中標準有提供的 inter-kernel 間資料串連的方式.
而對於 FPGA 中, 使用 Channel/Pipe 要思考的運作方式如下:
也就是 Kernel 與 Kernel 間以 FIFO 方式來串連與傳遞資料, Host 並不介入資料的傳遞, Kernel 也不透過對於 RAM 的讀寫來傳遞.

Manager-Producer-Consumer Working Model

而對於 Kernel 間 Buffer 的傳遞, SDK 文件中建議以 Manager, Producer, Consumer 這3個角色的 Kernel 來實作.
而透過圖中描述的四步驟周期, 來彼此協調控制流程, 並作一些 resource 的 ping-pong 使用
  1. manager kernel 送出 token set 給 producer kernel 來告知哪些記憶體區塊是給 producer 使用
  2. 在 manager 配置好記憶體區塊後, producer 對該記憶體區塊的 ping-pong buffer 寫入資料
  3. 在 producer 完成寫入動作後, 它送出同步 token 給 consumer kernel, 來告知記憶體區塊有著資料待處理. consumer kernel 然後就自該 ping-pong buffer 區塊讀取資料
    • 必須注意的地方: 當 consumer 在執行讀取動作時, 由於 FPGA 同步運行著 producer, consumer 與 manager kernel 的緣故, producer 是能夠寫入資料到其他尚未使用的記憶體位置,
  4. 在 consumer 完成讀取動作, 它釋放了該記憶體區塊, 然後送 token 給 manager kernel. 而 manager kernel 就回收該區塊以提供給 producer 使用.

Memory Partition of Global Memory - Burst-Interleaved vs Separate

Global Memory 不管對於 CPU/GPU 而言都是相當遙遠的, 必須考量頻寬與 latency, 因此對於操作上有著不同的特性, CPU 有著 cache,  GPU 仰賴著 local memory 與 many-threads 方式. 在 FPGA 上, 為了的達到較高的頻寬使用, 預設使用 Burst-Interleaved 方式, 若要自行分割也提供選項關閉, 並且在 Host Coding 中自行指定使用的 Bank.

OpenCL Library

若有常會使用的功能, 或是以 OpenCL 的方式實作較無效率的功能, Intel FPGA SDK 也提供以 OpenCL 或是 HDL 的方式實作再以 OpenCL Library 的方式導入. 而 SDK 內已經內部預先做好的 library, 開發者也能自己實作屬於自己的 library.


使用的方法如上流程圖所顯示, 實作的 OpenCL Kernel 與 OpenCL Library 透過 SDK Offline Compiler 最後產生 .aocx 的 FPGA 執行檔案.

Parallel Execution Model of AOCL Pipeline Stages

而功能的實作上, 要考量的與 CPU/GPU 上的 OpenCL 的考量不同, 對於 CPU/GPU 的實作上, 通常考量的是 SIMD 與指令使用上的考量, 能夠 SIMD 化, Exec Unit 的數目與種類, 或是否具有專屬加速指令. 但而對於 FPGA 考量的是流程上的平行度以及最後完成的長度, 再加上所使用的 resource 與 path 長短(這部分會留待第2篇), 而這些其最主要的考量為實作後整個 function 的 latency. 如下圖的 Kernel, 其從頭到尾需要 4 cycles.

2017年1月30日 星期一

從 "Three tips for maximising your SoC performance" 看軟體優化

先前 ARM 官方提供了 Free Webinar "Three tips to Maximize your SoC performance"
目前簡報的錄影與投影片都已經上線, 填入一些個人資訊即可閱覽

從報告的內容可以看出這個簡報是為了其 "System Guidance" 服務提高能見度
但是從設計原則中也有許多軟體人員可以作為借鏡並思考的地方
而以簡報中對於 SoC 設計上三個對於效能的考量為:
  • 最短化自 CPU 到記憶體路徑 - 每個 clocks cycle 都會歸屬到 CPU latency
  • 最大化系統頻寬 -  確認系統記憶體已經對於效能優化
  • 依流量種類管理流量 - 在系統符合即時性的情況下, 儘可能提供 CPU 優先權

而從軟體優化的角度來看, 這三點反映了對於效能上, 實作上的考量為:
  • 評估各種類型記憶體的 memory latency: 了解 memory latency 才能評估效能, 並且透過理解 cache 管理的機制來避免不當的行為所造成的過長存取時間. 此外理解 CPU 的硬體設計是透過何種方式來克服這問題, 以此來分析軟體上對於硬體差異在效能落差的影響.
  • 量測平台系統的頻寬: 透過 profiling 與 behavior analysis 能了解何時程式達到了 bandwidth bound, 才能採取對應的優化方式
  • 了解應用上可能同時競爭頻寬的硬體: 應用上所仰賴的 GPU 與 硬體加速器都會消耗頻寬
對於 latency 問題主要採取的策略有上述三項, 這三者的意義分別是紙上架構推估, 以軟體模擬
推測, 實際硬體上的量測, 三個不同階段

上圖為以 SGM-773 (System Guidance for Mobile) 的推估 memory latency 的方式, 若僅考量單次的存取, 請注意 85.1ns 這個推估時間約為 209 CPU cycles (也可以看出 CPU 內 cache 為 15 CPU cycles, 而出了 CPU 到了 CCI 則會超過 50 CPU cycles ). 這樣的計算通常能夠以此推敲 best case 與 worst case (考量各階段的 queue depth)的狀況, 也能得知架構上的物理限制, 與合理的數值範圍.

此外 LMBench 也是不錯的工具套件, 以 latency 來說是其中 lat_mem_rd 這個工具,下圖為使用 SGM-773 平台透過 LMBench 去量測後的結果

有興趣者可以先於自己的 ubuntu 平台上安裝 lmbench 套件, 接著執行下列指令:
/usr/lib/lmbench/bin/x86_64-linux-gnu/lat_mem_rd 16 128
其中 16 代表為 16MB, 也就是 bench 的大小上限為 16MB
而 128 所代表的是 stride 大小, 執行後可以看到類似下列的 log:
"stride=128
0.00049 2.361
0.00098 2.361
0.00195 2.362
0.00293 2.361
0.00391 2.361
0.00586 2.361
0.00781 2.361
0.01172 2.361
0.01562 2.362
0.02344 11.838
0.03125 11.819
0.04688 11.827
0.06250 11.816
0.09375 11.818
0.12500 11.825
0.18750 11.822
0.25000 11.817
0.37500 12.190
0.50000 12.182
0.75000 12.188
1.00000 12.188
1.50000 12.249
2.00000 19.838
3.00000 37.352
4.00000 38.298
6.00000 39.394
8.00000 39.920
12.00000 40.455
16.00000 40.674
這裡每行的兩個數字, 前者為該次測試的大小, 後者為測出的 latency 以 ns 計
上面測試的為個人使用 A8-5545M 平台所測出的 (L1: 16KB, L2: 2MB)
可以觀察到對應兩個 size 的 latency 轉折


事實上, LMBench 也提供了 bandwidth 的估測工具 - bw_mem
簡易執行指令如下:
/usr/lib/lmbench/bin/x86_64-linux-gnu/bw_mem  16K rdwr
也就是測試以 16MB 為大小的 Read/Write 頻寬, 有興趣亦可以調整前面的 16K 的數字
輸出有兩個數字:
0.016000 9801.85
前者為所要求測試的大小 (16KB 為 0.016M), 後者為 MB/s (也就是測出為 9891.85MB/s)
了解系統的能力, 對於針對平台的軟體優化有相當的幫助 (像是 tiling 與批次演算作法, 其分割大小能夠以 L2 大小做考量)

2017年1月25日 星期三

解析 Qualcomm Hexagon 680 架構 III - Thread Model and Execution Model

Thread Model

最後讓我們講述 Hexagon 680 的 Thread Model
在 Qualcomm 開發 DSP 的過程中一直都有 Hardware Threads 的支援
因此在談 Hexagon 680 的 Thread Model 前, 讓我們先來看看 V5x 的 HW Threads

上圖為 Qualcomm 在 2013 年 Hotchips 會議上投影片的 Page 11
從這圖可以看到 Hexagon 680 的 V6 基本上與 V5 架構差異不大
也是 4-slot VLIW, 兩個是 Data Unit, 兩個是 eXecution Unit
同個 DSP 核心具有3個 Thread Context, 在硬體設計上已考慮簡化多工上的需求

在 2015 年度 Hotchips 中 Qualcomm 簡報的 Page 8:
由此可見, V6 Scalar DSP 以 2Ghz 頻率運作
俱備 4 HW Threads 支援, 每個 thread 以 500Mhz 運作
而 HVX coprocessor 以 1Ghz 頻率運作, 具有兩個 context, 一樣每個 thread 以 500 Mhz 運作
因此同一時間可以有兩個 Thread 控制著 HVX, 另外兩個處理 Scalar 工作
但光以上看投影片, 不知道是否有人懷疑過, 或許 V6 DSP 為 quad core, 而 HVX 為 dual core?

這裡我們回到 HVX 官方文件當中:
從這張圖可以看出, V6 DSP 具有的是 1C4T, 而 HVX 為 1C2T
但是, 官方在投影片與到此中所說明的, 並非 Hexagon 680 所有的模式
如果還有印象, 在系列文II當中留了一些不確定:
1. HVX 對於 L2 的總寬度為 512b x2, 而非 1024b x 1
2. 對於 VPF/VRF 的描述, 我加了 "基本上" 這個有所保留的詞

再談這之前, 先來介紹 HVX 的 Vector Modes:

也就是 HVX 中支援了兩種不同長度的 Vector
  • 64B 模式, Vector 寬度為 512 bits
  • 128B 模式, Vector 寬度為 1024 BITS
而這樣的模式並不是像 NEON 中分為長短 vector 並且可以混用, 而是如上圖, 直接將所有的單元(VX, VPF, VRF), 以 512b 寬度的方式等分為二

所以除了 1C2T(128B) 的方式外, 事實上 HVX 還存在另一種 HW thread 的型態 - 1C4T (64B)
在這個模式下, 4 個 V6 HW Threads 各自都可以控制一個 64B Vector Mode 的 VX Thread Context. 所以 Hexagon 680 提供多元且彈性的運作模式. 而這也說明了 系列文II 當中沒交代清楚的部分.

Execution Mode


Qualcomm 曾經官方撰文介紹過 Hexagon DSP 的軟體開發
在 Qualcomm 裝置上, 在 DSP 上執行工作需要幾個步驟:
  1. 下載與安裝 Qualcomm Hexagon SDK
  2. 將你於 DSP 上實作的功能 API 以其 IDL (Interface Description Language) 方式描述.
  3. SDK 會自動產生 Header files 與 stub (下圖中應用處理器端, 也就是 ARM 處理器端提供給 client 的呼叫介面, client 通常是其他的 library 或是 executable)及 skel (DSP 端去呼叫你實作功能的進入點) 等相關函式庫.
  4. 在 DSP 端實作你的 API, 並與第3點中自動產生的 skel 函式庫 link 成為一個 shared object 並放置於該平台裝置中.
  5. 將你的 native APP 與 link 到第3點自動產生的 stub 來呼叫你的 API.
  6. (選擇性) 建立你的 API 專屬的 Java bindings 好讓 APK 能夠使用.
而這些背後所仰賴的機制的核心即是上圖所描述的 FastRPC

一旦 Native APP 呼叫所需的 function, 便會執行自動產生的 Stub lib, 它會 透過 ARM 與 DSP 間橋接的 Driver-Framework, 載入先前所產生的 DSP 端的 shared object, 而 DSP 端上的 OS 會動態地載入該 object, 並且以 Skel 介面處理來自 ARM 處理器端的請求.