[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可以有較高的效率。
發佈留言
很抱歉,必須登入網站才能發佈留言。