公开(公告)号：US20060031802A1

公开(公告)日：2006-02-09

申请号：US10896495

申请日：2004-07-22

申请人： Charles Alpert ,  Gi-Joon Nam ,  Paul Villarrubia

发明人： Charles Alpert ,  Gi-Joon Nam ,  Paul Villarrubia

IPC分类号： G06F17/50

CPC分类号： G06F17/5072

摘要： A method of designing a layout of an integrated circuit, by grouping a plurality of logic cells in a region of the integrated circuit into at least two separate clusters, placing the clusters in the region of the integrated circuit to optimize total wire length between the clusters (e.g., using quadratic placement), partitioning the region, and recursively repeating the placing and the partitioning to place the logic cells in progressively smaller bins of the region, while ungrouping the clusters. Clustering preferably groups smaller logic cells before grouping larger logic cells, and can be repeated iteratively with further re-grouping of the clusters, prior to the placing and partitioning. The number of iterations can be limited by an operator input parameter. A given cluster is ungrouped when its size is larger than a fraction of total free space available in a corresponding bin. This fraction can also be an operator input parameter.

摘要翻译： 一种通过将集成电路的区域中的多个逻辑单元分组成至少两个分离的集群来设计集成电路的布局的方法，将集群放置在集成电路的区域中以优化集群之间的总线长度 （例如，使用二次放置），对该区域进行分区，以及递归地重复放置和分割以将逻辑单元放置在该区域的逐渐更小的块中，同时取消对该簇的分组。 在分组较大的逻辑单元之前，聚类优选地组合较小的逻辑单元，并且可以在放置和分割之前进一步重新分组聚类来迭代重复。 迭代次数可以由操作员输入参数限制。 当一个给定的集群的大小大于对应的bin中可用空闲空间的一小部分时，它将被取消分组。 该分数也可以是操作员输入参数。

公开(公告)号：US20060031804A1

公开(公告)日：2006-02-09

申请号：US10996293

申请日：2004-11-22

申请人： Charles Alpert ,  Gi-Joon Nam ,  Sherief Reda ,  Paul Villarrubia

发明人： Charles Alpert ,  Gi-Joon Nam ,  Sherief Reda ,  Paul Villarrubia

IPC分类号： G06F17/50

CPC分类号： G06F17/5072 ,  G06F17/50

摘要： A placement technique for designing a layout of an integrated circuit by calculating clustering scores for different pairs of objects in the layout based on connections of two objects in a given pair and the sizes of the two objects, then grouping at least one of the pairs of objects into a cluster based on the clustering scores, partitioning the objects as clustered and ungrouping the cluster after partitioning. The pair of objects having the highest clustering score are grouped into the cluster, and the clustering score is directly proportional to the total weight of connections between the two objects in the respective pair. The clustering scores are preferably inserted in a binary heap to identify the highest clustering score. After grouping, the clustering score for any neighboring object of a clustered object is marked to indicate that the clustering score is invalid and must be recalculated. The calculating and grouping are then repeated iteratively based on the previous clustered layout. Cluster growth can be controlled indirectly, or controlled directly by imposing an upper bound on cluster size.

摘要翻译： 一种用于通过基于给定对中的两个对象的连接和两个对象的大小的布局来计算布局中的不同对对象的聚类分数来设计集成电路的布局的布局技术，然后将至少一个对 对象基于聚类分数进入群集，将对象分区为群集，并在分区后取消分组群集。 具有最高聚类分数的一对对象被分组到聚类中，并且聚类分数与相应对中两个对象之间的连接的总权重成正比。 聚类分数优选插入二进制堆中以识别最高聚类分数。 分组后，将聚类对象的任何邻近对象的聚类分数标记为表示聚类分数无效并且必须重新计算。 然后基于先前的聚类布局迭代地重复计算和分组。 群集增长可以间接控制，也可以通过对群集大小施加上限直接控制。

公开(公告)号：US20050015738A1

公开(公告)日：2005-01-20

申请号：US10621950

申请日：2003-07-17

申请人： Charles Alpert ,  Gary Ellis ,  Gi-Joon Nam ,  Paul Villarrubia

发明人： Charles Alpert ,  Gary Ellis ,  Gi-Joon Nam ,  Paul Villarrubia

IPC分类号： G06F9/45 ,  G06F17/50

CPC分类号： G06F17/5045 ,  G06F17/5072

