公开(公告)号：US06988257B2

公开(公告)日：2006-01-17

申请号：US10334690

申请日：2002-12-31

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

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

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

CPC分类号： G06F17/5077

摘要： Some embodiments of the invention provide a method of defining a global route for a net in a region of a layout, where each net has a set of routable elements. The method partitions the region into several rectangular sub-regions. It then identifies a set of sub-regions that contain the routable elements of the net. Next, it defines a global route that connects the identified sub-regions, where the global route includes at least one non-Manhattan edge that crosses a boundary between two sub-regions at a non-vertex location.

摘要翻译： 本发明的一些实施例提供了一种在布局的区域中为网络定义全局路由的方法，其中每个网络具有一组可路由元件。 该方法将该区域划分为几个矩形子区域。 然后，它标识一组包含网络的可路由元素的子区域。 接下来，它定义了连接所识别的子区域的全局路由，其中​​全局路由包括穿过非顶点位置处的两个子区域之间的边界的至少一个非曼哈顿边缘。

公开(公告)号：US06892369B2

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

申请号：US10335086

申请日：2002-12-31

申请人： Steven Teig ,  Jonathan Frankle

发明人： Steven Teig ,  Jonathan Frankle

IPC分类号： G06F17/50

CPC分类号： G06F17/5077

摘要： Some embodiments of the invention provide a method of costing routes for a set of nets. The method identifies at least one route for each net, where each route has a particular length. It also identifies an estimated route length for each net. It then computes a cost that includes an exponential expression for each net. Each net's exponential expression includes a base and an exponent. The exponent of each net's exponential expression includes the length of the net's route divided by the estimated route length for the net.

摘要翻译： 本发明的一些实施例提供了一组网络的路由成本计算方法。 该方法识别每个网络的至少一个路由，其中​​每个路由具有特定的长度。 它还标识每个网络的估计路由长度。 然后计算一个包含每个网络的指数表达式的成本。 每个网络的指数表达式包括基数和指数。 每个网络的指数表达式的指数包括网络路由的长度除以网络的估计路由长度。

公开(公告)号：US07171635B2

公开(公告)日：2007-01-30

申请号：US10334689

申请日：2002-12-31

申请人： Steven Teig ,  Jonathan Frankle

发明人： Steven Teig ,  Jonathan Frankle

IPC分类号： G06F17/50

CPC分类号： G06F17/5077

摘要： Some embodiments of the invention provide a method of identifying global routes for nets in a region of a layout with multiple layers, where each net has a set of routable elements. The method partitions each layer of the region into several sub-regions. For each net, the method then identifies a route that connects the sub-regions that contain the net's set of routable elements. Some of the identified routes have at least one non-Manhattan edge and traverse sub-regions on multiple layers.

摘要翻译： 本发明的一些实施例提供了一种在具有多个层的布局的区域中识别网络的全局路由的方法，其中每个网络具有一组可路由元件。 该方法将该区域的每个层分成几个子区域。 对于每个网络，该方法然后识别连接包含网络的可路由元素集合的子区域的路由。 一些已识别的路由具有至少一个非曼哈顿边缘并遍历多个层上的子区域。

公开(公告)号：US07093221B2

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

申请号：US10335087

申请日：2002-12-31

申请人： Steven Teig ,  Jonathan Frankle

发明人： Steven Teig ,  Jonathan Frankle

IPC分类号： G06F17/50

CPC分类号： G06F17/5077

摘要： Some embodiments of the invention provide a method of identifying a group of routes for a set of nets. The group of routes includes one route for each net in the set of nets. The method identifies a set of routes for each net. It then iteratively selects one identified route for each net. During each iteration, the method selects the identified route that least increases a tracking cost that accounts for each of the previously selected routes.

摘要翻译： 本发明的一些实施例提供了一种识别一组网络的路由组的方法。 该组路由包括一组网络中的每个网络的一条路由。 该方法识别每个网络的一组路由。 然后它迭代地为每个网络选择一个确定的路由。 在每次迭代期间，该方法选择识别的路线，其最小地增加了占用每个先前选择的路线的跟踪成本。

公开(公告)号：US07010771B2

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

申请号：US10335251

申请日：2002-12-31

申请人： Steven Teig ,  Jonathan Frankle

发明人： Steven Teig ,  Jonathan Frankle

IPC分类号： G06F17/50

CPC分类号： G06F17/5077

摘要： Some embodiments of the invention provide a method of searching for a global path between first and second sets of routable elements in a region of a layout. The method partitions the region into several rectangular sub-regions. It then identifies a set of sub-regions that contain the two sets of elements. Next, it performs a path search to identify a set of path expansions between a sub-region that contains a first-set element and a sub-region that contains a second-set element. When the method performs the path search, it explores expansions along non-Manhattan directions between the sub-regions.

