公开(公告)号：US08555229B2

公开(公告)日：2013-10-08

申请号：US13151413

申请日：2011-06-02

申请人： Xiaoping Tang ,  Michael S. Gray ,  Xin Yuan

发明人： Xiaoping Tang ,  Michael S. Gray ,  Xin Yuan

IPC分类号： G06F17/50

CPC分类号： G06F17/5081 ,  G06F17/5068

摘要： Solutions for optimizing an integrated circuit layout for implementation in an integrated circuit are disclosed. In one embodiment, a computer-implemented method is disclosed including: obtaining a plurality of hierarchical constraints in mathematical form, the plurality of hierarchical constraints defining a first integrated circuit layout; partitioning the plurality of hierarchical constraints into groups according to one or more partitioning rules; determining whether a boundary condition exists between two of the groups, and distributing a slack or a gap between the two of the groups in the case that the boundary condition exists; creating a plurality of integer linear programming problems associated with each of the groups; determining a solution for each of the plurality of integer linear programming problems; and integrating each solution together to form a second integrated circuit layout.

摘要翻译： 公开了用于优化用于在集成电路中实现的集成电路布局的解决方案。 在一个实施例中，公开了一种计算机实现的方法，包括：以数学形式获得多个分层约束，所述多个层级约束限定第一集成电路布局; 根据一个或多个分区规则将多个分层约束划分成组; 确定在两个组之间是否存在边界条件，并且在存在边界条件的情况下分配两组之间的松弛或间隙; 创建与每个组相关联的多个整数线性规划问题; 确定所述多个整数线性规划问题中的每一个的解; 并将每个解决方案集成在一起以形成第二集成电路布局。

公开(公告)号：US20120311517A1

公开(公告)日：2012-12-06

申请号：US13151413

申请日：2011-06-02

申请人： Xiaoping Tang ,  Michael S. Gray ,  Xin Yuan

发明人： Xiaoping Tang ,  Michael S. Gray ,  Xin Yuan

IPC分类号： G06F17/50

CPC分类号： G06F17/5081 ,  G06F17/5068

摘要： Solutions for optimizing an integrated circuit layout for implementation in an integrated circuit are disclosed. In one embodiment, a computer-implemented method is disclosed including: obtaining a plurality of hierarchical constraints in mathematical form, the plurality of hierarchical constraints defining a first integrated circuit layout; partitioning the plurality of hierarchical constraints into groups according to one or more partitioning rules; determining whether a boundary condition exists between two of the groups, and distributing a slack or a gap between the two of the groups in the case that the boundary condition exists; creating a plurality of integer linear programming problems associated with each of the groups; determining a solution for each of the plurality of integer linear programming problems; and integrating each solution together to form a second integrated circuit layout.

摘要翻译： 公开了用于优化用于在集成电路中实现的集成电路布局的解决方案。 在一个实施例中，公开了一种计算机实现的方法，包括：以数学形式获得多个分层约束，所述多个层级约束限定第一集成电路布局; 根据一个或多个分区规则将多个分层约束划分成组; 确定在两个组之间是否存在边界条件，并且在存在边界条件的情况下分配两组之间的松弛或间隙; 创建与每个组相关联的多个整数线性规划问题; 确定所述多个整数线性规划问题中的每一个的解; 并将每个解决方案集成在一起以形成第二集成电路布局。

公开(公告)号：US20110265055A1

公开(公告)日：2011-10-27

申请号：US12767375

申请日：2010-04-26

申请人： Michael S. Gray ,  Xiaoping Tang ,  Xin Yuan

发明人： Michael S. Gray ,  Xiaoping Tang ,  Xin Yuan

IPC分类号： G06F17/50

CPC分类号： G06F17/5068

摘要： A computer-implemented method for handling a plurality of constraints in layout optimization for an integrated circuit (IC) layout is disclosed. In one embodiment, the method includes building a graph representing the plurality of constraints; marking two-dimensional constraints in the plurality of constraints; generating two-dimensional clusters including groups of the two-dimensional constraints; handling at least one of the two-dimensional clusters, the handling including finding a solution for the two-dimensional constraints in the at least one two-dimensional cluster; repeating the handling for any unprocessed two-dimensional clusters until all of the two-dimensional clusters are handled; and adopting the solution for each of the two-dimensional clusters to solve at least a portion of the plurality of constraints including the two-dimensional clusters.

