最小环最大化的FPGA布线资源结构设计方法

第22卷第6期2010年6月

计算机辅助设计与图形学学报

JournalofComputer AidedDesign&ComputerGraphicsVol.22No.6June2010

最小环最大化的FPGA布线资源结构设计方法

余建德,谢 丁,邵 赟,王 健,陈利光,来金梅,童家榕

(复旦大学专用集成电路与系统国家重点实验室 上海 201203)(yujiande@)

*

摘要:为了提高FPGA布线资源的灵活性,提出一种通过扩大布线资源图的最小环来设计布线资源的方法.首先

分析了布线资源图的最小环大小和布线资源中信号传播灵活性的关系,并通过调整布线资源中线网的连接结构来扩大该最小环.采用该方法设计了一种新的开关盒结构!!!最小环最大化(MLM)开关盒.实验数据表明,MLM开关盒与4种学术上典型的开关盒结构!!!Disjoint,Universal,Wilton和JSB相比,在时序上处于平均水平,而布通率分别提高了17.7%,8.0%,2.4%和2.2%.

关键词:FPGA结构设计;布线资源;开关盒;布通率中图法分类号:TN402

Min Loop MaximizationMethodonFPGARoutingResourcesArchitectureDesign

YuJiande,XieDing,ShaoYun,WangJian,ChenLiguang,LaiJinmei,andTongJiarong

(StateKeyLaboratoryofASIC&System,FudanUniversity,Shanghai 201203)

*

Abstract:Amethodthatmaximizestheminimumloopsizeintherouting resourcegraphisproposedinFPGAroutingresourcesarchitecturedesigntoimprovetheflexibilityoftheroutingresources.Firstanalyzetherelationshipbetweentheminimumloopsizeintherouting resourcegraphandthetransitionflexibilityofsignalsintheroutingresources.Thenmaximizetheminimumloopbyadjustingthewiresconnectionsintheroutingresources.Designanovelswitchbox,calledminimum loopmaximization(MLM)switchboxwiththismethod.Experimentalresultsshowthatwhilecomparedwith4typicalacademicswitchboxes,Disjoint,Universal,WiltonandJSB,MLMisataveragelevelintimingandoutperformalloftheminroutabilityby17.7%,8.0%,2.4%and2.2%separately.Keywords:FPGAarchitecturedesign;routingresources;switchbox;routability FPGA硬件的基本组成部分包括可编程逻辑单元、输入输出单元和可编程互连资源.

对于特定的FPGA结构,需要一套CAD软件系统来利用FPGA逻辑单元阵列和布线资源实现电路功能并尽可能地提高性能.而只有FPGA逻辑单元阵列与布线资源的结构设计合理,软件才有可

能有效、合理地利用它们.

本文针对布线资源的结构设计问题提出了一种最小环最大化的FPGA互连结构设计方法.此方法对布线资源建立布线资源图模型,从图的角度来研究分析布线资源的性能,并提出以最小环大小来评估一种布线资源的灵活度.为了验证该设计方法的

收稿日期:2009-07-11;修回日期:2010-01-18.基金项目:国家自然科学基金(60876015);国家 八六三 高技术研究发展计划(2007AA01Z285).余建德(1985!),男,硕士研究生,主要研究方向为FPGA互连结构设计;谢 丁(1984!),男,博士研究生,主要研究方向为FPGA布图软件设计;邵 赟(1984!),女,硕士研究生,主要研究方向为FPGA工艺映射设计;王 健(1982!),男,硕士,主要研究方向为FPGA硬件结构设计;陈利光(1979!),男,博士,主要研究方向为FPGA结构设计;来金梅(1965!),女,博士,教授,论文通讯作者,主要研究();(1942!),,,FPGA.

第6期余建德,等:最小环最大化的FPGA布线资源结构设计方法

935

有效性,针对岛型FPGA的布线资源设计了一种新的开关盒结构!!!最小环最大化(minimum loopmaximization,MLM)开关盒,并将其与4种学术上典型的开关盒结构相比,结果表明,MLM开关盒在布通率方面有良好表现.

