公开(公告)号：US20050138578A1

公开(公告)日：2005-06-23

申请号：US10738711

申请日：2003-12-17

申请人： Charles Alpert ,  Rama Gandham ,  Milos Hrkic ,  Stephen Quay

发明人： Charles Alpert ,  Rama Gandham ,  Milos Hrkic ,  Stephen Quay

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

CPC分类号： G06F17/5077 ,  G06F17/505

摘要： A mechanism for constructing Steiner trees using simultaneous blockage avoidance, delay optimization, and design density management are provided. An initial tiled timing-driven Steiner tree is obtained for an integrated circuit design. The Steiner tree is broken into 2-paths for which plates are generated designated the permissible area in which a Steiner point may migrate. Each 2-path is optimized by calculating a cost for each tile in the plate as a function of an environmental cost, a tile delay cost, and a trade-off value. A minimum cost tile is then selected as the point to which the Steiner point in the 2-path, if any, is to migrate. Once each 2-path is processed in this manner, routing is performed so as to minimize the cost at the source. This process may be iteratively repeated with new trade-off values until all of the nets have zero or positive slew.

摘要翻译： 提供了一种使用同时阻止避免，延迟优化和设计密度管理构建Steiner树的机制。 获得用于集成电路设计的初始平铺时序驱动的Steiner树。 Steiner树被分解为2路径，其中生成了板，指定Steiner点可能迁移的允许区域。 通过根据环境成本，瓦片延迟成本和折衷值计算板中每个瓦片的成本来优化每个2路径。 然后选择最小成本图块作为2路径中Steiner点（如果有）要迁移的点。 一旦以这种方式处理了每个2路径，就执行路由以最小化源的成本。 可以用新的权衡值迭代地重复该过程，直到所有网络具有零或正的摆动。

公开(公告)号：US20050138589A1

公开(公告)日：2005-06-23

申请号：US10738714

申请日：2003-12-17

申请人： Charles Alpert ,  Milos Hrkic ,  Stephen Quay

发明人： Charles Alpert ,  Milos Hrkic ,  Stephen Quay

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

CPC分类号： G06F17/5077

摘要： A method, apparatus, and computer program product for performing density biased buffer insertion in an integrated circuit design are provided. A tiled Steiner tree topology map is used in which density values are associated with each tile in the map. A directed acyclic graph (DAG) is created over an initial set of potential candidate points. A subset of the candidate points is selected by associating costs with each tile, and with each path or edge, to each tile. The total costs associated with placement of a buffer at a position within each tile are calculated. The lowest cost tile is then selected as a candidate position for buffer insertion. This process is then repeated to obtain an asymmetrically distributed set of candidate buffer insertion points between a source and a sink.

摘要翻译： 提供了一种用于在集成电路设计中执行密度偏移缓冲器插入的方法，装置和计算机程序产品。 使用平铺的Steiner树拓扑图，其中密度值与地图中的每个图块相关联。 在一组初始潜在候选点上创建有向非循环图（DAG）。 通过将成本与每个瓦片相关联，并将每个路径或边缘与每个瓦片相关联来选择候选点的子集。 计算与在每个平铺内的位置放置缓冲区相关联的总成本。 然后选择最低成本图块作为缓冲区插入的候选位置。 然后重复该过程以获得在源和宿之间的不对称分布的候选缓冲区插入点集合。

公开(公告)号：US20060156266A1

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

申请号：US11032878

申请日：2005-01-11

申请人： Charles Alpert ,  Zhuo Li ,  Stephen Quay

发明人： Charles Alpert ,  Zhuo Li ,  Stephen Quay

IPC分类号： G06F17/50

CPC分类号： G06F17/5077

摘要： A method of estimating routing congestion between pins in a net of an integrated circuit design, by establishing one or more potential routes between the pins which pass through buckets in the net, assigning a probabilistic usage to each bucket based on any partial blockage of the wiring tracks in each bucket, and computing routing congestion for each bucket using its probabilistic usage. When the net is a two-pin net that is a part of a larger multi-pin net, and a tree is constructed to bridge the two-pin net to another pin of the multi-pin net. The routing congestion for each bucket is computed as a ratio of the bucket usage to bucket capacity. For L-shaped routes (having at least one bend in a bucket), the probabilistic usage is proportional to a scale factor a which is a ratio of a minimum number of available wiring tracks for a given route to a sum of minimum numbers of available wiring tracks for all possible routes. For Z-shaped routes (having at least two bends in two respective buckets), the probabilistic usage is equal to a ratio of a minimum capacity of a given route to a sum of minimum capacities of all routes having an associated orientation with the given route. Assignment of the usage values may entail the creation of a temporary usage map of the net buckets with an initial value of zero usage in every temporary usage map bucket, thereafter storing usage values in corresponding buckets of the temporary usage map, and deriving a final usage map from the temporary usage map

