[發明專利]一種自適應的動態流水線并行方法

在審

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

本發明屬于計算機技術領域，具體涉及一種自適應的動態流水線并行方法。將一個應用劃分為多個功能階段，各個階段以相互銜接的并行方式工作，并通過各個階段間的共享緩沖區交互中間結果；其中，各流水線階段的線程數根據各個階段現有的工作負載情況進行動態地調整：如果某一個流水線階段的工作負載比較重，此階段的線程分配數量上升，保證處于該階段的負載能被及時處理；反之，如果某一階段的工作負載較低，此階段分配的線程數就下調，避免負載不足導致的線程空閑；為適應不同類型輸入，對流水線進行劃分：根據負載任務分為細粒度和粗粒度。本發明方法能克服算法在并行化過程中存在的各種固有限制，并利用底層多核硬件的計算資源，提高計算效率。

技術領域

本發明屬于計算機技術領域，具體涉及一種自適應的動態流水線并行方法。

背景技術

在大數據時代，計算機系統處理的數據量越來越大，實時性要求也越來越高。隨著多核乃至眾核的普及，多核處理器已經成為各種云平臺或數據中心的主流硬件。因此，越來越多的研究者試圖通過并行化算法，利用多核平臺提供的計算資源加速算法的處理速度，實現對數據的實時處理。這些不同的算法，處理的對象和計算的過程雖然有很多不同，但并行化的過程中存在一些相似的模式。多媒體服務是大數據時代的典型應用，而多媒體檢索應用算法是多媒體相關數據服務的基礎，有著廣泛的應用前景。我們以多媒體檢索應用算法的并行化為例，闡述算法并行化過程中的典型問題。

多媒體檢索應用需要對大量圖片進行分析和處理，因此已有多媒體算法都面臨十分嚴重的實時處理的性能挑戰。盡管多媒體檢索算法已有很多并行加速方面的研究，但這些設計并沒有考慮多媒體檢索算法在并行設計時存在的不確定的時間分配問題以及各個方面負載不均衡等問題，并行設計并沒有充分利用多核計算資源，也沒能取得較好的可擴展并行加速效果。

負載均衡對并行設計的加速效果和可擴展性有至關重要的影響，是設計并行程序需要解決的最重要的問題之一。多媒體檢索應用面臨的主要問題包括：

負載不均衡挑戰：圖像級別不均衡是負載不均衡的主要原因之一。導致這種不均衡的主要原因是因為圖像的內在特性千差萬別，導致不同圖像中存在的特征點數目存在較大的差異。一些復雜圖像可能擁有上千的特征點，而另一些相對簡單的圖像可能只包含幾十個特征點。同時，即使圖像中包含有相同數目的特征點，因為不同特征點所處的層級不同，不同特征點處理過程中所需的時間也存在差異，這種不均衡依然存在。因此，不論采用圖像級別并行還是特征點級別并行來加速多媒體檢索算法，都存在負載不均衡的問題，從而很難獲得理想的加速效果和可擴展性。

規模級別和塊級別并行的負載不均衡：規模級別的并行限制同樣是由各自層面的負載不均衡導致的。此外，為利用規模層級的并行性或塊級別的并行性，在并行設計的過程中不得不引入額外的同步，以保證結果的正確性。以SIFT算法的塊級別并行為例，高斯金字塔（GaussianPyramid）的每一層級建立后，就需要一次同步，這是因為每一個高斯層級的計算結果都會用到其他塊的計算結果。因此，頻繁的同步是影響性能的另一個重要原因。

流水線并行的限制：由于多媒體檢索算法的基本流程是將特征點均等地向下傳遞，因此流水線并行在針對多媒體檢索算法并行的過程中是一種可行的考慮。但是，不同階段間不確定的運行時間分布導致流水線并行設計過程中計算資源分配十分困難。此外，在把應用劃分成不同的功能單元時，由于涉及應用的邏輯和不同功能單元間的數據交互，很難將流水線劃分為太多階段。當物理硬件節點可用的硬件核心數上升時，流水線并行設計也很難取得可擴展的性能。

根據多媒體檢索算法的并行化過程，本發明提出了一種自適應的動態流水線并行方法。

發明內容

本發明的目的在于克服一類算法在并行化過程中存在的各種固有限制，提供一種能夠充分利用底層多核硬件計算資源的自適應的動態流水線并行方法。