• / 15
  • 下載費用:30 金幣  

FPGA動態部分可重構區域的配置方法.pdf

關 鍵 詞:
FPGA 動態 部分 可重構 區域 配置 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
摘要
申請專利號:

CN201310693431.6

申請日:

2013.12.17

公開號:

CN103677837A

公開日:

2014.03.26

當前法律狀態:

駁回

有效性:

無權

法律詳情: 發明專利申請公布后的駁回IPC(主分類):G06F 9/44申請公布日:20140326|||實質審查的生效IPC(主分類):G06F 9/44申請日:20131217|||公開
IPC分類號: G06F9/44 主分類號: G06F9/44
申請人: 清華大學
發明人: 馬昱春; 何瑞寧; 張超
地址: 100084 北京市海淀區100084-82信箱
優先權:
專利代理機構: 北京清亦華知識產權代理事務所(普通合伙) 11201 代理人: 張大威
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201310693431.6

授權公告號:

||||||

法律狀態公告日:

2017.09.26|||2014.04.23|||2014.03.26

法律狀態類型:

發明專利申請公布后的駁回|||實質審查的生效|||公開

摘要

本發明提出一種FPGA動態部分可重構區域的配置方法,包括以下步驟:根據多個功能模塊的運行信息生成執行表;根據執行表生成多個功能模塊的互斥圖;根據互斥圖生成交集圖;計算多個交集圖節點的權值,并將滿足非并發約束的交集節點組合成多組候選重構集;計算每組候選重構集的權值之和以及占用面積與未在候選重構集中的功能模塊的占用面積之和;將權值之和最大且占用面積小于調度區間總面積的候選重構集所對應的功能模塊配置到FPGA動態部分可重構區域。根據本發明實施例的方法,通過計算交集圖節點的權值最優且占用面積滿足條件的功能模塊配置到重構區域,可有效地利用片上的資源,降低重構時延,提高可重構系統的處理速度和效率。

權利要求書

權利要求書
1.  一種FPGA動態部分可重構區域的配置方法,其特征在于,包括以下步驟:
執行表生成步驟,根據調度區間中多個功能模塊的運行信息,生成表示所述調度區間的每個時間片上的功能模塊運行狀態的執行表;
互斥圖生成步驟,根據所述執行表生成所述多個功能模塊的互斥圖,所述互斥圖描述所述多個功能模塊在時間上的非并發關系;
交集圖生成步驟,根據所述多個功能模塊在時間上的非并發關系,選取滿足非并發約束的多個功能模塊的集合作為交集圖節點,生成交集圖;
候選重構集組合步驟,計算多個交集圖節點的權值,并將所述多個交集圖節點中滿足非并發約束的交集節點組合成多組候選重構集;
權值計算步驟,計算每組所述候選重構集的權值之和;
面積計算步驟,計算每組所述候選重構集的占用面積與未在所述候選重構集中的功能模塊的占用面積之和;
可重構模塊確定步驟,按照所述權值之和最大且所述占用面積小于所述調度區間總面積的方式確定候選重構集,將對應的功能模塊配置到所述FPGA動態部分可重構區域。

2.  如權利要求1所述的FPGA動態部分可重構區域的配置方法,其特征在于,所述交集圖生成步驟中,所選取的滿足非并發約束的多個功能模塊的集合中,如果其中包含的多個功能模塊之間的資源請求差異超過了預設的閾值,則不選取為交集圖節點。

3.  如權利要求1所述的FPGA動態部分可重構區域的配置方法,所述候選重構集組合步驟具體為,
在所述多個交集圖節點中選取滿足所述非并發約束的至少兩個交集圖節點構成一組候選重構集,通過對所述多個交集圖節點中滿足所述非并發約束的所有交集圖節點進行組合得到所述多組候選重構集。

4.  如權利要求1所述的FPGA動態部分可重構區域的配置方法,其特征在于,所述權值計算步驟具體包括:
計算所述每組候選重構集中所述交集圖節點的配置幀數量;
根據所述配置幀數量和配置端口的最大帶寬分別得到所述每組候選重構集中對應交集圖節點的權值;以及
將對應候選重構集中的多個交集圖節點的權值相加得到所述每組候選重構集的權值之和。

5.  如權利要求4所述的FPGA動態部分可重構區域的配置方法,其特征在于,所述 配置幀數量通過如下公式獲得,所述公式為,
cfi=Σk=1num_types(areak×max_demandkarea_RF×uk),]]>
其中,cfi為交集圖中節點i(也是候選重構集中的節點i)的配置幀數量,num_types為該節點中對應的功能模塊所用的資源種類數目,areak為資源k對應的面積,max_demandk為在該功能模塊中用到資源k的最大數目,area_RF為每個可重構配置幀的面積,uk表示第k種資源構成的一個RF所對應的CF的個數。

6.  如權利要求4所述的FPGA動態部分可重構區域的配置方法,其特征在于,所述每個交集圖節點的權值通過如下公式獲得,所述公式為,
RD_PRRj=cfj×Wf/Rs,
其中,RD_PRRj為交集圖中節點i的權值,cfj為交集圖中節點i的配置幀數量,Wf為每個配置幀的大小,Rs為配置端口的最大帶寬。

7.  如權利要求1所述的FPGA動態部分可重構區域的配置方法,其特征在于,所述候選重構集對應方案的占用面積通過如下公式獲得,所述公式為,
area_total=μ×Σjarea_SMj+areaPRR,]]>
其中,area_total為所述候選重構集對應的方案的占用面積,μ為放大因子,area_SMj為每個靜態模塊的占用面積,areaPRR為所有動態模塊的占用面積之和。

說明書

說明書FPGA動態部分可重構區域的配置方法
技術領域
本發明涉及現場可編程門陣列技術領域,特別涉及一種FPGA動態部分可重構區域的配置方法。
背景技術
現場可編程門陣列(Field Programmable Gate Array,FPGA)技術具有現場編程(On-site Programming)和可重編程(Re-programming)的靈活性,它通過加載完整的配置文件實現對芯片整體功能的重構,使得在保證芯片運行速度的基礎上避免了舊芯片的浪費。
當前主流動態重構設計已完成了邏輯綜合,并且隨著物理網表文件的生成,系統模塊的詳細調度也可相應的確定。由于動態模塊是以分時的形式共享重構區域,使共享動態區域的幾個動態模塊在運行時間上不能有重疊。如果產生重疊,一旦系統運行到需要分時共享一個動態區域的多個動態模塊同時運行的時候,必然存在不能被及時裝入芯片的動態模塊,系統也就不能夠正確地執行下去。另外,也有部分學者提出將同時完成劃分、調度以及任務在可重構區域上的線性(Linear)布局。這種方式是在每個任務需要占據若干片上完整的資源列的條件下成立,然而隨著動態部分可重構技術的發展已不滿足該條件。
發明內容
本發明的目的旨在至少解決上述的技術缺陷之一。
為此,本發明需要提供一種FPGA動態部分可重構區域的配置方法。該配置方法可以解決功能模塊在時間片上的不能疊加且數據處理速度和效率低的問題。
有鑒于此,本發明的實施例提出一種FPGA動態部分可重構區域的配置方法,包括以下步驟:執行表生成步驟,根據調度區間中多個功能模塊的運行信息,生成表示所述調度區間的每個時間片上的功能模塊運行狀態的執行表;互斥圖生成步驟,根據所述執行表生成所述多個功能模塊的互斥圖,所述互斥圖描述所述多個功能模塊在時間上的非并發關系;交集圖生成步驟,根據所述多個功能模塊在時間上的非并發關系,選取滿足非并發約束的多個功能模塊的集合作為交集圖節點,生成交集圖;候選重構集組合步驟,計算多個交集圖節點的權值,并將所述多個交集圖節點中滿足非并發約束的交集節點組合成多組候選重構集;權值計算步驟,計算每組所述候選重構集的權值之和;面積計算 步驟,計算每組所述候選重構集的占用面積與未在候選重構集中的功能模塊的占用面積之和;可重構模塊確定步驟,按照所述權值之和最大且所述占用面積小于所述調度區間總面積的方式確定候選重構集,將對應的功能模塊配置到所述FPGA動態部分可重構區域。
根據本發明實施例的方法,通過計算交集圖節點的重構權值最大且占用面積滿足條件的功能模塊配置到重構區域,可有效地利用片上的資源,降低重構時延,提高可重構系統的處理速度和效率。
在本發明的一個實施例中,所述交集圖生成步驟中,所選取的滿足非并發約束的多個功能模塊的集合中,如果其中包含的多個功能模塊之間的資源請求差異超過了預設的閾值,則不選取為交集圖節點。
在本發明的一個實施例中,所述候選重構集組合步驟具體為,在所述多個交集圖節點中選取滿足所述非并發約束的至少兩個交集圖節點構成一組候選重構集,通過對所述多個交集圖節點中滿足所述非并發約束的所有交集圖節點進行組合得到所述多組候選重構集。
在本發明的一個實施例中,所述權值計算步驟具體包括:計算所述每組候選重構集中所述交集圖節點的配置幀數量;根據所述配置幀數量和配置端口的最大帶寬分別得到所述每組候選重構集中對應交集圖節點的權值;以及將對應候選重構集中的多個交集圖節點的權值相加得到所述每組候選重構集的權值之和。
在本發明的一個實施例中,所述配置幀數量通過如下公式獲得,所述公式為,其中,cfi為交集圖中節點i(也是候選重構集中的節點i)的配置幀數量,num_types為該節點中對應的功能模塊所用的資源種類數目,areak為資源k對應的面積,max_demandk為在該功能模塊中用到資源k的最大數目,area_RF為每個可重構配置幀的面積,uk表示第k種資源構成的一個RF所對應的CF的個數。在本發明的一個實施例中,所述每個交集圖節點的權值通過如下公式獲得,所述公式為,RD_PRRj=cfj×Wf/Rs,其中,RD_PRRj為交集圖中節點i的權值,cfj為交集圖中節點i的配置幀數量,Wf為每個配置幀的大小,Rs為配置端口的最大帶寬。
在本發明的一個實施例中,所述候選重構集對應方案的占用面積通過如下公式獲得,所述公式為,area_total=μ×Σjarea_SMj+areaPRR,]]>其中,area_total為所述候選重構集對應方案占用芯片的面積,μ為放大因子,area_SMj為每個靜態模塊的占用面積,areaPRR為所有動態模塊的占用面積之和。
本發明附加的方面和優點將在下面的描述中部分給出,部分將從下面的描述中變得 明顯,或通過本發明的實踐了解到。
附圖說明
本發明上述的和/或附加的方面和優點從下面結合附圖對實施例的描述中將變得明顯和容易理解,其中:
圖1為根據本發明一個實施例的FPGA動態部分可重構區域的配置方法的流程圖;
圖2為根據本發明一個實施例的調度區間圖;
圖3為根據本發明一個實施例的執行表;
圖4為根據本發明一個實施例的互斥圖;
圖5為根據本發明一個實施例的交集圖;
圖6為根據本發明一個實施例的候選重構集;
圖7為根據本發明一個實施例的面積計算的示意圖;以及
圖8為根據本發明一個實施例的方法與硬件相結合的設計流程圖。
具體實施方式
下面詳細描述本發明的實施例,實施例的示例在附圖中示出,其中自始至終相同或類似的標號表示相同或類似的元件或具有相同或類似功能的元件。下面通過參考附圖描述的實施例是示例性的,僅用于解釋本發明,而不能理解為對本發明的限制。
在本發明的描述中,需要理解的是,術語“中心”、“縱向”、“橫向”、“上”、“下”、“前”、“后”、“左”、“右”、“豎直”、“水平”、“頂”、“底”、“內”、“外”等指示的方位或位置關系為基于附圖所示的方位或位置關系,僅是為了便于描述本發明和簡化描述,而不是指示或暗示所指的裝置或元件必須具有特定的方位、以特定的方位構造和操作,因此不能理解為對本發明的限制。此外,術語“第一”、“第二”僅用于描述目的,而不能理解為指示或暗示相對重要性。
在本發明的描述中,需要說明的是,除非另有明確的規定和限定,術語“安裝”、“相連”、“連接”應做廣義理解,例如,可以是固定連接,也可以是可拆卸連接,或一體地連接;可以是機械連接,也可以是電連接;可以是直接相連,也可以通過中間媒介間接相連,可以是兩個元件內部的連通。對于本領域的普通技術人員而言,可以具體情況理解上述術語在本發明中的具體含義。
圖1為根據本發明一個實施例的FPGA動態部分可重構區域的配置方法的流程圖。如圖1所示,根據本發明實施例的FPGA動態部分可重構區域的配置方法包括以下步驟:根據調度區間中多個功能模塊的運行信息,生成表示調度區間的每個時間片上的功能模 塊運行狀態的執行表(步驟101)。根據執行表生成多個功能模塊的互斥圖,互斥圖描述多個功能模塊在時間上的非并發關系(步驟102)。根據多個功能模塊在時間上的非并發關系,選取滿足非并發約束的多個功能模塊的集合作為交集圖節點,生成交集圖(步驟103)。計算多個交集圖節點的權值,并將多個交集圖節點中滿足非并發約束的交集節點組合成多組候選重構集(步驟104)。計算每組候選重構集的權值之和(步驟105)。計算每組候選重構集的占用面積與未在候選重構集中的功能模塊的占用面積之和(步驟106)。按照權值之和最大且占用面積小于調度區間總面積的方式確定候選重構集,將對應的功能模塊配置到FPGA動態部分可重構區域(步驟107)。
根據本發明實施例的方法,通過計算交集圖節點的重構權值最大且占用面積滿足條件的功能模塊配置到重構區域,可有效地利用片上的資源,降低重構時延,提高可重構系統的處理速度和效率。
下面將結合圖2-8對本發明進行詳細說明。
在步驟101中,根據任務數據、模塊信息,以及描述硬件模塊調度的調度區間圖等運行信息統計調度區間圖上每個分片處于活動狀態的所有模塊生成每個時間片上的功能模塊運行狀態的執行表。該執行表的第一列為時間分片,第二列為在該時間分片內運行的模塊。
在步驟102中,將每個模塊為一個結點。如果兩個模塊出現在執行表的同一行,則把對應的兩個結點連接。通過對每個時間片上的對應模塊均采用該方式進行相連,以生成互斥圖。該互斥圖可以表示調度區間內的模塊在時間片上的并發關系,即如果兩個模塊有連線,則表示該兩個模塊同時發生。
在步驟103中,所選取的滿足非并發約束的多個功能模塊的集合中,如果其中包含的多個功能模塊之間的資源請求差異超過了預設的閾值例如三分之二,則不選取為交集圖節點。將剩余的多個模塊的每個集合作為交集圖節點。如果兩個交集圖節點之間有交集,則用一條線將該兩個交集圖節點相連。通過對多個模塊的集合進行相應處理可生成交集圖。
在步驟104中,在多個交集圖節點中選取滿足非并發約束的至少兩個交集圖節點構成一組候選重構集,通過對多個交集圖節點中滿足非并發約束的所有交集圖節點進行組合得到多組候選重構集。
在步驟105中,計算每組候選重構集中交集圖節點的配置幀數量。該配置幀數量通過如下公式獲得,公式為,cfi=Σk=1num_types(areak×max_demandkarea_RF×uk)]]>-公式1,其中,cfi為交集圖中節點i(也是候選重構集中的節點i)的配置幀數量,num_types為該節點中對應的功能模塊所用的資源種類數目,areak為資源k對應的面積,max_demandk為在該功能模塊中用到資源k的最大數目,area_RF為每個可重構配置幀的面積,其大小依賴于具體 的芯片型號,uk表示第k種資源構成的一個RF所對應的CF的個數,其數值也由具體的FPGA芯片型號確定。然后,根據配置幀數量和配置端口的最大帶寬分別得到每組候選重構集中對應交集圖節點的權值。每個交集圖節點的權值通過如下公式獲得,公式為,RD_PRRj=cfj×Wf/Rs-公式2,其中,RD_PRRj為交集圖中節點i的權值,cfj為交集圖中節點i的配置幀數量,Wf為每個配置幀的大小,Rs為配置端口的最大帶寬。計算RD_PRRj,即切換點j對應的重構區域完成一次切換所需的時延。Xilinx根據配置端口的最大帶寬和重構包含的配置幀(Configuration Frame,CF)數來估算重構時延,對時延取反即為權值。之后,將對應候選重構集中的多個交集圖節點的權值相加得到每組候選重構集的權值之和。
在步驟106中,首先計算動態模塊占用的面積之和,通過如下公式獲得,其中,μ為放大因子,通過放大因子μ彌補由于芯片上資源分布的不均勻所帶來的面積低估,area_PRRj為候選重構集中節點j對應的占用面積。
將候選重構集所對應的功能模塊的占用面積和靜態模塊的占用面積相加可得到整個調度區域的總面積,該總面積通過如下公式獲得,-公式4,其中,area_total為候選重構集對應的方案占用芯片的面積,μ為放大因子,area_SMj為每個靜態模塊的占用面積,areaPRR為所有動態模塊的占用面積之和。
由于靜態模塊和功能模塊都要占用調度區域的面積因此需要滿足如下關系,area_total≤area_FPGA,即靜態模塊和功能模塊的占用總面積要小于該調度區域的總面積。
在步驟107中,通過步驟105和步驟106的方式得到每組候選重構集的權值之和和占用面積之和。并將權值之和最大且占用面積小于調度區域總面積的候選重構集的功能模塊配置到FPGA動態部分可重構區域。
實施例1
通過如圖2所示的調度區間圖和任務信息等運行信息所獲得的執行表如圖3所示。圖3的時間分片1中,模塊A、C、E都在執行,則得到表的第一行。依此類推得到執行表。對于執行表的每一行,在互斥圖上完成活動模塊間的兩兩連接生成互斥圖。例如根據執行表的第一行,模塊A、C、E同時執行,說明它們不滿足非并發約束,也就是說不能進行重構,于是在結點A、C、E之間互相連線。以此類推,得到如圖4所示的互斥圖。對圖4的互斥圖中選取滿足非并發約束的多個功能模塊的集合可以得到包括{A,B},{B,C},{C,D}三個交集節點的交集圖,該交集圖如圖5所示。
去除其中包含的多個功能模塊之間的資源請求差異超過了預設的閾值例如三分之 二的剩余交集圖節點生成交集圖,比如{A,B}對應結點1,{B,C}對應結點2,{C,D}對應結點3。邊則表示其連接的兩個獨立集之間含有交集,比如結點1和結點2有交集{B},則在兩個結點之間連一條邊得到候選重構集如圖6所示。
通過將動態區域PR Region PRRj內的資源的數量和對應的配置幀想成累加得到每個功能模塊的配置幀。
假設動態區域1內包含功能模塊A,B,其數據需求如下表1所示:

