基于可重構系統的時域劃分技術的研究

摘要：可重構計算是一種介于ASIC和通用微處理器之間的新的提升計算機性能的方法，對于數字信號處理、流媒體技術、圖像壓縮、密碼學、生物信息處理等計算密集型方面的應用，可重構計算技術可以發揮巨大的優勢。基于具有較少重構時間的實時可編程邏輯器件（如FPGA）的用戶可編程性，其可作為多種硬件資源使用。如果其配置信息可以迅速更改，則由邏輯器件實現的硬件功能也可實現迅速切換。硬件資源的大小是有限的，那些超過器件有效硬件資源的較大任務需要通過時域劃分來解決。該文對可重構計算以及時域劃分的定義、分類，國內外研究現狀和常見的研究方法做了詳細的描述，并綜合分析了一系列時域劃分算法并進行了相關比較。

關鍵詞：時域劃分；可重構計算；現場可編程門陣列（FPGAs）；數據流圖

中圖分類號：TP301文獻標識碼：A 文章編號：1009-3044(2011)04-0910-03

The Research on the Temporal Partitioning Based on Reconfigurable System

ZHOU Zhou

(Tongji University， Shanghai 201804， China)

Abstract: Reconfigurable computing is a new method between ASIC and GPP to improve the performance of the computer， which could be used to the application about Digital Signal Processing， the technology of Stream Media， Image Data Compression， Cryptology， Bioinformation and so on. Chips based on runtime programmable logic devices (such as the case of FPGAs--field programmable gate arrays) with low reconfigurable time is programmable by users， so it could be used as various hardware resources. If we could change the reconfiguring information of the devices quickly， the switching of hardware function can be realized by logic devices. As the hardware resource is limited， the large scale task which exceed the available hardware resources should be temporal partitioned. This paper introduces the definition， classification， the research status internal and oversea and some general research methods. We also analyse some of temporal partitioning methods and compare them with each other.

Key words: temporal partition; reconfigurable computing; FPGAs; DFG

1 概述

現今，隨著計算機技術和應用的飛速發展，人們對計算機性能的要求也是越來越高。長期以來，人們通常使用兩種方法以獲得其性能上的提高：一種是使用專用集成電路（Application Specific Integrated Circuits， ASIC），這種方法具有很高的執行速度和運算精度，但是它缺乏靈活性，功能單一，一旦設計制造完成，就只能支持某個或者某類固定的算法，要想實現不同的算法必須得重新設計集成電路，同時ASIC的設計流程復雜，隨著集成電路呈指數級增長，系統出錯的可能性也在增加，這都會帶來設計周期的延長和研發成本的增加；另一種是使用通用微處理器（General-Purpose Processor， GPP），通過軟件來實現算法，這種方法靈活性高，但指令的串行執行以及指令集的有限性使得GPP的性能并不理想，對于實時性要求高的應用，軟件的方法難以滿足要求。

在20世紀60年代末，美國加州大學洛杉磯分校的Geraid Estrin在其論文提出了重構計算的概念[1]， 并研制了原型系統，該系統由非柔性但可編程的處理器和柔性的由程序控制重構的數字邏輯部件兩部分組成。簡單來說就是，對結構固定的硬件計算平臺，根據應用的不同需要進行配置，并在輔助設備（包括外圍控制硬件和軟件）的協同下完成相應的計算任務。可重構引入了空間域的可編程能力，即可重構硬件除了時間域上的可編程能力外，空間域上的邏輯塊或者功能塊的邏輯結構是可以配置的。ASIC功能固定，在空間域和時間域只能被編程一次，而可重構硬件則可以被多次配置為不同的邏輯功能，在空間域和時間域上均可變，這種基于可重構硬件實現可重構計算的系統即為可重構系統（Reconfigurable System）。從本質而言，可重構計算是一種時空域上的計算模式，而傳統的通用處理器是時域上的計算模式，ASIC則位于空域上。

可重構計算(Reconfigurable Computing， RC)既具有ASIC高的計算速度及效率，又具有微處理器方法的可編程性和良好的靈活性。對于數字信號處理、流媒體技術、圖像壓縮、密碼學、生物信息處理等計算密集型方面的應用，可重構計算技術可以發揮巨大的優勢，使得可重構計算理論和技術成為當前的研究熱點。VLSI技術的進步促進了以FPGA為代表的可重構硬件的快速發展，尤其是具有動態部分重構能力的可重構硬件的出現，使可重構計算成為解決這類問題的重要方法。可重構硬件適合于執行應用程序中控制相對簡單、數據訪問比較規則、計算量相對較大的那些“計算密集型”任務，而應用程序中不可避免地存在一些控制相對復雜、計算相對簡單以及無法硬件綜合的計算任務，因此，現有可重構計算系統多采用可重構硬件結合微處理器核的硬件體系結構。

2 關于時域劃分國內外研究現狀

時域劃分本質是要解決可重構系統中有限的硬件資源與滿足大規模任務所需大量硬件資源之間的矛盾。時域劃分的關鍵是減少總的執行時間，具體表現在：一是劃分盡量要做到每個子任務占用資源數相近，并且最好能達到硬件所能提供資源的最大數目；二是每個模塊中可以并行的操作越多，其關鍵路徑越短，系統總處理時間就越少；三是盡量減少模塊間數據交換，也能減少總執行時間。總之，時域劃分是個多目標的優化問題。模塊的數目要減少，配置次數要減少；每個模塊的執行時間越短越好；模塊間通信的數據量越少越好，以縮短任務切換時，用于數據傳遞的時間。

由于劃分過程復雜，早期可重構系統任務劃分都是由開發人員手工完成[2]，后來研究者開始嘗試采用算法自動進行任務劃分。Purna等人[7]提出了時間分割的思想，任務圖中每個節點都有自己的ASAP (As Soon As Possible)值，用來反映節點執行時間的先后順序。根據ASAP值來劃分任務圖，同時保證每個劃分模塊不能超過可重構單元的大小。在此基礎上，Purna給出了兩種算法：基于層次的劃分算法（Level Based， LB）和基于簇聚集劃分（Cluster Based， CB）的劃分算法。

逐層劃分算法思想：首先是要為DFG中節點分配不同的層次，通過ASAP調度算法就可以實現為節點分層。分配層次后，依次從最高層到低層逐層將節點放入模塊中，如果模塊占用資源大于硬件提供的資源，則新產生一個模塊。LB算法的優點：目標是盡可能提高各個劃分模塊內部操作的并行度，因為每一層中的節點都是可以并行執行的，逐層劃分方法可以有效的減少模塊的執行時間。同時LB算法也保證了節點的先后執行次序不會被打亂，其劃分示例圖如圖1所示。

聚集劃分算法思想：盡可能將聯系緊密的操作放到一個模塊中，從而減少了通信代價，即跨模塊的數據通信量。LB算法的優點：目標是盡可能減少劃分之間的通信代價。其劃分示例圖如圖2所示。

上述兩種方法的缺點是它們都是基于單一目標的貪婪方法，并沒有全面考慮影響劃分結果的所有因素（如執行時間等）。

Vemuri等人[4]提出用整數線性規劃（Integer Linear Programming， ILP）方法求解時域劃分問題。ILP方法的優點：是能夠將問題形式化地表述，一旦ILP模型建立，通過求解工具就可以進行求解優點。ILP方法的缺點：該方法所建ILP模型中并沒有考慮模塊間數據通信的代價，并且ILP方法由于不對搜索空間進行裁減，其求解過程非常耗時，該方法只能用于求解規模比較小的問題，幾乎不具有實用性。

張學杰等人[5]采用分解---合并的方法來實現任務時域劃分，該方法主要減少劃分的模塊之間數據交換，取得較好效果。該算法思想是，首先，對待劃分任務產生若干個較小規模的劃分，稱作簇；然后，分析簇之間的關系，在滿足硬件資源限制的前提下，如果將多個簇合并能夠減少通信量，就將它們合并，形成較大的劃分模塊。該方法也有一些不足之處，一方面，初始的劃分很難確定（因為存在硬件資源約束，初始產生的劃分并不能都滿足合并的條件），會降低資源利用率；另一方面，該方法也存在不能充分利用劃分模塊中各操作之間并行性的問題。

Jo?觔o等人[6]提出了一種ELS劃分算法，它是一個多目標優化的任務劃分算法，該算法是基于增強的靜態列表調度算法構造的DFG圖劃分算法。該算法首先對數據流圖進行ASAP和ALAP(As Late As Possible)調度，分別為每個節點計算ASAP和ALAP的層次值，然后根據這個值通過一個加權公式計算每個節點的權重，這個公式將通信代價和執行代價統一起來，形成一個量化的權重。ELS算法是一個多目標優化的算法，綜合考慮了通信和執行代價，通過調整比例系數，還可以使算法側重于某一個優化方向選擇節點，但是，ELS算法在所獲得結果中，生成的模塊數量比較多，對系統執行效率也有不利影響。

