基于空間管理器和適配器的可重構設備在線放置

彭晶晶，閔陽陽，范 平

(1.湖北科技學院 計算機科學與技術學院，湖北 咸寧 437100；2.內蒙古工業大學 紡織工程系，呼和浩特 010000)

0 引言

處理器(微處理器和數字信號處理器等)是當前大多數高性能計算平臺的核心。它們提供了一個靈活的計算平臺，能夠執行大型類應用程序。微處理器的每個組件的功能是固定的。應用程序是通過解碼來自軟件的指令流并操作存儲在內存層次結構中的數據來執行的。因此，相同固定的硬件可以用于許多通用應用。然而，順序指令解碼和執行、內存訪問瓶頸和固定的控制架構限制了所使用處理器所能達到的性能。專用集成電路(AISC,application specific integrated circuits)提供了一種解決通用處理器性能問題的替代方案。ASIC是為專門應用而設計的，因此，每個ASIC對于高度受限的應用程序集都具有固定的功能和優越的性能。然而，大多數應用都有不斷更新的算法，需要支持新興的標準。因此，ASIC限制了架構的靈活性，并限制了任何功能和算法的后期設計優化和升級；采用可重構計算的新計算模式確保了可擴展性和性能之間的權衡。可重構計算利用可以在運行時進行調整的硬件，以促進更大的靈活性，而不影響性能。可重構體系結構由于其適應性，可以利用應用程序中可用的細粒度和粗粒度并行性。與傳統微處理器相比，利用這種并行性獲得重要的性能優勢。硬件的可重構性允許對每個應用程序中的特定計算進行硬件適配，以實現比軟件更高的性能。復雜的功能可以映射到架構上，從而實現更高的芯片利用率，減少指令獲取和執行瓶頸。

大多數計算任務都具有較高的計算需求和實時吞吐量限制。除了大量的精細計算之外，還有復雜的數據，這些數據在單個應用程序和不同應用程序之間是不同的。一般用途的架構，如微處理器和數字信號處理器，通常不能維持所需的計算和數據流吞吐量。可重構計算正在成為滿足應用程序性能和可擴展性同時需求的新范式。與通用體系結構相比，自定義體系結構以匹配應用程序的計算和數據流的能力表明了其優越性。在低級的算法中，有規則的、重復的計算操作于大量具有可預測數據依賴性的數據集上進行。在較高級的算法上，計算具有不規則的依賴性。這些應用特點與可重構架構的優勢有重要的關聯。

現代可重構設備允許對一部分器件進行重新配置，而其余部分則保持不變，從而在可重構設備的部分空間上分配任務并執行任務。運行時的空間分配(也稱為臨時放置或在線放置)是可重構計算的核心部分，但目前許多研究都沒有專門針對這一目標進行，這在一定程度上是由于可重構設備的制造商通常沒有提供無條件部分重新配置功能以及部分重新配置的工具。隨著這類設備在市場上的出現，需要對在線放置進行深入的研究。對于在線放置問題，必須解決2個子問題：

子問題1：確定放置由新模塊(或新組件，這兩個名詞表示相同含義，有時也說成任務，文中敘述交替使用這3個說法)實現的新任務的潛在位置集合。

子問題2：按照一組給定的準則選擇放置新模塊或新組件的最佳位置。

