本文續篇在這裡。
以往只需等待廠商出更高頻率的CPU，程式效能就能獲得免費提升。現在必須靠善用多核心，才能在核心數增加時獲得好處。但程式要怎麼寫才能善用多核架構呢，最基本也最容易想到的方法是依照任務種類來切割，例如把程式分成以下數個thread：
Doom3 BFG的作法
由於Vulkan即將推出，它的設計非常適合Job架構。為了因應即將到來的變化，我打算重新設計一個Job系統。理想目標是：
初步將架構設計成有一個manager thread專門負責處理dependency、FIFO與LIFO控制、Job的收集與分配。將所有Job狀態的改變動作都放在同一個thread裡面，可以減少不少麻煩。Manager與main thread若是沒事做會進入睡眠狀態，將CPU釋放出來給worker使用。為了避免worker間偷工作造成的設計複雜度，不採用預先平均分配job給所有worker的做法，而是讓manager來負責管理。每個Worker右手實際做事，manager看到左手空著就把下一件工作放上去。用意是減少worker的閒置時間，worker兩手空空時也會睡下去。
效能測試
可以看出Job計算量越高，越能隱藏worker切換Job的overhead。推測新架構比較慢的原因是以job為最小單位，沒辦法像Doom3 BFG那樣將所有job打包後一口氣送出，而且檢查每個job的dependency也需要一點時間。效能問題就等以後靈感來了再解決，接下來的課題是把我的繪圖程式碼都切碎變成Job。
追加以實際運用時可能出現的job數量的測試，設定Job數量為2000個。
新架構增加切換手動或自動釋放job記憶體功能。
對照組，完全不使用平行處理，測試1000次得到的平均時間
追加可以一次送一組Job給Manager的機制，Manager內處理整組Job時也盡量整批一起處理。設定Job數量為2000個。
參考資料
以往只需等待廠商出更高頻率的CPU，程式效能就能獲得免費提升。現在必須靠善用多核心，才能在核心數增加時獲得好處。但程式要怎麼寫才能善用多核架構呢，最基本也最容易想到的方法是依照任務種類來切割，例如把程式分成以下數個thread：
- Main thread
- Render thread
- Physic thread
- Resource thread
某些thread只會忙碌一陣子就進入睡眠狀態，例如Resource thread可能不會時常接到讀取新資源的要求，大部分時間只有main、render、physic thread會很忙碌。若CPU是8核心，就會有5核心處於閒置狀態。想要讓程式效能能夠隨著核心數增加而提升，上面的設計顯然無法達到要求。
近年的遊戲有個作法是把各種運算拆成小塊，稱作Task或Job。再搭配類似Thread Pool的概念，有數個worker thread等著執行送來的job，但worker數量不會超過核心數。例如場景中有十個人物的影子，就拆成十個job來處理。只要每個job彼此獨立(不需同步動作)，就能以最高速度進行平行處理。如此作法理論上核心數越多，處理速度越快，而且即使是異質核心架構如PS3，也能因此受惠。
Doom3 BFG的作法
由於Doom3 BFG有開放原始碼，所以以此處為研究起點。在Doom3 BFG中是以Job List為操作單位，將數個Job打包以後再送給worker。為了減低切換工作的負擔，每個job至少得超過1000 clock cycles，但需低於100,000 clock cycles以保持負載平衡。id sofeware沒有採用將job平均分給所有worker，先把事做完的worker去偷別人工作的作法。而是將所有job公開，讓所有worker去搶，簡化了實作的複雜度。
另外Doom3 BFG又有sync和dependency機制，sync用於job list內，dependency用於job list之間的相依關係。這裡舉個例子來說明sync，假設將洗餐盤叫做Job A，把餐盤疊好叫Job B。洗完所有餐盤後，所有人才能開始疊餐盤，且一種工作只能讓一個人做。Job list會長這樣：
A Signal Sync B
其中Signal和Sync也是一種job，但實際不做任何事情。worker遇到Sync的時候會去檢查Signal之前的工作完成了沒，完成的話才去做Sync之後的工作。假如有兩個worker來處理這個job list，一定有一個worker會沒事情做。
我們可以利用ｓｙｎｃ做出pipeline效果。如果把餐盤分成兩份，即洗餐盤的工作拆成A1 A2，疊餐盤也分成兩個工作B1 B2。洗好第一份餐盤之後就允許worker去把第一份餐盤疊起來，現在Job list長這樣：
A1 Signal A2 Sync Signal B1 Sync B2
現在餐盤可以有兩個worker一起洗，而且不需要等餐盤全洗完就能開始疊餐盤。
其他遊戲的作法
至於Frostbite engine會依照dependency將所有job串成一個graph，每個job平均有25k行程式碼，比起Doom3 BFG多出許多，但有偷工作的機制。Killzone Shadow Fall的文件對架構更是輕描淡寫，不過似乎有一個thread專門處理job的分派，在demo中每個frame會執行1000個job。
我的實作經驗
我照著Doom3 BFG的Job架構實作了一個簡化版本，沒有實作dependency機制。雖然有實作sync，但找不到地方用。在我的4核心機器上，我的繪圖程式有套用此架構的地方，速度最多變成兩倍。度過一陣蜜月期之後開始發現對方的缺點：
- Nvidia的PhysX要求job內可以生出新job，且建議採LIFO方式會比較快，即最後生出的Job最先執行。
- Doom3 BFG的架構只能靠priority來控制job list被處理的先後順序。
- 沒辦法在job內部生出新的job，因為架構先天上會使此行為可能造成deadlock。
- 最小操作單位是job list，即使我只想送一個job，還是得生一個job list才能送給worker。
- 每個wokrer沒事幹的時候都呼叫yield()，即使沒做事CPU使用率還是會飆高。
- 我資質駑鈍，不曉得怎麼大規模應用Sync機制．．．
由於Vulkan即將推出，它的設計非常適合Job架構。為了因應即將到來的變化，我打算重新設計一個Job系統。理想目標是：
- 最小操作單位是Job
- 切換Job的overhead減至最低，不必撐大Job以避免切換負荷過於明顯
- 支援FIFO與LIFO
- 可設定Job之間的dependency
- 任何thread都能送出job，包括worker thread
- 一部分worker優先處理FIFO，一部分優先處理LIFO，沒事做時會去偷別人工作
- 可限制特定類型Job同時執行的數量，例如不可以同時執行太多IO相關的job
- 避免先搶先贏的做法，因為可能會造成cache ping-pong
- 避免沒事做的thread還會飆高CPU使用率
初步將架構設計成有一個manager thread專門負責處理dependency、FIFO與LIFO控制、Job的收集與分配。將所有Job狀態的改變動作都放在同一個thread裡面，可以減少不少麻煩。Manager與main thread若是沒事做會進入睡眠狀態，將CPU釋放出來給worker使用。為了避免worker間偷工作造成的設計複雜度，不採用預先平均分配job給所有worker的做法，而是讓manager來負責管理。每個Worker右手實際做事，manager看到左手空著就把下一件工作放上去。用意是減少worker的閒置時間，worker兩手空空時也會睡下去。
實作完成測試速度時，發現使用condition variable來叫醒manager的設計會造成反應速度不夠快，當job很短能很快做完時，worker時常會兩手空空。manager來不及送job給worker，worker醒來的速度也很不理想，於是乾脆回頭繼續用yield()來讓出CPU。
worker的左右手設計也被改掉，變成manager事先平均分配job給每個worker，worker把工作做完就去偷別人的工作。但想不到這方法也不夠快，目前想到的可能性是worker之間的local queue距離太遠，導致偷工作的時候時常造成cache miss。最後還是回歸讓worker搶工作的做法，一部分worker優先搶FIFO的工作，一部分優先搶LIFO。最後兩個理想目標沒有達成，不過反正只要速度夠快就OK。
效能測試
在測試中，所有job都互相獨立，沒有設定dependency關係。整個程式只包含測試用程式碼，沒有和我的繪圖程式搭在一起。測試用的job設計得有點隨便，用改變迴圈次數來模擬不同長短的job：
void jobFunc( Data* data )
{
vec3 vector( data->input, data->input + 1, data->input + 2 );
for ( int i = 0; i < 1000; ++i )
vector += (data->input * data->input * i);
data->result = dot( vector, vector );
}
{
vec3 vector( data->input, data->input + 1, data->input + 2 );
for ( int i = 0; i < 1000; ++i )
vector += (data->input * data->input * i);
data->result = dot( vector, vector );
}
job數量固定為10000個，也就是此函式必須執行10000次才算完成，每個job會拿到不同的data。在我的i5-3470 3.2GHz CPU上的執行結果如下：
對照組，完全不使用平行處理，執行此函式10000次
迴圈1000，需時12.07ms
迴圈5000，需時59.52ms
迴圈10000，需時119.07ms
使用我的簡化版Doom3 BFG Job架構，測試1000次得到的平均時間
迴圈1000，需時3.503ms，效能提升3.44倍
迴圈5000，需時15.667ms，效能提升3.8倍
迴圈10000，需時30.862ms，效能提升3.86倍
使用新架構測試1000次得到的平均時間
迴圈1000，需時4.082ms，效能提升2.96倍
迴圈5000，需時17.059ms，效能提升3.49倍
迴圈10000，需時32.991ms，效能提升3.61倍
可以看出Job計算量越高，越能隱藏worker切換Job的overhead。推測新架構比較慢的原因是以job為最小單位，沒辦法像Doom3 BFG那樣將所有job打包後一口氣送出，而且檢查每個job的dependency也需要一點時間。效能問題就等以後靈感來了再解決，接下來的課題是把我的繪圖程式碼都切碎變成Job。
追加以實際運用時可能出現的job數量的測試，設定Job數量為2000個。
新架構增加切換手動或自動釋放job記憶體功能。
對照組，完全不使用平行處理，測試1000次得到的平均時間
迴圈1000，需時2.359ms
迴圈5000，需時11.705ms
迴圈10000，需時23.343ms
使用我的簡化版Doom3 BFG Job架構，測試1000次得到的平均時間
迴圈1000，需時0.704ms，效能提升3.35倍
迴圈5000，需時3.127ms，效能提升3.74倍
迴圈10000，需時6.200ms，效能提升3.77倍
使用新架構測試1000次得到的平均時間
迴圈1000，需時0.798ms，效能提升2.96倍
迴圈5000，需時3.243ms，效能提升3.61倍
迴圈10000，需時6.246ms，效能提升3.74倍
舊架構的優勢被減弱，新架構的弱點也變得稍不明顯，但可以確定每個job最好包含多一點指令。追加可以一次送一組Job給Manager的機制，Manager內處理整組Job時也盡量整批一起處理。設定Job數量為2000個。
使用新架構測試1000次得到的平均時間
迴圈1000，需時0.782ms，效能提升3.02倍
迴圈5000，需時3.181ms，效能提升3.68倍
迴圈10000，需時6.194ms，效能提升3.78倍
和修改前相比，效能只有些微進步而已。
達人