Takayam等人[7]給出了一種綜合考慮提高操作并行度和減少模塊間通信量的劃分算法，這個算法本質上是逐層劃分和聚集劃分兩個算法的結合與改進。它隨機地在并行度和通信量兩個優化方向進行選擇。算法定義了兩個度量，一個稱作“最晚開始時間”，另一個稱作“最長完成時間”，在進行節點選擇時，根據不同優化目標，以這兩個度量為標準選擇節點；該算法也有不足之處，它通過選擇“最長完成時間”節點并不一定能達到減少通信量的目的。

Jo?觔o[8]提出了一種基于功能單元共享的時域劃分算法。該算法在虛擬硬件[9]概念（硬件資源假定為無限制的，并且通過時域劃分解決所需資源遠大于器件有效資源的任務執行問題）的基礎上，執行時域劃分的同時進行功能單元的共享，從而減少了劃分模塊數目和整個任務的執行延遲。功能單元的共享是一種多個相同功能操作重用一個獨立配置的功能單元的技術。該算法的優點是通過功能單元共享使得所用的功能單元器件減少了，但是同時它的執行時間并沒有得到很好的改善。

近年來，在國內也有相關工作的研究。浙江大學孫康等人[10]提出一種基于時域的快速劃分算法—MOTPA，首先建立劃分問題的模型，在模型中考慮影響劃分結果的多個因素，在此基礎上，MOTPA算法通過代價估計在模塊數、操作并行度和通信量3個優化目標中進行折中點選擇決定優化的目標。但算法實時性不夠，時間和空間復雜度較高。

3 問題定義

我們用數據流圖（data flow graph， DFG）作為待劃分任務的行為級描述，假設該DFG圖是拓撲有序無環的。下面給出了數據流圖和時域劃分問題相關的形式化模型定義。

定義1：數據流圖G = (V， E)是一個有向無環圖，其中V = {v1， v2， ...， v|n|}為圖中所有節點的集合，E為圖中所有有向邊的集合，分別記|V| = n和|E| = m為節點和邊的數目，其中?坌vi∈V表示待劃分任務中的一個運算操作，且一個運算操作對應唯一一個功能單元部件，?坌ei，j∈E表示節點vi和vj的依賴關系，該依賴關系可以是簡單的前驅依賴，也可以是兩節點間由于數據流而產生的傳輸依賴（譬如一個變量被賦值給一個節點并為該節點的后繼節點所用）。

定義2：P = {p1， p2， ...， pk}為數據流圖G = (V， E)的一種劃分，其中?坌pi∈P為G中V的非空子集合，我們稱之為模塊。下面為一些文中所用到的符號標識：Rmax表示目標可重構器件中可用硬件資源的總數；R(pi)表示模塊pi中已用資源數目；R(vi)表示執行節點vi所代表運算操作所需資源數目；TP(pi)表示被劃分入模塊pi的所有節點集合；P(vi)表示節點vi所在的模塊號；劃分模塊集可表示為，其中k代表所有劃分模塊數。正確的時域劃分應該滿足一下條件：

1）每個節點vi∈V只劃分入唯一一個模塊中；

2）所有的節點都被劃分入相應的模塊中；

3）每個劃分模塊所占資源必須小于器件可用資源總數；

4）劃分模塊的執行順序不能違反DFG圖中各個操作的依賴關系，對于任何兩個模塊，其映射到可重構硬件上有先后次序，后映射的模塊中的任何操作在原始DFG圖中的執行順序不能先于先映射的模塊中的任何操作的執行順序；

4 劃分算法描述

時域劃分本質是要解決可重構系統中有限的硬件資源與滿足執行大規模任務所需大量硬件資源之間的矛盾。時域劃分的關鍵是減少總的執行時間，具體表現在：一是劃分盡量要做到每個劃分模塊已占用資源總數與該模塊最大資源數相近，并且最好能達到硬件所能提供資源的最大數目；二是每個模塊中可以并行的操作越多，其關鍵路徑越短，系統總處理時間就越少；三是盡量減少模塊間數據交換，也能減少總執行時間。

我們選取了具有典型代表的ELS（增強靜態列表）時域劃分算法和基于功能單元共享的時域劃分算法進行了研究并加以實現，得出了其各自的劃分結果。

