公开(公告)号：US07155697B2

公开(公告)日：2006-12-26

申请号：US10046926

申请日：2002-01-13

申请人： Steven Teig ,  Oscar Buset ,  Etienne Jacques ,  Andrew Caldwell ,  Jonathan Frankle

发明人： Steven Teig ,  Oscar Buset ,  Etienne Jacques ,  Andrew Caldwell ,  Jonathan Frankle

IPC分类号： G06F17/50

CPC分类号： G06F17/5077 ,  G11B7/08582

摘要： A method for routing of some embodiments defines global routes for nets in an arbitrary region of a circuit layout in which each net has a set of pins. The method uses a first set of lines of measure the length of the global routes, a second set of lines to measure congestion of the global routes, and a third set of lines to partition the arbitrary region into a first set of sub-regions. For each net, the method identifies a global route that connects a group of first-set sub-regions that contain the net's set of pins.

摘要翻译： 一些实施例的路由的方法定义了在每个网络具有一组引脚的电路布局的任意区域中的网络的全局路由。 该方法使用第一组测量线，全局路由的长度，用于测量全局路由的拥塞的第二组线路，以及将该任意区域划分为第一组子区域的第三组线路。 对于每个网络，该方法标识连接一组包含网络引脚组的第一组子区域的全局路由。

公开(公告)号：US07143383B1

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

申请号：US10335054

申请日：2002-12-31

申请人： Steven Teig ,  Andrew Caldwell

发明人： Steven Teig ,  Andrew Caldwell

IPC分类号： G06F17/50

CPC分类号： G06F17/5081

摘要： The present invention introduces a method for implementing a gridless non Manhattan router by modifying an existing gridless Manhattan router. In the method of the present invention, a tile based router that uses tiles to represent circuit geometry or free space between circuit geometry is first selected. Next, at least one tile routing layer of the tile based router is rotated to implement a diagonal wiring layer. The code of the router is then adjusted to ensure that a via that will connect a Manhattan layer to a non Manhattan layer (a diagonal layer) will fit within a tile on both layers.

摘要翻译： 本发明通过修改现有的无格子曼哈顿路由器来介绍一种用于实现无网格非曼哈顿路由器的方法。 在本发明的方法中，首先选择使用瓦片来表示电路几何形状或电路几何形状之间的自由空间的基于瓦片的路由器。 接下来，基于瓦片的路由器的至少一个瓦片路由层被旋转以实现对角线布线层。 然后调整路由器的代码，以确保将曼哈顿层连接到非曼哈顿层（对角层）的通孔将适合两层的瓦片。

公开(公告)号：US07114141B1

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

申请号：US10222088

申请日：2002-08-14

申请人： Steven Teig ,  Andrew Caldwell

发明人： Steven Teig ,  Andrew Caldwell

IPC分类号： G06F17/50

CPC分类号： G06F17/5077

摘要： Some embodiments of the invention provide a method of decomposing a design layout. The method decomposes the layout into a tessellated graph with several edges. It then computes the capacity of the edges based on a interconnect line model that is used to connect elements in the design layout. The layout has two orthogonal coordinate axes. At least one interconnect line specified by the model is neither parallel nor perpendicular to the coordinate axes. Also, in some embodiments, some of the edges are neither parallel nor perpendicular to the coordinate axes.

摘要翻译： 本发明的一些实施例提供了一种分解设计布局的方法。 该方法将布局分解成具有多个边的细分图。 然后，它基于用于连接设计布局中的元素的互连线模型来计算边缘的容量。 布局有两个正交的坐标轴。 由模型指定的至少一条互连线既不平行也不垂直于坐标轴。 而且，在一些实施例中，一些边缘既不平行也不垂直于坐标轴。

公开(公告)号：US07107564B1

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

申请号：US10066060

申请日：2002-01-31

申请人： Steven Teig ,  Andrew Caldwell

发明人： Steven Teig ,  Andrew Caldwell

IPC分类号： G06F17/50

CPC分类号： G06F17/5077

摘要： One embodiment of the invention is a method of specifying routes for a group of nets. The method identifies different routing solutions for the group of nets. It then selects the best routing solution.

摘要翻译： 本发明的一个实施例是一种用于指定一组网络的路由的方法。 该方法识别网络组的不同路由解决方案。 然后选择最佳路由解决方案。

公开(公告)号：US07047512B1

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

申请号：US10227016

申请日：2002-08-23

申请人： Steven Teig ,  Andrew Caldwell

发明人： Steven Teig ,  Andrew Caldwell

IPC分类号： G06F17/50

CPC分类号： G06F17/5077

摘要： Some embodiments of the invention provide a method of specifying a cost function that represents the estimated distance between an external state and a set of states in a multi-state space that represents a region of a design layout. The method identifies a polygon that encloses the set of states. It then identifies vectors to project from the vertices of the polygon. Based on the projected vectors, the method identifies a set of distances that includes the distance between the polygon and each point in a set of points in the external state. The method then uses the identified set of distance to specify the cost function.

摘要翻译： 本发明的一些实施例提供了一种指定成本函数的方法，所述成本函数表示在表示设计布局的区域的多状态空间中的外部状态与一组状态之间的估计距离。 该方法标识包围状态集的多边形。 然后识别从多边形的顶点投影的向量。 基于投影向量，该方法识别一组距离，其包括多边形与外部状态的一组点中的每个点之间的距离。 然后，该方法使用所识别的一组距离来指定成本函数。

公开(公告)号：US07000209B1

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

申请号：US10233312

申请日：2002-08-28

申请人： Steven Teig ,  Andrew Caldwell

