公开(公告)号：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树中的原始驱动程序相同类型的驱动程序，并将其虚拟插入到解决方案中。 对于所选择的驱动程序检索延迟罚分，随后利用新驱动程序的特性，利用第一组解决方案生成第二组解决方案。

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

公开(公告)号：US07137081B2

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

申请号：US10738714

申请日：2003-12-17

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

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

IPC分类号： 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）。 通过将成本与每个瓦片相关联，并将每个路径或边缘与每个瓦片相关联来选择候选点的子集。 计算与在每个平铺内的位置放置缓冲区相关联的总成本。 然后选择最低成本图块作为缓冲区插入的候选位置。 然后重复该过程以获得在源和宿之间的不对称分布的候选缓冲区插入点集合。

公开(公告)号：US20070300193A1

公开(公告)日：2007-12-27

申请号：US11569546

申请日：2005-05-24

申请人： John Lillis ,  Milos Hrkic

发明人： John Lillis ,  Milos Hrkic

IPC分类号： G06F17/50

CPC分类号： G06F17/5072

摘要： A Computer-Aided Design (CAD) system operates according to a method (100) having the steps of placing (102) a plurality of cells of one or more circuits in a layout, generating (106) a plurality of fanin trees from the layout, applying (110) fanin tree embedding on the plurality of fanin trees, and generating (112) a new layout from the embedded fanin trees.

摘要翻译： 计算机辅助设计（CAD）系统根据方法（100）进行操作，该方法具有以下步骤：将一个或多个电路的多个单元放置在布局中，从布局生成（106）多个扇形树 ，在多个扇形树上应用（110）扇形树嵌入，并从嵌入的扇形树生成（112）新的布局。

公开(公告)号：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）。 通过将成本与每个瓦片相关联，并将每个路径或边缘与每个瓦片相关联来选择候选点的子集。 计算与在每个平铺内的位置放置缓冲区相关联的总成本。 然后选择最低成本图块作为缓冲区插入的候选位置。 然后重复该过程以获得在源和宿之间的不对称分布的候选缓冲区插入点集合。

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