ELS針對DFG圖中每一個節點，設定一個權衡該節點執行延遲與通信成本的權值函數模型，我們通過該節點的出入度、ASAP值（節點最早執行時間）、ALAP值（節點最晚執行時間）綜合計算該節點的權值W，在整個劃分過程中，按各個節點權值大小降序排列依次插入至待劃分就緒節點列表中。

基于功能單元共享的時域劃分思想是建立在硬件虛擬化概念的基礎之上的，執行時域劃分的同時進行功能單元的共享，從而減少了劃分模塊數目和整個任務的執行延遲及其通信量。功能單元的共享是一種多個具有相同功能操作共用一個獨立配置的功能單元的技術。

5 實驗結果與分析

本實驗采用C語言實現了該劃分算法，并利用多種基準程序對算法性能進行了測試，基準程序包括了快速傅里葉變換、快速離散余弦變換、FEAL加密算法、EWF濾波器等11種常用的多媒體應用算法。

實驗以相同環境實現了ELS劃分算法和基于功能單元共享原始劃分算法，并獲得相應數據。為便于比較，本文采用了相同的約束條件。幾種劃分算法對基準程序測試用例的運行結果如表1所示，其中ELS代表一種增強型靜態列表調度的時域劃分算法，SoFU代表改進前的基于功能單元共享原始劃分算法。表中給出了在不同硬件資源約束下得到的各個劃分算法的模塊數。

6 結論

本文綜合分析研究了一系列可重構系統任務時域劃分算法，充分考慮到任務中模塊數和并行性、通信量之間的關聯，并采取適當的約束條件加以限制。通過實驗可知，該改進算法能夠取得較好的劃分結果，并行運行速度較快。下一步工作我們將各個算法已得結果進行比較分析，在此基礎上提出新的劃分效果更好的時域劃分算法。

參考文獻：

[1] Estrin G.Parallel Processing in a Restructurable Computer System[J].IEEE Trans.Electronic on Computers，1963，12(5):747-755.

[2] Bhat N.Novel Techniques for High Performance Field Programmable Logic Devices[D].PhD thesis，Univ. of California， Berkeley， Electronic Reserach Laboratory，UCB/ERL-93-80，1993.

[3] Long X P，Amano H.WASMII: a Data Driven Computeron a Virtual Hardware[C]//Napa Valley，CA:Proc 1st IEEE Workshop on Field Programmable Custom Computing Machines1993:33-42.

[4] Cardoso J M P.On Combining Temporal Partitioning and Sharing of Functional Units in Compilation for Reconfigurable Architectures[J].IEEE Transaction On Computers，2003，52(11):1362-1375.

[5] Cardoso J M P，Neto H C.An Enhanced Static-List Scheduling Algorithm for Temporal Partitioning onto RPUs[C]//Lisbon:IFIP X International Conference on Very Large Scale Integration，1999.Silveira L M，Devadas S，ReisR.VLSI:Systems on a Chip， Kluwer Academic Publishers，1999:485-496.

[6] Hudson R，Lehn D I，Athannas P M.A Run-time Reconfigurable Engine for Image Interpolation[C]//Proceedings of 6th IEEE Symposium on FPGAs for Custom Computing Machines，Napa Valley:IEEE，1998:88-95.

[7] Purna K M G，Bhatia D.Temporal Partitioning and Scheduling Data Flow GraPhs for Reconfigurable Computers[J].IEEE Transactions on Computers，1999，48(6):579-590.

[8] Kaul M，Vemuri R.Temporal Partitioning combined with Design Space Exploration for Latency Minimization of Run-Time Reconfigured Designs[C]//Paris，France:Proc. of Design， Automation Test in Europe，1999:202-209.

[9] Zhang X J，Ng K W.A Temporal Partitioning Approach Based on Reconfiguration Granularity Estimation for Dynamically Reconfiguration Systems[C]//Proceedings of 2nd IEEE International Conference on Field-Programmable Technology，Tokyo:IEEE，2003:344-347.

[10] Takayama A，Shlbata Y，Iwal K，et al.Dataflow Partitioning and Scheduling Algorithms for WASMII: A virtual Hardware[C]//Villach， Austria:Proceedings of 10th International Conference on Field-Programmable Logic and Applications，2000:685-694.

[11] Cardoso J M P.A Novel Algorithm Combining Temporal Partioning and Sharing of Function Units[C]//Rohnert Park， California:Proceedings of the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines，2001:31-40.

[12] 潘雪增，孫康，陸魁軍，等.動態可重構系統任務時域劃分算法[J].浙江大學學報，2007，41(11):1839-1844.