[發(fā)明專利]一種可重構(gòu)器件片上面積管理優(yōu)化方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201710111642.2
• 申請(qǐng)日: 2017-02-28
• 公開(kāi)（公告）號(hào): CN106991009B
• 公開(kāi)（公告）日: 2020-08-11
• 發(fā)明（設(shè)計(jì)）人: 胡威;張瑜;沈歡;劉小明;張凱;劉俊;賀娟娟;王磊;馬添奧;馬榮萱
• 申請(qǐng)（專利權(quán)）人: 武漢科技大學(xué)
• 主分類號(hào): G06F9/50
• 分類號(hào): G06F9/50
• 代理公司: 杭州宇信知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 33231
• 代理人: 張宇娟

1.一種可重構(gòu)器件片上面積管理優(yōu)化方法，其特征在于，包括如下步驟：

S1、模型化可重構(gòu)器件；將可重構(gòu)器件建模為一個(gè)二維數(shù)組C(X,Y)，該二維數(shù)組C(X,Y)稱為可重構(gòu)矩陣，其中X和Y分別是可配置邏輯塊所構(gòu)成的陣列的寬度和高度，可重構(gòu)矩陣中的每一個(gè)可配置邏輯塊與二維數(shù)組C(X,Y)中的一個(gè)數(shù)組成員對(duì)應(yīng)；

S2、確定可用候選位置；使用可重構(gòu)矩陣中位于矩陣中凹角處的頂點(diǎn)作為候選位置選擇的基礎(chǔ)，基于該頂點(diǎn)構(gòu)建和維護(hù)可用候選位置列表；

S3、在新的可重構(gòu)計(jì)算任務(wù)T_j到達(dá)時(shí)，檢查所述可用候選位置列表，將可重構(gòu)計(jì)算任務(wù)T_j分配到滿足要求的區(qū)域，并更新所述可用候選位置列表，之后進(jìn)行下一步；若無(wú)滿足T_j分配要求的區(qū)域，則退出分配程序；若新的可重構(gòu)計(jì)算任務(wù)T_j的寬度屬性為w，高度屬性為h，則該可重構(gòu)計(jì)算任務(wù)T_j需要的可配置邏輯塊的數(shù)量為w*h；

當(dāng)可用候選位置列表選用左下頂點(diǎn)列表時(shí)，檢查所述可用候選位置列表具體包括：

S31a、檢查左下頂點(diǎn)列表，如果沒(méi)有未檢查過(guò)的左下頂點(diǎn)，到步驟S33a；

S32a、如果有未檢查過(guò)的左下頂點(diǎn)，取未檢查過(guò)的第一個(gè)左下頂點(diǎn)BL_k，檢查以下條件：

E_x2＝X₂-w；

E_y2＝Y(jié)₂-h；

如果E_x2和E_y2均大于或者等于0，該左下頂點(diǎn)BL_k滿足要求，將可重構(gòu)計(jì)算任務(wù)T_j分配到與該左下頂點(diǎn)BL_k鄰接的右上方區(qū)域，大小為w*h，可重構(gòu)計(jì)算任務(wù)T_j的分配完成；如果E_x2和E_y2中有一個(gè)小于0，則回到步驟S31a；

S33a、無(wú)法滿足可重構(gòu)計(jì)算任務(wù)T_j的分配任務(wù)，退出分配程序；

當(dāng)可用候選位置列表選用右下頂點(diǎn)列表時(shí)，檢查所述可用候選位置列表具體包括：

S31b、檢查右下頂點(diǎn)列表，如果沒(méi)有未檢查過(guò)的右下頂點(diǎn)，到步驟S33b；

S32b、如果有未檢查過(guò)的右下頂點(diǎn)，取未檢查過(guò)的第一個(gè)右下頂點(diǎn)BR_k，檢查以下條件：

E_x1＝X₁-w；

E_y1＝Y(jié)₁-h；

如果E_x1和E_y1均大于或者等于0，該左下頂點(diǎn)BL_k滿足要求，將可重構(gòu)計(jì)算任務(wù)T_j分配到與該右下頂點(diǎn)BL_k鄰接的左上方區(qū)域，大小為w*h，可重構(gòu)計(jì)算任務(wù)T_j的分配完成；如果E_x1和E_y1中有一個(gè)小于0，則回到步驟S31b；

S33b、無(wú)法滿足可重構(gòu)計(jì)算任務(wù)T_j的分配任務(wù)，退出分配程序；

當(dāng)可用候選位置列表選用左上頂點(diǎn)列表時(shí)，檢查所述可用候選位置列表具體包括：

S31c、檢查左上頂點(diǎn)列表，如果沒(méi)有未檢查過(guò)的左上頂點(diǎn)，到步驟S33c；

S32c、如果有未檢查過(guò)的左上頂點(diǎn)，取未檢查過(guò)的第一個(gè)左上頂點(diǎn)BR_k，檢查以下條件：

E_x4＝X₄-w；

E_y4＝Y(jié)₄-h；