關于在線放置的大多數研究[1-3]都采用空閑空間管理器來解決子問題1，把設備上的空閑空間表示為一組空的矩形。文獻[1]研究了一維路由結構和二維路由結構的表示模型，重點研究了針對這兩種表示模型的任務調度，并針對可重構系統，提出了硬模塊和軟模塊的在線和離線啟發式放置方法。這些方法可以在內部或外部進行，所提出的在線放置算法能比實際中常用的在線放置算法快約15～30倍。對于離線放置，提出了一種基于模擬退火和貪婪方法的放置算法，并表明了其放置要優于在線算法生成的放置，仿真實驗驗證了算法的性能和運行效率；文獻[2]為了提高可重構計算的效率和多任務系統中的在線模塊定位，提出了在現場可編程門陣列(FPGA，field-programmable gate array)上的多任務處理方法，即一種新的多階段任務到可重構硬件映射的方法，并提出了一種新的適配算法作為在線放置的一部分，實驗結果表明能夠顯著減少重新配置的開銷；文獻[3]提出了一種可重構FPGA在線任務放置的快速最大空矩形(MER, maximal empty rectangle)枚舉算法。在每個任務都利用矩形資源的假設下，該算法可以通過MER列表來管理FPGA上的空閑空間。在分配或刪除任務時，根據任務及其分配位置選擇一系列MER并將其分割成段。通過處理這些段，MER列表可以以較低的內存消耗快速更新。在FPGA上證明了MERS數的上限，分析了算法的時間復雜度和空間復雜度，最后用實驗驗證了該算法的有效性；文獻[4]針對可重構平臺上可用系統門數量的增大，以及這些資源的管理和它們在應用程序和用戶之間的共享問題，提出了在可重構操作系統中來管理這些資源，給出了操作系統的一組可行組件和一種可行的軟件架構，提出了一些性能指標來衡量操作系統實現的質量如區域分割、算法性能和應用性能，最后實現了一個可重構平臺上的操作系統；文獻[5]針對多任務操作系統的可重構資源管理，提出了一種管理模型和在線調度算法。具體實現是把任務分配給基于塊劃分的可重構器件。同時在在線調度器和放置器運行2個函數fSPLIT和fSELECT來實現任務在可重構器件上的配置和調度。仿真結果表明，提出的資源管理模型和調度算法不僅能夠實現任務集平均響應時間的最小化和有效調度，而且相比于其他調度算法，還能獲得更高的資源利用率；文獻[6]針對多叉樹任務數據流圖的劃分映射問題，基于粗粒度行并行可重構架構，提出了一種行列剪枝映射算法，分析和比較了二維沒有跳變近鄰點點互連和行并行互連的可重構單元陣列的映射性能。實驗結果表明，該算法可以減少執行時間；對于放入組件，根據放置策略(最佳適配(BF，best fit)、第一適配(FF,first fit)等)[7-9]選擇其中一個空矩形，把任務放置在所選擇的矩形內，并計算出新的空矩形集合。這種方法(空閑空間分割)的主要缺點是：每當一個新的任務被放置時，空矩形集增加非?？欤瑥亩沟脤ふ乙粋€合適的位置(子問題2)變得困難；此外，到達的任務被作為獨立實體處理，因此，通信方面又被忽略了；文獻[10]提出了一種任務驅動的嵌入式可重構異構計算平臺，通過集群構建的方式，對多個分布式的、承載各種不同異構計算資源的嵌入式計算板卡統一調度管理。利用容器化技術，構建任務驅動的、可重構的任務執行的虛擬計算環境。開發了基于B/S模式的平臺可視化用戶界面，實現了用戶對平臺的隨遇接入和全網資源可見；文獻[11]提出了一種可重構單元的二維任務放置方法。結合包括當前任務與其鄰接任務在時間上的重合度，當前任務與其鄰接任務的邊長的重合度，以及當前任務對其它空閑塊的影響程度，依次計算當前任務的長、寬分別沿每個空閑塊的每兩條相鄰邊放置時的合適度，選出所有空閑塊的所有位置中合適度最大的位置作為當前任務的最終放置位置，可使任務放置更為緊湊合理，減少可重構單元中的碎片，提高可重構單元的空間利用率；文獻[12]針對異構系統中可重構計算的任務調度問題進行了研究。通過分析FPGA的硬件結構的主要單元，結合異構系統中可重構計算系統的架構，提出了帶有路由資源考慮的FPGA通信架構模型。通過分析現有可重構資源管理策略，提出了基于任務頂點劃分矩形的資源管理策略，通過狀態矩陣維護跟蹤可重構資源的實時信息，并根據任務頂點劃分最大空閑矩形；文獻[13]提出通過將新到達的硬件任務放置在己布局硬件任務的頂點處，通過對可重構芯片內部計算單元進行編碼來迅速判斷新任務是否可放置在該頂點。如果硬件任務無法放置，可以通過旋轉該硬件任務再進行判斷，以提高可重構芯片空間的利用率，并有效地減少布局開銷；[14]基于Xilinx設計套件提出了一種放置器架構，適用于異構可重構邏輯體系結構的靈活、快速和無約束的定向放置，特別適合異構FPGA，使得應用程序設計人員能夠利用部分動態重新配置的優勢，通過動態調度硬件預取來加速應用程序。

