基于空間管理器和適配器的可重構(gòu)設(shè)備在線放置

彭晶晶，閔陽(yáng)陽(yáng)，范 平

(1.湖北科技學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 咸寧 437100；2.內(nèi)蒙古工業(yè)大學(xué) 紡織工程系，呼和浩特 010000)

0 引言

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

大多數(shù)計(jì)算任務(wù)都具有較高的計(jì)算需求和實(shí)時(shí)吞吐量限制。除了大量的精細(xì)計(jì)算之外，還有復(fù)雜的數(shù)據(jù)，這些數(shù)據(jù)在單個(gè)應(yīng)用程序和不同應(yīng)用程序之間是不同的。一般用途的架構(gòu)，如微處理器和數(shù)字信號(hào)處理器，通常不能維持所需的計(jì)算和數(shù)據(jù)流吞吐量。可重構(gòu)計(jì)算正在成為滿足應(yīng)用程序性能和可擴(kuò)展性同時(shí)需求的新范式。與通用體系結(jié)構(gòu)相比，自定義體系結(jié)構(gòu)以匹配應(yīng)用程序的計(jì)算和數(shù)據(jù)流的能力表明了其優(yōu)越性。在低級(jí)的算法中，有規(guī)則的、重復(fù)的計(jì)算操作于大量具有可預(yù)測(cè)數(shù)據(jù)依賴性的數(shù)據(jù)集上進(jìn)行。在較高級(jí)的算法上，計(jì)算具有不規(guī)則的依賴性。這些應(yīng)用特點(diǎn)與可重構(gòu)架構(gòu)的優(yōu)勢(shì)有重要的關(guān)聯(lián)。

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

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

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

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

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

1 系統(tǒng)模型

在討論在線放置問題之前，先給出本文要研究的系統(tǒng)模型的相關(guān)定義和假設(shè)。

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

本文的動(dòng)態(tài)重構(gòu)模型是在一個(gè)調(diào)度器、一個(gè)在線放置器和一個(gè)可重構(gòu)設(shè)備上建立的，如圖1所示。調(diào)度器管理任務(wù)，并決定何時(shí)執(zhí)行任務(wù)，然后把任務(wù)提交給放置器，放置器嘗試將任務(wù)放置到設(shè)備上，即為該任務(wù)分配一組PE。如果放置器不能為新任務(wù)找到一個(gè)位置，那么該任務(wù)將被發(fā)送回調(diào)度器，調(diào)度器可以決定稍后發(fā)送它或?qū)⒘硪粋€(gè)任務(wù)發(fā)送給放置器，在這種情況下，我們說任務(wù)被拒絕了。由于本文主要針對(duì)系統(tǒng)中的放置器部分進(jìn)行研究，所以關(guān)于調(diào)度器的設(shè)計(jì)不在本文的研究之列。對(duì)于要放置到可重構(gòu)設(shè)備上的每個(gè)任務(wù)來說，我們進(jìn)一步假設(shè)一個(gè)矩形模塊的實(shí)現(xiàn)是可用的，其邊界上有輸入和輸出端口，這個(gè)實(shí)現(xiàn)存儲(chǔ)在一個(gè)模塊數(shù)據(jù)庫(kù)中，并將按需檢索。

圖1 一種可重構(gòu)設(shè)備的多任務(wù)處理系統(tǒng)

我們定義任務(wù)特征如下：

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

tk=(ak,ek,wk,hk)

(1)

一個(gè)任務(wù)的到達(dá)時(shí)間是放置器從調(diào)度器接收該任務(wù)的時(shí)間，它與該任務(wù)是否被放置或拒絕無關(guān)。在每個(gè)時(shí)間點(diǎn)，放置器包含一組動(dòng)態(tài)的任務(wù)(DST, dynamic set of task)，DST由正在運(yùn)行的任務(wù)和要放置到設(shè)備上的新任務(wù)構(gòu)成，PE從DST中動(dòng)態(tài)地插入和移除。