如果E_x4和E_y4均大于或者等于0，該左下頂點(diǎn)BL_k滿足要求，將可重構(gòu)計(jì)算任務(wù)T_j分配到與該左上頂點(diǎn)BL_k鄰接的右下方區(qū)域，大小為w*h，可重構(gòu)計(jì)算任務(wù)T_j的分配完成；如果E_x4和E_y4中有一個(gè)小于0，則回到步驟S31c；

S33c、無(wú)法滿足可重構(gòu)計(jì)算任務(wù)T_j的分配任務(wù)，退出分配程序；

當(dāng)可用候選位置列表選用右上頂點(diǎn)列表時(shí)，檢查所述可用候選位置列表具體包括：

S31d、檢查右上頂點(diǎn)列表，如果沒(méi)有未檢查過(guò)的右上頂點(diǎn)，到步驟S33d；

S32d、如果有未檢查過(guò)的右上頂點(diǎn)，取未檢查過(guò)的第一個(gè)右上頂點(diǎn)BR_k，檢查以下條件：

E_x3＝X₃-w；

E_y3＝Y(jié)₃-h；

如果E_x3和E_y3均大于或者等于0，該左下頂點(diǎn)BL_k滿足要求，將可重構(gòu)計(jì)算任務(wù)T_j分配到與該右上頂點(diǎn)BL_k鄰接的左下方區(qū)域，大小為w*h，可重構(gòu)計(jì)算任務(wù)T_j的分配完成；如果E_x3和E_y3中有一個(gè)小于0，則回到步驟S31d；

S33d、無(wú)法滿足可重構(gòu)計(jì)算任務(wù)T_j的分配任務(wù)，退出分配程序；

S4、在可重構(gòu)計(jì)算任務(wù)T_j執(zhí)行完成后，檢查可重構(gòu)計(jì)算任務(wù)T_j所占用的每個(gè)可配置邏輯塊，并檢查可重構(gòu)矩陣中不再是可用候選位置和新產(chǎn)生的可用候選位置，更新所述可用候選位置列表，進(jìn)行下一次分配；其中更新所述可用候選位置列表具體包括：

可重構(gòu)計(jì)算任務(wù)T_j插入后，檢查可重構(gòu)計(jì)算任務(wù)T_j所占用的每個(gè)可配置邏輯塊，將可重構(gòu)計(jì)算任務(wù)T_j所占用的每個(gè)可配置邏輯塊都標(biāo)記為占用狀態(tài)；可重構(gòu)計(jì)算任務(wù)T_j執(zhí)行完成后，將可重構(gòu)計(jì)算任務(wù)T_j所占用的每個(gè)可配置邏輯塊都標(biāo)記為空閑狀態(tài)；檢查不再是可用候選位置，并將這些不再是可用候選位置對(duì)應(yīng)的頂點(diǎn)從可用候選位置列表中刪除；檢查新產(chǎn)生的可用候選位置，并將新產(chǎn)生的可用候選位置所對(duì)應(yīng)的頂點(diǎn)加入到可用候選位置列表中；更新每個(gè)可用候選位置所對(duì)應(yīng)的頂點(diǎn)的屬性；對(duì)可用候選位置列表中的頂點(diǎn)按照從上到下、從左到右的規(guī)則排序；

對(duì)于一個(gè)可用候選頂點(diǎn)V_i，有屬性V_iT(X₁,Y₁)，屬性V_iB(X₂,Y₂)，屬性V_iL(X₃,Y₃)和屬性V_iR(X₄,Y₄)，分別表示在頂點(diǎn)左上方、頂點(diǎn)右上方、頂點(diǎn)左下方和頂點(diǎn)右下方可用的可配置邏輯塊所組成的矩形的寬度和高度；如果可用候選頂點(diǎn)某個(gè)方向上沒(méi)有可用的可配置邏輯塊，則對(duì)應(yīng)的值為0；

對(duì)于右下頂點(diǎn)，只有頂點(diǎn)左上方可能存在可用的可配置邏輯塊所組成的矩形，右下頂點(diǎn)列表只維護(hù)和更新每個(gè)右下頂點(diǎn)的屬性VBR_iT(X₁,Y₁)；對(duì)于左下頂點(diǎn)，只有頂點(diǎn)右上方可能存在可用的可配置邏輯塊所組成的矩形，左下頂點(diǎn)列表只維護(hù)和更新每個(gè)左下頂點(diǎn)的屬性VBL_iB(X₂,Y₂)；對(duì)于右上頂點(diǎn)，只有頂點(diǎn)左下方可能存在可用的可配置邏輯塊所組成的矩形，右上頂點(diǎn)列表只維護(hù)和更新每個(gè)右上頂點(diǎn)的屬性VTR_iL(X₃,Y₃)；對(duì)于左上頂點(diǎn)，只有頂點(diǎn)右下方可能存在可用的可配置邏輯塊所組成的矩形，左上頂點(diǎn)列表只維護(hù)和更新每個(gè)左上頂點(diǎn)的屬性VTL_iR(X₄,Y₄)。