层次式布线资源FPGA连线开关的设计

摘　要: 提出了一种层次式布线资源FPGA 连线开关的设计方法,采用迷宫算法,对连线开关的结构进行了分析。针对连线连接盒CB(connection box) ,提出了较为节省芯片面积的半连通结构;针对连线开关盒SB( switch box) ,在给出连通度f s 概念后,提出了使SB 连通能力达到最大值的设计方法,并通过数学推导予以证明。应用这种设计方法,设计了一种f s = 3 的SB ;成功地实现了采用这种结构的SB 和半连通CB 作为连线开关的FPGA 芯片FDP-100 K。该芯片在电路布通率和芯片面积方面取得了较好的平衡结果。

关键词: FPGA ; 互连资源; 连接盒; 开关盒; 布通率

　引　言

目前,FPGA 器件已经成为快速实现数字逻辑的媒介,其主要优点在于可大大缩短产品研制周期,降低开发成本。FPGA 主要由三大部分组成:可编程逻辑单元CLB (Configurable Logic Block) 、布线资源( Interconnection Resource) 和可编程I/ O ( I/ OBlock) 。布线资源是FPGA 中非常重要的一部分,原因在于布线资源占用了FPGA 约70 %～ 80 %的芯片面积和约50 %～60 %的信号时延,因此,布线资源设计的好坏直接影响到FPGA 芯片的性能。

本文针对基于LU T 的FPGA , 其互连资源主要由三部分组成:连线通道( t rack) ,连线连接盒CB(connection box) 和连线开关盒SB ( switch box) 。CLB 的I/ O 通过CB 连入CLB 周围行(x) 、列(y) 分布的布线通道中,其中,x 、y 方向走线交叉处由连线开关盒SB ( switch box) 决定x 、y 方向走线是否可以连通。在CB 和SB 中,交叉点的连接与否由可编程MOS 管的导通与截止来实现。较多的编程管对提高布通率有利,但通常并不需要每一个交叉点均设置编程管,因为编程管及控制其通与断的SRAM 要占用相当多的芯片面积。CB 和SB 的设计应根据芯片的物理结构求得布通率和芯片面积的最佳平衡。

CB 和SB 的连通方式有多种类型,其中较为经典的有Xilinx 公司XC4000 系列器件所采用的全连通结构CB 和disjoint 结构SB,如图1 所示。全连通CB 结构中,假设x 和y 方向布线通道中均有W 条连线资源,那么,CLB 的每个I/ O 与这W 条连线都相连接( I/ O 与连线交叉点上的斜线表示该处设有可编程开关管) 。disjoint 结构SB 中,送入SB的编号为I 的连线只能与其他三个方向上编号同样为I 的连线相连接(每个编程点都有6 个开关管来实现这种连接) 。这种CB 和SB 的结构在对称式FPGA 器件(布线通道中连线的长度都只跨越1 个CLB) 中取得了良好的布线结果。

为了降低FPGA 器件中信号的时延,处理更大的逻辑电路。近期FPGA 研究的热点集中在层次式(hierarchical) 结构上。研究表明,更大规模的可编程逻辑单元,以及连线长度大于1 (连线长度跨越1 个以上CLB) 的FPGA 有着更高的面积利用率和更好的信号时延特性。在前期的工作中,我们设计了一个具有层次式布线资源的FPGA 芯片FDP-100 K。FDP-100 K中可分割长线的长度为4 ,即这些连线都是跨越4 个CLB 后才断开的。这意味着绝大多数连线送入SB 时,其自身( x 方向或y方向) 都是连通的。针对FDP100 K 层次式互连资源中长度大于1 的的可分割长线,为了提高芯片的布线布通率,减小芯片面积,我们提出了一种适用于层次式布线资源的CB 和SB 结构设计方法。

　CB 和SB 设计的迷宫算法分析

迷宫算法是目前FPGA 布线中广泛使用的算法。应用迷宫算法中的波扩散原理,对CB 和SB 的结构设计进行分析。迷宫算法波扩散原理最基本的思想如图2 所示,模拟波浪在源点与终点之间传播。可以被布线的区域用空白节点代表,而已经被占用的布线区域用黑色节点表示,目的是在源点S 与终点T 之间找到通路,使通路上所有节点都是空白节点。具体过程是从源点开始, 按照节点上所标明的层号逐层向外传播,绕开障碍区域,直到波浪传播到终点T 上。

利用迷宫算法进行FPGA 器件布线时,不同的CB 和SB 结构将导致连线资源不同的连接关系。图3 (a) 示出FPGA 片段中CB 为全连通( x 和y 方向走线交叉点处的斜线表示该处设有可编程开关管) ,SB 为f s = 1 的一种结构。

