基于部分局部互连结构的FPGA逻辑块

摘要

一种基于部分局部互连结构的FPGA逻辑块，其特征在于，包括：8个逻辑单元，该逻辑单元之间采用专用的进位链连接；该逻辑单元包括12个端口，该12个端口包括5个数据输入端口、3个控制输入端口、1个时钟输入端口、3个输出端口；42个端口，该42个端口包括2个全局输入端口、24个输入端口和16个输出端口；该逻辑块内部采用部分局部互连结构；该逻辑块内部局部互连是均匀分布的，逻辑块输入输出端口均匀分布在矩形逻辑块四周，逻辑单元的输入输出端口均匀地连接到逻辑块四周的端口；逻辑块内部的连接单元采用二级多路复用器。

说明书

技术领域

本发明涉及一种FPGA逻辑块，更具体地是指一种基于部分局部互连结构的FPGA逻辑块。

背景技术

现场可编程门阵列(FPGA)的用户可编程性和低开发成本使它成为实现现代电路和系统的一种重要技术。布线资源是FPGA中非常重要的一部分，原因在于布线资源占用了FPGA约84％～92％的芯片面积，其中逻辑块内部的局部互连资源占用了FPGA约26％～46％的芯片面积。因此，逻辑块内部的局部互连结构的好坏直接影响到FPGA芯片的性能。

在FPGA的设计中，一般逻辑块内部的局部互连采用完全连接的方式，即允许逻辑块的每个输入(输出)端口都能连接到所有的逻辑单元输入(输出)端口。这种高密度的连通性使得布线更加容易，但是却大大增加了对于面积的开销。因此很多商用FPGA的逻辑块内部采用部分局部互连的结构，比如Altera的Stratix系列芯片。在Stratix系列芯片中，每个逻辑单元的输入端口可以连接到一半的逻辑块输入端口和逻辑单元输出端口，形成了50％的连通度。实验数据显示这种结构减小了大约7％的面积，而布线延迟仅仅增大了1％。

目前不同FPGA厂商在逻辑块内部采用了不同结构的逻辑单元，由于逻辑单元设计的不同，逻辑块内部的局部互连结构也有着很大的不同。逻辑单元每个端口都有着不同的逻辑特性，不同特性的逻辑端口对布线资源会有不同的需求。因此在设计部分局部互连结构的时候，需要根据端口特性的差异设定不同的连通性，有些端口还需要进行特殊的设计，从而保证逻辑块内部局部互连资源的有效利用。

采用部分局部互连结构降低了逻辑块的面积，却增大了自动布线工具布线以及逻辑映射工具包装逻辑单元的难度。传统的逻辑单元包装算法基于完全局部互连结构，并没有考虑逻辑块内部布线资源的有效分配。采用完全匹配的算法来实现逻辑块内部布线资源的分配，软件的时间复杂度太高，不适合用于包装算法的实现当中。采用贪婪策略的近似算法，可以极大减小时间复杂度，比较适合在包装算法中实现。但是贪婪策略极大依赖于内部互连结构的合理设计。因此设计出适合贪婪策略的部分局部互连结构非常重要。

发明内容

本发明的目的在于，提供一种基于部分局部互连结构的FPGA逻辑块，其与完全局部互连的逻辑块结构相比，占用了更小的芯片面积。

本发明一种基于部分局部互连结构的FPGA逻辑块，其特征在于，包括：

8个逻辑单元，该逻辑单元之间采用专用的进位链连接；该逻辑单元包括12个端口，该12个端口包括5个数据输入端口、3个控制输入端口、1个时钟输入端口、3个输出端口；

42个端口，该42个端口包括2个全局输入端口、24个输入端口和16个输出端口；

该逻辑块内部采用部分局部互连结构；

该逻辑块内部局部互连是均匀分布的，逻辑块输入输出端口均匀分布在矩形逻辑块四周，逻辑单元的输入输出端口均匀地连接到逻辑块四周的端口；

逻辑块内部的连接单元采用二级多路复用器。

其中该逻辑块内部的局部互连是：

逻辑块全局输入端口与逻辑单元时钟输入端口连接；

逻辑块输入端口与逻辑单元输入端口连接；

逻辑块输出端口与逻辑单元输出端口连接；

逻辑单元输出端口与逻辑单元数据输入端口反馈连接；

所述的逻辑块全局输入端口与逻辑单元时钟输入端口连接的局部互连是采用完全连接模式，即每个逻辑单元的时钟端口连接到所有的逻辑块全局输入端口；其他的局部互连采用部分互连模式。

其中该逻辑单元的5个数据输入端口、3个控制输入端口、1个时钟输入端口到逻辑块端口中的输入端口的连通度分别是0.5、0.5、0.5、0.25、0.25、0.25、0.25、0.25、0.25。

其中逻辑单元的3个输出端口到逻辑块输出端口的连通度均为0.5。

其中逻辑单元的3个输出端口到逻辑单元数据输入端口的连通度分别是0.25、0.5、0.5。

其中所述的二级多路复用器使用NMOS传输管作为开关单元，在SMIC 0.13 CMOS工艺条件下，NMOS传输管的栅宽是0.13微米。

