綜合時間因素和空間因素的fpga任務放置方法

2023-07-05 10:59:06 3

專利名稱：綜合時間因素和空間因素的fpga任務放置方法
技術領域：
本發明涉及一種綜合時間因素和空間因素的FPGA任務放置方法，更具體的說，通過綜合考慮任務的到達時刻、執行時間和任務與空閒塊的空間匹配，設代價函數為任務選擇合適的放置位置。
背景技術：
FPGA由可重構資源構成，具有動態局部可重構特性。FPGA及在FPGA上執行的任務可以被抽象成具有一定長度和寬度的矩陣，矩陣中的每個元素即是代表一個可重構單元。每個任務均具有兩個時間屬性，即，到達FPGA的時刻(簡稱到達時刻)和在FPGA內 開始執行的時間(簡稱執行時間)。任務在FPGA內執行過程包括三步首先，CPU為任務在FPGA內選擇一塊與其空間大小相同的可重構資源塊，即任務放置；其次，CPU將該任務調度到該空閒塊開始執行，SP任務執行；最後，任務執行完成後退出FPGA，FPGA重構該任務佔用的可重構單元，使其變成空閒狀態，即任務退出。FPGA具有動態局部可重構的特性能夠保證多個任務可以佔用FPGA內不同的可重構單元塊並行執行而不相互幹擾。合適的任務放置方法能夠充分利用FPGA內的空閒空間，使得多個任務能夠在FPGA內並行執行，從而有效提高FPGA的利用率，縮短任務隊列的完成時間。目前在FPGA上常用的任務放置方法是first fit與best fit，它們均用鍊表記錄FPGA內的空閒塊，當有任務要執行時查找不小於其矩陣規模的空閒塊作為其放置位置。first fit選擇其查找到的第一個滿足條件的空閒塊，該方法效率較高，但會使得FPGA產生大量碎片空間，故導致FPGA利用率較差。best fit將遍歷所有空閒塊，將滿足下列條件的空閒矩陣作為任務的放置位置即，該空閒矩陣的周長或面積不小於空閒塊，且相比較於其他空閒塊，該空閒塊與任務塊的周長或面積的差值是最小的。相比於first fit, best fit能夠有效提高FPGA利用率。

發明內容
本發明的目的在於，針對以上背景技術中提出的問題，提供一種綜合時間因素和空間因素的FPGA任務放置方法為任務選擇最佳放置位置，提高FPGA的空間利用率。為達到上述目的，本發明的構思是根據⑴碎片度越小，任務放置越緊湊，則空間利用率越高；(2)FPGA內相鄰任務在空間和時間上的重疊度越高，碎片就越小，任務就越緊湊。本發明綜合考慮了任務與空間塊在時間上和空間上的重疊長度，使得任務緊湊地放置在FPGA內，從而減少FPGA內的碎片空間，提高了 FPGA的空間利用率。根據上述發明構思，本發明採用下述技術方案
一種綜合時間因素和空間因素的FPGA任務放置方法，其特徵在於操作步驟如下首先將FPGA及在FPGA上執行的任務抽象成具有一定長度和寬度的矩形塊。然後對每個新到達的任務均記錄兩個時間屬性到達FPGA的時刻和在FPGA內執行的時間。最後，通過綜合考慮任務的到達時刻、執行時間和任務與空閒塊的空間匹配，設計代價函數為任務選擇合適的放置位置。本發明所述的代價函數的表達式定義為
權利要求
1.一種綜合時間因素和空間因素的FPGA任務放置方法，其特徵在於操作步驟為首先將FPGA及在FPGA上執行的任務抽象成具有一定長度和寬度的矩形塊；然後對每個新到達的任務均記錄兩個時間屬性到達FPGA的時刻——簡稱到達時刻和在FPGA內執行的時間簡稱執行時間；最後，通過綜合考慮任務的到達時刻、執行時間和任務與空閒塊的空間匹配，設計代價函數為任務選擇合適的放置位置。
2.根據權利要求I所述的代價函數，其特徵在於所述的代價函數應該考慮到以下幾個因素的影響(I)空間上，新到任務與放置位置的相鄰任務鄰接邊的重疊長度；(2)時間上，新到任務與放置位置的相鄰任務執行時間的重疊度。
3.根據權利要求2所述的影響因子，其特徵在於，所述的代價函數的表達式定義為/C = F (0E; X OtJ /ecs, + e, > present_moment + ecOt =|If1 X ess. -f e5 = Co Xk2 X (S1 4- - pres戀ntjnoment) Si + ^ < presint_moTOerit -r ec 其中 If2 k± X 即保證情況I的代價函數值大於情況2的代價函數值；而1^2的設定是為了使U1X ec> k2 X (S1 + Si- present_moment),即保證情況3的代價函數值小於情況2與情況I的代價函數值。
4.根據權利要求3所述的綜合時間因素和空間因素的FPGA任務放置方法，其特徵在於所述代價函數求法按如下步驟 (I).比較新到任務的完成時刻(當前時刻present_moment加上新到任務的執行時間)與第i個任務的完成時刻(第i個任務的實際開始時刻&加上該任務的執行時間)；若前者大，則跳轉至步驟(2);若後者大，則跳轉至步驟(3);若一樣大，則跳轉至步驟(4)；(2).求出重疊長度％,重疊度&為％乘以常數fc2,跳至步驟(5)； I*s (3).求出重疊長度OGi,重疊度Ots為新到任務的執行時間，跳至步驟(5)； (4).求出重疊長度(jg,重疊度a為新到任務的執行時間乘以常數乘以Jk1，跳至步驟(5)； (5).由公式
全文摘要
本發明公開了一種綜合時間因素和空間因素的FPGA任務放置方法。本發明首先將FPGA及在FPGA上執行的任務抽象成具有一定長度和寬度的矩形塊。然後對每個新到達的任務均記錄兩個時間屬性，即，到達FPGA的時刻(簡稱到達時刻)、在FPGA內執行的時間(簡稱執行時間)。最後，通過綜合考慮任務的到達時刻、執行時間和任務與空閒塊的空間匹配，設計代價函數為任務選擇合適的放置位置。本發明綜合考慮了任務與空閒塊在空間上和時間上的重疊長度，使得任務緊湊地放置在FPGA內，從而減少了FPGA內的空閒碎片空間，提高了FPGA的空間利用率。
文檔編號G06F17/50GK102760187SQ201210201498
公開日2012年10月31日 申請日期2012年6月19日 優先權日2012年6月19日
發明者張雋豐, 陳雪, 高英虎 申請人:上海大學