[發(fā)明專利]有向無環(huán)圖的可重構(gòu)系統(tǒng)的混合任務(wù)調(diào)度方法

在審

• 申請?zhí)枺?/td>: 201410211523.0
• 申請日: 2014-05-19
• 公開（公告）號: CN104239135A
• 公開（公告）日: 2014-12-24
• 發(fā)明（設(shè)計）人: 朱志宇;沈舒;吳將;王彪;王遜;陳迅;李陽;薛文濤;黃巧亮
• 申請（專利權(quán)）人: 江蘇科技大學(xué)
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 南京經(jīng)緯專利商標(biāo)代理有限公司 32200
• 代理人: 樓高潮

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

本發(fā)明涉及可重構(gòu)計算領(lǐng)域，具體是一種動態(tài)可重構(gòu)任務(wù)調(diào)度方法。

背景技術(shù)

可重構(gòu)計算既保持了傳統(tǒng)的基于硬件的執(zhí)行效率，又保持了可變的體系結(jié)構(gòu)，可以適應(yīng)實際應(yīng)用中的多元需求，是當(dāng)今一種前沿技術(shù)。它打破了軟硬件之間的界線，其性能介于微處理器和專用集成電路之間，在高性能計算領(lǐng)域應(yīng)用廣泛。

可重構(gòu)計算技術(shù)的研究對可重構(gòu)邏輯器件的開發(fā)有著極強的依賴性，以FPGA為代表的動態(tài)可重構(gòu)器件內(nèi)部由一系列可配置邏輯塊CLBs(Configurable?Logic?Blocks)組成，這使其具備了部分可重構(gòu)的能力。它可以根據(jù)應(yīng)用對可重構(gòu)邏輯器件上的資源做相應(yīng)的調(diào)配，特別是對已有任務(wù)正常執(zhí)行的器件的空閑資源進行新的配置。為了充分利用可重構(gòu)資源，提高系統(tǒng)的并行執(zhí)行能力，需要對硬件任務(wù)和可重構(gòu)資源進行有效管理。

現(xiàn)有的可重構(gòu)系統(tǒng)可以簡化為由主CPU和可重構(gòu)器件(FPGA)組成，如圖1，CPU主要由調(diào)度器、放置器和加載器構(gòu)成，分別負(fù)責(zé)可重構(gòu)任務(wù)的調(diào)度、放置和配置加載。以FPGA為代表的可重構(gòu)系統(tǒng)在實際運行時存在重構(gòu)過程即配置過程的延遲，以及多次配置過程大量的數(shù)據(jù)訪問，導(dǎo)致FPGA的能耗很大。

一個實際應(yīng)用可以依據(jù)一定的算法將其劃分為軟件任務(wù)和硬件任務(wù)。一般地，軟件任務(wù)被分配在處理器上執(zhí)行，而硬件任務(wù)是指內(nèi)部綜合，寬度、高度固定，具備特定的功能且不可旋轉(zhuǎn)的邏輯模塊，需要配置后才能在硬件資源上執(zhí)行，因此配置時間不可缺少。將可重構(gòu)硬件任務(wù)的配置時間隱藏在前一個任務(wù)的執(zhí)行時間里，對其進行調(diào)度。在許多計算密集型的應(yīng)用中可能會使用相同的邏輯單元處理不同的數(shù)據(jù)。因此，對于相同類型的任務(wù)，可以通過重復(fù)使用之前配置好的邏輯單元，這樣可以減少配置次數(shù)，降低配置開銷，極大地提高可重構(gòu)任務(wù)的調(diào)度效率。

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

本發(fā)明針對現(xiàn)有技術(shù)的問題提出了一種基于有向無環(huán)圖(Directed?Acyclic?Graph，DAG)以及預(yù)配置優(yōu)先級的可重構(gòu)任務(wù)調(diào)度方法，應(yīng)用DAG改進預(yù)配置優(yōu)先級，具體為一種有向無環(huán)圖的可重構(gòu)系統(tǒng)的混合任務(wù)調(diào)度方法。

一種有向無環(huán)圖的可重構(gòu)系統(tǒng)的混合任務(wù)調(diào)度方法，所述方法如下：將應(yīng)用分解為DAG描述的多個小任務(wù)經(jīng)過調(diào)度器調(diào)度，軟件任務(wù)進入Q₁，Q₁中的軟件任務(wù)經(jīng)過任務(wù)管理器后按照CPU是否空閑以及調(diào)度優(yōu)先級進行計算；而硬件任務(wù)進入Q₂，當(dāng)Q₂中的硬件任務(wù)能重復(fù)利用可重構(gòu)資源，則進入Q₃，否則繼續(xù)保持在Q₂中按優(yōu)先級排隊，并通過加載器配置加載；完成配置加載或者Q₃中的任務(wù)進入Q₄，Q₄中的任務(wù)經(jīng)過任務(wù)管理器進入Q₅按照優(yōu)先級運行，依次循環(huán)，直到任務(wù)全部運行結(jié)束，返回總的運行時間；其中Q₁：軟件任務(wù)隊列、Q₂：預(yù)配置硬件任務(wù)隊列、Q₃：配置重用隊列、Q₄：配置完成隊列、Q₅：運行任務(wù)隊列。

所述任務(wù)采用五元組{w_i,h_i,c_i,e_i,s_i}進行描述，w_i,h_i表示任務(wù)占用可重構(gòu)資源的寬和高，c_i表示任務(wù)的配置時間，e_i表示任務(wù)的運行時間，s_i表示任務(wù)類型，如果是軟件任務(wù)，則令w_i,h_i,c_i為零。

所述調(diào)度優(yōu)先級如下：