嵌入式系統第十章（多核心系統）
===
###### tags: `嵌入式系統筆記`

## 1. 對稱和非對稱多工處理
* 依照其他系統軟體之間有無監測其他軟體使用資源之狀況分為對稱和非對稱。
* 對稱式多工（SMP）
RTOS 為即時作業系統，特色為即時性
SMP不適合處理資料密集應用程式，像是影音
* 非對稱式多工 (AMP)
又分為同質性AMP和非同質性AMP，差別為是否使用同樣的作業系統，而非同質性AMP必須嚴格定義好各處理器間的溝通。
AMP 比較適合影音處理。
AMP 對於多工處理比SMP更經濟，不管是效能、所需能量、空間等。

## 2. 平行處理可以節省能源
* 因為耗能的關係，過去以提高時脈或新架構提高CPU效能的方法漸趨困難
* 在耗能上比較單一CPU和多CPU：
設以單一CPU達到A效能則電路有電容值 C 、電壓 V 以及頻率 F
所以可以得到 $$power_{CPU*1}=CV^2F$$
再考慮以兩顆CPU同樣達到A效能，則
-> 電容值變為兩倍，再加上CPU間管理電路，在此設為 2.1 C
-> 電壓應為單一CPU電路之一半但稍微做預留假設為0.7 V
-> 頻率則降為一半，設為 0.5 F
所以我們得到 $$power_{CPU*2}=(2.1C)(0.7V)^2(0.5F)=0.5145CV^2F$$可以節省約$1-0.5145=0.4855$，節省約49%耗能

## 3. 使用平行處理的時機
* 範例：假設我們有以下程式碼
1. A=B+C
2. D=A+2
3. E=D+A
4. For (i=0;i<E;i++) (迴圈一定會跑完)
5. N(i)=0
則，其中1～4必須依序執行，因為使用到的變數依序產生，而5為可平行處理部分，4和5可以同時做因為知道E的值就可以知道i的值了

* Data Dependencies (資料相依性) 會限制CPU不能做平行處理
1. True data dependencies：在某些演算法中可能可以重新構建演算法解決
2. Antidependence：常見於 sequential code，例如多工處理時， for 迴圈外定義的變數在迴圈內重複使用可能導致競爭，因為 iterations 各自平行在執行，這時可以讓每個 iteration 用 local variable 運算，減少變數生命週期以將低此種資料相依性
3. Output dependencies：在上圖中，最後一行對 A 的指派不能移到第一行之前，不然變數值會不對

* 效能計算
假設我們有以下 tasks 需要排程
則在單核系統上我們必須最少花12單位的時間
----------分隔線-------------
在雙核系統上必須最少花7單位的時間，比起單核快了 12/7=1.7..倍
----------分隔線-------------
在四核系統上必須最少花5單位時間，比起單核快了 12/5=2.4...倍
----------分隔線-------------
計算加速程度
上圖 f 為小數，表不可平行處理的 task 比例，所以計算單核與多核的時間比率為
$$ \frac{t_s}{t_p}=\frac{t_s}{f*t_s+\frac{(1-f)*t_s}{n}}=\frac{1}{f+\frac{1-f}{n}} $$
由下圖和公式可以看出在同樣的 task 下，一味的增加 N 並不會線性提高加速程度

## 3.1 多工處理的粒度
* Granularity (粒度)可以定義為在一個平行處理的程式中 computation 和 communication 的比例

* Coarse-grained parallelism (粗粒度平行運算)：由 task 拆解的工作之間彼此溝通成分較多，例如拆解一個 app 變成數個 high-level task 再送入多核執行，優點是同一時間有更多平行運算在執行但是 point 更少，缺點是 high-level task 對CPU的負載可能不一樣、不平衡。
* Fine-grained parallelism (細粒度平行運算)：將 task 拆解成較不需溝通的小工作，缺點是可能會產生很多 synchronization points 因為可能每個 iteration 都被插入一個 point

## 多核心應用本地化
為了加速多核心系統，我們必須減少搬運資料到CPU的時間 (Data reuse、Data locality)
* 多核心系統通常鄰近 CPU 的 Cache 比較大
* 範例：block matrix multiply，reuse data
分析結果請見jupyter notebook/嵌入式系統/Block Matrix Multiply

## 4.1 負載失衡
指多核心系統中因每個核心所分配之 task 不同可能有某核心或資源閒置
## 4.2 Data Parallelism (資料平行)

將資料切割讓多個核心同時處理
## 4.3 Task Parallelism (任務平行)
將任務切割讓多個核心處理

<strong>以上兩者應該不能理解成同一工作可以套用這兩個方法同時做</strong>

## 5 多核心程式模型 (Multicore Programming Models)
通常，多核心的程式模型會包含以下三點
* Control: 平行的架構和相依性如何建立，例如，決定 thread 的執行順序
* Data: 資料的共享或隱藏，例如，決定在多執行緒下那些資料應該共享，那些不行
* Synchronization: 決定那些 operation 可以平行處理，那些不行，例如，定義明確的"機制"調節 data 的訪問權
---------分隔線----------
有兩種模型供選擇，左邊是以 thread 實現平行處理，會有共享記憶體可以溝通，右邊是 CPU 執行不同 process 實現平行處理並且彼此以 message 溝通

在 share-memory 的系統可以使用 OpenMP 這類的函式庫幫我們實作 data 的 lock 或 flag，或是使用 pthread
在 message-passing 的系統中 可以使用像是 Message Passing Interface (MPI) 這類的函式庫

## 6 多核心系統的效能及優化
首先，優化可能是個大坑，因為過早過多的優化都是不好的，對於進度有負面影響
以下介紹多核心系統在軟體方面優化應該考慮的面向
1. 為專案選擇適合的CPU
* latency-oriented / throughtput- oriented
* $\color{red}{hardware acceleration Yes / No}$
* heterogeneous architecture / homogeneous architecture
* compiler
* operating system

2. 先增加 serial Performance (尤其是 Instruction-Level Parallelism)
* 指令層級平行（英語：Instruction-level parallelism，縮寫為 ILP，也譯為指令級並行），一種平行計算形式，在一個程式運行中，許多指令操作，能在同時間進行。
它也是一個測量值，用來計算在一個程式運算中，它有多少個指令能夠在同時間運算，稱為指令層級平行度。
* 提高ILP最常見且最簡單的方法，就是於迴圈裡每次迭代間來開發平行，這類的平行稱為循環層級平行(loop-level parallelism)，因為每次迭代的資料跟上一次的資料並沒有關係，故每次迭代可以跟其他次迭代並行。
#### 針對ILP的基本編譯器技術

* 為了增加平行度，編譯器要盡可能將指令間的相依性找出來並做scheduling，編譯器最常用的方法就是loop unrolling。

3. 適當的負載平衡(在 SMP Linux 上)與排程
* Linux 本身就有支援多核心系統，像是 SMP schedulers、different form of synchronization、load balencer for interrupts、affinity-scheduling 以及 CPU isolation，所以如果使用得當就可以增加系統效能
* Linux 的 process scheduler 對於多個 process 的排程的基於
1. 對於 process 平均分配核心
2. 適當選擇下一個應該被執行的process
3. 若有需要，重新平衡 SMP 系統中 process 到多核心執行的優先權
* 負載平衡有兩種通用方法：推送遷移和拉取遷移。
1. 使用推送遷移，特定任務會定期檢查每個處理器上的負載，如果發現不平衡，則通過將進程從過載的處理器移動（或推送）到空閒或不太繁忙的處理器來平均分配負載。
2. 當空閑處理器從繁忙處理器中拉出等待任務時，就會發生拉式遷移。
3. 推和拉遷移不需要相互排斥，實際上通常在負載平衡系統上並行實施。

* 使用到多核心系統的 app 可分為 $\color{red}{CPU bound 和 I/O bound}$。前者為執行運算居多 (例如 server)，後者則花費大部分時間等待相對慢的 I/O 運作 (例如手機等待使用者輸入)。**兩者的 trade off 在於若花多一點時間在運算，則 I/O 必須等待更長但能完成比較多工作**

4. Improve Data Locality (減少系統搬運資料的時間)
* 在程式設計時可以分割重要的部分留在 $\color{red}{Cache}$ 以減少程式搬運資料的距離

5. 減少或消除 False Sharing
False Sharing 只發生在多執行緒，因為資料相鄰太近所以在這些資料被搬進 $\color{red}{Cache line}$ 時他們也會相鄰，可能會造成 Cache line 一直需要被更新
{%youtube kMRLgCtxjvg %}
解決方法為在資料做 padding 的動作
{%youtube Ms0uYlnauUM %}

6. 在需要時使用 Affinity Scheduling
* 指定一個 thread 在某一個核心上執行，避免 OS 自身的排程頻繁的更換此 thread 的執行核心導致花了很多時間在搬資料，在 Linux 系統上程式碼為
PID 為 process 的 ID，len 為 $\color{red}{bitmask}$ 的長度，ptr 為指向 bitmask 的 pointer；bitmap 可以用來設定要用哪一個核心
*但可能也會導致其他不明顯的問題，要小心使用，阿這不是廢話嗎...