摘要： A method of designing an integrated circuit including executing a placement algorithm to place a set of objects within the integrated circuit. The set of objects includes latched objects and non-latched objects. The algorithm places objects to minimize clock signal delay subject to a constraint on the placement distribution of the latched objects relative to the placement distribution of the non-latched objects. The latched object and non-latched object placement constraints may limit the difference between the latched object center of mass and a non-latched object center of mass. The latched object center of mass equals a sum of size-location products for each latched object divided by the sum of sizes for each latched object. The constraints may require that the latched object center of mass and the non-latched center of mass both equal the center of mass for all objects.

摘要翻译： 一种设计集成电路的方法，包括执行放置算法以将一组对象放置在集成电路内。 对象集包括锁存对象和非锁定对象。 该算法使对象最小化时钟信号延迟，受限于锁存对象相对于非锁定对象的位置分布的位置分布。 锁定对象和非锁定对象放置约束可能会限制被锁定的物体质心和未锁定的物体质心之间的差异。 被锁定的物体质心等于每个被锁定物体的大小位置乘积之和除以每个锁定物体的大小之和。 约束可能要求被锁定的物体质心和非锁定质心均等于所有物体的质心。

公开(公告)号：US20050235237A1

公开(公告)日：2005-10-20

申请号：US10825148

申请日：2004-04-15

申请人： Charles Alpert ,  Gi-Joon Nam ,  Paul Villarrubia ,  Mehmet Yildiz

发明人： Charles Alpert ,  Gi-Joon Nam ,  Paul Villarrubia ,  Mehmet Yildiz

IPC分类号： G06F9/45 ,  G06F17/50

CPC分类号： G06F17/5072

摘要： A method of assessing the stability of a placement tool used in designing the physical layout of an integrated circuit chip, by constructing different layouts of cells using the placement tool with different sets of input parameters, and calculating a stability value based on the movement of respective cell locations between the layouts. The stability value can be normalized based on cell locations in a random placement. One stability metric measures absolute movement of individual cells in the layouts, weighted by cell area. The cell movements can be squared in calculating the stability value. Another stability metric measures the relative movement of cells with respect to their nets. Shifting of cells and symmetric reversal of cells about a net center does not contribute to this relative movement, but spreading of cells and rotation of cells with respect to the net center does contribute to the relative movement. Relative cell movements can again be squared in calculating the stability value. Many different layouts can be designed using the same placement tool with a range of different input parameters and different movement metrics to build a collection of comparative values that can be used to identify stability characteristics for that tool.

摘要翻译： 一种评估用于设计集成电路芯片的物理布局的放置工具的稳定性的方法，通过使用具有不同输入参数集合的放置工具构造不同的单元布局，以及基于相应的运动来计算稳定性值 单元格位置之间的布局。 稳定性值可以根据随机位置中的单元格位置进行归一化。 一个稳定度度量衡量单元格在布局中的绝对运动，由单元格区域加权。 在计算稳定性值时，单元格移动可以平方。 另一个稳定度量度衡量细胞相对于网的相对运动。 细胞的移位和细胞对网络中心的对称反转对这种相对运动没有贡献，但是细胞的扩散和细胞的相对于网络中心的旋转确实有助于相对运动。 在计算稳定性值时，相对单元移动可以再次平方。 可以使用具有一系列不同输入参数和不同运动度量的相同放置工具来设计许多不同的布局，以构建可用于识别该工具的稳定性特征的比较值集合。

公开(公告)号：US20050086622A1

公开(公告)日：2005-04-21

申请号：US10687246

申请日：2003-10-16

申请人： Charles Alpert ,  Gi-Joon Nam ,  Paul Villarrubia

发明人： Charles Alpert ,  Gi-Joon Nam ,  Paul Villarrubia

IPC分类号： G06F9/45 ,  G06F17/50

CPC分类号： G06F17/5072

摘要： A method of designing a layout of an integrated circuit first places logic cells in an initial region of the integrated circuit using a first placement algorithm then, after partitioning the initial region into two or more partitioned regions, uses a second placement algorithm (different from the first placement algorithm) to place a portion of the logic cells in at least one of the partitioned regions. The placement algorithms are preferably quadratic placement algorithms such as the conjugate gradient placement algorithm and the successive over-relaxation placement algorithm. The selection of the particular placement algorithm to be used may be based on, e.g., the cut level or the number moveable objects for the given partition region.

摘要翻译： 设计集成电路的布局的方法首先使用第一放置算法将逻辑单元放置在集成电路的初始区域中，然后在将初始区划分成两个或更多个分区之后，使用第二放置算法（不同于 第一放置算法）将逻辑单元的一部分放置在至少一个分割区域中。 放置算法优选地是二次放置算法，例如共轭梯度放置算法和连续过度弛放放置算法。 要使用的特定布局算法的选择可以基于例如给定分区区域的切割级别或数量可移动对象。

公开(公告)号：US20070143724A1

公开(公告)日：2007-06-21

申请号：US11304955

申请日：2005-12-15

申请人： Charles Alpert ,  Haoxing Ren ,  Paul Villarrubia

发明人： Charles Alpert ,  Haoxing Ren ,  Paul Villarrubia

IPC分类号： G06F17/50

CPC分类号： G06F17/5072

摘要： A method, apparatus, and computer program product for cell placement in an integrated circuit design that use the principles of diffusion.

摘要翻译： 用于使用扩散原理的集成电路设计中的单元格放置的方法，装置和计算机程序产品。

公开(公告)号：US20050166169A1

公开(公告)日：2005-07-28

申请号：US10766549

申请日：2004-01-27

申请人： Zahi Kurzum ,  Paul Villarrubia ,  Shyam Ramji

发明人： Zahi Kurzum ,  Paul Villarrubia ,  Shyam Ramji

IPC分类号： G06F17/50

CPC分类号： G06F17/5072

摘要： A method for resolving overlaps in the cell placement (placement legalization) during the physical design phase of an integrated chip design is described. This problem arises in several contexts within the physical design automation area including global and detailed placement, physical synthesis, and ECO (Engineering Change Order) mode for timing/design closure The method involves capturing a view of a given placement, solving a global two-dimensional area migration model and locally perturbing the cells to resolve the overlaps with minimal changes to the given placement. The method first captures a two-dimensional view of the placement including blockage-space, free-space and the given location of cells by defining physical regions. The desired global area migration across the physical regions of the placement image is determined such that it satisfies area capacity-demand constraints. The method also provides moving the cells between physical regions along previously computed directions of migration to minimize the movement cost. Also provided is an approximate method to model the movement of multi-row high cells.

摘要翻译： 描述了在集成芯片设计的物理设计阶段期间解决单元格放置（布局合法化）中的重叠的方法。 这个问题出现在物理设计自动化领域中的几个环境中，包括全局和详细的布局，物理综合以及用于定时/设计闭合的ECO（工程变更订单）模式。该方法涉及捕获给定位置的视图， 三维区域迁移模型和本地扰动单元格以解决重叠，给定位置的最小变化。 该方法首先通过定义物理区域来捕获位置的二维视图，包括阻塞空间，自由空间和单元格的给定位置。 确定放置图像的物理区域的期望的全局区域迁移使其满足区域容量需求约束。 该方法还提供沿着先前计算的迁移方向在物理区域之间移动小区以最小化移动成本。 还提供了一种用于建模多列高单元移动的近似方法。

公开(公告)号：US20050166164A1

公开(公告)日：2005-07-28

申请号：US10707942

申请日：2004-01-27

申请人： Haoxing Ren ,  Paul Villarrubia ,  Zahi Kurzum ,  Shyam Ramji

发明人： Haoxing Ren ,  Paul Villarrubia ,  Zahi Kurzum ,  Shyam Ramji

IPC分类号： G06F17/50

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

摘要： A generalized method for optimizing the global placement of a VLSI chip across multiple cost metrics, such as total wire length, timing, congestion, and signal integrity is described. The method relies upon a “look ahead” technique, combined with any generic cost function that can be used to set placement directives. These placement directives include net weights and cell spreading. The method of performing the placement involves the iterative reuse of the process of successive partitioning. This iterative reuse establishes the capability of looking ahead to determine what is to happen. Based on the look ahead, it is possible to evaluate the qualities of the placement about to be generated. The method proceeds through the placement from while maintaining the current state of the placement along with the look-ahead state of the placement. Directives are generated and modified in order that the next steps applied to the current state of the placement will cause it to change to achieve an ultimate higher quality final output.