摘要翻译： 一种在集成电路设计的网络中估计引脚之间的路由拥塞的方法，通过在通过网络中的网段的引脚之间建立一个或多个潜在路由，基于线路的任何部分阻塞向每个分组分配概率使用 每个桶中的轨道，以及使用其概率使用来计算每个桶的路由拥塞。 当网是作为较大多针网的一部分的双引脚网络，并且构造一棵树将双引脚网络桥接到多引脚网的另一个引脚。 每个桶的路由拥塞被计算为桶使用量与桶容量的比率。 对于L形路径（在桶中至少有一个弯道），概率使用与比例因子a成比例，比例因子a是给定路线的可用线路的最小数量与可用的最小数量之和的比率 所有可能的路线的线路。 对于Z形路线（在两个相应的桶中具有至少两个弯曲），概率使用等于给定路由的最小容量与具有与给定路由相关联的定向的所有路由的最小容量之和的比率 。 使用值的分配可能需要在每个临时使用地图桶中创建具有零使用的初始值的网络桶的临时使用图，然后将使用值存储在临时使用映射的相应桶中，并且导出最终使用 从临时使用地图映射

公开(公告)号：US20060112364A1

公开(公告)日：2006-05-25

申请号：US10996292

申请日：2004-11-22

申请人： Charles Alpert ,  Zhuo Li ,  Stephen Quay

发明人： Charles Alpert ,  Zhuo Li ,  Stephen Quay

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

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

摘要： A method of determining buffer insertion locations in an integrated circuit design establishes candidate locations for inserting buffers into a net, and selects buffer insertion locations from among the candidates based on slew constraints. The selection of buffer insertion locations preferably optimizes slack and buffer cost while keeping slew from any buffered node to any sink less than a required slew rate. The slew analysis computes an output slew SL(v) of a given buffer b inserted at a node v as SL(v)=RS(b)·C(v)+KS(b), where C(v) is the downstream capacitance at v, RS(b) is the slew resistance of buffer b, and KS(b) is the intrinsic slew of buffer b. The delay through a given buffer may also be computed based on signal polarity. However, the invention still preferably uses worst-case slew resistance and intrinsic slew in considering the slew constraints. If the selection of the buffer insertion locations results in no locations being selected due to slew violations, the present invention may advantageously find a partial solution by relaxing the slew constraint.

摘要翻译： 在集成电路设计中确定缓冲器插入位置的方法建立了用于将缓冲器插入网络的候选位置，并且基于回转约束从候选中选择缓冲器插入位置。 缓冲器插入位置的选择优选地优化松弛和缓冲器成本，同时保持从任何缓冲节点转到任何小于所需转换速率的接收端。 滑动分析计算插入在节点v处的给定缓冲器b的输出滑动SL（v）为SL（v）= RS（b）.C（v）+ KS（b），其中C（v）是下游 电容在v，RS（b）是缓冲器b的耐压，KS（b）是缓冲器b的固有电压。 也可以基于信号极性来计算给定缓冲器的延迟。 然而，本发明在考虑压摆约束的情况下仍然优选地使用最坏情况的耐回转电阻和固有的电压。 如果缓冲器插入位置的选择导致没有被选择的位置，因为本发明可以通过放松压摆约束来有利地找到部分解决方案。

公开(公告)号：US20080072202A1

公开(公告)日：2008-03-20

申请号：US11947706

申请日：2007-11-29

申请人： Charles Alpert ,  Zhuo Li ,  Stephen Quay

发明人： Charles Alpert ,  Zhuo Li ,  Stephen Quay

IPC分类号： G06F17/50

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

摘要： A method of determining buffer insertion locations in an integrated circuit design establishes candidate locations for inserting buffers into a net, and selects buffer insertion locations from among the candidates based on slew constraints. The selection of buffer insertion locations preferably optimizes slack and buffer cost while keeping slew from any buffered node to any sink less than a required slew rate. The slew analysis computes an output slew SL(v) of a given buffer b inserted at a node v as SL(v)=RS(b)·C(v)+KS(b), where C(v) is the downstream capacitance at v, RS(b) is the slew resistance of buffer b, and KS(b) is the intrinsic slew of buffer b. The delay through a given buffer may also be computed based on signal polarity. However, the invention still preferably uses worst-case slew resistance and intrinsic slew in considering the slew constraints. If the selection of the buffer insertion locations results in no locations being selected due to slew violations, the present invention may advantageously find a partial solution by relaxing the slew constraint.

摘要翻译： 在集成电路设计中确定缓冲器插入位置的方法建立了用于将缓冲器插入网络的候选位置，并且基于回转约束从候选中选择缓冲器插入位置。 缓冲器插入位置的选择优选地优化松弛和缓冲器成本，同时保持从任何缓冲节点转到任何小于所需转换速率的接收端。 滑动分析计算插入在节点v处的给定缓冲器b的输出滑动SL（v）为SL（v）= RS（b）.C（v）+ KS（b），其中C（v）是下游 电容在v，RS（b）是缓冲器b的耐压，KS（b）是缓冲器b的固有电压。 也可以基于信号极性来计算给定缓冲器的延迟。 然而，本发明在考虑压摆约束的情况下仍然优选地使用最坏情况的耐回转电阻和固有的电压。 如果缓冲器插入位置的选择导致没有被选择的位置，因为本发明可以通过放松压摆约束来有利地找到部分解决方案。

公开(公告)号：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.

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

公开(公告)号：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.

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