基于以上放置策略存在的各種不足，本文提出了一種新的策略在可重構設備上在線放置組件。一方面，利用空矩形集比放置矩形(任務)集增長更快的原理，因而更適合于管理設備上已占用的空間，而不是空閑空間；另一方面，在實際應用中，每個任務都以某種方式與其環境進行通信的，這種通信是以任務的輸入到輸出的形式進行，因此，任務之間的通信路由在放置策略中起著重要的作用，所以本文在尋找子問題2的解中充分考慮了路由成本的優化。實驗結果表明，本文提出的在可重構設備上的在線放置策略，本文提出的空間管理器和適配器相比于目前常用的幾種放置方法不僅有更低的復雜度，而且有更低的適配時間。

1 系統模型

在討論在線放置問題之前，先給出本文要研究的系統模型的相關定義和假設。

假設一個可重構設備R是在一組配置為H行和W列的矩形陣列中的可重構處理元件(PE， processing element)上產生的，這些PE可以某種方式連接在一起。

本文的動態重構模型是在一個調度器、一個在線放置器和一個可重構設備上建立的，如圖1所示。調度器管理任務，并決定何時執行任務，然后把任務提交給放置器，放置器嘗試將任務放置到設備上，即為該任務分配一組PE。如果放置器不能為新任務找到一個位置，那么該任務將被發送回調度器，調度器可以決定稍后發送它或將另一個任務發送給放置器，在這種情況下，我們說任務被拒絕了。由于本文主要針對系統中的放置器部分進行研究，所以關于調度器的設計不在本文的研究之列。對于要放置到可重構設備上的每個任務來說，我們進一步假設一個矩形模塊的實現是可用的，其邊界上有輸入和輸出端口，這個實現存儲在一個模塊數據庫中，并將按需檢索。

圖1 一種可重構設備的多任務處理系統

我們定義任務特征如下：

定義1 任務特征：給定一組任務T={t1,t2,…,tm}，一個任務tk∈T的特征是4-元組(ak,ek,wk,hk)，其中ak是任務tk的到達時間，ek是任務tk的執行時間，wk是使用PE的任務tk的對應模塊的寬度，hk是使用PE的任務tk的對應模塊的高度，我們令：

tk=(ak,ek,wk,hk)

(1)

一個任務的到達時間是放置器從調度器接收該任務的時間，它與該任務是否被放置或拒絕無關。在每個時間點，放置器包含一組動態的任務(DST, dynamic set of task)，DST由正在運行的任務和要放置到設備上的新任務構成，PE從DST中動態地插入和移除。

此外，我們還假設任務是不可搶占的(因為配置開銷很高,盡管這一假設并不影響放置方法)，運行模塊也是不可替換的。由于我們感興趣的是任務和它們的環境之間的通信，所以不僅要考慮不同任務之間的連接，但要考慮任務和設備邊界之間的連接，這對于具有離片通信的任務來說是有用的；對于一個給定的DST，我們定義一組動態連接(DSC,dynamic set of connections)，DSC的一個元素或者是兩個任務之間的一個連接，或者是一個任務與邊界設備上的一個位置之間的連接。

定義2 任務通信：給定一個DSTT和在可重構設備R邊界上的一組位置(引腳,pins)P，我們定義動態通信集為T和(T∪P)之間的邊集。

邊(p,q)∈C的權值wpq是連接兩個元素p∈T和q∈(T∪P)的總線的寬度。

在定義了任務特征、DST和DSC之后，我們在接下來的內容中來闡述本文的在線放置策略是如何實現的。

2 方案實現

2.1 空間管理器

如引言中所述，放置問題的第一部分是確定可以放置新模塊/組件的全部可能的位置。

解決這個子問題的最簡單的方法是采用Brute Force算法[15-17]。對于要放置的每個新模塊/組件c，Brute Force算法通過掃描設備上的所有位置來解決第一個子問題。對于每個位置p=(xp,yp)，算法檢查在c和放置模塊之間是否會發生重疊，如果組件c要放置在位置p上。

在解決了子問題1之后，通過計算第一步中找到的每個位置的放置成本來計算最佳放置位置，并選擇最好的一個作為最優解。

Brute Force算法需要O(H×W×n)的時間來求解子問題1，其中H是可重構設備的高度，W是寬度，n是硬件上運行的任務數。

文獻[3,18-19]提出將空閑空間僅存儲為最大矩形，這種方法的復雜度是O(n2)。對于大型可重構設備來說，H和W都比n大，因此采用文獻[3]的方法要優于Brute Force方法。然而，在文獻[3]的方法中，采用二叉樹來管理空矩形，這對于通過刪除和插入模塊來保持更新就非常復雜，因為在某些情況下需要改變樹的許多節點。因此，本文提出一種更簡單和更快的方法，其復雜度為O(n)。與文獻[3]的方法相反，本文提出管理設備占用空間，而不是空閑空間，主要是基于設備上的空矩形集的增長速度比放置組件集要快得多，因此算法將更快地使用已占用的空間來查找可以放置新組件的空閑位置集。

不失一般性，我們考慮組件放置相對于其左下角的位置，首先定義一個新組件的不可能放置區域(IPR，impossible placement region)。

定義1 相對于放置模塊的IPR：對于要放置在設備上的一個新組件c和已放置組件c′，c相對于c′的不可能放置區域(IPR)Ic′(c)是不與c′重疊的c不能放置的區域。對于一個已放置組件集C′來說，c的不可能放置區域IC′(c)是不與C′的一個元素重疊的c不能放置的區域，即：

IC′(c)=∪c′∈C′Ic′(c)

(2)

定義2 相對于設備的IPR：相對于設備的不可能放置區域IR(c)是不與該設備的外部區域重疊的c不能放置的區域。

定義3 不可能和可能的放置區域：一個新組件c的IPR是由IC′(c)和IR(c)來確定的，即：

I(c)=IC′(c)∪IR(c)

(3)

通過從設備區域減去運行組件的IPRs和設備的IPRs，就得到c的可能放置區域(PPR,possible placement region)P(c)。如果U是設備上的全部位置集，則有：

P(c)=U-I(c)

(4)

對于一個要放置到設備上的具有高度hc和寬度wc的新組件c以及一個已放置的組件c′，c相對于c′的不可能放置區域(IPR)Ic′(c)是通過計算組件c′的大小為hc-1的左部邊緣和大小為wc-1的底部邊緣來確定的，如圖2所示。

圖2 相對于已放置模塊的新模塊的IPR

通過集成這個邊緣和運行任務的區域，就可以得到放置新模塊(即由這個運行任務產生的)的不可能區域。然后，確定出全部運行模塊的這些邊緣，從而得到全部已放置模塊產生的不可能區域；此外，可重構設備的邊界也有兩個邊緣，顯然，當新模塊到達以供放置時，必須重新計算每個已放置模塊的邊緣。

如前所述，計算出相對于設備和每個已放置組件的IPR，就可以得到IPR集，如圖3所示。子問題1的解可以通過從總的設備區域減去IPR集來得到。由于需要計算運行模塊的擴展邊緣和相對于設備的兩個區域來求解子問題1，因此算法需要的計算復雜度是O(n)。

圖3 新模塊的不可能位置區域

2.2 適配器

在線放置的第二個子問題即子問題2是從可能放置區域集合中找到放置新模塊的最佳位置。一種簡單的方法[15-16]就是由掃描所有可能的放置位置和計算每個位置的放置成本構成，然后選擇最佳的一個位置。這種簡單低效的方法需要的復雜度是O(|PPR|*n)，其中n是放置組件的數量，因而Brute Force方法作為一種在線放置算法來說代價太高了。因此，本文首先計算能得到最佳放置成本的點popt，而不是計算出每個點的放置成本，然后選擇其中最佳的一個點。如果popt位于PPR內，則就得到了子問題2的解，否則，就尋找最靠近popt的點(popt位于PPR內)，并選擇它作為最佳放置位置。

為了確定最佳點，我們首先確定成本函數，這個成本函數應當通過最佳點來使其最小化。最重要的成本函數之一就是路由成本[20]，所以我們的主要目標就是以一種組件之間通信最優的方法來放置組件，這個目標可以通過將連接的組件放置在彼此附近來達到；此外，具有片外/離片連接的組件也應當放置在設備的邊界上，而不是遠離它們所使用的引腳。

我們定義最小化成本為放置在設備上的組件的通信成本，用距離和總線寬度來衡量，將這種成本稱為路由成本，并定義如下：

定義1 路由成本：對于兩個模塊i和j來說，定義它們之間的路由成本Cost(Rij)如下：

(5)

換句話說，兩個模塊之間的路由成本就是它們之間的加權距離。為了計算路由成本，我們采用組件的中心點而不是采用左下角點作為參考點，對于模塊i，它是由數據對(xi+wi/2,yi+hi/2)定義的，其中(xi,yi)定義i的左下角位置，wi定義i的寬度，hi定義i的高度。如果在兩個模塊i,j之間沒有通信，則wij以及它們之間的路由成本將為零。當我們已有(n-1)個放置模塊時，并希望放置第n個模塊，那么應當使這個模塊對于其他已放置模塊的路由成本最小化，根據定義1，得到：

(6)

式中，xn和yn為變量，其他參數是固定的。由于xn和yn是相互獨立的，所以式(6)可以寫成下列式(7)和式(8)：

(7)

(8)

式(7)的值是xn的函數，則為了最小化，我們必須找到這個函數對xn的偏導數為零的點，即：

(9)

(10)

以同樣的方法，可以計算出yn的最佳值為：

(11)

在找到放置新模塊的最佳點之后，必須檢查該點是否屬于PPR集。當該點不在PPR集中時，我們將尋找接近最佳點最近可能位置(NPP, nearest possible position)。如圖4所示，在IPR中有4個接近最佳點的點，我們把最接近的一點選擇為NPP。如果這一點也是不可行的，則重復前一步，直至找到最近的可行點。圖5為覆蓋最佳點的不可能區域，以及如何設法確定接近可能的點。

顯然，最優化的路由成本會大大降低適配器的適配時間。

圖4 接近最佳點的可能點

圖5 確定接近最佳點的可能點

為了找到NPP，根據每個重疊區域，采用一個接近可能位置的列表。在最壞的情況下，全部不可能區域覆蓋這個最佳點，而且列表中的點數目將是O(n)，那么NPP就可以在O(n)時間內計算。 NPP算法的實現步驟偽代碼如下：

計算最佳點(新組件)：

if 最佳點是可用的 then

把新組件放置在這個最佳點上

從表6可以看出，2012—2016年青島市總的就業人數不斷增加。2012—2016年青島市第一產業的就業比重呈現逐年遞減趨勢，但趨勢比較平緩；第二產業的就業人員比重同樣呈現逐年遞減趨勢，其中2013—2014年就業人員比重減少最多；第三產業的就業人員比重在逐年遞增，尤其2014年第三產業就業人員的比重增加最大，這是第二產業就業人員大量向第三產業轉移的結果。通過分析三次產業就業結構可以看出，2012年青島市的工業化發展水平屬于工業化后期，2013—2016年屬于工業化中期。

else

計算NPP:

1.找出所選點所在的邊緣外的4個接近點

2.插入這些點到最佳點列表中

3.從接近點列表中選擇最接近最佳點的點

4.if 選擇的點是可用的 then

把新組件放置在這個最佳點上

else

從接近點列表中刪除它,并重復NPP計算步驟

2.3 數據結構

為了實現本文提出的在線放置算法，首先使用一個大小為O(n)的鏈表(n為運行任務數)來存儲在可重構設備上要放置的和正在運行的模塊。

算法使用的第二個數據結構是具有與可重構設備尺寸相同的二維矩陣，它代表設備的總狀態，因此它的每個元素都給出了一個PE的狀態，這意味著當一個點(PE)被一個模塊占用時，矩陣中對應的元素將有一個指向相關模塊的指針，否則，矩陣中的點指示點為空；此外，為了識別PPR，將在此矩陣上應用擴展和刪除邊緣的效果。采用矩陣可以訪問每個元素并僅在1個計算步驟中獲得其狀態。另一種需要較少內存的替代數據結構是使用鏈表，但在這種情況下，必須解析運行模塊列表來獲取每個元素的狀態，其復雜度在每一步是O(n)。正如前面提到的，這里使用矩陣，因此計算速度更快；

