[發(fā)明專利]一種混合處理器架構(gòu)及其任務(wù)調(diào)度方法

在審

• 申請?zhí)枺?/td>: 201611150886.3
• 申請日: 2016-12-14
• 公開（公告）號: CN106815069A
• 公開（公告）日: 2017-06-09
• 發(fā)明（設(shè)計）人: 王普章;胡威;郭宏;蔣旻;劉靜;戴文麗;唐玉馨;劉丹;沈歡;張瑜
• 申請（專利權(quán)）人: 武漢科技大學(xué)
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50
• 代理公司: 杭州宇信知識產(chǎn)權(quán)代理事務(wù)所(普通合伙)33231
• 代理人: 張宇娟

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

本發(fā)明涉及處理器架構(gòu)技術(shù)領(lǐng)域，特別是涉及一種混合處理器架構(gòu)及其任務(wù)調(diào)度方法。

背景技術(shù)

可重構(gòu)計算被視為能夠?qū)鹘y(tǒng)處理器的高度靈活性與ASIC（Application Specific Integrated Circuit）所具有的高處理效率進行結(jié)合的有效解決方案。由于可重構(gòu)體系結(jié)構(gòu)具有較好的適應(yīng)性，針對不同應(yīng)用能夠通過不同粒度的并行來加快處理速度。在可重構(gòu)設(shè)備中，F(xiàn)PGA（Field－Programmable Gate Array）是最廣泛使用的可重構(gòu)器件。動態(tài)可充配置的FPGA是實現(xiàn)硬件級別多任務(wù)的重要基礎(chǔ)。此類FPGA的處理區(qū)域通常劃分成不同的子塊。這些子塊分屬于不同的硬件任務(wù)。當(dāng)新的硬件任務(wù)達到時，需要為該硬件任務(wù)分配一個空閑的子塊，同時其他的既存硬件任務(wù)不能受到影響。如果一個硬件任務(wù)執(zhí)行完成，那么該任務(wù)所占據(jù)的子塊應(yīng)當(dāng)被釋放，并作為候選子塊以備其他硬件任務(wù)的使用。在重分配期間，沒有任何的其他硬件任務(wù)會受到影響，多個硬件任務(wù)可以共享整個處理區(qū)域?？梢?，通過對子塊的重新利用，動態(tài)重配置能夠提高FPGA的利用率。并行任務(wù)的數(shù)據(jù)僅僅受到FPGA容量的限制。然而子塊的動態(tài)分配和替換操作會帶來額外時間損耗。硬件任務(wù)的復(fù)雜化和重定位的頻繁發(fā)生，導(dǎo)致了重配置代價的增加。因此，通過對重配置的資源映射進行高效管理以改善重構(gòu)的性能就變得非常重要。

在線的FPGA分配是減少重配置代價的重要方向。FPGA的高度碎片化會導(dǎo)致相當(dāng)差的配置結(jié)果：在有足夠空閑面積的情況下，卻由于碎片化問題造成硬件任務(wù)不能在片上進行配置。在線的FPGA分配用于確定怎樣將硬件任務(wù)分配到可重構(gòu)平臺的恰當(dāng)區(qū)域，從而能夠更好的利用可重構(gòu)FPGA。Bazargan等人提出了針對2D PRTR FPGA的bin-packing在線分配方法。該方法以可重配置計算系統(tǒng)的模型建立為基礎(chǔ)，通過對經(jīng)典算法的擴展來進行在線的實際分配；其中最大空閑方塊(Maximum Empty Rectangles, MER)的大小是Ω(n2)。Walder等人提出了使用哈希-矩陣數(shù)據(jù)結(jié)構(gòu)來對空閑區(qū)域進行管理，并設(shè)計了在線分配算法。該方法是既有方法的一種改進，其改進之處在于可用處理區(qū)域的實際分裂時間被推遲，從而能夠提高分配的質(zhì)量。Ahmadinia等人所提出的方法與Bazargan等人提出的方法相似。這兩種方法的主要差別在于所管理的處理區(qū)域(processing-area)：Ahmadinia方法用于管理已占用的區(qū)域，而Bazargan方法則用于管理空閑區(qū)域。這兩種方法具有相同的復(fù)雜度，在進行數(shù)據(jù)結(jié)構(gòu)管理時也非常耗時，所需要的時間復(fù)雜度函數(shù)是非線性的。

Cui等人提出了用來尋找和構(gòu)建完成MER集合的算法，能夠較為高效的進行處理區(qū)域的管理。Lu等人提出了運行時MER的管理算法。Lu等人的算法對MER完整集合的構(gòu)建基于已配置任務(wù)邊的動態(tài)信息。新的優(yōu)化方法提出了三種用于改善在線分配算法的技術(shù)，分別是僅在合需要時合并(Merging Only if Needed, MON)，部分合并(Partial Merging, PM)和直接合并(Direct Combination, DC)。這三種技術(shù)分別應(yīng)用于不同的具體操作環(huán)境當(dāng)中。Handa等人提出了在PRTR FPGA上快速找到空閑空間的方法。該算法的基礎(chǔ)是使用階梯型數(shù)據(jù)結(jié)構(gòu)以反映基于MER的空閑區(qū)域狀態(tài)。Tabero等人提出了硬件多任務(wù)的新方法，使用基于頂點列表集合的空間管理器來實現(xiàn)處理區(qū)域管理。頂點列表用來描述PRTR（Partial Run-Time Reconfigurable）平臺上未被占用區(qū)域的片段。當(dāng)新任務(wù)到達的時候，區(qū)域管理器將會搜索頂點列表并使用不同的位置啟發(fā)式算法來找到合適的位置。這種方法能夠以更高的效率來管理處理區(qū)域，但是由于任務(wù)的插入和刪除，導(dǎo)致對頂點列表的管理非常復(fù)雜。此外，不是所有頂點列表中的頂點都是可用的任務(wù)分配候選區(qū)域。事實上只有一部分頂點列表中的頂點能夠作為任務(wù)分配的候選位置使用。該算法的復(fù)雜度是Ο(n²)，其中n是FPGA平臺上運行時的任務(wù)數(shù)量。

目前的研究和實現(xiàn)主要關(guān)注于如何進行可重構(gòu)器件本身的管理和優(yōu)化，但是由于可重構(gòu)器件對于一般性任務(wù)的處理速度并不夠高效，因此可重構(gòu)器件往往需要與通用處理器進行協(xié)同，共同完成任務(wù)的處理。

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

本發(fā)明的目的在于提供一種基于可重構(gòu)器件的混合處理器架構(gòu)及其任務(wù)調(diào)度方法，以高效的處理不同類型的任務(wù)。

本發(fā)明解決其技術(shù)問題采用的技術(shù)方案如下：

一種混合處理器架構(gòu)，包括：