摘要翻译： 本发明的一些实施例提供了一种在布局的区域中搜索第一组和第二组可路由元件之间的全局路径的方法。 该方法将该区域划分为几个矩形子区域。 然后，它标识一组包含两组元素的子区域。 接下来，它执行路径搜索以识别包含第一集合元素的子区域和包含第二集合元素的子区域之间的路径扩展集合。 当该方法执行路径搜索时，它将探索在子区域之间沿非曼哈顿方向的扩展。

公开(公告)号：US07003752B2

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

申请号：US10335093

申请日：2002-12-31

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

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

IPC分类号： G06F17/50

CPC分类号： G06F17/5077

摘要： Some embodiments of the invention provide a method of routing nets in a region of a layout with multiple layers. The method defines a routing graph that has several of nodes on plurality of layers, where each node represents a sub-region on a layer. In the graph, there is a set of edges between the nodes on each layer. On one layer, there is at least one set of edges that are neither orthogonal nor parallel to a set of edges on another layer. The method uses this routing graph to identify routes.

摘要翻译： 本发明的一些实施例提供了在具有多个层的布局的区域中布线网络的方法。 该方法定义了在多个层上具有若干节点的路由图，其中每个节点表示层上的子区域。 在图中，每层上的节点之间有一组边。 在一层上，至少有一组边缘既不正交也不平行于另一层上的一组边缘。 该方法使用此路由图来标识路由。

公开(公告)号：US07002572B1

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

申请号：US10175390

申请日：2002-06-19

申请人： Steven Teig ,  Jonathan Frankle

发明人： Steven Teig ,  Jonathan Frankle

IPC分类号： G06T17/00

CPC分类号： G06T17/00 ,  G06T2210/12

摘要： Some embodiments of the invention provide a method for constructing a convex polygon that encloses a set of points in a region. This method identifies a first polygon that encloses the set of points. It then identifies a second polygon that encloses the set of points. The method then specifies the convex polygon as the intersection of the first and second polygons.

摘要翻译： 本发明的一些实施例提供一种用于构造包围区域中的一组点的凸多边形的方法。 该方法识别包围该组点的第一个多边形。 然后，它标识包围该组点的第二个多边形。 该方法然后将凸多边形指定为第一和第二多边形的交点。

公开(公告)号：US07216308B2

公开(公告)日：2007-05-08

申请号：US10335239

申请日：2002-12-31

申请人： Steven Teig ,  Jonathan Frankle

发明人： Steven Teig ,  Jonathan Frankle

IPC分类号： G06F17/50

CPC分类号： G06F17/5077

摘要： Some embodiments of the invention provide a method of solving an optimization problem. The problem includes a plurality of elements, and one or more solutions have been previously identified for each element. The method specifies a first solution set that has one identified solution for each element. In some embodiments, the method then iteratively examines all the elements of the problem. During the examination of each particular element, the method iteratively examines all the identified solutions for the particular element. During the examination of each particular solution, the method replaces the current solution for the particular element in the first solution set with a previously unexamined solution for the particular element if the replacement would improve the first set.

摘要翻译： 本发明的一些实施例提供了一种解决优化问题的方法。 该问题包括多个元件，并且先前已经为每个元件识别了一个或多个解决方案。 该方法指定了每个元素具有一个已识别解决方案的第一个解决方案集。 在一些实施例中，该方法然后迭代地检查问题的所有元素。 在检查每个特定元素期间，该方法迭代地检查特定元素的所有识别的解决方案。 在检查每个特定解决方案期间，如果替换将改善第一组，则该方法将替换第一解决方案集中的特定元素的当前解与先前未被特定元素的解决方案。

公开(公告)号：US07047513B2

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

申请号：US10334692

申请日：2002-12-31

申请人： Steven Teig ,  Jonathan Frankle

发明人： Steven Teig ,  Jonathan Frankle

IPC分类号： G06F17/50

CPC分类号： G06F17/5077

摘要： Some embodiments of the invention provide a method of searching for a three-dimensional global path between first and second sets of routable elements in a region of a layout that has multiple layers. The method partitions the region into several sub-regions. It then performs a path search to identify a path between a first set of sub-regions that contains the first-set elements and a second set of sub-regions that contain a second-set element. When the method performing the path search, it explores expansions along Manhattan and non-Manhattan routing directions between the sub-regions on a plurality of layers.

摘要翻译： 本发明的一些实施例提供了一种在具有多个层的布局的区域中搜索第一和第二组可路由元件之间的三维全局路径的方法。 该方法将该区域划分为几个子区域。 然后，它执行路径搜索以识别包含第一集合元素的第一组子区域和包含第二集合元素的第二组子区域之间的路径。 当执行路径搜索的方法时，它探索沿着曼哈顿的扩展和在多个层之间的子区域之间的非曼哈顿路由方向。

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

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