7. 使用 Lock 的粒度和密度必須斟酌
* $\color{red}{lock 在 OS 中是運作成本高的API}$
* 在太細部使用 lock 迫使 OS 浪費許多時間，也增加出現 $\color{red}{deadlock}$ 的機會
* 在太大範圍使用 lock 會增加主程式的耗時，因為某區段程式碼不能執行直到 lock 被解除
* 所以你可以：
1. Organize global data structures into buckets and use a separate
lock for each bucket
2. Design the system to allow threads to compute private copies of a
value and then synchronize only to produce the global result. This
will require less locking
3. Avoid spinning on shared variables waiting for events
4. Use atomic memory read/writes to replace locks if the architecture
supports this
5. Avoiding atomic sections when possible (an atomic section is a set
of consecutive statements that can only be run by one thread at a
time).
6. Place locks only around commonly used fields and not entire
structures if this is possible
7. Compute all possible precalculations and postcalculations outside
the critical section, as this will minimize the time spent in a critical
section
8. Make sure that locks are taken in the same order to prevent dead-lock situations

8. $\color{red}{Synchronization Barrier (同步屏障)}$

任何執行緒在遇到同步屏障時都必須停下來等待其他執行緒到達同步屏障，用來確認屏障後要用到的變數一定在準備好的狀態

9. 最小化溝通所耗的時間 $\color{red}{延遲怎麼測量、延遲大於計算的例子、asynchronous communication、protocol}$
溝通所耗的時間可以如下計算$$ T_{com}(n)=\alpha + \beta*n $$ $\alpha$ 為啟用溝通服務所需時間，$\beta$ 為傳送1單元訊息所需時間，n 為訊息大小
如果要降低溝通所耗的時間你可以：
1. Gather small messages into larger ones when possible to increase the effective communications bandwidth (reduce β, reduce α, increase n).
2. Sending noncontiguous data is usually less efficient than sending contiguous data (increases α, decreases n).
3. Do not use messages that are too large. Some communication protocols change when messages get too large (increases α, increases
n, increases β).
4. The layout of processes/threads on cores may affect performance due to communication network latency and the routing strategy (increases α).
5. Use asynchronous communication techniques to overlap communication and computation. Asynchronous communication (nonblocking) primitives do not require the sender and receiver to “rendezvous” (decrease α).
6. Avoid memory copies for large messages by using zero-copy protocols (decrease β).

10. 使用 Thread Pools
一味的增加 thread 數量不會增加效能，因為要"養"每個 thread 都需要資源，所以為每個 task 都新增 thread 是不好的
所以可以使用 thread pools 來解決：
建立一特定數量 thread 來消化 封裝在 qenue 中的 task，當 thread 執行完一個 task 再從 qenue 中拿一個出來做，需要的 thread 數量可以如下計算：$$ Thread\,count=number\,of\,cores/(1-perentage\,average\,blocking\,time\,of\,threads) $$

11. 管理 Thread 數量
見第10.點

12. 避開使用 kernel (避開使用 $\color{red}{System call}$)
* 例如：Linux 支援 SMP 多核心系統 使用" futex (fast user space mutex) "
Thread 可以在 user space 做 lock 的動作，只要沒有其他 Thread 跟他搶 lock 就不會觸發 System call

13. 使用函式庫實作多執行緒程式
* 省去不必要的麻煩，自行開發卻沒有管理好程式
* 開發快速

## 7 OpenMP 函式庫
* 可以分離出執行緒執行平行運算
* 特性：
1. Support of parallel regions
2. Worksharing across processing elements
3. Support of different data environments (shared, private, …)
4. Support of synchronization concepts (barrier, flush, …)
5. Runtime functions/environment variables
* $\color{red}{有在 VSCode 使用 openMP 實作一個例子}$

8. 總結
展示如何將 sequential 的 app 轉換成平行運算，步驟為

1. Understand requirements: 了解程式輸入什麼輸出什麼，先不管效能及耗能，有功能就好
2. Sequential analysis: 檢查原始 Sequential Code，看看有沒有可以優化的地方，確定 libraries 可以支援平行運算
3. Exploration: 初步探索平行運算可能性，目標是簡單達成而非效能至上，要有檢查平行運算對不對的方法
4. Code optimization and tuning: 效能優化
注意以下幾點：
* Thread stalls
* Excessive synchronization
* Cache thrashing
通常需要許多實驗及驗證，你可以試試：
* Vary threads and the number of cores
* Minimize locking
* Separate threads from tasks