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

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

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

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

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

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

公开(公告)号：US06996789B2

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

申请号：US10335077

申请日：2002-12-31

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

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

IPC分类号： G06F17/50

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

摘要： Some embodiments of the invention provide a method of searching for a path. The method identifies a set of source and target elements. It then performs a path search that iteratively identifying path expansions in order to identify a set of associated path expansions that connect the source and target elements. The method costs at least one expansion based on an exponential equation that has an exponent that includes a cost associated with the expansion.

摘要翻译： 本发明的一些实施例提供了一种搜索路径的方法。 该方法标识一组源元素和目标元素。 然后，它执行迭代地识别路径扩展的路径搜索，以便识别连接源和目标元素的一组相关联的路径扩展。 该方法基于具有包括与扩展相关联的成本的指数的指数方程来花费至少一个扩展。

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

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

公开(公告)号：US20050273747A1

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

申请号：US11005169

申请日：2004-12-06

申请人： Anish Malhotra ,  Jonathan Frankle ,  Asmus Hetzel ,  Etienne Jacques

发明人： Anish Malhotra ,  Jonathan Frankle ,  Asmus Hetzel ,  Etienne Jacques

IPC分类号： G06F17/50

CPC分类号： G06F17/5077

摘要： Some embodiments of the invention provide a method for routing. The method defines at least one wiring layer that has at least two regions with different local preferred wiring directions. The method then uses the differing local preferred wiring directions to define a global route on the wiring layer. The two regions are a first region with a first local preferred wiring direction, and a second region with a second local preferred wiring direction. The global route traverses the first region along the first local preferred wiring direction and traverses the second region along the second local preferred wiring direction.

摘要翻译： 本发明的一些实施例提供了一种用于路由的方法。 该方法限定至少一个具有不同局部优选布线方向的至少两个区域的布线层。 然后，该方法使用不同的局部优选布线方向来定义布线层上的全局路线。 两个区域是具有第一局部优选布线方向的第一区域和具有第二局部优选布线方向的第二区域。 全局路线沿着第一本地优选布线方向穿过第一区域，并沿着第二局部优选布线方向穿过第二区域。

公开(公告)号：US07412682B2

公开(公告)日：2008-08-12

申请号：US11005169

申请日：2004-12-06

申请人： Anish Malhotra ,  Jonathan Frankle ,  Asmus Hetzel ,  Etienne Jacques

发明人： Anish Malhotra ,  Jonathan Frankle ,  Asmus Hetzel ,  Etienne Jacques

IPC分类号： G06F17/50

CPC分类号： G06F17/5077

摘要： Some embodiments of the invention provide a method for routing. The method defines at least one wiring layer that has at least two regions with different local preferred wiring directions. The method then uses the differing local preferred wiring directions to define a global route on the wiring layer. The two regions are a first region with a first local preferred wiring direction, and a second region with a second local preferred wiring direction. The global route traverses the first region along the first local preferred wiring direction and traverses the second region along the second local preferred wiring direction.

摘要翻译： 本发明的一些实施例提供了一种用于路由的方法。 该方法限定至少一个具有不同局部优选布线方向的至少两个区域的布线层。 然后，该方法使用不同的局部优选布线方向来定义布线层上的全局路线。 两个区域是具有第一局部优选布线方向的第一区域和具有第二局部优选布线方向的第二区域。 全局路线沿着第一本地优选布线方向穿过第一区域，并沿着第二局部优选布线方向穿过第二区域。

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

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