摘要翻译： 公开了一种用于处理集成电路（IC）布局的布局优化中的多个约束的计算机实现的方法。 在一个实施例中，该方法包括构建表示多个约束的图; 标记所述多个约束中的二维约束; 生成包括二维约束的二维群集; 处理所述二维集群中的至少一个，所述处理包括找到所述至少一个二维集群中的二维约束的解; 重复对任何未处理的二维簇的处理，直到处理所有二维簇; 并且针对每个二维聚类采用解，以解决包括二维聚类的多个约束的至少一部分。

公开(公告)号：US20090158223A1

公开(公告)日：2009-06-18

申请号：US11958606

申请日：2007-12-18

申请人： Michael S. Gray ,  Matthew T. Guzowski ,  Kevin W. McCullen ,  Xiaoping Tang ,  Robert F. Walker ,  Xin Yuan

发明人： Michael S. Gray ,  Matthew T. Guzowski ,  Kevin W. McCullen ,  Xiaoping Tang ,  Robert F. Walker ,  Xin Yuan

IPC分类号： G06F17/50

CPC分类号： G06F17/5068 ,  G06F2217/08

摘要： An adaptive weighting method for layout optimization differentiates different priorities by assigning the weight of a higher priority (pi) to be multiple of the weight of a lower priority (pi−1) where W(pi)=mi % W(pi−1. To avoid numerical imprecision, this method keeps the total cost in the objective function within a trustable range by scaling the initial weights in the objectives, while maintaining relativity, to produce the scaled weights.

摘要翻译： 用于布局优化的自适应加权方法通过将较高优先级（pi）的权重分配为较低优先级（pi-1）的权重的倍数来区分不同的优先级，其中W（pi）= mi％W（pi-1） 为了避免数值不精确，该方法将目标函数中的总成本保持在可信范围内，通过缩放目标中的初始权重，同时维持相对性，以产生缩放权重。

公开(公告)号：US08296706B2

公开(公告)日：2012-10-23

申请号：US12767375

申请日：2010-04-26

申请人： Michael S. Gray ,  Xiaoping Tang ,  Xin Yuan

发明人： Michael S. Gray ,  Xiaoping Tang ,  Xin Yuan

IPC分类号： G06F17/50

CPC分类号： G06F17/5068

摘要： A computer-implemented method for handling a plurality of constraints in layout optimization for an integrated circuit (IC) layout is disclosed. In one embodiment, the method includes building a graph representing the plurality of constraints; marking two-dimensional constraints in the plurality of constraints; generating two-dimensional clusters including groups of the two-dimensional constraints; handling at least one of the two-dimensional clusters, the handling including finding a solution for the two-dimensional constraints in the at least one two-dimensional cluster; repeating the handling for any unprocessed two-dimensional clusters until all of the two-dimensional clusters are handled; and adopting the solution for each of the two-dimensional clusters to solve at least a portion of the plurality of constraints including the two-dimensional clusters.

摘要翻译： 公开了一种用于处理集成电路（IC）布局的布局优化中的多个约束的计算机实现的方法。 在一个实施例中，该方法包括构建表示多个约束的图; 标记所述多个约束中的二维约束; 生成包括二维约束的二维群集; 处理所述二维集群中的至少一个，所述处理包括找到所述至少一个二维集群中的所述二维约束的解; 重复对任何未处理的二维簇的处理，直到处理所有二维簇; 并且针对每个二维聚类采用解，以解决包括二维聚类的多个约束的至少一部分。

公开(公告)号：US07895562B2

公开(公告)日：2011-02-22

申请号：US11958606

申请日：2007-12-18

申请人： Michael S. Gray ,  Matthew T. Guzowski ,  Kevin W. McCullen ,  Xiaoping Tang ,  Robert F. Walker ,  Xin Yuan

发明人： Michael S. Gray ,  Matthew T. Guzowski ,  Kevin W. McCullen ,  Xiaoping Tang ,  Robert F. Walker ,  Xin Yuan

IPC分类号： G06F17/50

CPC分类号： G06F17/5068 ,  G06F2217/08

摘要： An adaptive weighting method for layout optimization differentiates different priorities by assigning the weight of a higher priority (pi) to be multiple of the weight of a lower priority (pi−1) where W(pi)=mi % W(pi−1. To avoid numerical imprecision, this method keeps the total cost in the objective function within a trustable range by scaling the initial weights in the objectives, while maintaining relativity, to produce the scaled weights.

摘要翻译： 用于布局优化的自适应加权方法通过将较高优先级（pi）的权重分配为较低优先级（pi-1）的权重的倍数来区分不同的优先级，其中W（pi）= mi％W（pi-1） 为了避免数值不精确，该方法将目标函数中的总成本保持在可信范围内，通过缩放目标中的初始权重，同时维持相对性，以产生缩放权重。

公开(公告)号：US08302062B2

公开(公告)日：2012-10-30

申请号：US12712880

申请日：2010-02-25

申请人： Michael S. Gray ,  Xiaoping Tang ,  Xin Yuan

发明人： Michael S. Gray ,  Xiaoping Tang ,  Xin Yuan

IPC分类号： G06F17/50

CPC分类号： G06F17/5068

摘要： An approach that obtains a feasible integer solution in a hierarchical circuit layout optimization is described. In one embodiment, a hierarchical circuit layout and ground rule files are received as input. Constraints in the hierarchical circuit layout are represented as an original integer linear programming problem. A relaxed linear programming problem is derived from the original integer linear programming problem by relaxing integer constraints and using relaxation variables on infeasible constraints. The relaxed linear programming problem is solved to obtain a linear programming solution. Variables are then clustered, and at least one variable from each cluster is rounded to an integer value according to the linear programming solution. Next, it is determined whether all the variables are rounded to integer values. Unrounded variables are iterated back through the deriving of the integer linear programming problem, solving of the relaxed linear programming problem, and rounding of a subset of variables. A modified hierarchical circuit layout is generated in response to a determination that all the variables are rounded to integer values.

摘要翻译： 描述了在分层电路布局优化中获得可行整数解的方法。 在一个实施例中，接收分级电路布局和接地规则文件作为输入。 分层电路布局中的约束被表示为原始的整数线性规划问题。 通过放松整数约束和对不可行约束使用松弛变量，从原始整数线性规划问题导出松弛的线性规划问题。 解决了松弛的线性规划问题，以获得线性规划解决方案。 然后将变量进行聚类，根据线性规划解决方案，每个集群中至少有一个变量将四舍五入为整数值。 接下来，确定所有变量是否四舍五入为整数值。 通过导出整数线性规划问题，解决松弛线性规划问题以及变量子集的舍入来迭代未包围的变量。 响应于所有变量被舍入到整数值的确定而产生修改的分层电路布局。

公开(公告)号：US07761818B2

公开(公告)日：2010-07-20

申请号：US11782706

申请日：2007-07-25

申请人： Michael S. Gray ,  Xiaoping Tang ,  Xin Yuan

发明人： Michael S. Gray ,  Xiaoping Tang ,  Xin Yuan

IPC分类号： G06F17/50

CPC分类号： G06F17/5068

摘要： An approach that obtains a feasible integer solution in a hierarchical circuit layout optimization is described. In one embodiment, a hierarchical circuit layout and ground rule files are received as input. Constraints in the hierarchical circuit layout are represented as an original integer linear programming problem. A relaxed linear programming problem is derived from the original integer linear programming problem by relaxing integer constraints and using relaxation variables on infeasible constraints. The relaxed linear programming problem is solved to obtain a linear programming solution. A subset of variables from the relaxed linear programming problem is rounded to integer values according to the linear programming solution. Next, it is determined whether all the variables are rounded to integer values. Unrounded variables are iterated back through the deriving of the integer linear programming problem, solving of the relaxed linear programming problem, and rounding of a subset of variables. A modified hierarchical circuit layout is generated in response to a determination that all the variables are rounded to integer values.

摘要翻译： 描述了在分层电路布局优化中获得可行整数解的方法。 在一个实施例中，接收分级电路布局和接地规则文件作为输入。 分层电路布局中的约束被表示为原始的整数线性规划问题。 通过放松整数约束和对不可行约束使用松弛变量，从原始整数线性规划问题导出松弛的线性规划问题。 解决了松弛的线性规划问题，以获得线性规划解决方案。 来自松弛线性规划问题的变量子集根据线性规划解决方案舍入为整数值。 接下来，确定所有变量是否四舍五入为整数值。 通过导出整数线性规划问题，解决松弛线性规划问题以及变量子集的舍入来迭代未包围的变量。 响应于所有变量被舍入到整数值的确定而产生修改的分层电路布局。

公开(公告)号：US20100153892A1

公开(公告)日：2010-06-17

申请号：US12712880

申请日：2010-02-25

申请人： Michael S. Gray ,  Xiaoping Tang ,  Xin Yuan

发明人： Michael S. Gray ,  Xiaoping Tang ,  Xin Yuan

IPC分类号： G06F17/50

CPC分类号： G06F17/5068

摘要： An approach that obtains a feasible integer solution in a hierarchical circuit layout optimization is described. In one embodiment, a hierarchical circuit layout and ground rule files are received as input. Constraints in the hierarchical circuit layout are represented as an original integer linear programming problem. A relaxed linear programming problem is derived from the original integer linear programming problem by relaxing integer constraints and using relaxation variables on infeasible constraints. The relaxed linear programming problem is solved to obtain a linear programming solution. Variables are then clustered, and at least one variable from each cluster is rounded to an integer value according to the linear programming solution. Next, it is determined whether all the variables are rounded to integer values. Unrounded variables are iterated back through the deriving of the integer linear programming problem, solving of the relaxed linear programming problem, and rounding of a subset of variables. A modified hierarchical circuit layout is generated in response to a determination that all the variables are rounded to integer values.

摘要翻译： 描述了在分层电路布局优化中获得可行整数解的方法。 在一个实施例中，接收分级电路布局和接地规则文件作为输入。 分层电路布局中的约束被表示为原始的整数线性规划问题。 通过放松整数约束和对不可行约束使用松弛变量，从原始整数线性规划问题导出松弛的线性规划问题。 解决了松弛的线性规划问题，以获得线性规划解决方案。 然后将变量进行聚类，根据线性规划解决方案，每个集群中至少有一个变量将四舍五入为整数值。 接下来，确定所有变量是否四舍五入为整数值。 通过导出整数线性规划问题，解决松弛线性规划问题以及变量子集的舍入来迭代未包围的变量。 响应于所有变量被舍入到整数值的确定而产生修改的分层电路布局。

公开(公告)号：US20090031259A1

公开(公告)日：2009-01-29

申请号：US11782706

申请日：2007-07-25

申请人： Michael S. Gray ,  Xiaoping Tang ,  Xin Yuan

发明人： Michael S. Gray ,  Xiaoping Tang ,  Xin Yuan

IPC分类号： G06F17/50

CPC分类号： G06F17/5068

摘要： An approach that obtains a feasible integer solution in a hierarchical circuit layout optimization is described. In one embodiment, a hierarchical circuit layout and ground rule files are received as input. Constraints in the hierarchical circuit layout are represented as an original integer linear programming problem. A relaxed linear programming problem is derived from the original integer linear programming problem by relaxing integer constraints and using relaxation variables on infeasible constraints. The relaxed linear programming problem is solved to obtain a linear programming solution. A subset of variables from the relaxed linear programming problem is rounded to integer values according to the linear programming solution. Next, it is determined whether all the variables are rounded to integer values. Unrounded variables are iterated back through the deriving of the integer linear programming problem, solving of the relaxed linear programming problem, and rounding of a subset of variables. A modified hierarchical circuit layout is generated in response to a determination that all the variables are rounded to integer values.

摘要翻译： 描述了在分层电路布局优化中获得可行整数解的方法。 在一个实施例中，接收分级电路布局和接地规则文件作为输入。 分层电路布局中的约束被表示为原始的整数线性规划问题。 通过放松整数约束和对不可行约束使用松弛变量，从原始整数线性规划问题导出松弛的线性规划问题。 解决了松弛的线性规划问题，以获得线性规划解决方案。 来自松弛线性规划问题的变量子集根据线性规划解决方案舍入为整数值。 接下来，确定所有变量是否四舍五入为整数值。 通过导出整数线性规划问题，解决松弛线性规划问题以及变量子集的舍入来迭代未包围的变量。 响应于所有变量被舍入到整数值的确定而产生修改的分层电路布局。