1 布线资源图的MLM

1.1 布线资源图

图1所示为一个经典的岛型FPGA结构示意图,布线资源指的是其中的互连线、开关盒(switchbox,SB)和连接盒(connectionbox,CB)

[1 6]

图3 布线资源对应布线资源图

1.2 广度优先搜索与环

在布线过程中,所有主流的布线算法都是采用广度优先搜索(breadth firstsearch,BFS)算法或

是基于BFS的优化算法在布线资源图中寻找让信号从源端线网到终端线网的最短路径[1].在布线资源图中,从一个节点开始进行一次BFS,我们希望在BFS的每一层都搜到尽可能多的新节点,这样的BFS的效率就高.在布线资源中,信号可以在有限的搜索层次内到达更多的线网,或者说信号到达同样多线网所要经过的路径比较短,因此就可以说布线资源更灵活[6].于是,我们对于布线结构的设计就基于优化BFS这一个出发点展开.

在BFS的某一层搜索中能搜索到多少个新节点取决于:1)上一层搜索中新搜索到的节点;2)这些节点的出度;3)节点之间的具体连接关系.对于1),这是由上一层搜索决定的.对于2),取决于布线资源的连通度,在结构设计中往往受面积等因素的限制而被设为固定值.比如在一个Fs=3的SB[9]中,第一层搜索节点出度为3,之后每层中的搜索节点的出度均为2,如图4所示.由于以上原因,本文对于BFS的优化主要落实于3),保持布线资源中连接的数量不变,调整布线资源图的节点之间的具体连接关系.

[8]

;图2所

示为一个典型的tile型FPGA结构,其布线资源包括互连线和通用布线矩阵(generalroutingmatrix,GRM)[7]

.

图1 岛型FPGA

结构

图2 Tile型FPGA结构

本文首先用 布线资源图 来描述布线资源结构[1].布线资源中的每条线网在布线资源图中都用一个 节点 来表示,而线网之间的可编程连接在图

图4 Fs=3的SB中的BFS

已知上层节点数和上层节点的出度,那么由上层节点出发的边的总数就是已知的.我们希望每条,

936

计算机辅助设计与图形学学报 第22卷

而不是一个曾在之前的搜索中被搜索到过的节点,这样新找到的节点数目就实现了最大化.图5所示为2个BFS,本文定义如下:一条从上一层节点出发的边称为 搜索边 ,即图5中的线条,如果搜索边指向一个新的节点,那么这条搜索边被称为 有效搜索边 ,即图5中的实线;如果一个搜索边指向一个曾被搜索到过的节点,那么这条搜索边被称为 无效搜索边 ,即图5b中的虚线.由所有的有效搜索边的集合组成一个 广度优先搜索树

.

的大小.

在布线时,布线资源的每条线网都有可能成为信号的源,即每个节点都可能成为BFS的根节点.所以我们的目标是要在整个布线资源图中扩大所有的环,而无需去关心那些大的环,因为不可能把布线资源图设计成BFS树的结构.当大多数节点都被搜索到之后,环总是会出现的,它们并不构成损失.由于最严重损失都是由小的环带来的,因此只需要尽可能地去扩大那些比较小的环.

至此,我们得到了一个 MLM 的布线资源设计方法.让布线资源中所有的环的大小都大于等于最小环大小s,也就意味被每条无效搜索边的损失不会超过s.这样设计出来的布线资源图在BFS中更强大,对应的布线资源将在布线中更灵活

[6]

.

图5 BFS中的有效搜索边和无效搜索边

2 新型MLMSB结构设计

下面将以经典的岛型结构FPGA中的SB为例,用本文提出的 MLM 布线结构设计方法来设计一个SB.2.1 SB

SB是岛型FPGA的布线资源中最重要的一个组成部分,它是线网和线网之间的连接者,决定了线网和线网之间的连接关系.

对于一个SB最重要的参数是宽度W,它代表的是SB的上下左右每条边与多少线网相连;另一个参数是连通度Fs,代表每条连进SB的线网可以通过可编程开关与多少条其他线网相连.最广为采用并被证明为最优的Fs值为3,即某个方向连进SB的线网分别与其他方向的一条线网通过可编程开关相连[9].给定这2个参数后,决定SB性能就是线网间开关的具体连接关系了.学术上最经典的3个SB结构为Disjoint,Universal

[2]

[3]

从图5b中可以看出,每出现一条无效搜索边,就意味着有一个节点被以2种或2种以上的方式搜索到了,即有多条不同的路径从搜索根节点通向此节点,2条首尾相同的不同路径就可以围成一个环型.可以看到,无效搜索边出现得越早,对应产生的环的大小也就越小.1.3 MLM

每当出现一条无效搜索边,意味着BFS在这一层中就要少搜索到一个新的节点了,更糟糕的是这一层中损失一个新节点将导致下面的层次中损失更多的新节点,如图5b所示.无效搜索边在BFS中的无效也就是对应的可编程连接在此次布线中无效,这在有限的布线资源中就是一种浪费.因此,应该尽可能地改变图的结构来使无效搜索边尽可能晚地出现.

对于任意一次无效搜索边的出现,可用这条无效边所带来的环的大小(即2条功能重复的路径的长度之和)来衡量它的损失,因为这个损失是2条路径所共有的.环越小,说明损失的无效搜索边出现得越早,损失也就越大.我们的目标也由此定为扩大环

和Wilton,如图6

[4]

所示,它们都满足Fs=3限制.文献[10]中提出的shifty,diverse,diverse clique以及文献[5]中提出的JSB也都是Fs=3的SB.

6

第6期余建德,等:最小环最大化的FPGA布线资源结构设计方法

937

每种SB都是从不同的设计角度设计出来的,各有特点.Disjoint和Universal的连接方式比较简单,因此布通率较低,需要通道有更大的宽度才能成功布线.而其他SB的内部连接方式更复杂,让线网之间更易连通,从而提高了布通率.我们同样在Fs=3限制下通过MLM法设计SB,并命名它为MLMSB.

2.2 SB的布线资源图

在SB中,每个可编程开关都对应布线资源图里的一条无向边,连结的2个线网对应布线资源图中2个节点.一个通道宽度为W的SB中来自上下左右4个方向的线网共对应有4W个节点,4个通道之间有

42

=6种连接方式,在Fs=3的限制下对

描述一种通道和通道间的双向连接,如fA B=x的意思与(tA,i,tB,(i+x)modW)相同.2.3 最小环的优化目标

在图6a中,A0-B0-C0-A0构成一个大小为3的环,这就是它的最小环.UniversalSB与WiltonSB的最小环大小都是4.在MLMSB设计中,要使最小环尽可能地扩大.

对于不同的W,最小环可以被扩大到多大是不一样的.所以最大化最小环时,最大化的目标是随着W而变的.普遍的趋势是:W越大,最小环也可以被扩大到越大.

例如,如果W=4,整个布线资源图中一共有16个节点.从图8中可以看出,对这样的图进行BFS时,搜索到第3层就不能避免出现无效搜索边.因为当搜到第3层时,图中只剩6个未被搜索过的节点,而第3层共有12条搜索边,于是就会出现一个大小为6的环.由上面的论述可以得知,在W=4时,最小环不可能大于6;而当W值更大时情况则不同,如当W=18时图中有72个节点,保证了到第5层才遇到无效搜索边,最小环大小扩大到了10.

应地就有6W条边.我们的研究重点就是组织这些边与节点的连结关系.

对于要设计的SB,这4W个节点和6W条边在布线资源图中要满足以下3个规则:1)SB模型规则.这是一个4等分图,即图中的4W个节点可以被等分成4组,每组W个节点,且组内的节点之间没有边相连;2)Fs=3规则.图中每个节点的度数均为3,由节点引出的3条边分别连向另外3个组点的节点;3)偏移模型规则.MLMSB采用文献[10]中描述的偏移模型,即某个通道的W条线网和另一个通道的W条线网一一相连时,它们的编号整齐地偏移一个固定值.例如,当A通道和B通道之间的连接的偏移值为x时,A通道第0条线网A0与B通道第x条线网Bx相连,A1与B1+x相连,以此类推,记为(tA,i,tB,(i+x)modW).

上下左右通道分别称为A,B,C和D,如图7所示,一共有6种通道和通道之间的双向连接,即A B,C D,A C,A D,B C和B D.在偏移模型中,把6种通道之间的连接的偏移值记为fA B,fC D,fA C,f

A D

图8 Fs=3,W=4的SB的中的BFS

因此,我们将针对不同的W设定不同的优化目标,设计各自的结构.

注意到,在偏移模型下最小环的大小最多只能扩大到10.如图9所示,环形路径从A通道出发,将5种连接方式各走了一个来回,线网编号在10次偏移中将5个结构参数各加减一遍,抵消为0.当路径最后回到A通道时,线网编号必然恢复成最初值,

,f

B C

和f

B D

6个参数,这样用6个参数就可以

描述一种偏移模型下的SB结构了.其中每个参数

图 SB6种连接图9SB10

938

计算机辅助设计与图形学学报 第22卷

即路径在出发点闭合成了环.因此,对于大于18的W值,也都以10作为最小环大小的优化目标.2.4 线网的重新排序

对于一个给定的W,在偏移模型下可用6个参数来描述一种结构设计,每个参数都是0~(W-1)之间的整数,共有W种排列,代表了W种可能的结构.对某一通道内的线网任意重新排列编号不会改变布线资源图的拓扑结构,因此也不会影响最小环大小.因为B通道内的每条线网都与A通道中某条线网相连,可按照对应的A通道中的线网的顺序对B通道中的线网进行重新排序.这样处理之后,SB的拓扑结构没变,但fA B就变成0了.再按照同样的方法把fA C与f

C D6

6

该算法进行修改,得到了计算最小环大小的算法,其伪代码如下:

Min LoopSize(G)

n%|V[G]| D%E[G]&loopsize%+, fork%1tondo(fori%1tondo) forj%1tondo

loopsize%min(loopsize,dij+dik+dkj)+ dij%min(dij,dik+dkj) returnloopsize

也转变成0.这样,6个参数

6

其中第&, , 行是为了计算最小环大小而加入的,其余部分皆为Floyd Warshall算法.

Floyd Warshall是一个构造型算法,外循环每次引入一个新节点k,就由二重内循环更新一遍图中任意2个节点在有k的情况下的最短路径.如果图中的最小环是由p到q的2条路径围成的,那么这2条路径必然是从p到q的最短路径和次短路径.如图10所示,假设x是这2条路径中除了p和q之外编号最大的节点,那么在x作为k被引入之前,从p到q的不包含x的最短路径已经被计算出来并作为dpq被存储,如图10中虚线所示,从p到x和从x到q的最短路径也已获得并作为dpx和dxq存储,如图10中实线所示.因此,在k的第x次循环中,这个环的大小就由(dpq+dpx+dxq)计算得到,即伪代码中第 行.

中3个参数的值就变成了0,所有的W种结构中只剩下W3需要讨论了.

注意到,如果原先SB结构满足偏移模型,则在重新排序后它仍然满足偏移模型,因为只需要通道内整体偏移一个量就可以完成重新排序.2.5 遍历与选择

对于某个W值,遍历所有的W3种可能的SB结构,计算每种可能结构的最小环大小,就可以知道在这个W值的情况下偏移模型所能得到的最小环的最大值;然后将能够达到这个大小的最小环结构记录下来.

2.5.1 建立布线资源图

首先对给定的W和6个偏移参数建立对应的布线资源图.由于本文是针对经典模型设计SB结构,用传输管之类的双向可编程连接,因此为它建立一个无向图.图中共4W个节点,6W条无向边,其中0~(4W-1)共4W个节点按顺序分别对应A,B,C,D通道中编号从0~(W-1)的节点.其伪代码如下:

Undirected Graph(G,W,fA B,ffA D,fB C,f

B D

C D

,fA C,

图10 最小环的2条路径

)

addvertices0#4W-1toV[G] fori%0toW-1do& addedge(i,W+(i+f( addedge(i,W+(i+f

A B

)modW)toE[G])modW)toE[G]

)modW)toE[G])modW)toE[G]

2.5.3 计算无向图中最小环大小算法

根据SB双向开关的性质,我们为其建立的是无向图.对应的计算最小环的算法也需要进行一定的改动.这里的环的大小不再是2条功能相同的有向路径长度和,而是一个首尾相连无向路径的长度.如下面的伪代码所示,同样是在Floyd Warshall算法上进行改动,添加的是第&,(,), , 行.设 图中的最小环上的节点中编号最大的为x,它在最.

addedge(i+2W,3W+(i+fC D)modW)toE[G]

A C

) addedge(i,3W+(i+fA D)modW)toE[G] addedge(i+W,2W+(i+f+ addedge(i+W,3W+(i+f

B CB D

2.5.2 计算最小环大小算法

Floyd Warshall算法可以计算布线资源图任意

3

[8]

第6期余建德,等:最小环最大化的FPGA布线资源结构设计方法

表1 适用于W/[9,14]的12组参数

f

A B

939

那么这个环的剩余部分就是不包含x的p和q之间的最短路径,如图11中虚线所示,这条路径上所有的点编号都比x小,因此一定会在循环到k=x之前就被计算得到并存入dpq,在循环到k=x时,第 行中(dpq+dqk+dkp)就得到了这个最小环的大小.

Min LoopSizeinUndirectedGraph(G)

n%|V[G]| D%E[G]&loopsize%+, fork%1tondo( fori%1tok-2do) forj%i+1tok-1do

loopsize%min(loopsize,dij+djk+dki)+ fori%1tondo forj%1tondo

. dij%min(dij,dik+dkj) returnloopsiz

e

000000000000

f

C D

fA C000000000000

fA D243412132434

f

B C

f

B D

000000000000

424321314243

112255555555

2.6 MLMSB结构

本文为所有的W值一共选取了6组参数.

MLMSB在不同的W值的情况下选取对应的一组参数来得到对应的结构.表2所示为当W从1~+,时对应的参数组,可以看出由于偏移模型的限制,最小环最大只能达到10,所以当W>22之后不再遍历所有的参数排列,只需验证最后一组参数(0,0,0,3,7,2)能否将最小环优化到10即可.

表2 MLMSB在不同W下的结构

W

f

A B

f

C D

fA C00000

fA D01121

fB C01347

f

B D

min loopsize

34679109

图11 无向图中最小环路径12~34~8

00000

00000

00213

2.5.4 选择参数

对某个W值遍历所有的W种可能的SB结构,计算每种可能的情况下的最小环,就可以知道对于这个W值,偏移模型下SB的最小环所能达到的最大值,并将能达到这个大小的最小环结构记录下来.

一般而言,能使最小环达到最大值的结构不止一个,于是会记录下很多组参数来.如在W=10的情况中,最小环的大小最优可以达到7,共有48组参数满足.在选择时,尽可能地选择更通用的,即这组参数不仅适用W=10,而且适用于W为其他值的情况.如W=10时取到48组参数中,有12组在W为9~14之间都适用,表1所示为这12组参数.

在这12组参数中,我们更倾向于选择数值较小的,因为它们偏移小,叠加后不容易等于W,所以当它被使用到更大或更小的W的情况中时,效果也相对较好.如在表1中,我们就选择第一组参数(0,0,0,,).

3

9~1415~171819202122~+,

00037210910

W/{1},S={(tA,0,tB,0),(tC,0,tD,0),(tA,0,tC,0), (tA,0,tD,0),(tB,0,tC,0),(tB,0,tD,0)},

W/{2,3},S=0{(tA,i,tB,i),(tC,i,tD,i),(tA,i,tC,i),

i=0W-1

(tA,i,tD,(i+1)modW),(tB,i,tC,(i+1)modW),(tB,i,tD,i)},W/[4,8],S=0{(tA,i,tB,i),(tC,i,tD,i),(tA,i,tC,i),

i=0W-1

(tA,i,tD,(i+1)modW),(tB,i,tC,(i+3)modW),(tB,i,tD,(i+4)modW)},W/[9,14],S=0{(tA,i,tB,i),(tC,i,tD,i),(tA,i,tC,i),

i=0W-1

(tA,i,tD,(i+2)modW),(tB,i,tC,(i+4)modW),(tB,i,tD,(i+1)modW)},W/[15,17],S=0{(tA,i,tB,i),(tC,i,tD,i),(tA,i,tC,i),

i=0W-1

(A,i,t1),(B,i,tC,(i7)W),(tD,(i+3W),

940

W/[18,+,),S=

W-1i=0

计算机辅助设计与图形学学报 第22卷

0{(tA,i,tB,i),(tC,i,tD,i),(tA,i,tC,i),

modW

(tA,i,tD,(i+3)modW),(tB,i,tC,(i+7)modW),(tB,i,tD,(i+2)

)};

是MLM结构的另一种表述方法,其中(tA,i,tB,j)表示在A通道的i线网和B通道的j线网之间存在可编程连接,S则是所有连接的合集,即整个SB结构.举例说明,当W在9~14之间时,用fA B=0,fC D=0,fA C=0,fA D=2,fB C=4和fB D=1这样一组参数来描述结构,当W=10时的具体结构表示为S=i=00{(tA,i,tB,i),(tC,i,tD,i),(tA,i,tC,i),(tA,i,tD,(i+2)mod10),(tB,i,tC,(i+4)mod10),(tB,i,tD,(i+1)mod10)},其结构示意图如图12所示

.

9

在20组对比中,MLM得到了全胜,每次对于同样的网表都可以用最小的通道宽度成功布通,如表3所示.

表3 布通电路所需最小通道宽度比较

网表

Disjoint

alu4apex2apex4bigkeyclmadesdiffeqdsipellipticex1010ex5pfriscmisex3pdcs298

333737234823282539413943355927343237512517.7

31353621472126213637373931512431313545238.0

SB

UniversalWilton

29353319431925203536353729482331283343232.4

JSB29333319441924203535353730492429293343232.2

MLM2933331943182419343535372947232928334221

图12 W=10的MLMSB结构

s38417s38584

3 实验结果与分析

比较MLMSB与Disjoint,Universal和Wilton这3种学术上的经典SB设计,以观察其性能差异,参加比较的还有文献[5]中提出的JSB.在这5种设计中,SB都将以一个单一的结构遍布整块芯片,可以做到一致的版图实现;而文献[10]中提出的shifty,diverse和diverse clique这3种新的设计都需要2种SB结构在芯片中交替排布,不符合上述设计规则,因此没有比较.

本文使用VPR工具[1,6,11]来进行仿真.VPR的布线算法是一种典型的基于BFS的路径搜索算法,其具有代表性,可以检验出MLM在布线中的优劣.我们将MLMSB结构与JSBSB结构一起加入到VPR工具中,作为Disjoint,Universal和Wilton之外的另外2种结构.3.1 布通率

我们用了20个MCNC电路来进行VPR布局布线.对于同一个电路,用这5种SB结构分别进行布线,使用二分查找法找到可以使电路成功布通的最小的通道宽度,然后对比5种SB结构所需的通.

seqsplatseng

平均与MLM相差 %

可以看出,Disjoint,Universal,Wilton和JSB平均比MLM分别多需要17.7%,8.0%,2.4%和2.2%的通道宽度.这意味着当电路在使用MLM的布线资源中能够布通时,使用其他4种SB结构的布线资源中就可能没布通.由此体现了MLM结构更为灵活,布通率更高.3.2 时 序

在验证了MLMSB出色的布通率之后,我们又对比了5种SB结构在时序上的表现.还是用20个MCNC基准电路运行VPR工具进行比较,对5种SB采用相同通道的宽度,取的是能让5种SB都成功布通的最小值.对5种SB进行布线后,比较电路的关键路径延时观察不同的SB结构对时序的影响.如表4所示,20组测试中,MLM只在其中3组比较中关键路径延时最小,用Disjoint和UniversalSB布线的平均结果分别比MLM快了2.8%和7.9%,而Wilton和JSB分别比MLM慢了7.0%和.

第6期余建德,等:最小环最大化的FPGA布线资源结构设计方法

表4 关键路径延时比较

网表

Disjoint

alu4apex2apex4bigkeyclmadesdiffeqdsipellipticex1010ex5pfriscmisex3pdcs298s38417s38584seqsplatseng

平均与MLM相差 %

7.12E-086.23E-086.73E-084.62E-081.57E-075.61E-085.04E-084.68E-089.55E-082.27E-075.58E-081.03E-076.00E-081.35E-071.01E-078.20E-081.38E-076.89E-081.35E-074.90E-08-2.8

Universal6.19E-088.36E-087.32E-084.39E-081.47E-077.34E-085.68E-085.63E-081.04E-071.17E-075.58E-081.08E-075.52E-081.31E-071.15E-078.43E-085.48E-088.09E-089.98E-085.09E-08-7.9

SBWilton5.93E-087.64E-081.05E-075.90E-081.51E-075.94E-086.66E-086.79E-081.12E-071.39E-077.04E-081.31E-076.83E-081.28E-071.50E-078.81E-086.31E-088.24E-082.15E-075.24E-08

7.0

JSB6.46E-081.62E-077.52E-085.01E-081.33E-078.22E-085.80E-087.58E-081.62E-071.40E-078.65E-081.09E-076.16E-081.57E-071.44E-079.32E-087.06E-088.18E-081.22E-075.65E-0810.7

MLM6.64E-089.18E-087.62E-085.04E-081.24E-076.54E-087.73E-084.48E-081.08E-071.33E-077.00E-089.50E-087.07E-081.90E-071.06E-079.46E-089.00E-088.05E-081.41E-075.62E-08

941

3.3 在GRM中的表现

为了研究MLMSB在GRM中的表现,我们用软件模拟了Xilinx公司Spantan2E产品的GRM

[7]

互连结构(图2)的布线过程,再把该GRM中的SB改为MLM结构并重复之前的模拟过程,以对比观察其性能上的差别.实验中我们发现,将SB改为MLM结构对于整个GRM的布通率和时序所带来的影响都非常小,表明在Spantan2E的GRM型互连结构中SB只占一小部分,因而在SB方面的改动对于布线资源的性能所带来的影响从总体上看不敏感.

为了说明该方法的使用以及验证其效果,我们设计了一个Fs=3的经典模型下的SB结构!!!MLMSB.与同类其他SB相比,MLM在详细布线中对通道宽度的需求最小,显示了最好的布通率;在时序方面,MLM超过Wilton和JSB,稍弱于Disjoint和Universal.

从MLMSB在布通率方面的出色表现可以看出,MLM方法在布线资源的设计中起到了良好的作用.我们相信该方法可用于更多布线资源类型的设计中,如连接盒结构(图1中的CB)[1]或者是更复杂的GRM型结构,这将是我们下一步研究的重点.参考文献(References):

[1]BetzV,RoseJ,MarquardtA.ArchitectureandCADfor

deep submicronFPGAs[M].s,Boston:

KluwerAcademic

4 结 论

为了优化FPGA布线资源,本文提出一种MLM布线资源设计法,通过增进布线资源图中的

942

计算机辅助设计与图形学学报 第22卷

[2]XilinxInc.XC4000EandXC4000Xseriesfieldprogrammable

gatearrays[OL].[2009 07 11].http: support documentation data.sheets 4000.pdf

[3]ChangYW,WongDF,WongCK.Universalswitch

moduledesignforsymmetric array basedFPGAs[C] ProceedingsoftheACMSIGDAInternationalSymposiumonField ProgrammableGateArrays,NewYork,1996:80 86[4]WiltonSJE.

Architecturesandalgorithmsforfield

programmablegatearrayswithembeddedmemory[D].Toronto:UniversityofToronto,1997

[5]TanJun,ShenQiushi,WangLingli,etal.Hierarchical

modelingandoptimizationofversatileFPGASB[J].JournalofElectronics&InformationTechnology,2008,30(5):1239 1242(inChinese)

(谈 珺,申秋实,王伶俐,等.FPGA通用开关盒层次化建模与优化[J].电子与信息学报,2008,30(5):1239 1242)[6]YuJD,LaiJM.AnovelminloopSBdesigntoimprove

FPGAroutability[C] Proceedingsofthe17thACMSIGDA

InternationalSymposiumonField ProgrammableGateArrays,Monterey,2009:286

[7]XilinxInc.Spartan IIEFPGAfamilydatasheet[OL].[2009

07 11].http: support documentation data_sheets ds077.pdf

[8]CormenTH,LeisersonCE,RivestRL,etal.Introduction

toalgorithms[M].2nded.Cambridge:TheMITPress,2001

[9]RoseJ,BrownS.Flexibilityofinterconnectionstructuresfor

field programmablegatearrays[J].IEEEJournalofSolid StateCircuits,1991,26(3):277 282

[10]LemieuxGG,LewisDM.Analyticalframeworkforswitch

blockdesign[M] LectureNotesinComputerScience.Heidelberg:Springer,2002,2438:122 131

[11]BetzV,CampbellT,FangWM,etal.VPRandT VPack

user smanual[OL].[2009 07 11].http: www.eecg.utoronto.ca vpr VPR_5.pdf

(上接第933页)

[6]

WuQiang,BianJinian,XueHongxi.Multi wayhardware softwarepartitioningalgorithmbasedonabstractarchitecturetemplate[J].

Journal

of

Computer Aided

Design

&

[10]

ComputerGraphics,2004,16(11):1563 1567(inChinese)(吴 强,边计年,薛宏熙.基于抽象体系结构模板的多路软硬件划分算法[J].计算机辅助设计与图形学学报,2004,16(11):1563 1567)[7]

AbdelhalimMB,SalamaAE,HabibSED.Constrainedandunconstrained

hardware softwarepartitioning

using

[11]

particleswarmoptimizationtechnique[C] ProceedingsofInternationalFederationforInformationProcessing.Boston:Springer,2007:207 220[8]

XiongZhihui,LiSikun,ChenJihua.Hardware softwarepartitioningbased

on

dynamiccombinationof

genetic

algorithmandantalgorithm[J].JournalofSoftware,2005,16(4):503 512(inChinese)

(熊志辉,李思昆,陈吉华.遗传算法与蚂蚁算法动态融合的软硬件划分[J].软件学报,2005,16(4):503 512)

[12][9]

KennedyJ,EberhartR.Particleswarmoptimization[C] ProceedingsofIEEEInternationalConferenceonNeuralNetworks.Piscataway,NJ:IEEEPress,1995:1942 1948GaoHaibing,ZhouChi,GaoLiang.Generalparticleswarmoptimizationmodel[J].

ChineseJournalofComputers,

2005,28(12):1980 1987(inChinese)

(高海兵,周 驰,高 亮.广义粒子群优化模型[J].计算机学报,2005,28(12):1980 1987)

BlasiL,CoreGD.Particleswarmapproachinfindingoptimumaircraftconfiguration[J].2007,44(2):679 682DengLinyi,

LinYan.Particleswarmoptimizationfor

project

scheduling

problems

with

resource constrained

JournalofAircraft,

activitysplitting[J].ControlandDecision,2008,23(6):681 684+688(inChinese)

(邓林义,林 焰.粒子群算法求解任务可拆分项目调度问题[J].控制与决策,2008,23(6):681 684+688)

本文来源：https://www.bwwdw.com/article/k9oe.html