附图说明

为进一步说明本发明的具体技术内容以下结合实施例及附图详细说明如后，其中：

图1示出的是逻辑块端口分布图。

图2示出的是逻辑单元结构图。

图3示出的是逻辑块输入端口到逻辑单元输入端口的互连图(控制和时钟端口互连结构调节前)。

图4示出的是逻辑块输入端口到逻辑单元输入端口的互连图(控制和时钟端口互连结构调节后)。

图5示出的是进位链互连图。

图6示出的是二级多路复用器拓扑结构图。

图7示出的是逻辑块输入端口数目对FPGA面积的影响趋势图。

具体实施方式

请参阅图1、图2和图3所示，本发明一种基于部分局部互连结构的FPGA逻辑块，包括：

8个逻辑单元43(图3中)，该逻辑单元43之间采用专用的进位链连接；该逻辑单元43包括12个端口，该12个端口包括5个数据输入端口46、3个控制输入端口47、1个时钟输入端口CK、3个输出端口48；

42个端口42(图1中)，该42个端口10包括2个全局输入端口、24个输入端口和16个输出端口；

该逻辑块内部采用部分局部互连结构；

该逻辑块内部局部互连是均匀分布的，逻辑块输入输出端口均匀分布在矩形逻辑块四周，逻辑单元43的输入输出端口均匀地连接到逻辑块四周的端口42；

其中该逻辑块内部的局部互连是：

逻辑块全局输入端口与逻辑单元43时钟输入端口CK连接(图2中)；

逻辑块输入端口与逻辑单元43输入端49连接；

逻辑块输出端口与逻辑单元43输出端48连接；

逻辑单元输出端口与逻辑单元43数据输入端口46反馈连接；

所述的逻辑块全局输入端口与逻辑单元43时钟输入端口CK连接的局部互连是采用完全连接模式，即每个逻辑单元43的时钟端口CK连接到所有的逻辑块全局输入端口；其他的局部互连采用部分互连模式。

其中该逻辑单元43的5个数据输入端口46、3个控制输入端口47、1个时钟输入端口CK到逻辑块端口42中的输入端口的连通度分别是0.5、0.5、0.5、0.25、0.25、0.25、0.25、0.25、0.25。

其中逻辑单元43的3个输出端口4到逻辑块输出端口的连通度均为0.5。

其中逻辑单元43的3个输出端口48到逻辑单元数据输入端口46的连通度分别是0.25、0.5、0.5。

逻辑块内部的连接单元采用二级多路复用器50。

其中所述的二级多路复用器50使用NMOS传输管51作为开关单元，在SMIC 0.13 CMOS工艺条件下，NMOS传输管51的栅宽是0.13微米。

在下文中，通过参照附图以及表格，本发明的实例将被详细地描述。但是，本发明可以以许多不同的形式加以实施，并不应限定于这里给出的实例，该实例的提供是为了使本公开是彻底的和完整的，并且向熟悉本领域的人员全面地传达本发明的思想。

参照图1，逻辑块四周分散有42个端口42，其中包括2个全局输入端口、24个输入端口和16个输出端口。其中输入输出端口均匀分布在矩形逻辑块四周。均匀分布的设计能够均衡逻辑块对四周布线通道的需求，避免布线通道的局部拥塞。

参照图2，逻辑块中采用的逻辑单元43由两个三输入查找表44和一个触发器45组成。两个查找表44既可以独立工作，也可以合并成为一个四输入查找表。逻辑单元43包括数据输入端口A0、A1、A2、A3、B、控制输入端口CE、SR、REV、时钟输入端CK、输出端口XB、XF、XQ。

逻辑块内部的局部互连分成四个部分：

(1)，逻辑块全局输入端口与逻辑单元43时钟端口CK之间的连接；

(2)，逻辑块输入端口与逻辑单元43输入端口49之间的连接；

(3)，逻辑块输出端口与逻辑单元43输出端口48之间的连接；

(4)，逻辑单元输出端口与逻辑单元43数据输入端口46之间的反馈连接；

局部互连(1)采用完全连接模式，即每个逻辑单元43的时钟端口CK连接到所有的逻辑块全局输入端口。前述的局部互连(2)(3)(4)采用部分互连模式。局部互连结构中端口间的连接密度被称为连通度。完全连接模式中，每个端口到其他端口的连通度均为100％。逻辑单元43输入端口A0、A1、A2、A3、B、CK、CE、SR、REV到逻辑块输入端口的连通度分别是0.5、0.5、0.5、0.25、0.25、0.25、0.25、0.25、0.25。逻辑单元43输出端口XB、XF、XQ到逻辑块输出端口的连通度均为0.5。逻辑单元43输出端口XB、XF、XQ到逻辑单元43数据输入端口46的连通度分别是0.25、0.5、0.5。

参照图3，逻辑块包括8个逻辑单元43，逻辑单元43输入端口49到逻辑块输入端口的部分局部互连是均匀分布的，逻辑单元43的输入输出端口均匀地连接到逻辑块四周的端口，其他类型的部分互连同样采用均匀分布的方式。均匀分布的设计保证了逻辑单元43的输入输出信号能够从逻辑块的四周进出，增加了布线的自由度。同时均匀分布的设计减少了基于贪婪策略的逻辑单元包装算法对某些逻辑块端口的偏袒，增加了逻辑块端口42的有效使用率。