算法實現的第三個數據結構是一個動態二維矩陣，它表示每對運行模塊之間的通信帶寬，其維度大小與運行的任務數相同。該通信矩陣用于選擇放置一個新模塊的最佳位置，因為需要通信寬度來計算并使放置新模塊的路由成本最小化。為了找到放置一個新模塊的最佳或接近最佳的點，使用一個鏈表來保存接近最佳的點，我們總是從這個列表中選擇最接近最佳點的點，而且將在上述矩陣中檢查這個點，看該點是否是可用的位置，如果是，那么就得到NPP，否則這一點就被一個運行模塊或它的邊緣所占用；然后，從運行模塊的每個邊界插入最接近的點到這個列表，并將所選擇的點移除；同樣在這個列表中，將搜索的蹤跡存儲起來，因為為了確保不選擇運行模塊中的一個接近點(它已經覆蓋了先前的一個選擇的接近點)。如前所述，在最壞的情況下，我們將在這個列表中得到3n個接近的點，因此計算NPP的復雜度是O(n)。

3 方案性能評價

正如前面所討論的，本文所提出的空間管理器的復雜度是O(n)，而文獻[15-16]和文獻[3,17]的放置方法的復雜度分別是O(H×W×n)和O(n2)，因此本文提出的空間管理器比一般的空間管理器更優更快。

為了比較采用不同適配方法的性能，把本文提出的適配器即最近可能位置(NPP,nearest possible position)與最佳適配(BF，best fit)和第一是配(FF,first fit)兩種策略[7-8]進行比較，比較指標是不同適配方法的適配時間。對此，芯片的尺寸分別設定為56×84(mm2)和80×120(mm2)的二維PE陣列，分別類似于Xilinx Virtex XCV 800和 XCV2000E FPGA設備，針對不同的任務大小和形狀，實現一個具有隨機生成任務集的系統模型，這對于寬度和高度在不同間隔內均勻分布的任務是精確的。得到的對于具有不同任務大小即[20,40]和[20,30]時的運行結果，分別如圖6和圖7所示，也得到了近似方形的任務即[28,30]范圍的運行結果，如圖8所示。

圖6 任務大小為[20,40]時不同適配方法的適配時間

圖7 任務大小為[20,30]時不同適配方法的適配時間

圖8 任務大小為[28,30]時不同適配方法的適配時間

從圖6、圖7和圖8可見，本文提出的適配器在不同大小和形狀的任務下都得到了最小的路由成本，從而有最小的適配時間，而BF適配方法得到了最大的路由成本即最大的適配時間；還可看到，在近似正方形任務的情況下，FF適配方法可以得到與本文方法相近的結果，但在全部情況下都比本文提出的適配器方法需要更多的適配時間；另一方面，FF適配方法在路由成本方面比BF適配方法要優。而且當采用更大的芯片尺寸時，本文提出的適配器比FF和BF表現更好，因為它有更多的空間來找到最佳位置。

4 結束語

可重構計算是一種新的模式，與傳統計算相比，它具有更高的性能和更高的可擴展性。許多應用程序具有與可重構計算的優勢相匹配的計算特征。本文對可重構計算的不同方面作了介紹，概述了可重構計算的顯著特征及其分類和體系結構；重點討論了在可重構設備上的在線放置技術，提出了一種新的空間管理器和適配器用于在線放置。與其他在線放置方案相比，本文所提出的空間管理器保存已占用空間的信息，而不是空閑/自由空間的信息，具有更低的復雜度；同時還考慮了適配器中任務的路由成本，從而得到更低的適配時間；最后采用實驗評價了本文所提出的適配器算法和現有的適配器算法的比較。

關于未來的研究，我們打算開發一種框架，使得設計人員在臨時放置和通信成本的仿真方面能夠直接采用有效的模塊來實現；此外，還將研究本文的方案在嵌入式系統環境中的實現。