表1
通過公式1得到該動態區域需要的配置幀數目為12+2+4=18個。
假設需要18個配置幀,假設Wf為1000bits,Rs為1MB/s,則根據公式2得到延時(即權值)為0.018s。候選重構集1的權值為0.018。
通過表1和公式4得到每個動態區域中功能模塊的占用面積。每個動態區域中功能模塊的占用面積和權值如表2所示。

表2
從表2中可知,候選重構集1的權值為-0.018,選重構集1的權值為-0.024,候選重構集13的權值為-0.009。約束為選取的獨立結點使用的面積加上靜態模塊的面積小于100,將尋找盡可能多的獨立結點,使得權值之和最大。
在這里為結點1,3。候選重構集1包含模塊A、B,候選重構集3包含模塊C、D。因此將模塊A、B放在動態區域1內,把模塊C、D放在動態區域2內以完成功能模塊的可重構。
圖8為根據本發明一個實施例的方法與硬件相結合的設計流程圖。如圖8所示,給 定一個C或C++實現的程序,本發明中使用高層次綜合工具進行綜合和分析,得到該程序對應的甘特圖以及對應的硬件實現代碼;通過工具(比如planahead等)對硬件實現代碼進行綜合和分析,得到程序中每個模塊需要使用的資源、面積,并生成網表文件。甘特圖和每個模塊的資源需求作為我們的方法ISBA的輸入,經過處理得到功能模塊的劃分和組合方案;根據該方案,以及工具生成的網表,進一步完成后續設計,流程和Xilinx提出的EAPR流程是一致的。

表3
通過上述圖8的方法對多個功能模塊進行綜合得到如表3所示的每個模塊的資源請求向量。對上述表3的數據對對應的功能模塊通過上述方法進行配置后,通過PlanAhead驗證的結果顯示,本發明提供的方案在XC5VLX50T上消耗6408Slices和16DSPs。也就是說,通過采用節省資源、功耗和成本的動態部分可重構技術,GSM在XC5VLX50T上得到了實現(Implement)。
根據本發明實施例的方法,通過計算交集圖節點的重構權值最大且占用面積滿足條件的功能模塊配置到重構區域,可有效地利用片上的資源,降低重構時延,提高可重構系統的處理速度和效率。
盡管上面已經示出和描述了本發明的實施例,可以理解的是,上述實施例是示例性的,不能理解為對本發明的限制,本領域的普通技術人員在不脫離本發明的原理和宗旨的情況下在本發明的范圍內可以對上述實施例進行變化、修改、替換和變型。

關于本文
本文標題:FPGA動態部分可重構區域的配置方法.pdf
鏈接地址:http://www.pqsozv.live/p-6180534.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
钻石光影