图4 (a) 示出CB 为半连通,SB 为连通度f s = 2的一种结构。因为FDP-100 K的可分割长线有专门的开关控制其通或断,因此,FDP-100 K 的可分割长线在送入SB 时,其自身都是连通的,相应交叉点上可编程开关只由一个晶体管构成。这里,SB 的连通度f s 指的是通过编程能与水平(竖直) 送入SB 的可分割长线连通的竖直(水平) 的可分割长线数。假设两图中均要求第一行中间CLB 的I/ O 端S 与右下角CLB 的I/ O 端T 相连。图3 ( b) 和图4 ( b) 分别表示不同CB 和SB 结构导致S 和T 端之间连线资源不同的连接关系。图3 (b) 和图4 (b) 中,左右两个圆形节点分别代表S 和T 端,椭圆形节点代表可分割长线,若这些节点之间有连线,则说明这些节点通过编程可连接。图3 ( b) 用黑色粗线标注出图3 (a)中S 和T 之间的一条通路, S 通过CB 中的开关与y 方向可分割长线V _1-4 相连。在SB1 中,V _1-4 通过开关与x 方向可分割长线H_1-4 相连, H_1-4 又在SB2 中与V _2-4 相连;在SB3 中,V _2-4 与H_2-4 相连,最终, H_2-4通过CB 中的开关与T 连接。在用迷宫算法布线时,波浪从S 端开始逐级向右传播, 直至到达T 端为止。CB 的结构决定了可与S 和T 节点连接的椭圆节点数目,SB 的f s 值决定了波从一个椭圆形节点出发向右可以传播到的椭圆形节点数。

假设图3和图4 中有一些相同的布线资源已被占用而无法使用,在图3 ( b) 和图4 ( b) 中用灰色节点表示。结果是,图3 中,f s = 1 时,源点S 和终点T 之间无法布通。而图4 中,虽然CB 为半连通,但由于f s = 2 ,在大范围的波的传播中,找到了图4 (b) 中黑线所示的这条通路。这说明f s 值越大,越有助于FPGA 布线时绕开障碍,找到未被占用的连线资源,提高连线资源的利用率,从而提高布通率。

　FDP 的CB 结构和SB 的设计方法

应用迷宫算法对CB 和SB 结构进行分析,FDP-100 K中,CB 采用半连通结构,即CLB 的I/ O只与通道中一半的连线通过编程可连接,SB 采用了连通度f s > 1 的结构。问题的关键是针对某一f s值,如何合理设计SB 结构,使其具有针对这一f s 值最大的连通能力。

本文中,对SB 连通能力的衡量标准是一根连线在经过2 个SB 后,所能驱动的最大连线数。之所以采用经过2 个SB 的这个标准,是因为从下面数学推导的结论中可以得知,f s = 3 或4 的SB ,经过2 个SB 后,可以分别驱动最多7 和13 根连线。相对于实际FPGA 芯片的布线通道而言,这样的驱动能力已经足够,再大的驱动能力也会被布线通道的实际宽度所限制。因此,本文中所采用的SB 连通能力的衡量标准是可行的。

下面的数学推导用来证明具有不同f s 值的SB ,他们的连通能力分别有一个最大值。从公式中归纳出的规律可以为在相应条件下设计具有最大连通能力的SB 结构提供一种方法。

