技术领域technical field
本发明涉及集成电路设计领域，尤其涉及一种FPGA（Field Programmable GateArray，现场可编程门阵列）总体布局合法化方法。The invention relates to the field of integrated circuit design, in particular to an FPGA (Field Programmable Gate Array, Field Programmable Gate Array) overall layout legalization method.
背景技术Background technique
FPGA采用了逻辑单元阵列LCA（Logic Cell Array）这样一个概念，内部包括可配置逻辑模块CLB（Configurable Logic Block）、输入输出模块IOB（Input Output Block）和内部连线（Interconnect）等部分。现场可编程门阵列（FPGA）是可编程器件，与传统逻辑电路和门阵列（如PAL可编程阵列逻辑，GAL门阵列逻辑及CPLD复杂可编程逻辑器件）相比，FPGA具有不同的结构。FPGA利用小型查找表（16×1RAM）来实现组合逻辑，每个查找表连接到一个D触发器的输入端，触发器再来驱动其他逻辑电路或驱动I/O，由此构成了既可实现组合逻辑功能又可实现时序逻辑功能的基本逻辑单元模块，这些模块间利用金属连线互相连接或连接到I/O模块。FPGA的逻辑是通过向内部静态存储单元加载编程数据来实现的，存储在存储器单元中的值决定了逻辑单元的逻辑功能以及各模块之间或模块与I/O间的连接方式，并最终决定了FPGA所能实现的功能，FPGA允许无限次的编程。FPGA adopts the concept of logic cell array LCA (Logic Cell Array), which includes configurable logic module CLB (Configurable Logic Block), input and output module IOB (Input Output Block) and internal wiring (Interconnect) and other parts. Field programmable gate array (FPGA) is a programmable device. Compared with traditional logic circuits and gate arrays (such as PAL programmable array logic, GAL gate array logic and CPLD complex programmable logic devices), FPGA has a different structure. FPGA uses a small look-up table (16×1RAM) to implement combinatorial logic, each look-up table is connected to the input of a D flip-flop, and the flip-flop drives other logic circuits or drives I/O, thus forming a combinatorial The logic function can also realize the basic logic unit module of the sequential logic function, and these modules are connected to each other or to the I/O module by metal wires. The logic of the FPGA is realized by loading programming data to the internal static storage unit. The value stored in the memory unit determines the logic function of the logic unit and the connection mode between modules or between modules and I/O, and finally determines the The functions that FPGA can realize, FPGA allows unlimited programming.
典型FPGA的开发流程一般包含功能定义、器件选型、设计输入、功能仿真、综合优化、综合后仿真、布局、布线、后仿真、板级仿真以及芯片编程与调试等主要步骤。The development process of a typical FPGA generally includes main steps such as function definition, device selection, design input, function simulation, synthesis optimization, post-synthesis simulation, layout, wiring, post-simulation, board-level simulation, and chip programming and debugging.
如图1所示，显示了布局在整个芯片物理设计中所处的位置，其输入是打包之后网表信息、芯片的约束信息和用户自定义的约束信息，包括写在用户约束文件（UserConstraint File，简写UCF）中的物理约束及写在新思科技设计约束文件（SynopsysDesign Constraint，简写SDC）中的时延约束，输出是布局之后的网表，供自动布线器进行布线。As shown in Figure 1, it shows the location of the layout in the entire physical design of the chip. The input is the packaged netlist information, chip constraint information and user-defined constraint information, including the constraints written in the user constraint file (UserConstraint File , abbreviated as UCF) and the delay constraints written in the Synopsys Design Constraint (abbreviated as SDC), the output is the netlist after layout for the automatic router to route.
如图2所示，FPGA芯片的自动化布局包含以下步骤：输入输出布局，全局时钟布局，初始布局，总体布局，合法化布局和详细布局。As shown in Figure 2, the automatic layout of FPGA chips includes the following steps: input and output layout, global clock layout, initial layout, general layout, legalized layout and detailed layout.
输入输出布局：摆放电路中的输入输出模块，根据芯片的物理约束（电压、电平等）随机将所有IOB摆放到指定的位置上，即构建一个整数规划问题，通过求解整数规划问题获得最优的输入输出布局，如果不能获得最优解，报相关的错误。Input and output layout: arrange the input and output modules in the circuit, randomly place all the IOBs in the designated positions according to the physical constraints of the chip (voltage, level, etc.), that is, construct an integer programming problem, and obtain the optimal solution by solving the integer programming problem Optimal input and output layout, if the optimal solution cannot be obtained, a related error will be reported.
时钟布局：如果电路用到的时钟线网多于每个时钟区域支持的不同时钟的数目时，需把时钟线网驱动的单元模块进行位置的预分配，这些单元模块分配到指定的时钟区域内，保证整个电路的时钟线网不出现拥挤，这样布线器才能顺利进行。Clock layout: If the circuit uses more clock nets than the number of different clocks supported by each clock region, it is necessary to pre-allocate the positions of the unit modules driven by the clock net, and allocate these unit modules to the specified clock region , to ensure that the clock line network of the entire circuit is not crowded, so that the router can proceed smoothly.
初始布局：根据已经摆放好输出模块的位置及时钟区域约束，构建二次线长的目标约束问题，并采用预优处理的共轭梯度法对其求解，即获得所有单元模块的初始位置，其不依赖于布局的初始解，从而获得线长最短的布局。Initial layout: According to the position of the output module that has been placed and the constraints of the clock area, construct the target constraint problem of the secondary line length, and use the pre-optimized conjugate gradient method to solve it, that is, obtain the initial positions of all unit modules, It does not depend on the initial solution of the layout, so as to obtain the layout with the shortest line length.
总体布局：根据所有单元模块的初始位置和电路的拓扑连接，构建近似于半周长的目标约束问题，并采用基于混合步长调整策略的共轭梯度法求解，针对不同级别的模块，布局的状态，动态调整步长的计算方式，总体分布单元模块。总体布局之后，单元模块总体分布是十分均匀的，但局部存在重叠的单元模块。Overall layout: According to the initial position of all unit modules and the topological connection of the circuit, construct a target constraint problem that is approximately half-perimeter, and use the conjugate gradient method based on the hybrid step size adjustment strategy to solve it. For different levels of modules, the state of the layout , the calculation method of dynamically adjusting the step size, and the overall distribution unit module. After the overall layout, the overall distribution of unit modules is very uniform, but there are overlapping unit modules locally.
合法化布局：总体布局之后，在整个FPGA芯片上，单元模块分布的相对均匀，但其仍然是浮点坐标，要将其近距离移动到合法的整数的位置上，保证单元模块不存在重叠，且单元移动到的位置与这个单元的类型要相互兼容，这步是总体布局之后必须的步骤。Legalized layout: After the overall layout, the unit modules are relatively evenly distributed on the entire FPGA chip, but they are still floating-point coordinates. It is necessary to move them to the positions of legal integers at a close distance to ensure that the unit modules do not overlap. And the position to which the unit is moved must be compatible with the type of the unit. This step is a necessary step after the overall layout.
详细布局：总体布局并没有保证局部的最优性，合法化布局进一步破坏了局部的最优解，所以需进行详细布局，弥补前两步对局部布局造成的破坏。详细布局基于低温模拟退火的方法，近距离的移动或者交换两个单元模块，优化局部区域的布局。Detailed layout: The overall layout does not guarantee local optimality, and the legalized layout further destroys the local optimal solution. Therefore, detailed layout is required to make up for the damage caused by the first two steps to the local layout. The detailed layout is based on the low-temperature simulated annealing method, moving or exchanging two unit modules at close range to optimize the layout of the local area.
每部分布局之后，可以衡量下当前布局的状态，如果发现其不可继续往下执行别的部分，需返回到前面的部分，重新调整执行整个布局流程。After each part of the layout, you can measure the status of the current layout. If you find that you cannot continue to execute other parts, you need to return to the previous part and readjust and execute the entire layout process.
布局是整个流程中比较费时的一步，其将逻辑网表中的硬件原语和底层单元合理地配置到芯片内部的固有硬件结构上，并且往往需要在速度最优和面积最优之间做出选择。目前，FPGA的规模越来越大，结构越来越复杂，其中逻辑单元模块的类型越来越多，且包含像DSP和RAM这种大的逻辑单元，并且有些单元之间的走线都是固定连接，如进位链（carry chain）和移位寄存器（shift register）等等，这些都限制了逻辑单元的随意摆放，特别是在有时序约束条件时，由于布局对FPGA版图速度的快慢起到决定性作用，从而在布局过程中就要将时序约束考虑进去，否则通过后续的布线等优化很难满足时序的约束。因此，如何快速有效的进行自动化布局，对FPGA版图设计起到至关重要的作用。为了加速自动化布局软件的效率，都采用总体布局的方式进行全局优化，但总体布局的结果不是合法的布局，所以要在总体布局之后增加一步合法化操作。合法化的好坏对布局的结果影响非常大，尤其是总体布局之后存在局部拥挤的区域的时候，不合理的合法化很容易造成单元模块的大范围移动，违背总体布局，不能很好的衔接总体布局的结果。Layout is a time-consuming step in the whole process. It reasonably configures the hardware primitives and underlying units in the logic netlist to the inherent hardware structure inside the chip, and often needs to make a decision between the optimal speed and the optimal area. choose. At present, the scale of FPGA is getting bigger and bigger, and the structure is getting more and more complex. There are more and more types of logic unit modules, including large logic units like DSP and RAM, and the wiring between some units is Fixed connections, such as carry chain (carry chain) and shift register (shift register), etc., all of which limit the random placement of logic units, especially when timing constraints, because the layout affects the speed of the FPGA layout. Therefore, the timing constraints must be taken into account in the layout process, otherwise it is difficult to meet the timing constraints through subsequent optimization such as wiring. Therefore, how to quickly and efficiently automate layout plays a vital role in FPGA layout design. In order to speed up the efficiency of the automated layout software, the overall layout is used for global optimization, but the result of the overall layout is not a legal layout, so a legalization operation must be added after the overall layout. The quality of legalization has a great influence on the result of the layout, especially when there is a partially crowded area after the overall layout, unreasonable legalization can easily cause large-scale movement of unit modules, which violates the overall layout and cannot be well connected The result of the general layout.
发明内容Contents of the invention
本发明提供一种FPGA总体布局合法化方法，通过分级处理不同类型不同约束的单元模块的合法化，通过小范围的单元移动，在尽量小的破坏总体布局结果的情况下进行合法化操作，确保总体布局的有效性。The present invention provides a legalization method for the general layout of FPGA, which can process the legalization of different types of unit modules with different constraints hierarchically, move the units in a small range, and carry out the legalization operation under the condition of destroying the overall layout result as little as possible, so as to ensure The effectiveness of the overall layout.
为了达到上述目的，本发明提供一种FPGA总体布局合法化方法，包含以下步骤：In order to achieve the above object, the present invention provides a kind of legalization method of FPGA general layout, comprises the following steps:
步骤S1、采用整数规划和网络流的方式对宏模块进行合法化；Step S1, using integer programming and network flow to legalize the macromodule;
所述的宏模块的资源稀疏、合法位置之间的间距比较远；The resources of the macro-modules are sparse, and the distance between legal positions is relatively far;
步骤S2、采用分级的整数规划的方式对有约束的标准单元进行合法化；Step S2, using hierarchical integer programming to legalize the constrained standard unit;
所述的有约束的标准单元是占用资源比较多、带有相对位置约束的标准单元模块；The constrained standard unit is a standard unit module that occupies more resources and has relative position constraints;
步骤S3、采用分级的网络流的方式对无约束的标准单元进行合法化。Step S3 , legalizing the unconstrained standard unit by means of hierarchical network flow.
所述的步骤S1中，在进行整体布局的同时，采用整数规划和网络流的方式对宏模块进行合法化。In the step S1, while the overall layout is being carried out, the macro modules are legalized by means of integer programming and network flow.
所述的步骤S2中，采用分级的整数规划的方式对有约束的标准单元进行合法化的方法具体包含以下步骤：In the step S2, the method of legalizing the constrained standard unit by means of hierarchical integer programming specifically includes the following steps:
步骤S2.1、将芯片划分为多个列，使标准单元在水平方向上移动到最近的列中；Step S2.1, dividing the chip into multiple columns, so that the standard cells are moved to the nearest column in the horizontal direction;
所述的列可包含一列网格，也可包含多列网格；The column may contain one column of grids or multiple columns of grids;
每一列中的标准单元的数量应该小于等于该列的容量；The number of standard cells in each column should be less than or equal to the capacity of the column;
步骤S2.2、采用贪婪的方法对相邻的两列进行标准单元的移动，降低列中的局部拥挤度；Step S2.2, using a greedy method to move the standard units of two adjacent columns to reduce the local congestion in the columns;
步骤S2.3、使每列中的标准单元在垂直方向上移动到最近的类型兼容的位置上；Step S2.3, moving the standard units in each column to the nearest type-compatible position in the vertical direction;
每一个位置中的标准单元的数量应该小于等于该位置的容量。The number of standard units in each location should be less than or equal to the capacity of that location.
所述的步骤S3中，采用分级的网络流的方式对无约束的标准单元进行合法化的方法包含以下步骤：In the step S3, the method for legalizing the unconstrained standard unit by means of hierarchical network flow includes the following steps:
步骤S3.1、将芯片划分为多个窗口，采用网络流单纯型方法求解MFC问题而获得标准单元对应的窗口的坐标，将标准单元移动到每个窗口内；Step S3.1, dividing the chip into multiple windows, using the network flow simplex method to solve the MFC problem to obtain the coordinates of the window corresponding to the standard unit, and moving the standard unit into each window;
所述的窗口包含多个网格；The window includes a plurality of grids;
步骤S3.2、采用网络流单纯型方法或匈牙利算法求解二分图的最优匹配问题，将每个窗口内的标准单元移动到匹配的位置上。Step S3.2, using the network flow simplex method or the Hungarian algorithm to solve the optimal matching problem of the bipartite graph, and moving the standard unit in each window to the matching position.
当宏模块也有约束的时候，其采用如步骤S2所述的分级的整数规划的方式对有约束的宏模块进行合法化，当宏模块没有约束时，其采用如步骤S3所述的分级的网络流的方式对没有约束的宏模块进行合法化。When the macromodule also has constraints, it adopts the hierarchical integer programming method as described in step S2 to legalize the constrained macromodule, and when the macromodule has no constraints, it adopts the hierarchical network as described in step S3 The streaming method legalizes unconstrained macromodules.
相对位置约束包含两大类：一类是用户指定的显示约束，另外一类是芯片相关的隐式约束，每种约束的单元共同构成一个大的宏模块。There are two types of relative position constraints: one is user-specified display constraints, and the other is chip-related implicit constraints. The units of each constraint together form a large macromodule.
将用户指定的显示约束构造成一个稀疏的宏模块来处理：Construct user-specified display constraints as a sparse macromodule for processing:
同种类型标准单元相对位置的指定：采用的坐标系是局部类型对应的坐标系；Designation of the relative position of the standard unit of the same type: the coordinate system adopted is the coordinate system corresponding to the local type;
异种类型标准单元相对位置的指定：采用的坐标系只能是全局的坐标系RPM。Designation of the relative position of heterogeneous standard units: the coordinate system used can only be the global coordinate system RPM.
将芯片相关的隐式约束转换成稠密的宏模块处理。Convert chip-dependent implicit constraints into dense macroblock processing.
当每个步骤中的合法化操作结束后，都会合法化操作是否失败，如果未失败，进行下一个步骤，如果失败，如果失败次数小于指定次数时，会重新调整参数，重新执行当前步骤的合法化，如果失败次数大于等于指定次数时，则整个合法化流程重新开始。When the legalization operation in each step is over, it will check whether the legalization operation fails. If it does not fail, proceed to the next step. If it fails, if the number of failures is less than the specified number of times, the parameters will be readjusted and the legalization of the current step will be re-executed. If the number of failures is greater than or equal to the specified number of times, the entire legalization process will start again.
本发明具有以下优点：The present invention has the following advantages:
1、通过减少局部拥挤度，减少合法化对总体布局的破坏。1. By reducing local congestion, reduce legal damage to the overall layout.
2、通过分级的方式很容易扩展合法化框架。2. It is easy to expand the legalization framework by means of classification.
3、合法化布局的效率明显提高。3. The efficiency of the legalization layout has been significantly improved.
附图说明Description of drawings
图1是背景技术中布局在整个芯片物理设计中的位置关系图。FIG. 1 is a positional diagram of the layout in the physical design of the entire chip in the background art.
图2是背景技术中FPGA芯片的自动化布局的步骤流程图。FIG. 2 is a flow chart of the steps of automatic layout of FPGA chips in the background technology.
图3是本发明提供的一种FPGA总体布局合法化方法的流程图。Fig. 3 is a flow chart of a method for legalizing the general layout of FPGA provided by the present invention.
图4是对有约束单元的合法化的分级示意图。Fig. 4 is a hierarchical schematic diagram of the legalization of constrained units.
图5是无约束标准单元芯片窗口的划分示意图。FIG. 5 is a schematic diagram of division of unconstrained standard cell chip windows.
图6是相对位置约束的类型示意图。Fig. 6 is a schematic diagram of types of relative position constraints.
图7是显示相对位置约束的示意图。Fig. 7 is a schematic diagram showing relative position constraints.
图8是隐式相对位置约束的示意图。Fig. 8 is a schematic diagram of implicit relative position constraints.
具体实施方式Detailed ways
以下根据图3～图8，具体说明本发明的较佳实施例。A preferred embodiment of the present invention will be specifically described below with reference to FIGS. 3 to 8 .
合法化布局在整个布局流程中起到承上启下的作用，是将不合法的布局转换成合法布局的必经之路。总体布局之后单元模块的坐标是浮点值，而芯片上可摆放单元的位置（Site）的坐标却是整数值，这时我们就要单元模块的坐标进行取整处理，类似于分支界定的处理操作。所以从本质讲，合法化布局是一个整数规划的问题。但是如果用通用的整数规划的求解器去解的话，运行时间不允许，当问题规模增长时，运行时间成指数级增长。The legal layout plays a connecting role in the whole layout process, and it is the only way to convert the illegal layout into a legal layout. After the overall layout, the coordinates of the unit module are floating-point values, but the coordinates of the position (Site) on the chip where the unit can be placed are integer values. At this time, we need to round the coordinates of the unit module, similar to the branch definition. Processing operations. So in essence, legalizing the layout is an integer programming problem. However, if a general-purpose integer programming solver is used to solve it, the running time is not allowed. When the problem scale increases, the running time will increase exponentially.
如图3所示，本发明提供一种FPGA总体布局合法化方法，包含以下步骤：As shown in Figure 3, the present invention provides a kind of legalization method of FPGA general layout, comprises the following steps:
步骤S1、采用整数规划和网络流的方式对宏模块进行合法化；Step S1, using integer programming and network flow to legalize the macromodule;
所述的宏模块的资源稀疏、合法位置之间的间距比较远，所述的宏模块包含数字信号处理器DSP、随机存储器RAM和约束非常紧的单元模块等等；The resources of the macro-module are sparse, and the distance between legal positions is relatively far, and the macro-module includes a digital signal processor DSP, a random access memory RAM and a very tightly constrained unit module, etc.;
每次合法化宏模块后，判断合法化操作是否失败，如果未失败，进行步骤S2，如果失败，进一步判断失败次数，如果合法化失败次数小于指定次数时，重新进行步骤S1，如果合法化失败的次数大于等于指定次数时，重新进行步骤S1；After legalizing the macromodule each time, judge whether the legalization operation failed. If not, go to step S2. If it fails, further judge the number of failures. If the number of legalization failures is less than the specified number, go to step S1 again. If the legalization fails When the number of times is greater than or equal to the specified number of times, repeat step S1;
步骤S2、采用分级的整数规划的方式对有约束的标准单元进行合法化；Step S2, using hierarchical integer programming to legalize the constrained standard unit;
所述的有约束的标准单元是占用资源比较多、带有相对位置（RLOC）约束的标准单元模块；The constrained standard unit is a standard unit module that occupies more resources and has a relative location (RLOC) constraint;
每次合法化有约束的标准单元后，判断合法化操作是否失败，如果未失败，进行步骤S3，如果失败，进一步判断失败次数，如果合法化失败次数小于指定次数时，重新调整参数（包含调整不同约束的优先级，每个标准单元可摆放的位置的范围等等），重新进行步骤S2，如果合法化失败的次数大于等于指定次数时，重新进行步骤S1；After each legalization of a constrained standard unit, judge whether the legalization operation fails. If not, go to step S3. If it fails, further judge the number of failures. If the number of legalization failures is less than the specified number of times, readjust the parameters (including adjusting Priority of different constraints, the range of positions that each standard unit can be placed, etc.), repeat step S2, if the number of legalization failures is greater than or equal to the specified number of times, repeat step S1;
步骤S3、采用分级的网络流的方式对无约束的标准单元进行合法化；Step S3, legalizing the unconstrained standard unit by means of hierarchical network flow;
每次合法化无约束的标准单元后，判断合法化操作是否失败，如果未失败，结束合法化，如果失败，进一步判断失败次数，如果合法化失败次数小于指定次数时，重新调整参数（包含调整分级的层次，分级之后窗口的划分方式等等），重新进行步骤S3，如果合法化失败的次数大于等于指定次数时，重新进行步骤S1。After each legalization of an unconstrained standard unit, judge whether the legalization operation fails. If not, end the legalization. If it fails, further judge the number of failures. If the number of legalization failures is less than the specified number of times, readjust the parameters (including adjustment grading level, the division method of the window after grading, etc.), repeat step S3, if the number of legalization failures is greater than or equal to the specified number of times, repeat step S1.
当每小步合法化失败小于指定次数时，会重新调整参数，重新执行当前步骤的合法化，当每小步合法化的次数大于等于指定次数时，则整个合法化流程重新开始，确保获得合法的布局或者报告出相应的错误信息。When the number of legalization failures in each small step is less than the specified number of times, the parameters will be readjusted and the legalization of the current step will be re-executed. When the number of legalizations in each small step is greater than or equal to the specified number of times, the entire legalization process will restart to ensure legalization layout or report the corresponding error message.
所述的步骤S1中，在进行总体布局的同时，采用整数规划和网络流的方式对宏模块进行合法化，提前固定宏模块，防止其资源的不连续性造成布局结果的波动。In the step S1, while the overall layout is being carried out, the macromodules are legalized by means of integer programming and network flow, and the macromodules are fixed in advance to prevent the discontinuity of their resources from causing fluctuations in the layout results.
宏模块合法化对DSP、RAM 和物理约束（描述模块自身或者与别的模块相对位置的约束）复杂的单元模块做合法化操作，整个芯片上，DSP 和RAM 分布比较稀疏，相对CLB 来说比较少，一列DSP 或RAM 距离相邻的DSP 或RAM 相对比较远，从而DSP 和RAM 单元从一个合法位置移动到另外一个合法位置的移动范围相对比较大，为了防止其在总体布局之后进行大范围的移动对布局造成影响，本发明在前几轮总体布局结束后就将其固定住，防止后面对布局造成颠簸的现象。The legalization of macro modules performs legalization operations on complex unit modules with DSP, RAM and physical constraints (constraints that describe the module itself or its relative position with other modules). On the entire chip, the distribution of DSP and RAM is relatively sparse, compared to CLB. A row of DSP or RAM is relatively far away from the adjacent DSP or RAM, so the moving range of DSP and RAM cells from one legal position to another is relatively large, in order to prevent it from performing large-scale after the overall layout The movement affects the layout, and the present invention fixes it after the first few rounds of overall layout are finished to prevent the phenomenon of jolting the layout at the back.
所述的步骤S2中，采用分级的整数规划的方式对有约束的标准单元进行合法化，在整个布局的过程中，相对位置约束是特别难处理的约束，当这种约束多的时候，其很容易造成局部无解。布局合法化就是在满足布局约束的情况下，小幅度的移动单元将其摆放到合法的位置上，其实质是一个整数规划的问题。由于整数规划问题随着规模的增大，求解时间指数级别的增长，所以当单元模块比较多时，求解效率大打折扣，所以当前框架采用分级整数规划的模型，分为水平和垂直两个独立的方向，从X 和Y 方向分别进行优化。In the step S2, a hierarchical integer programming method is used to legalize the constrained standard cells. During the entire layout process, relative position constraints are particularly difficult constraints. When there are many such constraints, other It is easy to cause local confusion. Layout legalization is to move units in a small range to a legal position under the condition of satisfying the layout constraints, which is essentially an integer programming problem. As the scale of the integer programming problem increases, the solution time increases exponentially. Therefore, when there are many unit modules, the solution efficiency is greatly reduced. Therefore, the current framework adopts a hierarchical integer programming model, which is divided into two independent directions: horizontal and vertical. , optimize from the X and Y directions respectively.
图4是对有约束单元的合法化的分级示意图，所述的采用分级的整数规划的方式对有约束的标准单元进行合法化的方法具体包含以下步骤：Fig. 4 is a hierarchical schematic diagram of the legalization of constrained units, and the method for legalizing constrained standard units by means of hierarchical integer programming specifically includes the following steps:
步骤S2.1、将芯片划分为多个列，使标准单元在水平方向上移动到最近的列中；Step S2.1, dividing the chip into multiple columns, so that the standard cells are moved to the nearest column in the horizontal direction;
所述的列可包含一列网格（Tile），也可包含多列网格；如图4所示，所述的网格（Tile）是二维的网格结构，一个CLB是一个Tile，一个DSP也是一个Tile，每一列网格（Tile）构成一个Col；The column can contain one column of grid (Tile), and can also contain multiple columns of grid; as shown in Figure 4, the grid (Tile) is a two-dimensional grid structure, a CLB is a Tile, a DSP is also a Tile, each column grid (Tile) constitutes a Col;
每一列中的标准单元的数量应该小于等于该列的容量；The number of standard cells in each column should be less than or equal to the capacity of the column;
此阶段所有标准单元只能进行水平方向移动，其目标位置是划分出来的列，这样可以构建一个整数规划问题，目标方程是所有标准单元水平移动的代价最小，约束是所有标准单元移动到对应的列中，且每列中各种类型的标准单元不能超出列的容量；At this stage, all standard units can only move horizontally, and the target position is the divided column, so that an integer programming problem can be constructed. The objective equation is that the cost of all standard units moving horizontally is the minimum, and the constraint is that all standard units move to the corresponding Columns, and each type of standard unit in each column cannot exceed the capacity of the column;
步骤S2.2、采用贪婪的方法对相邻的两列进行标准单元的移动，降低列中的局部拥挤度；Step S2.2, using a greedy method to move the standard units of two adjacent columns to reduce the local congestion in the columns;
当标准单元被分配到各列之后，虽说其满足列的容量的约束，但由于每列的高度很高，可能造成列内局部区域的拥挤度比较高，而相邻的列此处的拥挤度比较低，从而采用贪婪的方法对相邻的两列进行简单的标准单元的移动，进一步降低局部拥挤度，通过减少拥挤度的方式驱使标准单元小范围的移动，保证总体布局的结果；After the standard unit is allocated to each column, although it satisfies the capacity constraints of the column, due to the high height of each column, the congestion degree of the local area in the column may be relatively high, while the congestion degree of the adjacent column here Relatively low, so the greedy method is used to move the simple standard unit of the adjacent two columns, further reduce the local congestion, and drive the standard unit to move in a small range by reducing the congestion to ensure the result of the overall layout;
步骤S2.3、使每列中的标准单元在垂直方向上移动到最近的类型兼容的位置上；Step S2.3, moving the standard units in each column to the nearest type-compatible position in the vertical direction;
每一个位置中的标准单元的数量应该小于等于该位置的容量；The number of standard units in each location should be less than or equal to the capacity of the location;
对每列内的标准单元进行合法化操作，其仍然是整数规划的问题，其优化目标是标准单元垂直移动的代价最小，约束是所有的标准单元移动到对应的Tile内部的位置上，且每个位置内的标准单元不能超出位置的容量且与所在位置的类型相兼容。It is still an integer programming problem to legalize the standard units in each column. The optimization goal is to minimize the cost of vertical movement of standard units. The constraint is that all standard units move to the corresponding positions inside the Tile, and every Standard units within a location cannot exceed the capacity of the location and are compatible with the type of location it is in.
通过采用上述分级的合法化策略，极大的减少整数规划问题的规模，从而减少分支定界的时间，加速有约束单元模块的合法化。By adopting the above-mentioned hierarchical legalization strategy, the scale of the integer programming problem is greatly reduced, thereby reducing the time of branch and bound, and accelerating the legalization of constrained unit modules.
所述的步骤S3中，采用分级的网络流的方式对无约束的标准单元进行合法化，整数规划问题随着规模的增大，求解速度变慢，而无约束的标准单元在整个电路中占有大部分的比例，所以无约束的标准单元的合法化采用网络流的方式求解。In the step S3, the unconstrained standard unit is legalized in the form of hierarchical network flow, and the solution speed of the integer programming problem becomes slower as the scale increases, and the unconstrained standard unit occupies 100% of the entire circuit. For most proportions, the legalization of unconstrained standard cells is solved in a network flow manner.
所述的采用分级的网络流的方式对无约束的标准单元进行合法化的方法包含以下步骤：The method for legalizing unconstrained standard units in the manner of hierarchical network flow includes the following steps:
步骤S3.1、将芯片划分为多个窗口（Window），采用网络流单纯型方法求解MFC问题而获得标准单元对应的窗口的坐标，将标准单元移动到每个窗口内；Step S3.1, divide the chip into multiple windows (Window), use the network flow simplex method to solve the MFC problem to obtain the coordinates of the window corresponding to the standard unit, and move the standard unit into each window;
所述的窗口包含多个Tile，本实施例中，每个窗口的大小相当于十几个到几十个Tiles的大小；The window includes a plurality of Tiles, and in this embodiment, the size of each window is equivalent to the size of a dozen to dozens of Tiles;
如图5所示，是无约束标准单元芯片窗口的划分示意图，总体布局之后，只能保证全局单元模块分布是均匀的，但其仍然存在一些拥挤的区域，并且当芯片的利用率高的时候，将所有的标准单元一起进行合法化对算法的效率影响比较大，所以先采用网络流的方式先局部的分配各个标准单元到各个窗口内，保证分配给特定窗口的标准单元可以摆放到当前的窗口内；As shown in Figure 5, it is a schematic diagram of the division of unconstrained standard unit chip windows. After the overall layout, the distribution of global unit modules can only be guaranteed to be uniform, but there are still some crowded areas, and when the utilization rate of the chip is high , the legalization of all standard units together has a great impact on the efficiency of the algorithm, so the method of network flow is used to locally allocate each standard unit to each window to ensure that the standard units allocated to a specific window can be placed in the current window. in the window;
分配单元模块到各个窗口内可以模拟成MFC 的问题，所有窗口及所有的单元构成MFC问题上所有的节点，所有节点都有容量约束，代表每个单元与可摆放的窗口之间都存在一条边，代表其摆放到对应窗口的代价；可以通过网络流单纯型的方法求解这个MFC 问题获得所有单元对应的窗口的坐标，网络流单纯型法的求解思想就是从一个合理解变换到另外一个合理解的方式，经有限次变换获得最优解；MCF 问题是构建一个生成树，从不在生成树上的边选择一条可减少代价的边加入到生成树中，多加入一条边，必然会使原有的生成树构成环，然后调整各个边的容量，删掉环上关键的边（不能增大或者减少流Flow 的边），这样经过有限次的生成树变换，即可以获得MCF 问题的解；Assigning unit modules to each window can be simulated as an MFC problem. All windows and all units constitute all nodes on the MFC problem. All nodes have capacity constraints, which means that there is a link between each unit and the windows that can be placed. The edge represents the cost of placing it in the corresponding window; the MFC problem can be solved by the network flow simplex method to obtain the coordinates of the windows corresponding to all units. The solution idea of the network flow simplex method is to transform from one reasonable understanding to another The optimal solution is obtained through a finite number of transformations in a reasonable way; the MCF problem is to construct a spanning tree, choose an edge that can reduce the cost from an edge that is not on the spanning tree, and add it to the spanning tree. Adding one more edge will inevitably make The original spanning tree forms a ring, and then adjusts the capacity of each edge, deletes the key edge on the ring (the edge of Flow cannot be increased or decreased), so that after a limited number of spanning tree transformations, the solution to the MCF problem can be obtained ;
步骤S3.2、采用网络流单纯型方法或匈牙利算法求解二分图的最优匹配问题，将每个窗口内的标准单元移动到匹配的位置上；Step S3.2, using the network flow simplex method or the Hungarian algorithm to solve the optimal matching problem of the bipartite graph, and moving the standard unit in each window to the matching position;
当所有单元分配到窗口上之后，可以对这个窗口内的单元进一步进行合法化操作，此时可以按照步骤S3.1的方法构建成MCF 的问题，每个标准单元及所有的位置是MFC 中的节点，每个节点上标有容量约束，每个标准单元到每个合法位置之间存在一条边，边上标有标准单元移动到对应位置上的代价，通过网络流单纯型方法或者匈牙利算法求解，即可获得合法的布局；After all the units are assigned to the window, the units in this window can be further legalized. At this time, the MCF problem can be constructed according to the method of step S3.1. Each standard unit and all positions are MFC Nodes, each node is marked with a capacity constraint, there is an edge between each standard unit and each legal position, and the cost of moving the standard unit to the corresponding position is marked on the edge, and it is solved by the simplex method of network flow or the Hungarian algorithm , the legal layout can be obtained;
匈牙利算法主要是解决二分图的最优匹配问题，而步骤S3.2的问题也即二分图匹配问题，把所有的标准单元与位置进行匹配，其主体思想就是不停地寻找增广路径来增加匹配中的匹配边和匹配点或者减小匹配的代价，经过有限步之后，找不到增广路径时，达到最优匹配，也即获得合法的布局。The Hungarian algorithm is mainly to solve the optimal matching problem of the bipartite graph, and the problem of step S3.2 is also the bipartite graph matching problem, matching all the standard units with the position, the main idea is to constantly find the augmentation path to increase Matching edges and matching points in matching or reducing the cost of matching, after finite steps, when no augmentation path can be found, the optimal matching is achieved, that is, a legal layout is obtained.
当宏模块也有约束的时候，其采用如步骤S2所述的分级的整数规划的方式对有约束的宏模块进行合法化，当宏模块没有约束时，其采用如步骤S3所述的分级的网络流的方式对没有约束的宏模块进行合法化。When the macromodule also has constraints, it adopts the hierarchical integer programming method as described in step S2 to legalize the constrained macromodule, and when the macromodule has no constraints, it adopts the hierarchical network as described in step S3 The streaming method legalizes unconstrained macromodules.
本发明支持带约束的宏模块或者带约束的标准单元的合法化，支持单元模块间相对位置的约束。The invention supports the legalization of a constrained macro module or a constrained standard unit, and supports the constraint of relative positions between unit modules.
在整个布局的过程中，相对位置约束（RLOC）是特别难处理的约束，当这种约束多的时候，其很容易造成局部无解。如图6所示，相对位置约束包含两大类，一类是用户指定的显示约束，是用户显示在UCF 文件中定义的，另外一类是芯片相关的隐式约束，是根据芯片的内部结构隐式存在的物理约束，每种约束的单元共同构成一个大的宏模块。During the entire layout process, the relative location constraint (RLOC) is a particularly difficult constraint. When there are many such constraints, it is easy to cause local unsolvability. As shown in Figure 6, relative position constraints include two categories, one is user-specified display constraints, which are defined by users in the UCF file, and the other is chip-related implicit constraints, which are based on the internal structure of the chip There are implicit physical constraints, and the units of each constraint together form a large macromodule.
将用户指定的显示约束构造成一个稀疏的宏模块（由于宏模块中间可能有洞，成为稀疏的宏模块）来处理：用户指定的显示约束都是通过UCF 文件指定的，其描述一组标准单元位置的相对关系，其可以指定同种类型标准单元位置的相对关系，也可以指定异种类型标准单元位置的相对关系。Construct the user-specified display constraints into a sparse macroblock (sparse macroblock due to possible holes in the middle of the macroblock) The relative relationship of positions, which can specify the relative relationship of the positions of the same type of standard units, and can also specify the relative relationship of the positions of different types of standard units.
同种类型标准单元相对位置的指定：采用的坐标系是局部类型对应的坐标系，IOB类型的有IOB合法位置的坐标系，如IOB_X1Y2，SLICEL和SLICEM对应SLICE坐标系，如SLICE_X8Y9，其余的类型也类似。Designation of the relative position of the same type of standard unit: the coordinate system used is the coordinate system corresponding to the local type, the coordinate system of the IOB type has the legal position of the IOB, such as IOB_X1Y2, SLICEL and SLICEM correspond to the SLICE coordinate system, such as SLICE_X8Y9, and other types Also similar.
异种类型标准单元相对位置的指定：当指定不同类型单元之间的相对位置的时候，只能采用全局的坐标系RPM，如指定单元DSP与单元SLICE的全局位置为RPM_X8Y9和RPM_X9Y10，其代表X和Y方向的相对位置为都为1。Designation of the relative position of different types of standard units: When specifying the relative position between different types of units, only the global coordinate system RPM can be used. For example, the global positions of the specified unit DSP and unit SLICE are RPM_X8Y9 and RPM_X9Y10, which represent X and The relative positions in the Y direction are all 1.
如图7所示，用户在UCF 文件中显示的定义一个RLOC 约束，即包含整个约束可摆放的区域RLOC_RANGE和5个单元的相对位置的对应关系，这5个单元无论移动到什么地方，其相对位置的偏差不能变，且其整体的外边界不能超出RLOC_RANGE。As shown in Figure 7, the user defines an RLOC constraint displayed in the UCF file, which includes the corresponding relationship between the region RLOC_RANGE where the entire constraint can be placed and the relative positions of the 5 units. No matter where the 5 units move, their The relative position deviation cannot be changed, and its overall outer boundary cannot exceed RLOC_RANGE.
将芯片相关的隐式约束转换成稠密的宏模块（由于宏模块中间没有洞，成为稠密的宏模块）处理：除了用户显示的指定的相对位置约束外，还有一种与芯片结构密切相关的相对位置的约束，如为了实现累加器的进位链，实现进位的移位寄存器， 构成多路选择器的Mux Tree，构成随机存取存储器的RAM Chain等等。如图8所示，由四个单元构成的进位链，其通过多条COUTàCIN 的Net 级联起来，由于物理实现上COUTàCIN线网的只能通过一条路径联通，所以这四个单元必须沿垂直方向紧挨着摆放。这种隐式相对位置的约束类型也比较多，各种类型的约束构成单元的类型及相对位置也不一样，但其可以转换成相对位置约束。Convert chip-related implicit constraints into dense macroblocks (dense macroblocks because there is no hole in the middle of the macroblock) processing: In addition to the specified relative position constraints displayed by the user, there is also a relative position closely related to the chip structure. Positional constraints, such as in order to realize the carry chain of the accumulator, the shift register to realize the carry, the Mux Tree that constitutes the multiplexer, the RAM Chain that constitutes the random access memory, and so on. As shown in Figure 8, the carry chain composed of four units is cascaded through multiple COUTàCIN Nets. Since the COUTàCIN line network can only be connected through one path in physical implementation, these four units must be connected in the vertical direction. placed next to each other. There are also many types of constraints for this implicit relative position, and the types and relative positions of the constituent units of various types of constraints are also different, but they can be converted into relative position constraints.
本发明提供的一种FPGA总体布局合法化方法，通过分级处理不同类型不同约束的单元模块的合法化，通过小范围的单元移动，在尽量小的破坏总体布局结果的情况下进行合法化操作，确保总体布局的有效性。The method for legalizing the overall layout of FPGA provided by the present invention is to process legalization of different types of unit modules with different constraints hierarchically, and to perform legalization operations with as little damage to the overall layout results as possible through small-scale unit movement. Ensure the effectiveness of the overall layout.
本发明具有以下优点：The present invention has the following advantages:
1、通过减少局部拥挤度，减少合法化对总体布局的破坏。1. By reducing local congestion, reduce legal damage to the overall layout.
2、通过分级的方式很容易扩展合法化框架。2. It is easy to expand the legalization framework by means of classification.
3、合法化布局的效率明显提高。3. The efficiency of the legalization layout has been significantly improved.
尽管本发明的内容已经通过上述优选实施例作了详细介绍，但应当认识到上述的描述不应被认为是对本发明的限制。在本领域技术人员阅读了上述内容后，对于本发明的多种修改和替代都将是显而易见的。因此，本发明的保护范围应由所附的权利要求来限定。Although the content of the present invention has been described in detail through the above preferred embodiments, it should be understood that the above description should not be considered as limiting the present invention. Various modifications and alterations to the present invention will become apparent to those skilled in the art upon reading the above disclosure. Therefore, the protection scope of the present invention should be defined by the appended claims.
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201610914808.XACN107967372B (en) | 2016-10-20 | 2016-10-20 | A Legalization Method of FPGA Overall Layout |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201610914808.XACN107967372B (en) | 2016-10-20 | 2016-10-20 | A Legalization Method of FPGA Overall Layout |
| Publication Number | Publication Date |
|---|---|
| CN107967372Atrue CN107967372A (en) | 2018-04-27 |
| CN107967372B CN107967372B (en) | 2021-05-28 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201610914808.XAActiveCN107967372B (en) | 2016-10-20 | 2016-10-20 | A Legalization Method of FPGA Overall Layout |
| Country | Link |
|---|---|
| CN (1) | CN107967372B (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111709205A (en)* | 2020-05-29 | 2020-09-25 | 成都华微电子科技有限公司 | FPGA wiring method |
| CN112711930A (en)* | 2020-12-24 | 2021-04-27 | 西安国微半导体有限公司 | Wire mesh distribution-based routability-driven global layout method and device |
| CN113221493A (en)* | 2021-05-31 | 2021-08-06 | 福州大学 | Clock legalization method based on heterogeneous FPGA layout |
| CN113343632A (en)* | 2021-05-31 | 2021-09-03 | 上海立芯软件科技有限公司 | Heterogeneous layout legalization method considering carry chain and position constraint |
| CN114417771A (en)* | 2020-10-28 | 2022-04-29 | Oppo广东移动通信有限公司 | Chip circuit layout method, circuit design method, apparatus, equipment and medium |
| CN120449816A (en)* | 2025-07-03 | 2025-08-08 | 芯行纪科技有限公司 | Method, apparatus and storage medium for optimizing digital logic circuit layout |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1545049A (en)* | 2003-11-14 | 2004-11-10 | 清华大学 | Large-Scale Mixed-Mode Layout Method Based on Virtual Modules |
| CN101002204A (en)* | 2004-08-04 | 2007-07-18 | 英赛特半导体有限公司 | Method and apparatus for locating short circuit faults in anintegrated circuit layout |
| US20080059931A1 (en)* | 2006-08-29 | 2008-03-06 | Jason Peters | Apparatus and Methods for Congestion Estimation and Optimization for Computer-Aided Design Software |
| CN103297983A (en)* | 2013-05-06 | 2013-09-11 | 南京邮电大学 | Wireless sensor network node dynamic deployment method based on network flow |
| US20150143309A1 (en)* | 2013-11-19 | 2015-05-21 | Arm Limited | Computer implemented system and method for generating a layout of a cell defining a circuit component |
| CN104699867A (en)* | 2013-12-04 | 2015-06-10 | 京微雅格（北京）科技有限公司 | Optimization method for local layout of FPGA chips |
| CN105740518A (en)* | 2016-01-25 | 2016-07-06 | 深圳市同创国芯电子有限公司 | FPGA resource placement method and apparatus |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1545049A (en)* | 2003-11-14 | 2004-11-10 | 清华大学 | Large-Scale Mixed-Mode Layout Method Based on Virtual Modules |
| CN101002204A (en)* | 2004-08-04 | 2007-07-18 | 英赛特半导体有限公司 | Method and apparatus for locating short circuit faults in anintegrated circuit layout |
| US20080059931A1 (en)* | 2006-08-29 | 2008-03-06 | Jason Peters | Apparatus and Methods for Congestion Estimation and Optimization for Computer-Aided Design Software |
| CN103297983A (en)* | 2013-05-06 | 2013-09-11 | 南京邮电大学 | Wireless sensor network node dynamic deployment method based on network flow |
| US20150143309A1 (en)* | 2013-11-19 | 2015-05-21 | Arm Limited | Computer implemented system and method for generating a layout of a cell defining a circuit component |
| CN104699867A (en)* | 2013-12-04 | 2015-06-10 | 京微雅格（北京）科技有限公司 | Optimization method for local layout of FPGA chips |
| CN105740518A (en)* | 2016-01-25 | 2016-07-06 | 深圳市同创国芯电子有限公司 | FPGA resource placement method and apparatus |
| Title |
|---|
| 朱利民等: "基于整数规划的层次式FPGA布线算法", 《计算机辅助设计与图形学学报》* |
| 王似飞等: "基于FastPlace总体布局算法的实现", 《小型微型计算机系统》* |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111709205A (en)* | 2020-05-29 | 2020-09-25 | 成都华微电子科技有限公司 | FPGA wiring method |
| CN114417771A (en)* | 2020-10-28 | 2022-04-29 | Oppo广东移动通信有限公司 | Chip circuit layout method, circuit design method, apparatus, equipment and medium |
| CN112711930A (en)* | 2020-12-24 | 2021-04-27 | 西安国微半导体有限公司 | Wire mesh distribution-based routability-driven global layout method and device |
| CN112711930B (en)* | 2020-12-24 | 2023-02-10 | 西安国微半导体有限公司 | Wire mesh distribution-based routability-driven global layout method and device |
| CN113221493A (en)* | 2021-05-31 | 2021-08-06 | 福州大学 | Clock legalization method based on heterogeneous FPGA layout |
| CN113343632A (en)* | 2021-05-31 | 2021-09-03 | 上海立芯软件科技有限公司 | Heterogeneous layout legalization method considering carry chain and position constraint |
| CN113221493B (en)* | 2021-05-31 | 2022-07-15 | 福州大学 | A Clock Legalization Method Based on Heterogeneous FPGA Layout |
| CN120449816A (en)* | 2025-07-03 | 2025-08-08 | 芯行纪科技有限公司 | Method, apparatus and storage medium for optimizing digital logic circuit layout |
| Publication number | Publication date |
|---|---|
| CN107967372B (en) | 2021-05-28 |
| Publication | Publication Date | Title |
|---|---|---|
| CN107967372A (en) | A kind of FPGA total arrangements legalize method | |
| CN108287932B (en) | Overall FPGA automatic layout method based on analysis method | |
| CN1996318B (en) | Method for macro placement of semiconductor chips and multi-size hybrid placement method | |
| US8418115B1 (en) | Routability based placement for multi-die integrated circuits | |
| CN104182556B (en) | The layout method of chip | |
| US6857107B2 (en) | LSI layout method and apparatus for cell arrangement in which timing is prioritized | |
| Shen et al. | Efficient rectilinear Steiner tree construction with rectilinear blockages | |
| JP2009140495A (en) | System and method for probabilistic interconnect structure design | |
| JPH0766718A (en) | Wafer scale structure for programmable logic | |
| US6958545B2 (en) | Method for reducing wiring congestion in a VLSI chip design | |
| CN106021722B (en) | Optimization method based on FPGA layout | |
| US8473881B1 (en) | Multi-resource aware partitioning for integrated circuits | |
| CN114065694A (en) | FPGA wiring resource map compression method and global wiring module | |
| Liang et al. | AMF-placer: High-performance analytical mixed-size placer for FPGA | |
| US8863062B2 (en) | Methods and apparatus for floorplanning and routing co-design | |
| CN116882340A (en) | Method for automatically generating ring oscillator layout | |
| KR20180028252A (en) | Integrated Circuit Designing System and Method of Manufacturing Integrated Circuit | |
| US10042971B1 (en) | Placement and routing of clock signals for a circuit design | |
| JP2006301961A (en) | Automatic floorplanning method for semiconductor integrated circuits | |
| US9330220B1 (en) | Clock region partitioning and clock routing | |
| US20170061063A1 (en) | Integrated circuit with reduced routing congestion | |
| US10303202B1 (en) | Method and apparatus for performing clock allocation for a system implemented on a programmable device | |
| Chen et al. | A congestion-based routing model and its optimization method for VLSI routing | |
| US8219957B1 (en) | Global placement legalization for complex packing rules | |
| JP3433025B2 (en) | Module placement method |
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |