[發明專利]一種基于任務長寬比的可重構硬件任務放置方法

無效

• 申請號: 201210066089.2
• 申請日: 2012-03-14
• 公開（公告）號: CN102629218A
• 公開（公告）日: 2012-08-08
• 發明（設計）人: 王濤;伍衛國;章慶
• 申請（專利權）人: 西安交通大學
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 西安智大知識產權代理事務所 61215
• 代理人: 賀建斌

技術領域

本發明屬于計算機技術領域，具體涉及一種基于任務長寬比的可重構硬件任務放置方法。

背景技術

在可重構計算系統中，可重構資源通常抽象為一維和二維兩種模型，在二維可重構資源模型中，計算資源以二維陣列的方式劃分和組織，重構的最小單位為二維陣列中的一個矩形單元，一個可重構硬件任務占用陣列中的一個矩形區域，多個任務通過調度的方式在可重構硬件中進行布局，由于每個任務在資源空間中的放置具有二維自由度，因此常采用空閑區域掃描和狀態矩陣記錄這兩種方法為待調度的任務查找合適的布局位置。空閑區域掃描方法主要是通過記錄空閑區域來對資源進行描述，其中最重要的是最大空閑矩形法MER(Maximal?Empty?Rectangle)，MER方法記錄一個互不交疊的空閑資源矩形列表，通過查找匹配的空閑資源矩形獲得待調度硬件任務的放置位置，該方法需要對資源矩形列表進行維護，并且任務調度時查找匹配空閑資源的復雜度相對較高；狀態矩陣記錄方法通過維護一個記錄可重構計算單元(Reconfigurable?Computing?Unit)狀態的矩陣來管理資源，并通過掃描狀態矩陣查找待調度硬件任務的可放置位置，此方法需掃描和查找狀態矩陣，花費時間相對較長。在任務布局時采用的放置策略常用的有兩種，一種為首次適合放置方法(First?Fit)，另一種是最佳放置方法(Best?Fit)，這兩種放置方法均沒有考慮二維器件模型和硬件任務的規模信息，因此在負載率較高和硬件任務規模相對一致的情況下，任務調度成功率不高。

發明內容

為了克服上述現有技術中存在的問題，本發明的目的在于提供一種基于任務長寬比的可重構硬件任務放置方法，在二維可重構資源模型的基礎上，利用二維器件模型的規模信息，再通過引入可重構硬件任務長寬比的信息對可重構硬件任務進行布局，以降低任務間競爭資源而引起沖突的概率，提高任務調度成功率。

為了達到上述目的，本發明所采用的技術方案是：

一種基于任務長寬比的可重構硬件任務放置方法，包括以下步驟：

第一步，在規模為W×H的二維可重構資源模型基礎上，構建X、Y軸組成的二維坐標系，X、Y軸的最小單位為一個可重構計算單元，基于二維坐標系的可重構硬件任務T_i所需重構資源以矩形進行標識，矩形大小描述為：T_i＝(w_i，h_i)，其中i為正整數，w_i是任務T_i占用資源的寬度，h_i是任務T_i占用資源的高度；任務T_i將占據二維坐標系中一個高為h_i，寬為w_i的矩形區域，稱為任務放置區域，第一個任務T₁的放置區域左下角坐標為(0，0)，則任務T₁的放置位置可表示為：【(0，0)，(w₁，h₁)】；

第二步，可重構硬件任務布局時，根據待放置任務的長寬比確定任務布局方向，如式(1)所示：

decisionV(wi,hi)=1,wi≥hi0,Other---(1)]]>

其中w_i、h_i為待放置的可重構硬件任務的寬和高，