首先,假设FPGA 器件布线通道宽度为W ,SB的连通度f s 为t (SB 中每根连线上都有t 个可编程开关,用来控制此根连线是否能和与之垂直的t 根连线相交) 。通过SB 的x 方向连线的编号,从上面第一根开始,依次为H₀ , H₁ , H₂ ,…,H_{W - 1} ,通过SB的y 方向连线的编号从左面第一根开始, 依次为V ₀ ,V ₁ ,V ₂ ,… ,V _{W - 1} 。假设选取第Hn 号线(0 ≤n 作为我们所考察的原始第一级驱动线,在经过第一个SB 时,与第Hn 号线通过编程开关可相交的,自左向右分别是编号为V _a1 , V _a2 ,…, V _at ( a1 ≠a2 ≠.≠at ,且0 ≤a1 < a2 < .< at ≤W - 1) 这t 根y 方向连线。

第1 步,第一级驱动线Hn 在经过第一个SB 时可通过编程开关驱动y 方向的t 根连线分别为V a1 ,V a2 , …,V at 。

第2 步,在经过第二个SB 时,这t 根y 方向上的连线V _a1 ,V _a2 , …, V _at , 每根都又作为第二级驱动线,分别驱动t 根x 方向连线。y 方向第二级驱动线驱动x 方向连线的驱动关系可以用方程(1) 表示

V _ai = H_g( ai , aj ) (1)

( ai ∈{ a₁ , a₂ , …, at} , aj 遍历{ a₁ , a₂ , …, at} 这t 个值)

方程(1) 表示当第V _ai 号线作为第二级驱动线经过第二个SB 时,它可以驱动的t 根x 方向连线由H _g ( ai , aj ) 表示, g ( ai , aj) 表示这些被驱动的x 方向连线的编号脚标。

　　因为共有t 根y 方向连线V _a1 ,V _a2 , …,V _at 作为第二级驱动线,因此, 一共有t 个方程(1) 。又因为每个方程(1) 中都是aj 遍历( a₁ , a₂ , …, at) 这t 个值,因此,由t 个方程(1) 所表示的驱动关系一共有t² 个。在t² 个解中,相异解越多,说明第Hn 号线在经过2 个SB 后,驱动的x 方向连线根数越多,相应结构的SB 的连通能力越大。取不同的V _ai , 方程(1) 在aj = ai 时都变为V _ai = H_n , 即无论哪根第二级驱动线V _ai 在经过第二个SB 时都得驱动第H_n 根x 方向连线。由此可知, t 根第二级驱动线V _a1 ,V _a2 ,…,V _at 在经过第二个SB 时所驱动的x方向连线中,至少有t 根是重合的。也就是说, 所有的t 根y 方向连线V _a1 ,V _a2 ,… ,V _at 在经过第二个SB 后,最多能驱动t² - ( t - 1) 根x 方向的连线。如何能使这t² -( t - 1) 个解中相异解最多, 成为设计SB 结构的关键。

分析方程(1) 可知,方程(1) 各个解的相异之处由函数g ( ai , aj) 中aj - ai 和W - | aj - ai| 决定。由此可知, | aj - ai| 的相异解越多, 方程(1) 的相异解越多,SB 的连通能力越大。当ai 取a1 , a2 , …, at中的一个值, aj 遍历a1 , a2 , …, at 这t 个值, 若| aj- ai| 的值各不相同,且不等于W/ 2 时, t 个方程(1)所得到的相异解总数最大,SB 的连通能力最大。在实际的SB 结构设计中,依据这些公式结论,只要保证一根连线上任两个编程开关放置的位置之间的距离不同,就能保证这样所设计的SB 的连通能力最大。

针对f s = 3 的情况,图5 (a) ( b) 分别表示两种SB 结构及其连通能力。图5 (a) 中, H0 号线上编程开关设置在它与V ₄ 、V ₆ 、V ₇ 号线的交叉点上。这些编程开关之间距离的绝对值分别为| 7 - 6| = 1 、| 6 -4| = 2 和| 7 - 4| = 3 。这些值各不相等,且不等于1/2 通道宽度值4 ,图5 (b) 中, H₀ 号线上,编程开关设置在它与V ₅ 、V ₆ 、V ₇ 号线的交叉点上。这些开关之间距离的绝对值分别为| 7 - 6| = 1 、| 6 - 5| = 1 和| 7- 5| = 2 ,并不是各不相同。依据公式推导的结论,图5 (a) 中的SB 将比图5 (b) 中的SB 有更大的连通能力,且图5 (a) 中的SB 应具有在f s = 3 情况下最大的连通能力,即一根连线在经过2 个图5 (a) 中的SB后,将可以驱动32 - (3 - 1) = 7 根连线。图5 (a) 、(b) 证实了这些结论。

FDP - 100 K中,通道宽度为8 ,SB 取连通度f s= 3 ,采用的正是图5 (a) 中连通能力为7 的结构。SB 的连通能力基本满足通道宽度的需要。

　实验和结论

FDE(FDP design environment ) 是我们自主开发的FPGA 设计软件。使用FDE ,将ISCAS’89 的23 个测试电路用FDP-100K 实现。首先,使用映射工具FMAP,对测试电路的网表进行映射,映射结果的优化性在于使用尽量少的LC。然后,使用布局布线工具FPAR,将映射后的网表布到采用两种SB 和CB 结构方案的FDP-100 K中,即逻辑资源均使用FDP-100 K的可编程逻辑单元,但互连资源中的CB 和SB 使用两种结构组合。第一种使用Xilinx 的全连通CB 和disjoint 的SB ;第二种使用FDP-100K的半连通CB 和f s = 3 的SB。

测试时,两种方案的芯片规模是相同的,都使用32 ×32 个可编程逻辑单元,通道宽度为8 。另外,由于CB 和SB只负责可分割长线的连接,因此,为了减少其他连线资源对实验结果的影响,我们在布线中只使用了可分割长线。两种结构的网表布通结果如表1 所示。从表1 中可以看到,在23 个电路网表中, Xilinx 全连通CB 和disjoint 结构的SB 互连组合共布通了22 个,而FDP-100K 中半连通CB 和f s = 3 的具有最大布通能力的SB 结构组合布通了20 个。但是,在一个宏单元MC (一个MC 包含4 ×4 = 16 个可编程逻辑单元) 中,Xilinx 的CB 和SB 将消耗1 544 个晶体管,而FDP-100 K 的CB 和SB 只消耗了1 088个晶体管。

FDP-100 K已经采用0.35 μm 工艺进行了流片。与Xilinx 的CB 和SB 结构比,FDP-100K 的CB 和SB 结构虽然在布通率上略有下降,但在互连资源CB 和SB 的面积上,FDP-100 K 比Xilinx 节省了29.53 %