发明人： Steven Teig ,  Andrew Caldwell

IPC分类号： G06F17/50

CPC分类号： G06F17/5077

摘要： Some embodiments of the invention provide a method for propagating a first piecewise linear function (PLF), which is defined over a first state, to a second state, which is a surface. In some embodiments, the space includes a set of states and a transition map that specifies a set of states that can be reached from each particular state. For instance, in some embodiments, the space is a graph that includes points, lines, and surfaces. The method projects vectors from points on the first state that are locations of inflection points in the first PLF. At each intersection of the boundary of the surface and one of the vectors, the method computes a cost. Based on the computed costs, the method specifying a second PLF that is defined over the second state.

摘要翻译： 本发明的一些实施例提供一种用于将第一分段线性函数（PLF）在第一状态下定义为将表面传播到第二状态的方法。 在一些实施例中，空间包括一组状态和指定可以从每个特定状态到达的一组状态的转换图。 例如，在一些实施例中，空间是包括点，线和表面的图形。 该方法从第一状态的点投影向量，它们是第一个PLF中拐点的位置。 在表面边界和向量之一的每个交点处，该方法计算成本。 基于计算出的成本，该方法指定在第二状态下定义的第二PLF。

公开(公告)号：US06957408B1

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

申请号：US10215563

申请日：2002-08-09

申请人： Steven Teig ,  Andrew Caldwell ,  Etienne Jacques

发明人： Steven Teig ,  Andrew Caldwell ,  Etienne Jacques

IPC分类号： G06F17/50

CPC分类号： G06F17/5077

摘要： Some embodiments of the invention provide a method of for routing nets within a region of an integrated circuit (“IC”) layout. The method selects a net in the IC layout region. It then identifies a topological route for the selected net. From the selected net's topological route, this method then generates a geometric route for the selected net.

摘要翻译： 本发明的一些实施例提供了一种用于在集成电路（“IC”）布局的区域内布线网络的方法。 该方法选择IC布局区域中的网络。 然后识别所选网络的拓扑路由。 从所选网络的拓扑路线中，该方法然后生成所选网络的几何路线。

公开(公告)号：US06948144B1

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

申请号：US10286253

申请日：2002-10-31

申请人： Steven Teig ,  Andrew Caldwell

发明人： Steven Teig ,  Andrew Caldwell

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

CPC分类号： G06F17/5077

摘要： Some embodiments of the invention provide a method of propagating a first cost function that is defined over a first state to a second slate in a space representing a design-layout region. In some embodiments, the space includes a set of states and a transition map that specifies a set of states that can be reached from each particular state. The space has several dimensional states. The method identifies several pairs of wedge vectors. Each vector has a tail, and each wedge-vector pair includes two vectors that are connected at their tails. The method assigns locations in the first state for the tails of at least some of the identified wedge-vector pairs. The method then uses the wedge-vector pairs that have assigned tail locations to propagate the first cost function.

摘要翻译： 本发明的一些实施例提供了一种将在第一状态下定义的第一成本函数传播到表示设计布局区域的空间中的第二平板的方法。 在一些实施例中，空间包括一组状态和指定可以从每个特定状态到达的一组状态的转换图。 空间有几个维度状态。 该方法识别几对楔形矢量。 每个向量具有尾部，并且每个楔形矢量对包括在它们的尾部连接的两个向量。 该方法为至少一些所识别的楔形矢量对的尾部分配处于第一状态的位置。 该方法然后使用已经分配尾部位置来传播第一个成本函数的楔形矢量对。

公开(公告)号：US06938234B1

公开(公告)日：2005-08-30

申请号：US10229196

申请日：2002-08-26

申请人： Steven Teig ,  Andrew Caldwell ,  Etienne Jacques

发明人： Steven Teig ,  Andrew Caldwell ,  Etienne Jacques

IPC分类号： G06F17/50

CPC分类号： G06F17/5077

摘要： Some embodiments of the invention provide a method of routing nets in a region of a design layout. The region contains a plurality of nets and has multiple interconnect layers. The method identifies routes for a set of nets in the region, where some of the routes utilize vias to traverse multiple interconnect layers. The method then moves at least one via to improve the routing.

摘要翻译： 本发明的一些实施例提供了一种在设计布局的区域中布线网络的方法。 该区域包含多个网络并且具有多个互连层。 该方法识别区域中的一组网络的路由，其中​​一些路由利用过孔来遍历多个互连层。 该方法然后移动至少一个通道以改善路由。

公开(公告)号：US06931615B1

公开(公告)日：2005-08-16

申请号：US10335074

申请日：2002-12-31

申请人： Steven Teig ,  Andrew Caldwell

发明人： Steven Teig ,  Andrew Caldwell

IPC分类号： G06F17/50

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

摘要： Some embodiments of the invention provide a path-searching method. This method identifies two sets of states in a multi-state space, where at least some of the states have at least one dimension. It then performs an epsilon-optimal path search to identify an epsilon-optimal path between the two set of states. The epsilon-optimal path is a path that is within an epsilon of the optimal path between the two sets of states. During the espsilon optimal search, the method propagates a cost function that is defined over one state to another state.

摘要翻译： 本发明的一些实施例提供一种路径搜索方法。 该方法识别多状态空间中的两组状态，其中至少一些状态具有至少一个维度。 然后，它执行ε-最优路径搜索以识别两组状态之间的ε-最优路径。 ε最优路径是在两组状态之间的最优路径的ε内的路径。 在espsilon最优搜索期间，该方法将在一个状态定义的成本函数传播到另一个状态。