逻辑块输入输出端口的数目根据以下分析得出。由于进位链的存在，逻辑块的输入输出端口有最小数目的限制。长度为8个逻辑单元43的进位链最多使用到20个逻辑块输入端口和16个逻辑块输出端口。因此逻辑块输入输出端口的最小数目分别是20和16。为了保证输入输出端口能够均匀地分布在逻辑块四周(参照图1)，逻辑块输入输出端口的数目应该设定为4的倍数。参照图7，当逻辑块输入端口数目为24的时候，FPGA的面积最小，因此逻辑块输入端口的数目确定为24。其中FPGA的面积是根据ITC‘99的30个基准电路经过布线之后得出的平均面积(按照最小要求的沟道宽度计算)，参考的是SMIC 0.13 CMOS工艺，逻辑单元所有端口的连通度均设定为0.5。采用同样的分析可以确定逻辑块的最佳输出端口数目是16，即最小输出端口数，这是由于逻辑块的输出端口并不存在共享特性，最少的输出端口能够获得最小的FPGA面积。逻辑块全局输入端口的数目设定为2，一个逻辑块中最多只允许使用两个不同的全局时钟，实验表明这种安排是合理的，因为同一个逻辑块中的逻辑单元采用不同时钟的概率是很小的。

参照表1，逻辑单元43各个端口的使用率有很大的差别。表1是根据ITC‘99的30个基准电路经过逻辑映射之后得出的统计结果，其中不包括全局信号所占用的连接。根据统计结果发现，逻辑单元43数据输入端口46使用率远远超过控制和时钟端口。逻辑单元43数据输入端口46中A0、A1、A2的使用率最高，而A3、B的使用率相对较小。逻辑单元43控制端口47和时钟端口CK中CE使用率最高，而其他端口使用率都很低。因此在分析各个输入端口连通度的时候，应该适当降低使用率低的端口的连通度。逻辑单元43的输出端口48中XB相对XF、XQ的使用率很低，按照前面的方法，应该降低XB的连通度。但是实验表明基于贪婪策略的包装算法在各个输出端口连通度相同的情况下能够获得最好的结果，因此在选择各个输出端口连通度的时候，应该使它们的值保持一致。对于逻辑块中逻辑单元43之间的反馈互连，从表1可以看出，不存在XB到B的连接，应该取消反馈互连中XB到B的连接。取消所有连接到控制端口47和时钟端口CK的反馈，因为这种反馈在实际电路中极少出现。同一逻辑单元43中连接到XB和XF的反馈属于组合循环(combinational cycle)，在反馈互连中也被取消。

逻辑单元43各个端口的连通度根据实验分析得出。其分析方法与逻辑块输入端口数目的分析方法相似。采用ITC‘99基准电路，分析连通度对芯片面积以及关键路径延迟的影响，从中选取最佳值。

参照图4，在图3的基础上对逻辑单元43控制端口47和时钟端口CK的互连结构进行了调节。充分利用了控制及时钟信号的共享特性，减少了逻辑块输入端口的数目。为逻辑单元43每种类型的控制端口47和时钟端口CK分配了一个专用的逻辑块输入端口，分别是：逻辑端口0-＞CE、逻辑端口1-＞SR、逻辑端口2-＞REV、逻辑端口3-＞CK。保留专用端口与逻辑单元43数据输入端口46的连接，取消专用端口与非所属类型控制端口47和时钟端口CK的连接，并且增加额外连接以保证该端口连接到所有其所属类型的控制端口47或时钟端口CK。例如，为逻辑单元43控制端口CE分配了一个专用的逻辑块输入端口0，逻辑块输入端口0与逻辑单元43数据输入端口46之间的互连结构保持不变，取消逻辑块输入端口0与所有逻辑单元43的SR、REV、CK端口的连接，增加额外连接保证逻辑块输入端口0连接到所有逻辑单元43的CE端口。

参照图5，逻辑单元43之间的CO和CI端口通过专用进位链互相连接。每个逻辑单元43的CO端口与相邻上侧的逻辑单元43的CI端口直接相连。芯片顶端逻辑单元43的CO端口与相邻右侧底端逻辑单元43的CI端口直接相连。专用的进位链连接允许相邻逻辑单元43串联在一起，加快了逻辑块之间的连接，并且节省了逻辑块内部的局部互连资源。

参照图6，逻辑块内部局部互连结构中使用二级多路复用器50作为其连接单元。使用NMOS传输管51作为开关单元，在SMIC 0.13 CMOS工艺条件下，NMOS传输管51的栅宽是0.13微米。使用SPICE对不同级数多路复用器50的时序延迟进行分析，同时考虑器件面积，结果表明二级多路复用器50具有最佳综合性能。

虽然参照示范性的实施例详细地描述了本发明，但是那些熟悉本领域的技术人员将了解，在不脱离所附的权利要求的情况下，在形式和细节上可以就此做出各种变化。