[發明專利]基于掃描線方法的查找FPGA芯片空白區域的方法

有效

• 申請號: 200810232214.6
• 申請日: 2008-11-10
• 公開（公告）號: CN101441679A
• 公開（公告）日: 2009-05-27
• 發明（設計）人: 段振華;肖艷;聶鵬程;范全潤
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 陜西電子工業專利中心
• 代理人: 王品華;黎漢華

技術領域

本發明屬于計算機技術領域，特別是一種查找可重構設備FPGA空白區域的方法，可用于在基于FPGA的可重構系統中查找FPGA的連續矩形區域。

背景技術

近幾年來，隨著可重構設備的進步與發展，基于可重構設備FPGA的計算機系統結構逐漸成為計算機中最流行的系統結構之一。FPGA可重構設備是由許多邏輯單元組成的門陣列，正確高效地分配該設備的區域供硬件任務進行配置是基于FPGA的可重構系統實現有效的資源共享、協同和保障性能的關鍵。當前，應用較廣的基于FPGA的可重構系統大多采用一下兩種：

1、樓梯查找方法SA。該算法是由Handa等人提出的，他們將最大空白矩形區域MER定義為不包含在其他它空白矩形區域的最大矩形區域。首先找到所有的最大樓梯，在這些樓梯中每個樓梯至少包含一個最大空白矩形區域MER；然后從這些樓梯中抽取出所有的最大空白矩形區域MER，組織成一系列的最大空白矩形區域MER，這樣方法最大缺陷就是存在重復查找問題。

2、掃描線查找方法SLA。這種算法是一種將空白區域組織成一系列MER的算法，不同于樓梯查找算法的是它并沒有查找樓梯的中間過程。

在SLA中每個硬件任務占據一個矩形區域，由四元組(x，y，w，h)表示。(x，y)是該矩形區域左下角單元的坐標，而(w，h)是該矩形用單元數來計算的寬度和高度。使用一個二維矩陣M[W+1][H]來表示該FPGA區域，如圖1。如果二維矩陣的第i行第j列的元素M[i][j]所對應的單元CLB沒有被使用，則M[i][j]為從該單元起向左所查找到的連續空白單元數，否則M[i][j]為0。關鍵單元KE是指這樣的空白單元CLB：右邊的單元CLB已被使用，或者是處于FPGA右邊界上。一條掃描線SL包含1個或多個KE，因此有1個或多個被使用的單元CLB在其右側。在SL上如果有一個單元CLB，它的上一單元的M值要大于它的M值并且其下單元的M值在一定區間內也是遞增的，那么該CLB被稱之為谷點VP。如果在該掃描線上有n個谷點，則在垂直方向上可以將其分成n+1個段。在每個段上M值最大的關鍵單元KE是一個最大關鍵單元MKE，如在圖1中，第5列是一個掃描線SL，單元(5，9)和(5，6)是谷點，掃描線上的單元(5，7)和(5，3)是最大關鍵元素MKE。

對于每個最大關鍵元素MKE，以其M值到1分別作為查找寬度w，首先在該最大關鍵元素MKE正上方向左查找寬w的連續空白區域，如果能找到這樣的區域，則繼續直到找不到這樣的空白區域或到達FPGA中的上界為止。并用top記錄當前查找的垂直坐標。然后在該最大關鍵元素MKE正下方向左查找寬w的連續空白區域，如果能找到這樣的區域，則繼續直到找不到這樣的空白區域或到達FPGA中的下界為止。并用bottom記錄當前查找的垂直坐標。這樣在top和bottom之間的寬w的空白區域被稱為一個最大空白矩形區域MER，該最大空白矩形區域MER可以用四元組表示為(i-w+1，bottom，w，top-bottom+1)。然而，當以w-1作為查找寬度后進行查找得到的空白區域的top值和bottom值都與上一次查找相同時，則該查找所得的空白區域并不是一個最大空白矩形區域MER。圖2展示了在最大關鍵元素MKE(5，3)處的查找過程。以w＝4作為查找寬度可得top＝4，bottom＝3，空白區域(2，3，4，2)，該區域不為任何矩形空白區域所覆蓋所以它是一個最大空白矩形區域MER。而以w＝3作為查找寬度可得top＝4，bottom＝3，空白區域(3，3，3，2)，該區域為上一次查找所得的最大空白矩形區域MER所包含，所以不是一個最大空白矩形區域MER。這就是一次不必要的查找，也就是掃描線方法SLA中的冗余現象。圖3展示了在最大關鍵元素MKE(5，7)處的查找過程。以w＝2作為查找寬度可得top＝8，bottom＝3，空白區域(4，3，2，6)，該區域不為任何矩形空白區域所覆蓋，所以它是一個最大空白矩形區域MER。在圖2中看到，在MKE(5，3)處以w＝2作為查找寬度同樣可得最大空白矩形區域MER(4，3，2，6)，這就是SLA中的重復現象。可見，這種掃描線方法SLA雖然查找簡單，靈活，容易實現。但是仍然存在冗余和重復查找的問題，因此使得整個查找過程的效率較低，進而影響基于FPGA可重構系統整體的性能。

發明內容

本發明的目的在于克服上述已有技術的不足，提供一種可重構系統中查找空白區域的方法，以避免查找空白區域的重復和冗余，提高可重構系統中查找空白區域的準確性。