[Paper Reading] Parallelization of AdaBoost algorithm on multi-coreprocessors

出處：SiPS 2008. IEEE Workshop on Signal Processing Systems, 2008.

論文名稱：Parallelization of AdaBoost algorithm on multi-core processors

作者：Yen-Kuang Chen   Wenlong Li   Xiaofeng Tong
單位：Corporate Technology Group, Intel Corporation

發表時間：2008年

這篇paper討論使用OpenCV及OpenMP來做到adaboost algorithm的平行化。這裡有提到幾個平行化的基本觀念：一般來說，要最大化load balance的方式，讓task盡可能變小，並且每個task的size差不多，然後動態地分散tasks。另外一點是必須降低overhead，這部份包含最小化communication、重複的computation、locks、barriers或synchronization。

本篇作者使用了有別於其他論文的技術，一般來說，為了顧及到運作效率，我們會使用haar-like feature來當作adaboost algorithm的操作feature。但本篇作者採用了在一般物件偵測的部份有較好效果的Histogram Oriented Gradients（HOG）當作我們要輸入adaboost algorithm的feature。關於HOG的使用可以參考下列兩份資料：

http://lear.inrialpes.fr/people/triggs/pubs/Dalal-cvpr05.pdf

http://en.wikipedia.org/wiki/Histogram_of_oriented_gradients

 

針對adaboost algorithm可以平行化的部份，作者整理出以下幾個項目，

1.      image flips

2.      scale factors of an image

3.      image ratios（不同的影像寬度及長度）

4.      image partition

 

而平行的策略，可粗分成coarse-grained thread-level parallelism及fine-grained data-level parallelism兩種：

1.      coarse-grained thread-level parallelism(coarse-grained TLP): 儘可能將多個小步驟整合，使得每個task較大。其實作上通常較簡單，且通常所有的code都可以被平行化，但是較沒有load balance。

2.      fine-grained thread-level parallelism(fine-grained TLP): 多個小tasks，可以盡可能有效率地分配tasks，但是卻可能造成overhead變大

3.      fine-grained data-level parallelism(fine-grained DLP): 對frame partition及HOG做平行化

作者在這裡不使用第二種策略，因為

(1). fine-grained TLP在image partition的步驟無法有好的效果，因為：

a. 多核的系統無法對較大的scale factor做適當的負載平衡，無法盡可能讓所有processor忙碌

b. 資料在image boundaries上的重複性，導致較高的平行化負擔

c. 當目標物件介於兩個partition界限上時，影響偵測準確度

(2). 後面的stages較不會被執行，會浪費掉某些core的使用率

(3). Fine-grained比較無法用在multi-core上，因為parallel overhead較高

基於上述理由，作者使用coarse-grained TLP及fine-grained TLP互相比較效果。以驗證以上的說法，並對讀者提出建議。由實驗結果得知，在multi-core平台上進行平行化，要考量task的大小及workloads。並且得知，藉由重新架構程式碼且合併一些迴圈來提供較多的tasks，coarse-grained平行化相較於fine-grained可以有較高的效率。