[發(fā)明專利]一種低功耗的自適應(yīng)流水線并行方法

在審

• 申請?zhí)枺?/td>: 201810647533.7
• 申請日: 2018-06-22
• 公開（公告）號: CN108845873A
• 公開（公告）日: 2018-11-20
• 發(fā)明（設(shè)計(jì)）人: 張為華;李弋;魯云萍
• 申請（專利權(quán)）人: 復(fù)旦大學(xué)
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 陸飛;陸尤

本發(fā)明屬于計(jì)算機(jī)技術(shù)領(lǐng)域，具體為一種低功耗的自適應(yīng)流水線并行方法。本發(fā)明方法包括：確定優(yōu)化目標(biāo)，建立優(yōu)化方程；進(jìn)行狀態(tài)管理；設(shè)計(jì)流水線；以及確定線程調(diào)度策略。本發(fā)明能自動適應(yīng)工作負(fù)載的變化，在保證性能的前提下可以實(shí)現(xiàn)更好的計(jì)算功耗比。

技術(shù)領(lǐng)域

本發(fā)明屬于計(jì)算機(jī)技術(shù)領(lǐng)域，具體涉及一種低功耗的自適應(yīng)流水并行方法。

背景技術(shù)

在大數(shù)據(jù)時代，計(jì)算機(jī)系統(tǒng)處理的數(shù)據(jù)量越來越大，實(shí)時性要求也越來越高。隨著多核乃至眾核的普及，多核處理器已經(jīng)成為各種云平臺或數(shù)據(jù)中心的主流硬件。因此，越來越多的研究者試圖通過并行化算法，利用多核平臺提供的計(jì)算資源加速算法的處理速度，實(shí)現(xiàn)對數(shù)據(jù)的實(shí)時處理。然而，已有的并行方法對于多核平臺的并行計(jì)算資源的利用效率較低，并行加速效果并不理想，其性能結(jié)果與理想加速效果存在較大差距。這些不同的算法，處理的對象和計(jì)算的過程雖然有很多不同，但并行化的過程中存在一些相似的模式。多媒體服務(wù)是大數(shù)據(jù)時代的典型應(yīng)用，而多媒體檢索應(yīng)用算法是多媒體相關(guān)數(shù)據(jù)服務(wù)的基礎(chǔ)，有著廣泛的應(yīng)用前景。我們以多媒體檢索應(yīng)用算法的并行化為例，闡述算法并行化過程中的典型問題。

大規(guī)模的數(shù)據(jù)中心和集群服務(wù)器中，由于功耗墻的問題，除了傳統(tǒng)的處理速度相關(guān)的性能指標(biāo)外，能耗已成為最重要的評測指標(biāo)之一。即在這些環(huán)境中，經(jīng)常使用計(jì)算功耗比代替單一的性能做為整個系統(tǒng)優(yōu)化的目標(biāo)。考慮到多媒體檢索算法常常被部署在大規(guī)模的云環(huán)境或者數(shù)據(jù)中心的集群上，并全天候地為用戶提供實(shí)時處理服務(wù)，其負(fù)載壓力在不同的時間段區(qū)別非常大。簡單地提升程序的運(yùn)行性能實(shí)際上不能滿足數(shù)據(jù)中心對于功耗的優(yōu)化目標(biāo)。因此，在性能損失很小的前提下，設(shè)計(jì)和實(shí)現(xiàn)適應(yīng)云計(jì)算環(huán)境功耗需求目標(biāo)的，具有更高計(jì)算功耗比的功耗優(yōu)先的多媒體檢索并行算法更為重要。

在自適應(yīng)的流水并行設(shè)計(jì)中，算法通過檢測不同階段間緩沖區(qū)的大小來動態(tài)地調(diào)整不同階段的線程分配，達(dá)到負(fù)載均衡的目標(biāo)。在這種設(shè)計(jì)中，在工作負(fù)載滿的時候可以很好的工作。然而當(dāng)負(fù)載動態(tài)變化時，很多線程將頻繁的在不同階段間切換，造成資源的浪費(fèi)。比如工作負(fù)載很輕時，不同階段的緩沖區(qū)會處于空的狀態(tài)，算法檢測緩沖區(qū)認(rèn)為第二階段的線程過多，逐步調(diào)度線程到第一階段。而隨著調(diào)度到第一個階段線程的增多，第二階段的線程數(shù)逐漸減少，共享緩沖區(qū)逐漸處于滿狀態(tài)，線程再反向遷移。從而導(dǎo)致顛簸狀態(tài)。因此，動態(tài)流水線并行算法在輸入工作集變化的時候不能取得較好的計(jì)算功耗比。

對于大型數(shù)據(jù)中心或云平臺的硬件配置一般是為了應(yīng)對最差的工作負(fù)載而設(shè)計(jì)的。然而這種情況出現(xiàn)的幾率并不是很高，或者絕大部分情況并不會出現(xiàn)。以商業(yè)購物網(wǎng)站的負(fù)載為例，一般在白天時負(fù)載相對較高，而進(jìn)入夜晚則負(fù)載會逐漸降低。同樣在白天，工作日的負(fù)載會小于雙休日的負(fù)載。由于較小的工作負(fù)載僅需要較少的計(jì)算資源，冗余的計(jì)算資源如果被設(shè)置為待機(jī)狀態(tài)或低功耗狀態(tài)，在負(fù)載增加時再喚醒，則可以有效降低能量消耗。為了實(shí)現(xiàn)更好的計(jì)算功耗比，我們在進(jìn)行動態(tài)流水線并行設(shè)計(jì)時，需要同時考慮輸入的工作負(fù)載情況和流水線內(nèi)部的工作負(fù)載情況來統(tǒng)一調(diào)度，從而達(dá)到節(jié)省能源實(shí)現(xiàn)更好的計(jì)算功耗比的目的。

發(fā)明內(nèi)容

本發(fā)明的目的在于克服算法在流水線并行化過程中存在的各種固有限制，提供一種功耗低的自適應(yīng)流水并行方法。

(一)確定優(yōu)化目標(biāo)，建立優(yōu)化方程

在流水線并行機(jī)制中，一個完整的應(yīng)用被劃分為多個功能階段，各個階段以相互銜接的并行方式工作，并通過各個階段間的共享緩沖區(qū)交互中間結(jié)果。輸入數(shù)據(jù)流經(jīng)各個階段并逐個被處理，在這里我們假定所有的階段在同一臺機(jī)器上處理。