公开(公告)号：US06591411B2

公开(公告)日：2003-07-08

申请号：US09810075

申请日：2001-03-15

申请人： Charles Jay Alpert ,  Rama Gopal Gandham ,  Jiang Hu ,  Stephen Thomas Quay ,  Andrew James Sullivan

发明人： Charles Jay Alpert ,  Rama Gopal Gandham ,  Jiang Hu ,  Stephen Thomas Quay ,  Andrew James Sullivan

IPC分类号： G06F1750

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

摘要： An apparatus and method for determining buffered Steiner trees for complex circuits is provided. The apparatus and method first clusters sinks with similar characteristics such as criticality, polarity and distance. The purpose of this step is to potentially isolate positive sinks from negative ones and non-critical sinks from critical ones. The present invention then constructs low-level Steiner trees over each of these clusters. Finally, a top-level timing driven Steiner tree is computed where each cluster is treated as a sink. The top-level tree is then merged with the low-level trees to yield a solution for the entire net.

公开(公告)号：US06915496B2

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

申请号：US10255469

申请日：2002-09-26

申请人： Charles Jay Alpert ,  Chong-Nuen Chu ,  Rama Gopal Gandham ,  Milos Hrkic ,  Jiang Hu ,  Chandramouli V. Kashyap ,  Stephen Thomas Quay

发明人： Charles Jay Alpert ,  Chong-Nuen Chu ,  Rama Gopal Gandham ,  Milos Hrkic ,  Jiang Hu ,  Chandramouli V. Kashyap ,  Stephen Thomas Quay

IPC分类号： G06F17/50

CPC分类号： G06F17/505

摘要： An apparatus and method for incorporating driver sizing into buffer insertion such that the two optimization techniques are performed simultaneously are provided. The apparatus and method extends van Ginneken's algorithm to handle driver sizing by treating a source node as a “driver library.” With the apparatus and method, the circuit design is converted to a Steiner tree representation of the circuit design. Buffer insertion is performed on the Steiner tree using the van Ginneken algorithm to generate a first set of possible optimal solutions. For each solution in the first set, a driver of the same type as the original driver in the Steiner tree is selected from a driver library and virtually inserted into the solution. A delay penalty is retrieved for the selected driver, which is then used long with the new driver's characteristics to generate a second set of solutions based o the first set of solutions.

摘要翻译： 提供了一种用于将驱动程序大小合并到缓冲器插入中以便同时执行两种优化技术的装置和方法。 该装置和方法扩展了van Ginneken的算法，通过将源节点视为“驱动程序库”来处理驱动程序大小。 利用该装置和方法，将电路设计转换为电路设计的Steiner树表示。 使用van Ginneken算法在Steiner树上执行缓冲区插入，以生成第一组可能的最优解。 对于第一组中的每个解决方案，从驱动程序库中选择与Steiner树中的原始驱动程序相同类型的驱动程序，并将其虚拟插入到解决方案中。 对于所选择的驱动程序检索延迟罚分，随后利用新驱动程序的特性，利用第一组解决方案生成第二组解决方案。

公开(公告)号：US07065730B2

公开(公告)日：2006-06-20

申请号：US10418469

申请日：2003-04-17

申请人： Charles Jay Alpert ,  Rama Gopal Gandham ,  Jiang Hu ,  Stephen Thomas Quay

发明人： Charles Jay Alpert ,  Rama Gopal Gandham ,  Jiang Hu ,  Stephen Thomas Quay

IPC分类号： G06F17/50

CPC分类号： G06F17/5077

摘要： A method, computer program product, and data processing system for porosity-aware buffered Steiner tree construction are disclosed. A preferred embodiment begins with a timing-driven Steiner tree generated without regard for porosity, then applies a plate-based adjustment guided by length-based buffer insertion. After performing localized blockage avoidance, the resulting tree is then passed to a buffer placement algorithm, such as van Ginneken's algorithm, to obtain a porosity-aware buffered Steiner tree.

摘要翻译： 公开了一种用于孔隙度感知缓冲Steiner树结构的方法，计算机程序产品和数据处理系统。 优选实施例从不考虑孔隙率产生的定时驱动的Steiner树开始，然后施加基于长度的缓冲器插入引导的基于板的调整。 在执行局部阻止避免之后，所得到的树然后被传递到缓冲器放置算法，例如van Ginneken的算法，以获得孔隙度感知缓冲的Steiner树。

公开(公告)号：US06898774B2

公开(公告)日：2005-05-24

申请号：US10324732

申请日：2002-12-18

申请人： Charles Jay Alpert ,  Rama Gopal Gandham ,  Jiang Hu ,  Stephen Thomas Quay

发明人： Charles Jay Alpert ,  Rama Gopal Gandham ,  Jiang Hu ,  Stephen Thomas Quay

IPC分类号： G06F17/50

CPC分类号： G06F17/5077

摘要： A method, computer program product, and data processing system for inserting buffers into integrated circuit routing trees are disclosed. The present invention dynamically modifies a Steiner tree configuration as needed to derive a maximal slack solution that takes into account blockages such as those presented by IP blocks.

摘要翻译： 公开了一种用于将缓冲器插入到集成电路布线树中的方法，计算机程序产品和数据处理系统。 本发明根据需要动态地修改Steiner树配置以导出考虑到由IP块所呈现的阻塞的最大松弛解决方案。

公开(公告)号：US06401234B1

公开(公告)日：2002-06-04

申请号：US09465294

申请日：1999-12-17

申请人： Charles Jay Alpert ,  Rama Gopal Gandham ,  Jiang Hu ,  Jose Luis Neves ,  Stephen Thomas Quay

发明人： Charles Jay Alpert ,  Rama Gopal Gandham ,  Jiang Hu ,  Jose Luis Neves ,  Stephen Thomas Quay

IPC分类号： G06F1750

CPC分类号： G06F17/5077

摘要： A method and system for re-routing interconnects within an integrated circuit design having blockages and bays is disclosed. A net within the integrated circuit design is initially decomposed into multiple two-paths. The net includes interconnects previously routed by utilizing a Steiner tree routing algorithm. Next, a cost associated with each of the two-paths is calculated. A two-path having a a high cost is subsequently selected and re-routed with a lower cost two-path.

摘要翻译： 公开了一种用于在具有阻塞和间隔的集成电路设计中重新路由互连的方法和系统。 集成电路设计中的网络最初分解成多个双向路径。 网络包括先前通过利用Steiner树路由算法路由的互连。 接下来，计算与每个双向路径相关联的成本。 随后选择具有高成本的双路径并以较低成本的双路径重新路由。

公开(公告)号：US07127696B2

公开(公告)日：2006-10-24

申请号：US10738711

申请日：2003-12-17

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

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

IPC分类号： 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路径，就执行路由以最小化源的成本。 可以用新的权衡值迭代地重复该过程，直到所有网络具有零或正的摆动。

公开(公告)号：US06560752B1

公开(公告)日：2003-05-06

申请号：US09611670

申请日：2000-07-06

申请人： Charles Jay Alpert ,  Rama Gopal Gandham ,  Jose Luis Pontes Correia Neves ,  Stephen Thomas Quay

发明人： Charles Jay Alpert ,  Rama Gopal Gandham ,  Jose Luis Pontes Correia Neves ,  Stephen Thomas Quay

IPC分类号： G06F1750

CPC分类号： G06F17/505

摘要： An apparatus and method for buffer selection for use in buffer insertion is provided. An optimal buffer library generator module operates to reduce a general buffer library down to a optimal buffer library based on parameters that are input to the optimal buffer library generator module. Based on these parameters, the optimal buffer library generator module selects buffers from the general buffer library for inclusion in an optimal buffer library. In a preferred embodiment, the optimal buffer library is generated by generating a set of superior buffers and inverters and clustering the set of superior buffers. A single buffer is then selected from each cluster for inclusion in the optimal buffer library. The result is a smaller buffer library which will provide approximately the same performance during buffer insertion while reducing the amount of computing time and memory requirements.

