[發(fā)明專利]一種自適應的動態(tài)流水線并行方法

在審

• 申請?zhí)枺?/td>: 201810659163.9
• 申請日: 2018-06-25
• 公開（公告）號: CN108984283A
• 公開（公告）日: 2018-12-11
• 發(fā)明（設計）人: 張為華;李弋;魯云萍
• 申請（專利權）人: 復旦大學
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 陸飛;陸尤

1.一種自適應的動態(tài)流水線并行方法，其特征在于，在流水線并行機制中，將一個完整的應用劃分為多個功能階段，各個階段以相互銜接的并行方式工作，并通過各個階段間的共享緩沖區(qū)交互中間結果；輸入數(shù)據(jù)流經過各個階段并逐個被處理；

其中，各流水線階段的線程數(shù)不作靜態(tài)分配，而是根據(jù)各個階段現(xiàn)有的工作負載情況進行動態(tài)地調整：如果某一個流水線階段的工作負載比較重，此階段的線程分配數(shù)量上升，從而保證處于該階段的負載能被及時的處理；反之，如果某一階段的工作負載較低，此階段分配的線程數(shù)就下調，從而避免負載不足導致的線程空閑。

2.根據(jù)權利要求1所述的自適應的動態(tài)流水線并行方法，其特征在于，為了適應不同類型輸入，對流水線進行劃分：根據(jù)負載任務分為細粒度和粗粒度：

（1）細粒度的劃分：把整個算法劃分成多個細粒度的功能單元，并利用這些劃分的細粒度功能單元進行并行處理；

（2）粗粒度的劃分：把整個算法劃分成少數(shù)的粗粒度的功能單元，并利用這些劃分的粗粒度功能單元進行并行處理。

3.根據(jù)權利要求2所述的自適應的流水線并行方法，其特征在于，設置一種全局化的多生產者多消費者的共享緩沖區(qū)，緩沖區(qū)中存儲從流水線并行前一階段產生的中間結果；該緩沖區(qū)是環(huán)形緩沖區(qū)，前一階段新生成的中間結果被存儲在緩沖區(qū)的尾部，后一階段則從當前緩沖區(qū)的頭部讀取傳遞的中間結果；利用信號量來檢測緩沖區(qū)狀態(tài)：是空或者滿，并通過細粒度的鎖機制保證每一個緩沖區(qū)元素存取的原子性。

4.根據(jù)權利要求3所述的自適應的動態(tài)流水線并行方法，其特征在于，進一步使用線程節(jié)流策略，即通過調節(jié)緩沖區(qū)大小和調節(jié)線程間隔時間這兩個參數(shù)，來控制線程調節(jié)頻率；

緩沖區(qū)的大小和線程間隔時間的具體配置由應用和典型的輸入決定，最優(yōu)值通過實驗來確定。

5.根據(jù)權利要求4所述的自適應的動態(tài)流水線并行方法，其特征在于，對于多媒體檢索算法，其包括特征提取算法和特征匹配算法，其并行算法的方式為：

（一）特征提取算法，采用SIFT或SURF，粗粒度劃分為特征檢測階段和特征描述階段兩個階段；

由于粗粒度流水線劃分階段數(shù)較少，存在并行可擴展的限制；為了克服這個限制，在粗粒度流水線的基礎上，結合圖像級別并行，實現(xiàn)更好的并行性；即當?shù)讓佑嬎阗Y源可用時，根據(jù)資源實際情況，配置多個粗粒度流水線，每個粗粒度流水線獨立執(zhí)行多媒體檢索算法，并完成分配給它的輸入圖像的處理；通過動態(tài)調度克服負載不均衡和階段比例不確定的問題；

在SIFT算法中，在流水線設計中，一些線程執(zhí)行特征檢測而另一些線程執(zhí)行特征描述；特征檢測階段，線程構建一個尺寸空間的金字塔，并發(fā)地檢測不同輸入圖像的特征點，并且將它們寫入一個共享的緩沖區(qū)；特征描述階段，線程則從這個緩沖區(qū)中讀取特征點，并且并發(fā)地描述為特征向量；為使得各個階段的負載均衡，周期性地檢查這些緩沖區(qū)，如果兩階段間的緩沖區(qū)在一段時間內處于滿的狀態(tài)，這就意味著前一階段的處理速率大于后一階段的處理速率；這種情況下，減小前一階段的線程數(shù)量，將這些線程調度給后面一個階段，提升后一階段的處理速度，從而平衡前后兩階段的負載均衡度；相應地，如果兩階段間的緩沖區(qū)長期處于空的狀態(tài)，就意味著后一階段的處理速率大于前一階段的處理速率，后一個階段的線程會處于工作負荷不足狀態(tài)，這種情況下，將一些線程從后一階段調度到前一階段，從而平衡兩階段的負載均衡度；

（二）特征匹配

采用VocTree算法，其匹配過程的階段劃分采用粗粒度的劃分標準，即將頂端樹形架構的特征匹配過程劃分為分布階段，下方的樹形結構劃分為另一個查詢階段，最后是匯總搜索結果的階段；

由于分布階段是每個查詢必經的階段，因此調度策略分配多個線程，加快該階段的處理；針對分布階段的輸出結果，根據(jù)結果的分布來確定線程的分布。

6.根據(jù)權利要求5所述的自適應的動態(tài)流水線并行方法，其特征在于，對于特征提取算法中的SIFT或SURF，其中，共享變量detnum用來將線程資源劃分成特征檢測階段和特種鋼描述階段兩部分；thread_id小于detnum的線程為檢測階段線程，大于detnum的為描述階段線程；信號量empty_sem和full_sem用來檢測緩存的狀態(tài)并幫助調節(jié)線程資源的分配；empty_sem和full_sem分別初始化為緩存的大小和0；當檢測階段線程要寫入緩存時，先檢測緩存中是否有空位；當empty_sem不為0時則說明有空位，并執(zhí)行empty_sem--，即P操作；相應地，描述階段線程在取出線程并計算完畢后，釋放緩存資源，執(zhí)行empty_sem++，即V操作；如果檢測階段線程工作量過大，緩存可能會被放滿，此時empty_sem會為零0，它的P操作一直等在那里直到有描述階段線程釋放緩存資源為止；一旦當檢測線階段程獲得資源時，會發(fā)現(xiàn)它曾長時間處于滿置狀態(tài)，于是會調整檢測階段線程的個數(shù)detnum--，來達到平衡線程資源分配的作用；同樣地，full_sem用來檢測緩存中是否有特征點；檢測線程工作完成后會full_sem++（V操作），描述工作前檢測full_sem是否為0，并占用資源（P操作）；當描述線程發(fā)現(xiàn)緩存長時間處于空置狀態(tài)時，線程資源也將重新劃分（detnum++）；為了避免過于頻繁的來回切換，每次調節(jié)detnum粒度為1；

另外，在緩存的讀寫過程中，用互斥量buffer_mutex來保證操作的原子性；由于特征檢測和特征描述兩個階段都是從緩存的頭部開始循環(huán)，且信號量控制著讀取線程訪問的緩存編號不會超過寫入線程，因此維護兩個整數(shù)in和out，就可獲取需要寫入/讀出的緩存位置。