此外，我們還假設(shè)任務(wù)是不可搶占的(因?yàn)榕渲瞄_銷很高,盡管這一假設(shè)并不影響放置方法)，運(yùn)行模塊也是不可替換的。由于我們感興趣的是任務(wù)和它們的環(huán)境之間的通信，所以不僅要考慮不同任務(wù)之間的連接，但要考慮任務(wù)和設(shè)備邊界之間的連接，這對(duì)于具有離片通信的任務(wù)來說是有用的；對(duì)于一個(gè)給定的DST，我們定義一組動(dòng)態(tài)連接(DSC,dynamic set of connections)，DSC的一個(gè)元素或者是兩個(gè)任務(wù)之間的一個(gè)連接，或者是一個(gè)任務(wù)與邊界設(shè)備上的一個(gè)位置之間的連接。

定義2 任務(wù)通信：給定一個(gè)DSTT和在可重構(gòu)設(shè)備R邊界上的一組位置(引腳,pins)P，我們定義動(dòng)態(tài)通信集為T和(T∪P)之間的邊集。

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

在定義了任務(wù)特征、DST和DSC之后，我們?cè)诮酉聛淼膬?nèi)容中來闡述本文的在線放置策略是如何實(shí)現(xiàn)的。

2 方案實(shí)現(xiàn)

2.1 空間管理器

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

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

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

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

文獻(xiàn)[3,18-19]提出將空閑空間僅存儲(chǔ)為最大矩形，這種方法的復(fù)雜度是O(n2)。對(duì)于大型可重構(gòu)設(shè)備來說，H和W都比n大，因此采用文獻(xiàn)[3]的方法要優(yōu)于Brute Force方法。然而，在文獻(xiàn)[3]的方法中，采用二叉樹來管理空矩形，這對(duì)于通過刪除和插入模塊來保持更新就非常復(fù)雜，因?yàn)樵谀承┣闆r下需要改變樹的許多節(jié)點(diǎn)。因此，本文提出一種更簡(jiǎn)單和更快的方法，其復(fù)雜度為O(n)。與文獻(xiàn)[3]的方法相反，本文提出管理設(shè)備占用空間，而不是空閑空間，主要是基于設(shè)備上的空矩形集的增長(zhǎng)速度比放置組件集要快得多，因此算法將更快地使用已占用的空間來查找可以放置新組件的空閑位置集。

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

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

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

(2)

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

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

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

(3)

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

P(c)=U-I(c)

(4)

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

圖2 相對(duì)于已放置模塊的新模塊的IPR

通過集成這個(gè)邊緣和運(yùn)行任務(wù)的區(qū)域，就可以得到放置新模塊(即由這個(gè)運(yùn)行任務(wù)產(chǎn)生的)的不可能區(qū)域。然后，確定出全部運(yùn)行模塊的這些邊緣，從而得到全部已放置模塊產(chǎn)生的不可能區(qū)域；此外，可重構(gòu)設(shè)備的邊界也有兩個(gè)邊緣，顯然，當(dāng)新模塊到達(dá)以供放置時(shí)，必須重新計(jì)算每個(gè)已放置模塊的邊緣。

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

圖3 新模塊的不可能位置區(qū)域

2.2 適配器

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

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

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

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

(5)

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

(6)

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

(7)

(8)

式(7)的值是xn的函數(shù)，則為了最小化，我們必須找到這個(gè)函數(shù)對(duì)xn的偏導(dǎo)數(shù)為零的點(diǎn)，即：

(9)

(10)

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

(11)

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

顯然，最優(yōu)化的路由成本會(huì)大大降低適配器的適配時(shí)間。

圖4 接近最佳點(diǎn)的可能點(diǎn)

圖5 確定接近最佳點(diǎn)的可能點(diǎn)

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

計(jì)算最佳點(diǎn)(新組件)：

if 最佳點(diǎn)是可用的 then

把新組件放置在這個(gè)最佳點(diǎn)上

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

else

計(jì)算NPP:

1.找出所選點(diǎn)所在的邊緣外的4個(gè)接近點(diǎn)

2.插入這些點(diǎn)到最佳點(diǎn)列表中

3.從接近點(diǎn)列表中選擇最接近最佳點(diǎn)的點(diǎn)

4.if 選擇的點(diǎn)是可用的 then

把新組件放置在這個(gè)最佳點(diǎn)上

else

從接近點(diǎn)列表中刪除它,并重復(fù)NPP計(jì)算步驟

2.3 數(shù)據(jù)結(jié)構(gòu)

為了實(shí)現(xiàn)本文提出的在線放置算法，首先使用一個(gè)大小為O(n)的鏈表(n為運(yùn)行任務(wù)數(shù))來存儲(chǔ)在可重構(gòu)設(shè)備上要放置的和正在運(yùn)行的模塊。

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

算法實(shí)現(xiàn)的第三個(gè)數(shù)據(jù)結(jié)構(gòu)是一個(gè)動(dòng)態(tài)二維矩陣，它表示每對(duì)運(yùn)行模塊之間的通信帶寬，其維度大小與運(yùn)行的任務(wù)數(shù)相同。該通信矩陣用于選擇放置一個(gè)新模塊的最佳位置，因?yàn)樾枰ㄐ艑挾葋碛?jì)算并使放置新模塊的路由成本最小化。為了找到放置一個(gè)新模塊的最佳或接近最佳的點(diǎn)，使用一個(gè)鏈表來保存接近最佳的點(diǎn)，我們總是從這個(gè)列表中選擇最接近最佳點(diǎn)的點(diǎn)，而且將在上述矩陣中檢查這個(gè)點(diǎn)，看該點(diǎn)是否是可用的位置，如果是，那么就得到NPP，否則這一點(diǎn)就被一個(gè)運(yùn)行模塊或它的邊緣所占用；然后，從運(yùn)行模塊的每個(gè)邊界插入最接近的點(diǎn)到這個(gè)列表，并將所選擇的點(diǎn)移除；同樣在這個(gè)列表中，將搜索的蹤跡存儲(chǔ)起來，因?yàn)闉榱舜_保不選擇運(yùn)行模塊中的一個(gè)接近點(diǎn)(它已經(jīng)覆蓋了先前的一個(gè)選擇的接近點(diǎn))。如前所述，在最壞的情況下，我們將在這個(gè)列表中得到3n個(gè)接近的點(diǎn)，因此計(jì)算NPP的復(fù)雜度是O(n)。

3 方案性能評(píng)價(jià)

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

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

圖6 任務(wù)大小為[20,40]時(shí)不同適配方法的適配時(shí)間

圖7 任務(wù)大小為[20,30]時(shí)不同適配方法的適配時(shí)間

圖8 任務(wù)大小為[28,30]時(shí)不同適配方法的適配時(shí)間

從圖6、圖7和圖8可見，本文提出的適配器在不同大小和形狀的任務(wù)下都得到了最小的路由成本，從而有最小的適配時(shí)間，而BF適配方法得到了最大的路由成本即最大的適配時(shí)間；還可看到，在近似正方形任務(wù)的情況下，F(xiàn)F適配方法可以得到與本文方法相近的結(jié)果，但在全部情況下都比本文提出的適配器方法需要更多的適配時(shí)間；另一方面，F(xiàn)F適配方法在路由成本方面比BF適配方法要優(yōu)。而且當(dāng)采用更大的芯片尺寸時(shí)，本文提出的適配器比FF和BF表現(xiàn)更好，因?yàn)樗懈嗟目臻g來找到最佳位置。

4 結(jié)束語(yǔ)

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

關(guān)于未來的研究，我們打算開發(fā)一種框架，使得設(shè)計(jì)人員在臨時(shí)放置和通信成本的仿真方面能夠直接采用有效的模塊來實(shí)現(xiàn)；此外，還將研究本文的方案在嵌入式系統(tǒng)環(huán)境中的實(shí)現(xiàn)。