[發(fā)明專利]基于掃描線方法的查找FPGA芯片空白區(qū)域的方法

有效

• 申請?zhí)枺?/td>: 200810232214.6
• 申請日: 2008-11-10
• 公開（公告）號: CN101441679A
• 公開（公告）日: 2009-05-27
• 發(fā)明（設(shè)計）人: 段振華;肖艷;聶鵬程;范全潤
• 申請（專利權(quán)）人: 西安電子科技大學(xué)
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 陜西電子工業(yè)專利中心
• 代理人: 王品華;黎漢華

1.一種基于掃描線方法的查找FPGA芯片空白區(qū)域的方法，包括如下步驟：

(1)將當(dāng)前向上查找的縱坐標(biāo)top和當(dāng)前向下查找的縱坐標(biāo)bottom初始化為給定最大關(guān)鍵元素MKE(i，j)的縱坐標(biāo)j，并將最大空白矩形區(qū)域集SMER初始化為空集；

(2)調(diào)用確定有效查找寬度集的方法，并將返回的結(jié)果賦給有效查找寬度集SVSW；

(3)判斷有效查找寬度集SVSW是否為非空集，如果有效查找寬度集SVSW不為空，則執(zhí)行(4)，否則，返回最大空白矩形區(qū)域集SMER，并結(jié)束執(zhí)行；

(4)從有效查找寬度集SVSW中選取一個有效查找寬度w；

(5)通過檢查查找標(biāo)記SWEAP[w][top+1]的值是否為1判斷最大關(guān)鍵元素MKE(i，j)是否被同一掃描線SL的其它最大空白矩形區(qū)域MER以查找寬度w查找過，如果是，則執(zhí)行(11)，否則，執(zhí)行(6)；

(6)判斷top所在行是否已經(jīng)到達FPGA中的上界，如果到達上界，則執(zhí)行(8)，否則判斷是否能在單元(i-w+1，top)與單元(i，top)之間找到寬度為w的空白區(qū)域，如果能找到，則執(zhí)行(7)，否則，執(zhí)行(8)；

(7)更新當(dāng)前向上查找的縱坐標(biāo)top為top+1，并通過將查找標(biāo)記SWEAP[w][top+1]設(shè)定為1標(biāo)記單元(i，top+1)已被某最大空白矩形區(qū)域MER以查找寬度w掃描過，返回執(zhí)行(6)；

(8)判斷bottom所在行是否已經(jīng)到達FPGA中的下界，如果到達下界，則執(zhí)行(10)，否則判斷是否能在單元(i-w+1，bottom)與單元(i，bottom)之間找到寬度為w的空白區(qū)域，如果能找到，則執(zhí)行(9)，否則，執(zhí)行(10)；

(9)更新當(dāng)前向下查找的縱坐標(biāo)bottom為bottom-1，并通過將查找標(biāo)記SWEAP[w][bottom-1]設(shè)定為1標(biāo)記單元(i，bottom-1)已被某最大空白矩形區(qū)域MER以查找寬度w掃描過，返回執(zhí)行(8)；

(10)將最大空白矩形區(qū)域MER(i-w+1，bottom，w，top-bottom+1)添加到最大空白矩形區(qū)域集SMER中；

(11)將本次查找所使用的有效查找寬度w從有效寬度集SVSW中去掉，再返回執(zhí)行(3)。?

2.根據(jù)權(quán)利要求1所述的查找FPGA芯片空白區(qū)域的方法，其中步驟(2)所述的調(diào)用確定有效查找寬度集SVSW的方法，按如下步驟進行：

1)將當(dāng)前向上查找的縱坐標(biāo)top和當(dāng)前向下查找的縱坐標(biāo)bottom初始化為給定單元(i，j)的縱坐標(biāo)j，并將有效查找寬度集SVSW初始化為空集；

2)給定FPGA單元(i，j)，并從該單元向左查找，將所得到的連續(xù)空白單元數(shù)M[i][j]作為有效查找寬度w，加入到有效查找寬度集SVSW中；

3)將向上查找到的當(dāng)前有效查找寬度topw和向下查找到的當(dāng)前有效查找寬度botw初始化為從給定單元(i，j)起向左所查找到的連續(xù)空白單元數(shù)M[i][j]；

4)判斷當(dāng)前向上查找的縱坐標(biāo)top所在行是否已經(jīng)到達上界，如果是，則執(zhí)行9)，否則，執(zhí)行5)；

5)判斷從單元(i，top+1)起向左查找到的連續(xù)空白單元數(shù)M[i][top+1]是否比向上查找到的當(dāng)前有效查找寬度topw小，如果是，則執(zhí)行6)，否則，執(zhí)行8)；

6)判斷單元(i，top+1)是不是已經(jīng)被使用，如果是，則執(zhí)行9)，否則執(zhí)行7)；

7)將從單元(i，top+1)起向左查找到的連續(xù)空白單元數(shù)M[i][top+1]添加到有效查找寬度集SV?SW中，并更新向上查找到的當(dāng)前有效查找寬度topw為M[i][top+1]；

8)更新當(dāng)前向上查找的縱坐標(biāo)top為top+1，返回執(zhí)行4)；

9)判斷當(dāng)前向下查找的縱坐標(biāo)bottom所在行是否已經(jīng)到達下界，如果是，返回有效查找寬度集SVSW，并結(jié)束執(zhí)行，否則，執(zhí)行10)；

10)判斷從單元(i，bottom-1)起向左查找到的連續(xù)空白單元數(shù)M[i][bottom-1]是否比向下查找到的當(dāng)前有效查找寬度botw小，如果是，則執(zhí)行11)，否則，執(zhí)行13)；

11)判斷單元(i，bottom-1)是不是已經(jīng)被使用，如果是，則返回有效查找寬度集SVSW，并結(jié)束執(zhí)行，否則，執(zhí)行12)；

12)將從單元(i，bottom-1)起向左查找到的連續(xù)空白單元數(shù)M[i][bottom-1]添加到有效查找寬度集SV?SW中，并更新向下查找到的當(dāng)前有效查找寬度botw為M[i][bottom-1]；

13)更新當(dāng)前向下查找的縱坐標(biāo)bottom為bottom-1，返回執(zhí)行9)。?