摘要翻译： 提供了用于缓冲​​器插入的缓冲器选择的装置和方法。 最佳缓冲库生成器模块可以根据输入到最优缓冲库生成器模块的参数，将通用缓冲库减少到最佳缓冲库。 基于这些参数，最优缓冲库生成器模块从通用缓冲库中选择缓冲区以包含在最优缓冲库中。 在优选实施例中，通过生成一组优越的缓冲器和反相器并对该组优越的缓冲器进行聚类来生成最佳缓冲器库。 然后从每个簇选择单个缓冲区以包含在最佳缓冲库中。 结果是一个较小的缓冲库，在缓冲区插入期间将提供大致相同的性能，同时减少计算时间和内存需求量。

公开(公告)号：US08386985B2

公开(公告)日：2013-02-26

申请号：US13102776

申请日：2011-05-06

申请人： Charles Jay Alpert ,  Zhuo Li ,  Stephen Thomas Quay ,  Ying Zhou

发明人： Charles Jay Alpert ,  Zhuo Li ,  Stephen Thomas Quay ,  Ying Zhou

IPC分类号： G06F17/50

CPC分类号： G06F17/5031 ,  G06F17/5077 ,  G06F2217/84

摘要： A method, system, and computer program product for timing driven routing in a design of an integrated circuit (IC) are provided in the illustrative embodiments. A router application executing in a data processing system performs a pre-global routing optimization of the design. A plurality of wirelength target constraints are set on a plurality of subsets of a set of nets in the design. Global routing is performed on the design. The design is adjusted using wires placed in the design during the global routing. A priority is assigned to each net in the set of nets. Detailed routing is performed on the design.

摘要翻译： 在说明性实施例中提供了用于在集成电路（IC）的设计中的定时驱动路由的方法，系统和计算机程序产品。 在数据处理系统中执行的路由器应用程序执行设计的全局前路由优化。 在设计中的一组网络的多个子集上设置多个线长目标约束。 在设计上执行全局路由。 在全局路由期间，使用设计中的电线来调整设计。 优先级分配给网络集合中的每个网络。 在设计上执行详细的路由。

公开(公告)号：US6117182A

公开(公告)日：2000-09-12

申请号：US94544

申请日：1998-06-12

申请人： Charles Jay Alpert ,  Stephen Thomas Quay ,  Anirudh Devgan

发明人： Charles Jay Alpert ,  Stephen Thomas Quay ,  Anirudh Devgan

IPC分类号： G06F17/50

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

摘要： A method for optimal insertion of buffers into an integrated circuit design. A model representative of a plurality of circuits is created where each circuit has a receiving node coupled to a conductor and a source. A receiving node is selected from the modeled plurality of circuits and circuit noise is calculated for the selected receiving node utilizing the circuit model. If the calculated circuit noise exceeds an acceptable value an optimum distance is computed from the receiving node on the conductor for buffer insertion. In a multi-sink circuit merging of the noise calculation for the two receiving circuits must be accomplished. If an intersection of conductors exists between the receiving node and the optimum distance a set of candidate buffer locations is generated. The method then prunes inferior solutions to provide an optimal insertion of buffers.

摘要翻译： 一种将缓冲器最佳插入集成电路设计的方法。 创建代表多个电路的模型，其中每个电路具有耦合到导体和源的接收节点。 从建模的多个电路中选择接收节点，并且利用电路模型为所选择的接收节点计算电路噪声。 如果计算出的电路噪声超过可接受的值，则从用于缓冲器插入的导体上的接收节点计算最佳距离。 在多宿电路中，必须实现两个接收电路的噪声计算合并。 如果在接收节点和最佳距离之间存在导体，则产生一组候选缓冲器位置。 该方法然后修剪较差的解决方案，以提供缓冲区的最佳插入。

公开(公告)号：US07392493B2

公开(公告)日：2008-06-24

申请号：US10996292

申请日：2004-11-22

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

发明人： Charles Jay Alpert ,  Zhuo Li ,  Stephen Thomas 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的固有电压。 也可以基于信号极性来计算给定缓冲器的延迟。 然而，本发明在考虑压摆约束的情况下仍然优选地使用最坏情况的耐回转电阻和固有的电压。 如果缓冲器插入位置的选择导致没有被选择的位置，因为本发明可以通过放松压摆约束来有利地找到部分解决方案。