技术领域technical field
本发明涉及集成电路计算机辅助设计技术领域，特别涉及一种基于三维重聚的三维现场可编程门阵列的分层设计方法及系统。The invention relates to the technical field of computer-aided design of integrated circuits, in particular to a hierarchical design method and system of a three-dimensional field programmable gate array based on three-dimensional reunion.
背景技术Background technique
目前，由于晶体管的尺寸已很难再减小，因此电路的集成度很难再通过传统的方法进一步得到提高。人们开始通过其它途径来解决这一问题。随着芯片设计需求的提高与制造工艺的发展，为了进一步降低互连线延迟，提高芯片集成度和性能，“三维芯片”的设计技术应时而生，并逐步成为集成电路设计领域的研究热点。作为一类特殊的芯片，FPGA（Field Programmable Gate Array，现场可编程门阵列）也向着三维的方向快速发展。3DFPGA（Three Dimensional Field-Programmable Gate Array，三维现场可编程门阵列）芯片设计是将多层传统的2D FPGA芯片集成到同一个芯片中，形成一种多个二维芯片的垂直叠放结构。在这种结构中，不同层芯片间仍保持着联系，而这种联系是通过TSV（Through-Si-Via，硅穿孔）来实现的。作为一个具体的例子，如图1所示，为一种3D FPGA芯片的结构。At present, since it is difficult to reduce the size of transistors, it is difficult to further improve the integration level of circuits through traditional methods. People began to solve this problem in other ways. With the improvement of chip design requirements and the development of manufacturing technology, in order to further reduce the delay of interconnect lines and improve the integration and performance of chips, the design technology of "3D chip" has emerged in time, and has gradually become a research hotspot in the field of integrated circuit design. As a special kind of chip, FPGA (Field Programmable Gate Array, Field Programmable Gate Array) is also developing rapidly towards three-dimensional direction. 3DFPGA (Three Dimensional Field-Programmable Gate Array, three-dimensional field programmable gate array) chip design is to integrate multiple layers of traditional 2D FPGA chips into the same chip to form a vertical stacking structure of multiple two-dimensional chips. In this structure, different layers of chips are still connected, and this connection is realized through TSV (Through-Si-Via, through-silicon via). As a specific example, as shown in FIG. 1 , it is a structure of a 3D FPGA chip.
图1a显示的是传统2D FPGA芯片的结构，其中包括了CLB（Configurable-Logic-Block，可配置逻辑模块）以及用于实现CLB之间互联的CB（Connection-Box，连接组件）和SB（Switching-Bo，开关组件）。图1b显示了3D FPGA芯片的结构，即多片2D FPGA的堆叠。为了实现不同层之间CLB的互联，部分传统的SB被扩展到三维空间，即3D-SB。每个3D-SB中都有固定数目的TSV，用于不同层间信号的传播。Figure 1a shows the structure of a traditional 2D FPGA chip, which includes CLB (Configurable-Logic-Block, configurable logic module) and CB (Connection-Box, connection component) and SB (Switching -Bo, switch component). Figure 1b shows the structure of a 3D FPGA chip, that is, a stack of multiple slices of 2D FPGA. In order to realize the interconnection of CLBs between different layers, some traditional SBs are extended to three-dimensional space, that is, 3D-SB. There are a fixed number of TSVs in each 3D-SB for the propagation of signals between different layers.
然而，无论是对于传统的2D FPGA芯片还是3D FPGA芯片，在设计流程中，布局和布线都是极其重要的两步。布局决定要用到哪些CLB，而布线决定要用到哪些CB和SB。但是与二维芯片不同的是，对于三维芯片来说，除了布局布线，设计流程中还包括另一个重要步骤：分层。由于三维芯片是由多层二维芯片堆叠而成的，在其设计中需要解决各功能模块应当被分配到哪层的问题，而分层就是解决这一问题的过程。However, whether it is for a traditional 2D FPGA chip or a 3D FPGA chip, placement and routing are two extremely important steps in the design process. Placement determines which CLBs are used, and routing determines which CBs and SBs are used. But unlike two-dimensional chips, for three-dimensional chips, in addition to layout and routing, the design process also includes another important step: layering. Since a three-dimensional chip is formed by stacking multiple layers of two-dimensional chips, it is necessary to solve the problem of which layer each functional module should be allocated to in its design, and layering is the process of solving this problem.
目前3D FPGA设计领域绝大部分分层的算法都是基于最小割的，即尽量减少不同层之间的联系。减少了不同层间的联系也就意味着减少了FPGA芯片中TSV的使用量。但是对于3D FPGA芯片来说，相应的TSV数量是制造时已经固定的，因此简单的以减少TSV数量的分层方法有其局限性。首先，分层的过程与布局布线是密切联系的，好的分层结果使得 之后的布局布线变得容易，差的结果使之变得困难，甚至无法得到合理的布局布线结果，而最小割并没有将分层与FPGA设计中的其它步骤联系起来，因此很难得到好的分层结果。其次，如图1b图所示，TSV在FPGA中是在设计前就已经确定的资源，即无论是TSV的数量还是其位置在设计前都是已知的，因此在设计时无论用没用到，TSV都存在于FPGA中。实际上，目前3DFPGA芯片中TSV的利用率还是很低的。At present, most of the layered algorithms in the field of 3D FPGA design are based on the minimum cut, that is, to minimize the connection between different layers. Reducing the connection between different layers means reducing the usage of TSV in the FPGA chip. However, for 3D FPGA chips, the corresponding number of TSVs is fixed during manufacture, so the simple layering method to reduce the number of TSVs has its limitations. First of all, the layering process is closely related to layout and routing. A good layering result makes subsequent layout and routing easier, while a poor result makes it difficult, and even a reasonable layout and routing result cannot be obtained. The minimum cut union Without linking layering to other steps in the FPGA design, it is difficult to get good layering results. Secondly, as shown in Figure 1b, TSV is a resource that has been determined before design in FPGA, that is, both the number and location of TSV are known before design, so whether it is used or not during design , TSVs all exist in the FPGA. In fact, the utilization rate of TSVs in 3DFPGA chips is still very low.
发明内容Contents of the invention
本发明旨在至少解决上述技术问题之一。The present invention aims to solve at least one of the above-mentioned technical problems.
为此，本发明的一个目的在于提出一种基于三维重聚的三维现场可编程门阵列的分层设计方法，该方法具有高效、可靠的优点，能够优化分层及布局的流程，并且改善分层及优化结果的线长和时延，且该方法实现简单、可移植性高。For this reason, an object of the present invention is to propose a layered design method of a three-dimensional field programmable gate array based on three-dimensional reassembly, which has the advantages of high efficiency and reliability, can optimize the process of layering and layout, and improve the The line length and delay of the layer and the optimization result, and the method is simple to implement and has high portability.
本发明的另一目的在于提供一种基于三维重聚的三维现场可编程门阵列的分层设计系统。Another object of the present invention is to provide a hierarchical design system of a three-dimensional field programmable gate array based on three-dimensional regrouping.
为了实现上述目的，本发明第一方面的实施例提出了一种基于三维重聚的三维现场可编程门阵列的分层设计方法，包括以下步骤：根据期望映射到三维现场可编程门阵列上的目标电路所包括的多个功能模块建立超图；对所述超图进行分析以获取所述超图中的重聚信息；根据所述重聚信息得到所述超图中的超边划分时对应的权重；根据所述权重将所述超图划分为多个层；以及将划分后的超图中的多个功能模块分别对应地布置到所述三维现场可编程门阵列的多个层中。In order to achieve the above object, the embodiment of the first aspect of the present invention proposes a hierarchical design method of a three-dimensional field programmable gate array based on three-dimensional reunion, including the following steps: A plurality of functional modules included in the target circuit establish a hypergraph; analyze the hypergraph to obtain reunion information in the hypergraph; obtain the hyperedge division in the hypergraph corresponding to weights; divide the hypergraph into multiple layers according to the weights; and correspondingly arrange multiple functional modules in the divided hypergraph into multiple layers of the three-dimensional field programmable gate array.
根据本发明实施例的基于三维重聚的三维现场可编程门阵列的分层设计方法，基于三维重聚，为期望映射到三维现场可编程门阵列上的目标电路建立超图，并对超图进行分析以获取超图中的重聚信息，再根据重聚信息计算得到超图中超边划分时对应的权重，并据此将超图划分为需要的多个层，最后将划分后的超图中包括的多个功能模块分别对应地分配到划分好的多个层中。因此，该方法能够为三维现场可编程门阵列提供更好的分层结果，以便于更好的布局，从而优化了分层及布局的流程，改善了分层及优化结果的线长和时延，因此，该方法具有高效、可靠的优点。另外，该方法实现简单，能够方便移植到各种面向三维现场可编程门阵列的分层设计工具中，因此，可移植性高。通过测试，本发明的方法能够更好地支持布局布线，具体例如：基于本发明的方法的分层结果进行的布局布线，对两层现场可编程门阵列能够带来7.06%的线长改善和4.86%的时延改善，对三层现场可编程门阵列能带来4.71%的线长改善和4.73%的时延改善。According to the hierarchical design method of the 3D field programmable gate array based on 3D reunion according to the embodiment of the present invention, based on the 3D reunion, a hypergraph is established for the target circuit expected to be mapped to the 3D field programmable gate array, and the hypergraph is Perform analysis to obtain the reunion information in the hypergraph, and then calculate the weight corresponding to the hyperedge division in the hypergraph according to the reunion information, and divide the hypergraph into multiple layers according to the need, and finally divide the hypergraph after division The multiple functional modules included in are correspondingly assigned to multiple divided layers. Therefore, the method can provide better layering results for 3D Field Programmable Gate Arrays for better layout, thereby optimizing the process of layering and layout, and improving the line length and delay of layering and optimization results , so this method has the advantages of high efficiency and reliability. In addition, the method is simple to implement and can be easily transplanted into various hierarchical design tools for three-dimensional field programmable gate arrays, so the method has high portability. Through testing, the method of the present invention can better support layout and wiring, specifically for example: the layout and wiring based on the layered results of the method of the present invention can bring 7.06% improvement in line length and The 4.86% delay improvement can bring 4.71% line length improvement and 4.73% delay improvement to the three-layer field programmable gate array.
另外，根据本发明上述实施例的基于三维重聚的三维现场可编程门阵列的分层设计方法还可以具有如下附加的技术特征：In addition, according to the above-mentioned embodiment of the present invention, the hierarchical design method of the three-dimensional field programmable gate array based on three-dimensional reunion may also have the following additional technical features:
在一些示例中，所述根据所述权重将所述超图划分为多个层，包括：根据分层算法将所述超图划分为多个层。In some examples, the dividing the hypergraph into multiple layers according to the weights includes: dividing the hypergraph into multiple layers according to a layering algorithm.
在一些示例中，所述分层算法为RALP算法。In some examples, the hierarchical algorithm is a RALP algorithm.
在一些示例中，所述根据所述重聚信息得到所述超图中的超边划分时对应的权重，进一步包括：如果所述超图中的重聚子图从节点X到节点Y，以及经过划分将原重聚从中间切分形成两个小重聚，其中所述两个小重聚被切点T连接，即X节点到切点T以及切点T到Y节点，则计算所述超图的超边的划分收益CBRXYij为：In some examples, the obtaining the weights corresponding to the hyperedge division in the hypergraph according to the regrouping information further includes: if the regrouped subgraph in the hypergraph is from node X to node Y, and After division, the original reunion is divided from the middle to form two small reunions, wherein the two small reunions are connected by the cut point T, that is, the X node to the cut point T and the cut point T to the Y node, then the calculation of the The division revenue CBRXYij of the hyperedge of the hypergraph is:
其中，Eij为所述超图的中连接节点i和节点j的超边，RXY表示三维重聚，此三维重聚从节点X到节点Y，p表示RXY中的从节点X到节点Y的若干路径，l(p)为p的长度，lXT(p)表示p被划分后节点X到切点T的路径长度，lTY(p)表示p被划分后切点T到节点Y的路径长度。Wherein, Eij is the hyperedge connecting node i and node j in the hypergraph, RXY represents a three-dimensional reunion, and this three-dimensional reunion is from node X to node Y, and p represents from node X to node in RXY Several paths of Y, l(p) is the length of p, lXT (p) indicates the length of the path from node X to node T after p is divided, lTY (p) indicates the length of the path from node T to node Y after p is divided the path length.
在一些示例中，所述根据所述重聚信息得到所述超图中的超边划分时对应的权重，还包括：计算所述超图中的每条边Ei的权值为：In some examples, the obtaining the weights corresponding to the hyperedge division in the hypergraph according to the regrouping information further includes: calculating the weight of each edge Ei in the hypergraph as:
其中，Wi表示边Ei的权重，如果Ei不在任何三维重聚中，Ni为0，如果Ei位于若干三维重聚中，Ni表示Ei所位于三维重聚的数目。Among them, Wi represents the weight of edge Ei , if Ei is not in any 3D reunion, Ni is 0, if Ei is in several 3D reunions, Ni represents the number of 3D reunions where Ei is located.
本发明第二方面的实施例提供了一种基于三维重聚的三维现场可编程门阵列分层设计系统，包括：超图建立模块，所述超图建立模块用于根据期望映射到三维现场可编程门阵列上的目标电路所包括的多个功能模块建立超图；重聚信息获取模块，所述重聚信息获取模块用于对所述超图进行分析以获取所述超图中的重聚信息；权重计算模块，所述权重计算模块用于根据所述重聚信息得到所述超图中的超边划分时对应的权重；分层模块，所述分层模块用于根据所述权重将所述超图划分为多个层；以及布局模块，所述布局模块用于将划分后的超图中的所述多个功能模块分别对应地布置到所述三维现场可编程门阵列的多个层中。The embodiment of the second aspect of the present invention provides a three-dimensional field programmable gate array layered design system based on three-dimensional reunion, including: a hypergraph building module, and the hypergraph building module is used to map to a three-dimensional field programmable gate array according to expectations. A plurality of functional modules included in the target circuit on the programming gate array establishes a hypergraph; a reunion information acquisition module, the reunion information acquisition module is used to analyze the hypergraph to obtain the reunion in the hypergraph information; a weight calculation module, the weight calculation module is used to obtain the weight corresponding to the hyperedge division in the hypergraph according to the re-gathering information; a layering module, the layering module is used to divide the hyperedge according to the weight The hypergraph is divided into a plurality of layers; and a layout module, the layout module is used to correspondingly arrange the plurality of functional modules in the divided hypergraph to the plurality of layers of the three-dimensional field programmable gate array. layer.
根据本发明实施例的基于三维重聚的三维现场可编程门阵列的分层设计系统，基于三维重聚，为期望映射到三维现场可编程门阵列上的目标电路建立超图，并对超图进行分析以获取超图中的重聚信息，再根据重聚信息计算得到超图中超边划分时对应的权重，并据此将超 图划分为需要的多个层，最后将划分后的超图所包括的多个功能模块分别对应地分配到划分好的多个层中。因此，该系统能够为三维现场可编程门阵列提供更好的分层结果，以便于更好的布局，从而优化了分层及布局的流程，改善了分层及优化结果的线长和时延，因此，该系统具有高效、可靠的优点。另外，该系统结构简单，且能够方便移植到各种面向三维现场可编程门阵列的分层设计工具中，因此，可移植性高。通过测试，本发明的系统能够更好地支持布局布线，具体例如：基于本发明的系统的分层结果进行的布局布线，对两层现场可编程门阵列能够带来7.06%的线长改善和4.86%的时延改善，对三层现场可编程门阵列能带来4.71%的线长改善和4.73%的时延改善。According to the hierarchical design system of three-dimensional field programmable gate array based on three-dimensional reunion according to an embodiment of the present invention, based on three-dimensional reunion, a hypergraph is established for the target circuit expected to be mapped to a three-dimensional field programmable gate array, and the hypergraph is Perform analysis to obtain the reunion information in the hypergraph, and then calculate the weight corresponding to the hyperedge division in the hypergraph according to the reunion information, and divide the hypergraph into multiple layers according to the need, and finally divide the hypergraph after division The included multiple functional modules are correspondingly assigned to multiple divided layers. Therefore, the system can provide better layering results for 3D Field Programmable Gate Arrays for better placement, thereby optimizing the process of layering and placement, and improving the line length and delay of layering and optimization results , therefore, the system has the advantages of high efficiency and reliability. In addition, the system has a simple structure and can be easily transplanted into various hierarchical design tools for three-dimensional field programmable gate arrays, so the system has high portability. Through testing, the system of the present invention can better support layout and wiring, specifically for example: the layout and wiring based on the layered results of the system of the present invention can bring 7.06% improvement in line length and The 4.86% delay improvement can bring 4.71% line length improvement and 4.73% delay improvement to the three-layer field programmable gate array.
另外，根据本发明上述实施例的基于三维重聚的三维现场可编程门阵列的分层设计系统还可以具有如下附加的技术特征：In addition, the layered design system of the three-dimensional field programmable gate array based on three-dimensional regrouping according to the above-mentioned embodiments of the present invention may also have the following additional technical features:
在一些示例中，所述分层模块用于根据分层算法将所述超图划分为多个层。In some examples, the layering module is configured to divide the hypergraph into layers according to a layering algorithm.
在一些示例中，所述分层算法为RALP算法。In some examples, the hierarchical algorithm is a RALP algorithm.
在一些示例中，如果所述超图中的重聚子图从节点X到节点Y，以及经过划分将原重聚从中间切分形成两个小重聚，其中所述两个小重聚被切点T连接，即X节点到切点T以及切点T到Y节点，则所述权重计算模块还用于计算所述超图的超边的划分收益CBRXYij为：In some examples, if the reunited subgraph in the hypergraph is from node X to node Y, and the original reunited is split from the middle after division to form two small reunited, wherein the two small reunited are The tangent point T connection, that is, the X node to the tangent point T and the tangent point T to the Y node, then the weight calculation module is also used to calculate the division revenue CBRXYij of the hyperedge of the hypergraph as:
其中，Eij为所述超图的中连接节点i和节点j的超边，RXY表示三维重聚，此三维重聚从节点X到节点Y，p表示RXY中的从节点X到节点Y的若干路径，l(p)为p的长度，lXT(p)表示p被划分后节点X到切点T的路径长度，lTY(p)表示p被划分后切点T到节点Y的路径长度。Wherein, Eij is the hyperedge connecting node i and node j in the hypergraph, RXY represents a three-dimensional reunion, and this three-dimensional reunion is from node X to node Y, and p represents from node X to node in RXY Several paths of Y, l(p) is the length of p, lXT (p) indicates the length of the path from node X to node T after p is divided, lTY (p) indicates the length of the path from node T to node Y after p is divided the path length.
在一些示例中，所述权重计算模块还用于计算所述超图中的每条边Ei为：In some examples, the weight calculation module is also used to calculate each edge Ei in the hypergraph as:
其中，Wi表示边Ei的权重，如果Ei不在任何三维重聚中，Ni为0，如果Ei位于若干三维重聚中，Ni表示Ei所位于三维重聚的数目。Among them, Wi represents the weight of edge Ei , if Ei is not in any 3D reunion, Ni is 0, if Ei is in several 3D reunions, Ni represents the number of 3D reunions where Ei is located.
本发明的附加方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。Additional aspects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention.
附图说明Description of drawings
本发明的上述和/或附加的方面和优点从结合下面附图对实施例的描述中将变得明显和容易理解，其中：The above and/or additional aspects and advantages of the present invention will become apparent and comprehensible from the description of the embodiments in conjunction with the following drawings, wherein:
图1a为传统二维FPGA芯片的结构示意图，图1b为三维FPGA芯片的结构示意图；Figure 1a is a schematic structural view of a traditional two-dimensional FPGA chip, and Figure 1b is a structural schematic view of a three-dimensional FPGA chip;
图2为根据本发明一个实施例的重聚的原理示意图；Fig. 2 is a schematic diagram of the principle of reunion according to an embodiment of the present invention;
图3为根据本发明一个实施例的基于三维重聚的三维现场可编程门阵列的分层设计方法的流程图；3 is a flow chart of a hierarchical design method for a three-dimensional field programmable gate array based on three-dimensional reunion according to an embodiment of the present invention;
图4为根据本发明一个实施例的三维重聚的原理示意图；FIG. 4 is a schematic diagram of the principle of three-dimensional refocusing according to an embodiment of the present invention;
图5a和图5b为根据本发明一个实施例的利用3DRV评估三维重聚长度的两种方案的示意图；Figure 5a and Figure 5b are schematic diagrams of two schemes for evaluating three-dimensional refocusing lengths using 3DRV according to an embodiment of the present invention;
图6为根据本发明另一个实施例的基于三维重聚的三维现场可编程门阵列的分层设计方法的流程图；6 is a flow chart of a hierarchical design method for a three-dimensional field programmable gate array based on three-dimensional reunion according to another embodiment of the present invention;
图7a和图7b为根据本发明一个实施例的基于三维重聚的三维现场可编程门阵列的分层设计方法的评估线长的两个具体例子的曲线示意图；以及Fig. 7a and Fig. 7b are the curve schematic diagrams of two specific examples of the evaluation line length of the hierarchical design method of the three-dimensional field programmable gate array based on the three-dimensional regrouping according to an embodiment of the present invention; and
图8为根据本发明一个实施例的基于三维重聚的三维现场可编程门阵列的分层设计系统的结构框图。FIG. 8 is a structural block diagram of a hierarchical design system for a 3D FPGA based on 3D regrouping according to an embodiment of the present invention.
具体实施方式detailed description
下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，而不能理解为对本发明的限制。Embodiments of the present invention are described in detail below, examples of which are shown in the drawings, wherein the same or similar reference numerals designate the same or similar elements or elements having the same or similar functions throughout. The embodiments described below by referring to the figures are exemplary only for explaining the present invention and should not be construed as limiting the present invention.
在本发明的描述中，需要理解的是，术语“中心”、“纵向”、“横向”、“上”、“下”、“前”、“后”、“左”、“右”、“竖直”、“水平”、“顶”、“底”、“内”、“外”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制。此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性。In describing the present invention, it should be understood that the terms "center", "longitudinal", "transverse", "upper", "lower", "front", "rear", "left", "right", " The orientations or positional relationships indicated by "vertical", "horizontal", "top", "bottom", "inner" and "outer" are based on the orientations or positional relationships shown in the drawings, and are only for the convenience of describing the present invention and Simplified descriptions, rather than indicating or implying that the device or element referred to must have a particular orientation, be constructed and operate in a particular orientation, and thus should not be construed as limiting the invention. In addition, the terms "first" and "second" are used for descriptive purposes only, and should not be understood as indicating or implying relative importance.
在本发明的描述中，需要说明的是，除非另有明确的规定和限定，术语“安装”、“相连”、“连接”应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或一体地连接；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通。对于本领域的普通技术人员而言，可以具体情况理解上述术语在本发明中的具体含义。In the description of the present invention, it should be noted that unless otherwise specified and limited, the terms "installation", "connection" and "connection" should be understood in a broad sense, for example, it can be a fixed connection or a detachable connection. Connected, or integrally connected; it may be mechanically connected or electrically connected; it may be directly connected or indirectly connected through an intermediary, and it may be the internal communication of two components. Those of ordinary skill in the art can understand the specific meanings of the above terms in the present invention in specific situations.
以下结合附图描述根据本发明实施例的基于三维重聚的三维现场可编程门阵列的分层 设计方法及系统。A hierarchical design method and system for a three-dimensional field programmable gate array based on three-dimensional refocusing according to an embodiment of the present invention will be described below in conjunction with the accompanying drawings.
图2为根据本发明一个实施例的基于三维重聚的三维现场可编程门阵列的分层设计方法的流程图。如图2所示，根据本发明一个实施例的基于三维重聚的三维现场可编程门阵列的分层设计方法，其中，重聚（例如记为RXY）是指存在于电路中的一种现象，即一个功能模块X输出的信息经过若干线网后在另一个功能模块Y又重新汇聚在一起，重聚是用来在布局之前评估线网长度的。重聚值RVXY是指RXY的平均路径长度，即FIG. 2 is a flow chart of a hierarchical design method for a 3D FPGA based on 3D regrouping according to an embodiment of the present invention. As shown in Figure 2, according to an embodiment of the present invention, a hierarchical design method of a three-dimensional field programmable gate array based on three-dimensional reunion, wherein reunion (for example, denoted as RXY ) refers to a kind of Phenomenon, that is, the information output by a functional module X passes through several nets and then gathers together again in another functional module Y. The reunion is used to evaluate the length of nets before layout. The reunion value RVXY refers to the average path length of RXY , i.e.
其中，p为RXY的任意一条路径，l(p)即为该路径的长度，N表示RXY中所有的路径条数。Among them, p is any path of RXY , l(p) is the length of the path, and N represents the number of all paths in RXY .
作为一个具体的例子，结合图3所示，表示一个具体的重聚RAF。即功能模块A的输出信号在经过不同的路径后在功能模块F处又重新汇聚到一起，而其平均路径长度（即重聚值）用来评估线网长度，也即图3中的重聚值RVAF=(3+3)/2=3。As a specific example, a specific re-aggregated RAF is shown in conjunction with Fig. 3 . That is, the output signals of functional module A converge together again at functional module F after going through different paths, and its average path length (ie, the reconvergence value) is used to evaluate the wire network length, that is, the reconvergence in Figure 3 The value RVAF =(3+3)/2=3.
进一步地，如果重聚RXY被分为两部分，则在RXY中加入一个新的结点，记为切点T，然后将之与RXY中相应功能模块相连。其中，T表示的是RXY被分布于不同层上所需要的TSV（硅穿孔）。综上所述，三维重聚即就是由切点T连接的多个小的普通的重聚。Further, if the reunited RXY is divided into two parts, a new node is added in RXY , which is recorded as the cut point T, and then it is connected with the corresponding functional module in RXY . Among them, T represents the TSV (through silicon via) required for RXY to be distributed on different layers. To sum up, the three-dimensional reunion is a plurality of small common reunions connected by the tangent point T.
具体而言，上述的基于三维重聚的三维现场可编程门阵列的分层设计方法包括以下步骤：Specifically, the above-mentioned hierarchical design method of a three-dimensional field programmable gate array based on three-dimensional reunion includes the following steps:
步骤S201，根据期望映射到三维现场可编程门阵列上的目标电路所包括的多个功能模块建立超图。具体而言，超图表示的就是目标电路，是对目标电路的一种抽象。其中，超图的超边表示电路的线网，超图的顶点表示电路的功能模块。期望映射到三维现场可编程门阵列3D FPGA上的目标电路包括多个功能模块，由于这些功能模块会分布在三维现场可编程门阵列3D FPGA的不同层上，因此，其原本的重聚结构也会被打开。在超图中，被打开的重聚会被表示为若干小重聚Rij，而这些小重聚分别由虚边与表示TSV（硅穿孔）的虚点相连。将上述若干个小重聚Rij中最大的重聚值max{RVij}作为整个三维重聚值3D-RVXY，用来评估线长。In step S201, a hypergraph is established according to multiple functional modules included in a target circuit expected to be mapped onto a three-dimensional field programmable gate array. Specifically, the hypergraph represents the target circuit, which is an abstraction of the target circuit. Among them, the hyperedge of the hypergraph represents the line network of the circuit, and the vertices of the hypergraph represent the functional modules of the circuit. It is expected that the target circuit mapped to the 3D FPGA includes multiple functional modules. Since these functional modules will be distributed on different layers of the 3D FPGA, the original reunion structure is also will be opened. In the hypergraph, the opened reunions are represented as several small reunions Rij , and these small reunions are respectively connected by virtual edges to virtual points representing TSVs (through-silicon vias). The largest refocusing value max{RVij } among the above several small refocusing Rij is used as the whole three-dimensional refocusing value 3D-RVXY to evaluate the line length.
作为一个具体示例，例如：As a concrete example, such as:
步骤S202，对超图进行分析以获取超图中的重聚信息。具体而言，该步骤即对超图进行分析，并找出超图中所有重聚。对于那些被打开的重聚，找到其相应的小重聚Rij，并得到每个小重聚Rij的重聚值及所有重聚值中的最大值。Step S202, analyzing the hypergraph to obtain reunion information in the hypergraph. Specifically, this step is to analyze the hypergraph and find all reunions in the hypergraph. For those opened reunions, find their corresponding small reunions Rij , and obtain the reunion value of each small reunion Rij and the maximum value among all reunion values.
作为一个具体的示例，结合图4所示，重聚RAF在分层时边AB、DE被打开，则功能模块A和D被划分在一层，而功能模块B、C、E和F则被分在另外一层，此处用3D RAF表示该三维重聚。另一方面，三维重聚用来评估其线长的参数即为三维重聚值3DRV，其大小等于组成这个三维重聚的若干个小重聚的重聚值中的最大值。具体例如：As a specific example, as shown in Figure 4, when the re-aggregated RAF is layered, the edges AB and DE are opened, then the functional modules A and D are divided into one layer, and the functional modules B, C, E and F are is divided into another layer, and the three-dimensional reassembly is represented by 3D RAF here. On the other hand, the parameter used to evaluate the line length of the 3D reunion is the 3D reunion value 3DRV, which is equal to the maximum value among the reunion values of several small reunions that make up the 3D reunion. For example:
其中T1、T2…TK分别表示将RXY划分产生的多个切点。Among them, T1, T2...TK represent multiple tangent points generated by dividing RXY respectively.
也就是说，上述图4中的三维重聚3D RAF的三维重聚值可表示为：That is, the three-dimensional refocusing value of the three-dimensionally refocused 3D RAF in Figure 4 above can be expressed as:
作为另一个具体地示例，图5说明了3DRV的确可以评估三维重聚长度。如图5a和图5b所示的两个不同的3D-RAF，其布局布线后最短线长分别为6和5。而图5a中3D RVAF=max{1,7/3}=7/3，图5b中3D RVAF=max{5/3,5/3}=5/3。因此，符合实际最短线长a要大于b。As another concrete example, Fig. 5 illustrates that 3DRV can indeed evaluate the three-dimensional refocusing length. For two different 3D-RAFs shown in Figure 5a and Figure 5b, the shortest line lengths after placement and routing are 6 and 5, respectively. While 3D RVAF =max{1,7/3}=7/3 in Figure 5a, and 3D RVAF =max{5/3,5/3}=5/3 in Figure 5b. Therefore, the actual shortest line length a is greater than b.
步骤S203，根据重聚信息得到超图中的超边划分时对应的权重。Step S203, according to the regrouping information, the weights corresponding to the hyperedge division in the hypergraph are obtained.
具体而言，由于3DRV可以评估线网长度，且3DRV越大，其长度越长，因此在分层时需满足在3D FPGA芯片TSV数量的限制下，尽量减小电路网表中的平均3DRV。具体做法如下：Specifically, since 3DRV can evaluate the length of the wire net, and the larger the 3DRV, the longer its length, so it is necessary to minimize the average 3DRV in the circuit netlist under the limitation of the number of TSVs of the 3D FPGA chip when layering. The specific method is as follows:
为每条线网计算其切割收益（Cut-Benefit，CB）。具体而言，电路网表可以抽象为一张超图，在这个超图中，其顶点表示功能模块，超边表示线网。假设边Eij位于RXY的路径p中。如果在分层时Eij被切，则根据3DRV计算公式，在计算3DRVXY时，路径p的长度不再是l(p)，而是max{lXT(p)，lTY(p)}。因此，通过切边Eij，对于p来说min{l(p)-lXT(p)，l(p)-lTY(p)}的收益。类似的，对于超图中的超边Eij的划分收益CBRXYij可通过下式计算：Calculate the cutting benefit (Cut-Benefit, CB) for each wire net. Specifically, the circuit netlist can be abstracted as a hypergraph. In this hypergraph, its vertices represent functional modules, and hyperedges represent line nets. Assume edge Eij lies on path p of RXY . If Eij is cut during layering, according to the 3DRV calculation formula, when calculating 3DRVXY , the length of path p is no longer l(p), but max{lXT (p), lTY (p)} . Thus, by cutting edge Eij , for p there is a payoff of min{l(p)-lXT (p), l(p)-lTY (p)}. Similarly, the division revenue CBRXYij of hyperedge Eij in the hypergraph can be calculated by the following formula:
其中，Eij为所述超图的中连接节点i和节点j的超边，RXY表示三维重聚，此三维重聚从节点X到节点Y，p表示RXY中的从节点X到节点Y的若干路径，l(p)为p的长度，lXT(p)表示p被划分后节点X到切点T的路径长度，lTY(p)表示p被划分后切点T到节点Y的路径长度。Wherein, Eij is the hyperedge connecting node i and node j in the hypergraph, RXY represents a three-dimensional reunion, and this three-dimensional reunion is from node X to node Y, and p represents from node X to node in RXY Several paths of Y, l(p) is the length of p, lXT (p) indicates the length of the path from node X to node T after p is divided, lTY (p) indicates the length of the path from node T to node Y after p is divided the path length.
另外，在本发明的一个实施例中，由于FPGA中每个CLB（可配置逻辑模块，也即功能模块）的大小一致，因此，对超图中每个顶点都设置相同的权重1，而每个超边的权重计算则是基于上述计算得到的收益CBRXYij。由于本发明实施例的方法期望切割边来获得最大的 收益，因此每条边Ei的权值可通过下式计算：In addition, in one embodiment of the present invention, since the size of each CLB (configurable logic module, that is, a function module) in the FPGA is consistent, the same weight 1 is set for each vertex in the hypergraph, and each The weight calculation of a hyperedge is based on the income CBRXYij obtained from the above calculation. Since the method of the embodiment of the present invention expects to cut the edge to obtain the maximum benefit, the weight of each edge Ei can be calculated by the following formula:
其中，Wi表示边Ei的权重，如果Ei不在任何三维重聚中，Ni为0，如果Ei位于若干三维重聚中，Ni表示Ei所位于三维重聚的数目。Among them, Wi represents the weight of edge Ei , if Ei is not in any 3D reunion, Ni is 0, if Ei is in several 3D reunions, Ni represents the number of 3D reunions where Ei is located.
步骤S204，根据权重将超图划分为多个层。具体而言，在设置好超图的超边划分时对应的权重后，便可据此对超图进行分层。Step S204, divide the hypergraph into multiple layers according to weights. Specifically, after the weights corresponding to the hyperedge division of the hypergraph are set, the hypergraph can be layered accordingly.
在本发明的一个实施例中，根据分层算法将超图划分为多个层，更为具体地，分层算法通过递归调用通用的图划分工具（例如hmetis算法）进行层划分。其中，上述的分层算法为但不限于RALP（Reconvergence-Aware-Layer-Partitioning）。In one embodiment of the present invention, the hypergraph is divided into multiple layers according to a layering algorithm. More specifically, the layering algorithm performs layer division by recursively invoking a general graph division tool (such as the hmetis algorithm). Wherein, the above-mentioned layering algorithm is but not limited to RALP (Reconvergence-Aware-Layer-Partitioning).
换言之，即在设置好超图中顶点和超边的权值之后，分层算法RALP便可通过递归调用hmetis对超图进行层划分，可将其换分为任意期望的层数。作为一个具体的例子，如果期望将超图划分为三层，则首先将其划分为二层，其中一层为原电路的三分之一大小，另一层为原电路的三分之二大小；然后再次调用hmetis对三分之二大小的那一层进行层次划分，将其划分为相等的两层，从而可获得大小均为原电路的三分之一大小的三个字电路，也即将超图分为三层。In other words, after setting the weights of the vertices and hyperedges in the hypergraph, the layering algorithm RALP can divide the hypergraph into layers by recursively calling hmetis, which can be divided into any desired number of layers. As a specific example, if it is desired to divide the hypergraph into three layers, first divide it into two layers, one of which is one-third the size of the original circuit, and the other is two-thirds the size of the original circuit ; Then call hmetis again to divide the two-thirds of the layer into two equal layers, so as to obtain three word circuits whose size is one-third of the original circuit, that is, The hypergraph is divided into three layers.
步骤S205，将划分后的超图中的多个功能模块分别对应地布置到三维现场可编程门阵列的多个层中。即在对超图分层完成之后，还需进一步将其包括的多个功能模块对应地布置到3D FPGA中的每层上，并决定层之间布局的顺序。其中，在将多个功能模块布置对应到相应层时，需以尽量减少不同层之间的联系为原则，通过枚举所有可能，以选择最优方案。In step S205, a plurality of functional modules in the divided hypergraph are correspondingly arranged in a plurality of layers of a three-dimensional field programmable gate array. That is, after the layering of the hypergraph is completed, it is necessary to further arrange the multiple functional modules it includes on each layer of the 3D FPGA correspondingly, and determine the order of layout between layers. Among them, when arranging multiple functional modules corresponding to the corresponding layers, it is necessary to minimize the connection between different layers as a principle, and to select the optimal solution by enumerating all possibilities.
在上述示例中，由于三维重聚反映了不同层之间有直接联系的功能模块，而影响不同层布局质量的原因是功能模块布局时受到其它层相关模块的制约，因此，在布局时首先要根据三维重聚来决定层次布局的顺序。作为一个具体示例，例如首先定义3D-RiXY和3D-Ri，其中，3D-RiXY表示3D-RXY中位于第i层的功能模块数量，3D-Ri表示对整个3D-FPGA的电路来说，划分层后位于第i层并属于三维重聚的功能模块数量。In the above example, since the three-dimensional reunion reflects the functional modules with direct connections between different layers, the reason for affecting the layout quality of different layers is that the layout of functional modules is restricted by other related modules in other layers. Therefore, the layout must first The order of the hierarchical layout is determined according to the three-dimensional reunion. As a specific example, for example, first define 3D-RiXY and 3D-Ri, wherein, 3D-RiXY represents the number of functional modules located in the i-th layer in 3D-RXY , and 3D-Ri represents the circuit of the entire 3D-FPGA That is, the number of functional modules located in the i-th layer and belonging to the three-dimensional reunion after layer division.
综上所述，在层次布局时，层次布局顺序取决于3D-Ri，且其值越大，则越应该先布局，从而可以减少再布局其他层时由这些层带来的矛盾。To sum up, in layer layout, the layer layout order depends on 3D-Ri, and the larger its value is, the more it should be laid out first, which can reduce the contradictions caused by these layers when laying out other layers.
作为一个具体的示例，上述的根据本发明实施例的基于三维重聚的三维现场可编程门阵列的分层设计方法，可结合图6所示的流程图简单的进行描述。具体包括以下步骤：As a specific example, the above-mentioned layered design method of a 3D FPGA based on 3D regrouping according to an embodiment of the present invention can be simply described in conjunction with the flow chart shown in FIG. 6 . Specifically include the following steps:
步骤S601，输入网表。网表即电路网表，电路网表反映了期望映射到3D FPGA上的目 标电路的电路连接。Step S601, inputting a netlist. The netlist is the circuit netlist, and the circuit netlist reflects the circuit connections expected to be mapped to the target circuit on the 3D FPGA.
步骤S602，建立超图并分析重聚信息。即完成超图的建立及重聚信息的分析。具体而言，根据上述输入的电路网表，为其建立超图，其中超图的顶点表示功能模块，超边表示电路网表中的线网。进一步地，对得到的超图进行分析，以获取超图中的重聚信息，更为具体地，即根据超图找出超图中所有的重聚。Step S602, building a hypergraph and analyzing the reunion information. That is, the establishment of the hypergraph and the analysis of the reunion information are completed. Specifically, according to the above-mentioned input circuit netlist, a hypergraph is established for it, wherein the vertices of the hypergraph represent functional modules, and the hyperedges represent the nets in the circuit netlist. Further, the obtained hypergraph is analyzed to obtain reunion information in the hypergraph, more specifically, all reunions in the hypergraph are found out according to the hypergraph.
步骤S603，计算线网权重。也即根据上述得到的重聚信息计算超图中的超边划分时对应的权重。Step S603, calculating the weight of the line net. That is, the weight corresponding to the hyperedge division in the hypergraph is calculated according to the above-mentioned obtained reunion information.
步骤S604，调用hmetis完成划分。即根据上述得到的权重，调用hmetis对超图进行分层。Step S604, calling hmetis to complete the division. That is, according to the weight obtained above, call hmetis to layer the hypergraph.
步骤S605，判断划分后结果的数量是否为期望的层数？即判断上述完成分层后的层数是否等于期望划分的层数，如果是，则执行步骤S607，否则执行步骤S606。Step S605, judging whether the number of divided results is the expected number of layers? That is, it is judged whether the above-mentioned number of layers after layering is equal to the number of layers expected to be divided, if yes, execute step S607, otherwise execute step S606.
步骤S606，分析三维重聚信息。即在分层结果的数量不等于（即小于）期望的层数时，重新分析三维重聚信息，并返回执行步骤S603。Step S606, analyzing the three-dimensional refocusing information. That is, when the number of layered results is not equal to (that is, smaller than) the expected number of layers, re-analyze the three-dimensional refocusing information, and return to step S603.
步骤S607，进行层分配。即在分层结果的数量等于期望的层数后，进一步将划分后的超图包括的功能模块对应地分配到3D FPGA相应的层上。Step S607, perform layer allocation. That is, after the number of layered results is equal to the expected number of layers, further assign the functional modules included in the divided hypergraph to corresponding layers of the 3D FPGA.
步骤S308，布局布线。即对每层中的功能模块及层与层之间进行布局布线。Step S308, layout and wiring. That is, the layout and routing are performed on the functional modules in each layer and between layers.
步骤S309，输出结果。Step S309, outputting the result.
为了验证本发明上述实施例的基于三维重聚的三维现场可编程门阵列的分层设计方法的有效性。作为一个具体的示例，通过用C++语言实现了本发明的上述方法，即基于三维重聚的3D FPGA的分层设计方法，并把它嵌入到学术界普遍使用的3D FPGA设计流程中。如果该方法是有效的，则同样的测试电路，对于同样的3D FPGA，经过这个新的流程后得到的结果，与原流程得到的结果相比应该是更优的。测试的结果恰恰符合这个期望。测试的平台为：操作系统Red Hat Enterprise Linux6；CPU Intel Core i5-2410M；内存1G。测试面向的3D FPGA主要分为两种：两层的FPGA和三层的FPGA。这两种3D FPGA中3D-SB（开关组件）的分布都是交错式的，即每两个3D-SB中间还有一个普通的2D-SB。每个3D-SB中TSV（硅穿孔）的数量是20。依据学术界普遍使用的20个电路例子中随机选择9个来做测试。需要强调的是，在测试中，包含本发明的流程（即实验结果表格中的RALP一栏）和原始流程（即实验结果表格中的TPR一栏）相比，两者除了分层的过程不同外，其它实验过程及实验对象一律相同。In order to verify the validity of the hierarchical design method of the 3D FPGA based on the 3D regrouping in the above-mentioned embodiments of the present invention. As a specific example, the above-mentioned method of the present invention, that is, the hierarchical design method of 3D FPGA based on three-dimensional reunion, is realized by using C++ language, and it is embedded into the 3D FPGA design flow generally used in the academic circle. If the method is effective, then the same test circuit, for the same 3D FPGA, the results obtained after this new process should be better than the results obtained by the original process. The results of the test were exactly in line with this expectation. The tested platform is: operating system Red Hat Enterprise Linux6; CPU Intel Core i5-2410M; memory 1G. There are mainly two types of 3D FPGAs for testing: two-layer FPGAs and three-layer FPGAs. The distribution of 3D-SB (switch components) in these two 3D FPGAs is interleaved, that is, there is an ordinary 2D-SB in the middle of every two 3D-SBs. The number of TSVs (Through Silicon Vias) in each 3D-SB is 20. According to the 20 circuit examples commonly used in academia, 9 are randomly selected for testing. It should be emphasized that, in the test, compared with the original process (that is, the column of TPR in the experimental result table) that includes the process of the present invention (that is, the RALP column in the experimental result table), the two are different except for the process of layering Other than that, the other experimental procedures and subjects were the same.
实验结果如下表一和表二所示：The experimental results are shown in Table 1 and Table 2 below:
表一表示两层FPGA的实验结果：Table 1 shows the experimental results of the two-layer FPGA:
表一Table I
表二表示三层FPGA的实验结果：Table 2 shows the experimental results of the three-layer FPGA:
表二Table II
综上，上述两个表说明了本发明实施例的方法虽然会多用TSV，但其数量依然满足FPGA芯片中TSV数量限制，与此同时测试结果在线长和时延方面都有明显改善，因此，可验证本发明实施例的方法的有效性。In summary, the above two tables show that although the method of the embodiment of the present invention will use more TSVs, the number still meets the limit on the number of TSVs in the FPGA chip. At the same time, the test results have significantly improved in terms of line length and delay. Therefore, The validity of the method of the embodiment of the present invention can be verified.
另一方面，为了确定本发明中三维重聚的确可以评估线网长度，以下对具体的例子alu4和des分别进行10次实验，记录布局后的线长和布局前平均的3DRV。数据如下表三所示：On the other hand, in order to confirm that the 3D reunion in the present invention can indeed evaluate the line network length, the following specific examples of alu4 and des were subjected to 10 experiments respectively, and the line length after layout and the average 3DRV before layout were recorded. The data are shown in Table 3 below:
表三Table three
根据上述数据绘制成折线图如图7所示。通过表三和图7所示，线长和3DRV的趋势是一致的，从而验证三维重聚可以评估线网的长度。Based on the above data, a line chart is drawn as shown in Figure 7. As shown in Table 3 and Figure 7, the trends of line length and 3DRV are consistent, thus verifying that 3D reconvergence can evaluate the length of line network.
下表四中的数据显示了本发明的方法中分层算法的速度，与布局布线相比，分层的过程所占的时间不足总过程时间的1%，从而表明本发明实施例的分层设计方法在分层时是十分快速的。各个过程的运行时间如表四所示：The data in the following table 4 shows the speed of the layering algorithm in the method of the present invention, compared with layout and wiring, the time occupied by the layered process is less than 1% of the total process time, thereby showing the layering of the embodiment of the present invention Design methods are very fast when layered. The running time of each process is shown in Table 4:
表四Table four
综上所述，本发明上述的基于三维重聚的三维现场可编程门阵列的分层设计方法有以下几个优点：In summary, the above-mentioned layered design method of the three-dimensional field programmable gate array based on the three-dimensional reunion of the present invention has the following advantages:
1、创造性的定义了三维重聚，可以评估面相3D FPGA的电路线网长度。1. The three-dimensional reunion is creatively defined, which can evaluate the circuit net length of a 3D FPGA.
2、该设计方法采用的分层算法能够更好的融入整个3D FPGA设计流程中，提供了更好的分层结果，从而优化了整个流程，改善了最终分层及布局结果的线长和时延。2. The layering algorithm used in this design method can be better integrated into the entire 3D FPGA design process, providing better layering results, thereby optimizing the entire process, and improving the line length and time of the final layering and layout results delay.
3、该设计方法的思路简单，能够方便的移植到各种面向3D FPGA的设计工具中，即移植性高，且计算速度快。3. The idea of the design method is simple, and it can be easily transplanted to various 3D FPGA-oriented design tools, that is, it has high portability and fast calculation speed.
根据本发明实施例的基于三维重聚的三维现场可编程门阵列的分层设计方法，为期望映射到三维现场可编程门阵列上的目标电路建立超图，并对超图进行分析以获取超图中的重聚信息，再根据重聚信息计算得到超图中超边划分时对应的权重，并据此将超图划分为需要的多个层，最后将划分后超图包括的多个功能模块分别对应地分配到划分好的多个层中。因此，该方法能够为三维现场可编程门阵列提供更好的分层结果，以便于更好的布局，从而优化了 分层及布局的流程，改善了分层及优化结果的线长和时延，因此，该方法具有高效、可靠的优点。另外，该方法实现简单，能够方便移植到各种面向三维现场可编程门阵列的分层设计工具中，因此，可移植性高。通过测试，本发明的方法能够更好地支持布局布线，具体例如：基于本发明的方法的分层结果进行的布局布线，对两层现场可编程门阵列能够带来7.06%的线长改善和4.86%的时延改善，对三层现场可编程门阵列能带来4.71%的线长改善和4.73%的时延改善。According to the hierarchical design method of 3D FPGAs based on 3D reunion in the embodiment of the present invention, a hypergraph is established for the target circuit expected to be mapped to a 3D FPGA, and the hypergraph is analyzed to obtain a supergraph. The re-aggregation information in the graph, and then calculate the weight corresponding to the hyper-edge division in the hyper-graph according to the re-aggregation information, and then divide the hyper-graph into the required layers, and finally divide the multiple functional modules included in the hyper-graph Correspondingly allocated to multiple divided layers. Therefore, the method can provide better layering results for 3D Field Programmable Gate Arrays for better layout, thereby optimizing the process of layering and layout, and improving the line length and delay of layering and optimization results , so this method has the advantages of high efficiency and reliability. In addition, the method is simple to implement and can be easily transplanted into various hierarchical design tools for three-dimensional field programmable gate arrays, so the method has high portability. Through testing, the method of the present invention can better support layout and wiring, specifically for example: the layout and wiring based on the layered results of the method of the present invention can bring 7.06% improvement in line length and The 4.86% delay improvement can bring 4.71% line length improvement and 4.73% delay improvement to the three-layer field programmable gate array.
本发明还提供了一种基于三维重聚的现场可编程门阵列分层设计系统。The invention also provides a field programmable gate array layered design system based on three-dimensional recombination.
图8为根据本发明一个实施例的基于三维重聚的现场可编程门阵列分层设计系统的结构框图。如图8所示，根据本发明一个实施例的基于三维重聚的现场可编程门阵列分层设计系统800，包括：超图建立模块810、重聚信息获取模块820、权重计算模块830、分层模块840和布局模块850。FIG. 8 is a structural block diagram of a hierarchical design system for FPGAs based on three-dimensional regrouping according to an embodiment of the present invention. As shown in FIG. 8 , according to an embodiment of the present invention, a FPGA hierarchical design system 800 based on three-dimensional reunion includes: a hypergraph establishment module 810, a reunion information acquisition module 820, a weight calculation module 830, a layer module 840 and layout module 850 .
其中，超图建立模块810用于根据期望映射到三维现场可编程门阵列（3D FPGA）上的目标电路所包括的多个功能模块建立超图。Wherein, the hypergraph building module 810 is used for building a hypergraph according to multiple functional modules included in a target circuit expected to be mapped onto a three-dimensional field programmable gate array (3D FPGA).
具体而言，期望映射到三维现场可编程门阵列3D FPGA的目标电路包括多个功能模块，用超图表示时，超边表示的是电路中的线网，顶点表示的是电路中的功能模块。由于不同的功能模块会分布在不同层上，因此，其原本的重聚结构也会被打开，这些被打开的重聚在超图中被表示为若干个小重聚Rij，并将这些小重聚用虚边和虚点连接起来。进一步地，将上述若干个小重聚Rij中最大的重聚值max{RVij}作为整个三维重聚值3D-RXY，用来评估线长。Specifically, the target circuit that is expected to be mapped to a 3D FPGA includes multiple functional modules. When represented by a hypergraph, the hyperedge represents the network in the circuit, and the vertices represent the functional modules in the circuit. . Since different functional modules will be distributed on different layers, their original reunion structures will also be opened, and these opened reunions are expressed as several small reunions Rij in the hypergraph, and these small reunions Regathers are connected with imaginary edges and imaginary points. Further, the largest refocusing value max{RVij } among the above several small refocusing Rij is used as the whole three-dimensional refocusing value 3D-RXY to evaluate the line length.
作为一个具体示例，例如：As a concrete example, such as:
重聚信息获取模块820用于对超图进行分析以获取超图中的重聚信息。具体而言，即重聚信息获取模块820对超图进行分析，并找出超图中所有重聚，对于那些被打开的重聚，找到其包括的小重聚Rij，并得到每个小重聚Rij的重聚值及所有重聚值中的最大值。The reunion information acquisition module 820 is configured to analyze the hypergraph to acquire reunion information in the hypergraph. Specifically, the reunion information acquisition module 820 analyzes the hypergraph, and finds out all reunions in the hypergraph, and for those opened reunions, finds the small reunions Rij included in them, and obtains The reunited value of reunited Rij and the maximum value among all reunited values.
权重计算模块830用于根据上述重聚信息获取模块820得到的重聚信息计算得到超图中的超边划分时对应的权重。具体而言，由于3DRV可以评估线网长度，且3DRV越大，其长度越长，因此在分层时需满足在3D FPGA芯片TSV（硅穿孔）数量的限制下，尽量减小电路网表中的平均3DRV。具体做法如下：The weight calculation module 830 is configured to calculate the weight corresponding to the hyperedge division in the hypergraph according to the regroup information obtained by the above regroup information acquisition module 820 . Specifically, since 3DRV can evaluate the length of the wire net, and the larger the 3DRV, the longer its length, so when layering, it is necessary to meet the limitation of the number of TSVs (through-silicon vias) in the 3D FPGA chip and minimize the number of wires in the circuit netlist. The average 3DRV. The specific method is as follows:
为每条线网计算其切割收益（Cut-Benefit，CB）。具体而言，电路网表可以抽象为一张超图，在这个超图中，其顶点表示功能模块，超边表示线网。假设边Eij位于RXY的路径p中。如果在分层时Eij被切，则根据3DRV计算公式，在计算3DRVXY时，路径p的长度不再是l(p)，而是max{lXT(p)，lTY(p)}。因此，通过切边Eij，对于p来说min{l(p)-lXT(p)，l(p)-lTY(p)} 的收益。类似的，在本发明的一个实施例中，如果所述超图中的重聚子图从节点X到节点Y，以及经过划分将原重聚从中间切分形成两个小重聚，其中所述两个小重聚被切点T连接，即X节点到切点T以及切点T到Y节点，则权重计算模块830还用于对超图中的超边Eij的划分收益CBRXYij通过下式进行计算：Calculate the cutting benefit (Cut-Benefit, CB) for each wire net. Specifically, the circuit netlist can be abstracted as a hypergraph. In this hypergraph, its vertices represent functional modules, and hyperedges represent line nets. Assume edge Eij lies on path p of RXY . If Eij is cut during layering, according to the 3DRV calculation formula, when calculating 3DRVXY , the length of path p is no longer l(p), but max{lXT (p), lTY (p)} . Thus, by cutting edge Eij , the payoff for p is min{l(p)-lXT (p), l(p)-lTY (p)}. Similarly, in one embodiment of the present invention, if the re-aggregation subgraph in the hypergraph is from node X to node Y, and the original re-aggregation is divided from the middle to form two small re-aggregations, wherein The above two small reunions are connected by the tangent point T, that is, the X node to the tangent point T and the tangent point T to the Y node, then the weight calculation module 830 is also used to divide the income CBRXYij of the hyperedge Eij in the hypergraph It is calculated by the following formula:
其中，Eij为所述超图的中连接节点i和节点j的超边，RXY表示三维重聚，此三维重聚从节点X到节点Y，p表示RXY中的从节点X到节点Y的若干路径，l(p)为p的长度，lXT(p)表示p被划分后节点X到切点T的路径长度，lTY(p)表示p被划分后切点T到节点Y的路径长度。Wherein, Eij is the hyperedge connecting node i and node j in the hypergraph, RXY represents a three-dimensional reunion, and this three-dimensional reunion is from node X to node Y, and p represents from node X to node in RXY Several paths of Y, l(p) is the length of p, lXT (p) indicates the length of the path from node X to node T after p is divided, lTY (p) indicates the length of the path from node T to node Y after p is divided the path length.
另外，在本发明的一个实施例中，由于FPGA中每个CLB（可配置逻辑模块，也即功能模块）的大小一致，因此，对超图中每个顶点都设置相同的权重1，而每个超边的权重计算则是基于上述计算得到的收益CBRXYij。由于本发明的系统期望切割边来获得最大的收益，因此权重计算模块830还用于对每条边Ei的权值通过下式计算：In addition, in one embodiment of the present invention, since the size of each CLB (configurable logic module, that is, a function module) in the FPGA is consistent, the same weight 1 is set for each vertex in the hypergraph, and each The weight calculation of a hyperedge is based on the income CBRXYij obtained from the above calculation. Since the system of the present invention expects to cut the edge to obtain the maximum benefit, the weight calculation module 830 is also used to calculate the weight of each edge Ei by the following formula:
其中，Wi表示边Ei的权重。如果Ei不在任何三维重聚中，Ni为0，如果Ei位于若干三维重聚中，Ni表示Ei所位于三维重聚的数目。Among them, Wi represents the weight of edge Ei . If Ei is not in any three-dimensional cluster, Ni is 0, if Ei is in several three-dimensional clusters, Ni represents the number of three-dimensional clusters where Ei is located.
分层模块840用于根据上述得到的权重将超图划分为多个层。更为具体地，在本发明的一个实施例中，分层模块840根据分层算法将超图划分为多个层。其中，该分层算法例如为但不限于RALP（Reconvergence-Aware-Layer-Partitioning）算法。具体而言，在权重计算模块830计算出超图的超边划分时对应的权重后，分层模块840便可据此对超图进行分层。在本发明的一个实施例中，分层模块根据分层算法RALP将超图划分为多个层，更为具体地，RALP算法通过递归调用通用的图划分工具（例如hmetis算法）进行层划分。The layering module 840 is used to divide the hypergraph into multiple layers according to the weights obtained above. More specifically, in one embodiment of the present invention, the layering module 840 divides the hypergraph into multiple layers according to a layering algorithm. Wherein, the layering algorithm is, for example, but not limited to RALP (Reconvergence-Aware-Layer-Partitioning) algorithm. Specifically, after the weight calculation module 830 calculates the weight corresponding to the hyperedge division of the hypergraph, the layering module 840 can layer the hypergraph accordingly. In one embodiment of the present invention, the layering module divides the hypergraph into multiple layers according to the layering algorithm RALP. More specifically, the RALP algorithm divides layers by recursively calling a general graph partitioning tool (such as the hmetis algorithm).
换言之，在设置好超图中顶点和超边的权值之后，分层模块840根据分层算法RALP便可通过递归调用hmetis对超图进行层划分，可将其划分为任意期望的层数。作为一个具体的例子，如果期望将超图划分为三层，则首先将其划分为二层，其中一层为原电路的三分之一大小，另一层为原电路的三分之二大小；然后再次调用hmetis对三分之二大小的那一层进行层次划分，将其划分为相等的两层，从而可获得大小均为原电路的三分之一大小的三个字电 路，也即将超图分为三层。In other words, after setting the weights of vertices and hyperedges in the hypergraph, the layering module 840 can divide the hypergraph into any desired number of layers by recursively calling hmetis according to the layering algorithm RALP. As a specific example, if it is desired to divide the hypergraph into three layers, first divide it into two layers, one of which is one-third the size of the original circuit, and the other is two-thirds the size of the original circuit ; Then call hmetis again to divide the two-thirds of the layer into two equal layers, so as to obtain three word circuits whose size is one-third of the original circuit, that is, The hypergraph is divided into three layers.
布局模块850用于将划分后超图包括的多个功能模块分别对应地布置到三维现场可编程门阵列的多个层中。即在分层模块840对超图分层完成之后，布局模块850还需进一步将超图包括的多个功能模块对应地布置到3D FPGA中的每层上，并决定层之间布局的顺序。其中，在将多个功能模块布置对应到相应层时，需以尽量减少不同层之间的联系为原则，通过枚举所有可能，以选择最优方案。The layout module 850 is used to correspondingly arrange multiple functional modules included in the divided hypergraph into multiple layers of the three-dimensional field programmable gate array. That is, after the layering module 840 completes the layering of the hypergraph, the layout module 850 needs to further arrange the multiple functional modules included in the hypergraph correspondingly on each layer in the 3D FPGA, and determine the order of layout between layers. Among them, when arranging multiple functional modules corresponding to the corresponding layers, it is necessary to minimize the connection between different layers as a principle, and to select the optimal solution by enumerating all possibilities.
在上述示例中，由于三维重聚反映了不同层之间有直接联系的功能模块，而影响不同层布局质量的原因是功能模块布局时受到其它层相关模块的制约，因此，布局模块850在布局时首先要根据三维重聚来决定层次布局的顺序。作为一个具体示例，例如首先定义3D-RiXY和3D-Ri，其中，3D-RiXY表示3D-RXY中位于第i层的功能模块数量，3D-Ri表示对整个3D-FPGA的电路来说，划分层后位于第i层并属于三维重聚的功能模块数量。In the above example, because the three-dimensional reunion reflects the functional modules that are directly related between different layers, the reason that affects the layout quality of different layers is that the layout of the functional modules is restricted by other layer-related modules. Therefore, the layout module 850 in the layout At first, the order of hierarchical layout should be determined according to the three-dimensional reunion. As a specific example, for example, first define 3D-RiXY and 3D-Ri, wherein, 3D-RiXY represents the number of functional modules located in the i-th layer in 3D-RXY , and 3D-Ri represents the circuit of the entire 3D-FPGA That is, the number of functional modules located in the i-th layer and belonging to the three-dimensional reunion after layer division.
综上所述，在层次布局时，层次布局顺序取决于3D-Ri，且其值越大，则越应该先布局，从而可以减少再布局其他层时由这些层带来的矛盾。To sum up, in layer layout, the layer layout order depends on 3D-Ri, and the larger its value is, the more it should be laid out first, which can reduce the contradictions caused by these layers when laying out other layers.
根据本发明实施例的基于三维重聚的三维现场可编程门阵列的分层设计系统，基于三维重聚，为期望映射到三维现场可编程门阵列上的目标电路建立超图，并对超图进行分析以获取超图中的重聚信息，再根据重聚信息计算得到超图中超边划分时对应的权重，并据此将超图划分为需要的多个层，最后将划分后超图包括的多个功能模块分别对应地分配到多个层中。因此，该系统能够为三维现场可编程门阵列提供更好的分层结果，以便于更好的布局，从而优化了分层及布局的流程，改善了分层及优化结果的线长和时延，因此，该系统具有高效、可靠的优点。另外，该系统结构简单，且能够方便移植到各种面向三维现场可编程门阵列的分层设计工具中，因此，可移植性高。通过测试，本发明的系统能够更好地支持布局布线，具体例如：基于本发明的系统的分层结果进行的布局布线，对两层现场可编程门阵列能够带来7.06%的线长改善和4.86%的时延改善，对三层现场可编程门阵列能带来4.71%的线长改善和4.73%的时延改善。According to the hierarchical design system of three-dimensional field programmable gate array based on three-dimensional reunion according to an embodiment of the present invention, based on three-dimensional reunion, a hypergraph is established for the target circuit expected to be mapped to a three-dimensional field programmable gate array, and the hypergraph is Carry out analysis to obtain the reunion information in the hypergraph, and then calculate the weight corresponding to the hyperedge division in the hypergraph according to the reunion information, and divide the hypergraph into multiple layers according to the need, and finally divide the hypergraph into A plurality of functional modules are correspondingly assigned to a plurality of layers. Therefore, the system can provide better layering results for 3D Field Programmable Gate Arrays for better placement, thereby optimizing the process of layering and placement, and improving the line length and delay of layering and optimization results , therefore, the system has the advantages of high efficiency and reliability. In addition, the system has a simple structure and can be easily transplanted into various hierarchical design tools for three-dimensional field programmable gate arrays, so the system has high portability. Through testing, the system of the present invention can better support layout and wiring, specifically for example: the layout and wiring based on the layered results of the system of the present invention can bring 7.06% improvement in line length and The 4.86% delay improvement can bring 4.71% line length improvement and 4.73% delay improvement to the three-layer field programmable gate array.
在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。In the description of this specification, descriptions referring to the terms "one embodiment", "some embodiments", "example", "specific examples", or "some examples" mean that specific features described in connection with the embodiment or example , structure, material or characteristic is included in at least one embodiment or example of the present invention. In this specification, schematic representations of the above terms do not necessarily refer to the same embodiment or example. Furthermore, the specific features, structures, materials or characteristics described may be combined in any suitable manner in any one or more embodiments or examples.
尽管已经示出和描述了本发明的实施例，本领域的普通技术人员可以理解：在不脱离本发明的原理和宗旨的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由权利要求及其等同限定。Although the embodiments of the present invention have been shown and described, those skilled in the art can understand that various changes, modifications, substitutions and modifications can be made to these embodiments without departing from the principle and spirit of the present invention. The scope of the invention is defined by the claims and their equivalents.
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201310714658.4ACN103678817B (en) | 2013-12-20 | 2013-12-20 | Layered design method based on the three-dimensional three-dimensional field programmable gate array met again |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201310714658.4ACN103678817B (en) | 2013-12-20 | 2013-12-20 | Layered design method based on the three-dimensional three-dimensional field programmable gate array met again |
| Publication Number | Publication Date |
|---|---|
| CN103678817A CN103678817A (en) | 2014-03-26 |
| CN103678817Btrue CN103678817B (en) | 2017-05-31 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201310714658.4AExpired - Fee RelatedCN103678817B (en) | 2013-12-20 | 2013-12-20 | Layered design method based on the three-dimensional three-dimensional field programmable gate array met again |
| Country | Link |
|---|---|
| CN (1) | CN103678817B (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN108959656A (en)* | 2018-08-13 | 2018-12-07 | 电子科技大学 | A kind of three-dimensional mapping synchronous method of more FPGA multichannel collecting systems |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN108595748B (en)* | 2018-03-09 | 2022-08-09 | 电子科技大学 | Three-dimensional topological structure of antifuse Field Programmable Gate Array (FPGA) |
| CN109033580A (en)* | 2018-07-11 | 2018-12-18 | 中国矿业大学(北京) | A kind of Layer assignment method applied to three dimensional integrated circuits |
| CN112183007B (en)* | 2020-09-28 | 2023-07-04 | 上海思尔芯技术股份有限公司 | Design segmentation method for multiple FPGAs |
| CN115000704B (en)* | 2022-06-22 | 2024-04-12 | 中国电子科技集团公司第二十九研究所 | A hierarchical calculation two-dimensional phased array beam control method and system |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5675500A (en)* | 1994-10-18 | 1997-10-07 | International Business Machines Corporation | Multi-chip device partitioning process |
| US7437695B1 (en)* | 2004-03-03 | 2008-10-14 | Xilinx, Inc. | Method of memory and run-time efficient hierarchical timing analysis in programmable logic devices |
| CN101373492A (en)* | 2008-05-04 | 2009-02-25 | 清华大学 | Three-dimensional chip thermal vias and white space redistribution method for performance optimization |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5675500A (en)* | 1994-10-18 | 1997-10-07 | International Business Machines Corporation | Multi-chip device partitioning process |
| US7437695B1 (en)* | 2004-03-03 | 2008-10-14 | Xilinx, Inc. | Method of memory and run-time efficient hierarchical timing analysis in programmable logic devices |
| CN101373492A (en)* | 2008-05-04 | 2009-02-25 | 清华大学 | Three-dimensional chip thermal vias and white space redistribution method for performance optimization |
| Title |
|---|
| Fast Placement for Large-scale Hierarchical FPGAs;Dai H, etc.;《Computer-Aided Design and Computer Graphics, 2009. CAD/Graphics 09. 11th IEEE International Conference on. IEEE》;20091231;第191-192页* |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN108959656A (en)* | 2018-08-13 | 2018-12-07 | 电子科技大学 | A kind of three-dimensional mapping synchronous method of more FPGA multichannel collecting systems |
| CN108959656B (en)* | 2018-08-13 | 2021-03-30 | 电子科技大学 | Three-dimensional mapping synchronization method of multi-FPGA multi-channel acquisition system |
| Publication number | Publication date |
|---|---|
| CN103678817A (en) | 2014-03-26 |
| Publication | Publication Date | Title |
|---|---|---|
| CN103678817B (en) | Layered design method based on the three-dimensional three-dimensional field programmable gate array met again | |
| KR102423040B1 (en) | Method for generating three-dimensional integrated circuit design | |
| US9064077B2 (en) | 3D floorplanning using 2D and 3D blocks | |
| CN111753482B (en) | Layout method of multi-die structure FPGA with automatic IO distribution | |
| CN111753484B (en) | A layout method of multi-die structure FPGA based on circuit performance | |
| US9922151B2 (en) | 3D circuit design method | |
| WO2013155969A1 (en) | Scanning and testing method based on three-dimensional chips | |
| JP2021514506A (en) | How to Select Routing Resources in Multi-Chip Integrated Circuit Devices | |
| Huang et al. | Layer-aware design partitioning for vertical interconnect minimization | |
| Minz et al. | Block-level 3-D global routing with an application to 3-D packaging | |
| CN111027274B (en) | Three-dimensional chip layout method | |
| Ebrahimi et al. | NoD: Network-on-Die as a standalone NoC for heterogeneous many-core systems in 2.5 D ICs | |
| Jagtap et al. | A methodology for early exploration of TSV placement topologies in 3D stacked ICs | |
| Halavar et al. | Accurate performance analysis of 3d mesh network on chip architectures | |
| Pangracious et al. | Designing a 3D tree-based FPGA: Optimization of butterfly programmable interconnect topology using 3D technology | |
| Ravichandran et al. | Physical layout automation for system-on-packages | |
| Minz et al. | Thermal and crosstalk-aware physical design for 3d system-on-package | |
| KR20120091497A (en) | Method for synthesizing tile interconnection structure of field programmable gate array | |
| Pangracious et al. | Exploration environment for 3D heterogeneous tree-based FPGA architectures (3D HT-FPGA) | |
| Pangracious et al. | Architecture level optimization of 3-dimensional tree-based FPGA | |
| Shanthi et al. | Thermal Aware Floorplanner for Multi-Layer ICs with Fixed-Outline Constraints | |
| Tsai et al. | A study on the trade-off among wirelength, number of TSV and placement with different size of TSV | |
| Joseph | Networks-on-Chip for heterogeneous 3D Systems-on-Chip | |
| Li et al. | Layout-aware multiple scan tree synthesis for 3-D SoCs | |
| Minz et al. | Layer assignment for reliable system-on-package |
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee | ||
| CF01 | Termination of patent right due to non-payment of annual fee | Granted publication date:20170531 Termination date:20171220 |