[發(fā)明專利]NoC中基于鏈路分配的無沖突測試調(diào)度方法

有效

• 申請?zhí)枺?/td>: 201410284247.0
• 申請日: 2014-06-23
• 公開（公告）號: CN104049200A
• 公開（公告）日: 2014-09-17
• 發(fā)明（設(shè)計）人: 歐陽一鳴;楊鑫;易茂祥;梁華國;黃正峰;詹文發(fā);常郝
• 申請（專利權(quán)）人: 合肥工業(yè)大學(xué)
• 主分類號: G01R31/28
• 分類號: G01R31/28
• 代理公司: 安徽合肥華信知識產(chǎn)權(quán)代理有限公司 34112
• 代理人: 余成俊

1.一種NoC中基于鏈路分配的無沖突測試調(diào)度方法，其特征在于：操作步驟如下：

第一步：劃分區(qū)域過程

a、使用分區(qū)初始化算法對網(wǎng)絡(luò)節(jié)點進行初始化，將節(jié)點看做方塊，每個區(qū)域都可以映射為一個矩形區(qū)域，確定需要裝入矩形區(qū)域的方塊的初始大??；

b、使用改進的裝箱算法對初始化后的方塊進行調(diào)度，選取測試時間最長的核先裝入矩形區(qū)域，然后對剩下的位寬和已調(diào)度的核測試時間所構(gòu)成的另一個矩形區(qū)域，調(diào)度剩下的核盡可能將其裝滿；分配完后，每個節(jié)點屬于一個區(qū)域，各個區(qū)域并行測試；

第二步：鏈路分配過程

c、將屬于同一個區(qū)域的相鄰節(jié)點進行合并，完成后每個區(qū)域包含若干個不相鄰的子區(qū)域；

d、對每個子區(qū)域的邊界節(jié)點建立路徑樹和備選路徑集合，綜合各個節(jié)點的備選路徑集合，分配網(wǎng)絡(luò)中的鏈路資源，連通屬于同一個區(qū)域的所有子區(qū)域，并且不與其他區(qū)域的鏈路發(fā)生沖突；如果有區(qū)域無法分配到鏈路使其子區(qū)域都連通，轉(zhuǎn)到步驟e；

e、將被孤立的節(jié)點或者子區(qū)域合并到它的鄰居區(qū)域，調(diào)整網(wǎng)絡(luò)使各個區(qū)域間的測試時間平衡，使并行測試無鏈路沖突。

2.根據(jù)權(quán)利要求1所述的NoC中基于鏈路分配的無沖突測試調(diào)度方法，其特征在于：步驟b中所述的改進的裝箱算法內(nèi)容包括：給定片上網(wǎng)絡(luò)一組待測核，將其視為一組長寬不一的方塊，其中方塊長表示核的測試時間，寬表示給核用的測試位寬，有若干個矩形區(qū)域，寬為總的測試位寬，長度不限，調(diào)度方塊裝入矩形區(qū)域，使最長的矩形區(qū)域的長度最短，此長度便為整個片上網(wǎng)絡(luò)的測試時間；

首先需要對待測核集進行初始化，根據(jù)公式：T_temp＝T_i(W_max)+p/100*(T_i(1)-T_i(W_max)計算出T_temp值，公式中，p值為一個變量，變化p值可得到不同的待測核集進行調(diào)度，最后可選取使測試時間最短的p值，T_i(W_max)表示核i在測試位寬最大的情況下的測試時間，計算出T_temp后，查找離其最近的測試時間值，這個值和其所對應(yīng)的位寬即為核i的長和寬；

待測核集初始化后，整個矩形區(qū)域都是空白的，將方塊按長度排序，選取一個矩形區(qū)域后，盡可能的將這個矩形區(qū)域的空白區(qū)域給裝滿，首先查找待調(diào)度的方塊集合，在若干個矩形區(qū)域中，選取起始位置最小的矩形區(qū)域，初始時每個矩形區(qū)域的起始位置都是零，將可裝入矩形區(qū)域的最大方塊調(diào)度進去，然后對矩形區(qū)域中剩下寬度和最大方塊的起始和結(jié)束位置所組成的空白區(qū)域，調(diào)度剩下的方塊盡可能裝滿，對于空白區(qū)域，如果在未調(diào)度的方塊中查找不到可裝入空白區(qū)域的核，則對剩下的核做變形處理，以調(diào)度進去，變形過程為，順序查找剩下的方塊，降低方塊的寬度，檢測長度是否超出空白區(qū)域，如果沒超過則調(diào)度，如果超過則順序查找下面的方塊，循環(huán)此過程，直到所有方塊都被調(diào)度進去。

3.根據(jù)權(quán)利要求1所述的NoC中基于鏈路分配的無沖突測試調(diào)度方法，其特征在于：步驟d中所述的的對每個子區(qū)域邊界節(jié)點建立節(jié)點路徑樹和備選路徑集合的內(nèi)容包括：對待合并部分中每個區(qū)域的邊界節(jié)點，以邊界節(jié)點為根節(jié)點，如果根節(jié)點某個方向鏈路未被占用，則將此鏈路作為一個分支加入到路徑樹中；接著探索此鏈路相連的鄰接節(jié)點是否有空閑鏈路，如果有，則繼續(xù)建立分支，直到樹的深度達到最大值；如果沒有，則結(jié)束此方向探索，搜索路徑樹，查找可以將與根節(jié)點屬于同一區(qū)域的子區(qū)域連通的路徑，加入到根節(jié)點的備選路徑集合中，重復(fù)查找，直到所有路徑都遍歷完全。