[發明專利]一種分區域的可重構硬件任務放置方法

有效

• 申請號: 201210139467.5
• 申請日: 2012-05-08
• 公開（公告）號: CN102681901A
• 公開（公告）日: 2012-09-19
• 發明（設計）人: 王濤;伍衛國;楊聰
• 申請（專利權）人: 西安交通大學
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 陸萬壽

技術領域

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

背景技術

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

發明內容

本發明的目的在于提供一種分區域的可重構硬件任務放置方法，從而降低可重構器件內布線的難度，有效提高組內硬件任務的高效管理。

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

第一步，以規模為W×H的二維可重構資源模型為基礎，W、H分別為可重構資源模型的寬度和高度，將可重構硬件任務集內的可重構硬件任務按照關聯的緊密程度分組；

第二步，將二維可重構資源模型分成若干個資源區域，資源區域與可重構硬件任務的分組一一對應；

第三步，對于可重構硬件任務集內的每個待放置可重構硬件任務，根據待放置可重構硬件任務所在的分組選擇對應的資源區域，按照資源區域的布局策略將待放置可重構硬件任務布局到資源區域，并記錄布局位置；

第四步，當可重構硬件任務執行完成后，可重構硬件任務按照結束時間依次從所在的資源區域退出，按照可重構硬件任務所在資源區域的布局策略刪除布局位置的記錄。

所述二維可重構資源模型為：構建X、Y軸組成的二維坐標系，X、Y軸最小單位為一個可重構計算單元，基于二維坐標系的可重構硬件任務T_i所需重構資源以矩形進行標識，矩形大小描述為(w_i,h_i)，其中i為正整數，w_i是可重構硬件任務T_i占用重構資源的寬度，h_i是可重構硬件任務T_i占用重構資源的高度；可重構硬件任務T_i將占據二維坐標系中一個高為h_i，寬為w_i的矩形區域，稱為任務放置區域。

所述第一步中分組的具體方法為：將可重構硬件任務集內的可重構硬件任務T_i根據任務間通信的密切程度，按照基于簇的層次敏感劃分算法分成m組，分組記為G_j，j為自然數且j≤m。

所述基于簇的層次敏感劃分算法的執行步驟為：

步驟1），采用有向無環圖表示可重構硬件任務集內的可重構硬件任務的關系，則有向無環圖中任務間有向邊的數量就表示可重構硬件任務間通信的密切程度，有向無環圖中根節點對應的可重構硬件任務稱為根節點任務，新建分組G₁作為當前分組，將有向無環圖中第一個根節點任務加入分組G₁內，同時生成就緒任務隊列Rdy，若存在多個根節點任務時，則將其余根節點任務加入就緒任務隊列Rdy中；當某一任務的直接前驅任務均已被劃分完畢時，則該任務即為就緒任務；計算組內理想任務數l=n/m，其中n為可重構硬件任務集內的可重構硬件任務總數，m為任務分組的組數，2≤m≤9；