摘要翻译： 描述了用于优化跨多个成本度量（例如总线长度，时间，拥塞和信号完整性）的VLSI芯片的全局放置的通用方法。 该方法依赖于“前瞻性”技术，并结合可用于设置布局指令的任何通用成本函数。 这些放置指令包括净重和细胞扩散。 执行放置的方法涉及对连续分区的过程的迭代重用。 这种迭代重用建立了展望未来可能发生的事情的能力。 根据展望，可以评估要生成的展示位置的质量。 该方法从保持布局的当前状态以及放置的预先状态的同时继续进行放置。 生成和修改指令，以便应用于当前布局状态的下一步骤将导致其更改以实现最终更高质量的最终输出。

公开(公告)号：US07089521B2

公开(公告)日：2006-08-08

申请号：US10766549

申请日：2004-01-27

申请人： Zahi M. Kurzum ,  Paul Villarrubia ,  Shyam Ramji

发明人： Zahi M. Kurzum ,  Paul Villarrubia ,  Shyam Ramji

IPC分类号： G06F9/45 ,  G06F17/50

CPC分类号： G06F17/5072

摘要： A method for resolving overlaps in the cell placement (placement legalization) during the physical design phase of an integrated chip design is described. This problem arises in several contexts within the physical design automation area including global and detailed placement, physical synthesis, and ECO (Engineering Change Order) mode for timing/design closure The method involves capturing a view of a given placement, solving a global two-dimensional area migration model and locally perturbing the cells to resolve the overlaps with minimal changes to the given placement. The method first captures a two-dimensional view of the placement including blockage-space, free-space and the given location of cells by defining physical regions. The desired global area migration across the physical regions of the placement image is determined such that it satisfies area capacity-demand constraints. The method also provides moving the cells between physical regions along previously computed directions of migration to minimize the movement cost. Also provided is an approximate method to model the movement of multi-row high cells.

摘要翻译： 描述了在集成芯片设计的物理设计阶段期间解决单元格放置（布局合法化）中的重叠的方法。 这个问题出现在物理设计自动化领域中的几个环境中，包括全局和详细的布局，物理综合以及用于定时/设计闭合的ECO（工程变更订单）模式。该方法涉及捕获给定位置的视图， 三维区域迁移模型和本地扰动单元格以解决重叠，给定位置的最小变化。 该方法首先通过定义物理区域来捕获位置的二维视图，包括阻塞空间，自由空间和单元格的给定位置。 确定放置图像的物理区域的期望的全局区域迁移使其满足区域容量需求约束。 该方法还提供沿着先前计算的迁移方向在物理区域之间移动小区以最小化移动成本。 还提供了一种用于建模多列高单元移动的近似方法。

公开(公告)号：US07076755B2

公开(公告)日：2006-07-11

申请号：US10707942

申请日：2004-01-27

申请人： Haoxing Ren ,  Paul Villarrubia ,  Zahi M. Kurzum ,  Shyam Ramji

发明人： Haoxing Ren ,  Paul Villarrubia ,  Zahi M. Kurzum ,  Shyam Ramji

IPC分类号： G06F17/50

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

摘要： A generalized method for optimizing the global placement of a VLSI chip across multiple cost metrics, such as total wire length, timing, congestion, and signal integrity is described. The method relies upon a “look ahead” technique, combined with any generic cost function that can be used to set placement directives. These placement directives include net weights and cell spreading. The method of performing the placement involves the iterative reuse of the process of successive partitioning. This iterative reuse establishes the capability of looking ahead to determine what is to happen. Based on the look ahead, it is possible to evaluate the qualities of the placement about to be generated. The method proceeds through the placement from while maintaining the current state of the placement along with the look-ahead state of the placement. Directives are generated and modified in order that the next steps applied to the current state of the placement will cause it to change to achieve an ultimate higher quality final output.

摘要翻译： 描述了用于优化跨多个成本度量（例如总线长度，时间，拥塞和信号完整性）的VLSI芯片的全局放置的通用方法。 该方法依赖于“前瞻性”技术，并结合可用于设置布局指令的任何通用成本函数。 这些放置指令包括净重和细胞扩散。 执行放置的方法涉及对连续分区的过程的迭代重用。 这种迭代重用建立了展望未来可能发生的事情的能力。 根据展望，可以评估要生成的展示位置的质量。 该方法从保持布局的当前状态以及放置的预先状态的同时继续进行放置。 生成和修改指令，以便应用于当前状态的下一步骤将导致其更改以实现最终更高质量的最终输出。