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

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

公开(公告)号：US07096448B2

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

申请号：US10040915

申请日：2002-01-05

申请人： Steven Teig ,  Oscar Buset ,  Heng-Yi Chao

发明人： Steven Teig ,  Oscar Buset ,  Heng-Yi Chao

IPC分类号： G06F17/50

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

摘要： Some embodiments provide a method of routing nets within a region of an integrated-circuit (“IC”) layout. The method uses a first set of lines to partition the IC region into a plurality of sub-regions. In addition, the method uses a second set of lines to measure congestion of routes for the nets within the IC region. According to this method, at least some of the lines in the second set are different from the lines in the first set.

摘要翻译： 一些实施例提供了在集成电路（“IC”）布局的区域内布线网络的方法。 该方法使用第一组线将IC区域划分成多个子区域。 此外，该方法使用第二组线来测量IC区域内的网络的路由拥塞。 根据该方法，第二组中的至少一些线与第一组中的线不同。

公开(公告)号：US06745379B2

公开(公告)日：2004-06-01

申请号：US10047997

申请日：2002-01-13

申请人： Steven Teig ,  Oscar Buset

发明人： Steven Teig ,  Oscar Buset

IPC分类号： G06F1750

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

摘要： Some embodiments provide a hierarchical method of routing nets within a particular region of a circuit layout. Each net has a set of pins. The method initially partitions the particular region into a first set of sub-regions. For each net, the method identifies a first route that connects a group of first-set sub-regions containing the first net's pins; where some of the routes have at least one route-edge that is at least partially diagonal. The method then partitions the sub-regions into a second set of smaller sub-regions. For a first net, the method identifies a propagation of the first-net's first route into the second-set sub-regions based on congestion between the second-set sub-regions. It then adjusts the congestion between the second set sub-regions based on the identified propagation. For a second net, the method then identifies a propagation of the second-net's first route into the second-set sub-regions based on congestion between the second-set sub-regions.

摘要翻译： 一些实施例提供了在电路布局的特定区域内布线网络的分层方法。 每个网络都有一组引脚。 该方法最初将特定区域划分为第一组子区域。 对于每个网络，该方法识别连接包含第一网络引脚的一组第一组子区域的第一路由; 其中一些路线具有至少部分对角线的至少一个路线边缘。 该方法然后将子区域划分成第二组较小的子区域。 对于第一网络，该方法基于第二集合子区域之间的拥塞来识别第一网络的第一路由到第二集合子区域的传播。 然后，它基于所识别的传播来调整第二组子区域之间的拥塞。 对于第二网络，该方法然后基于第二集合子区域之间的拥塞来识别第二网络的第一路由到第二集合子区域的传播。

公开(公告)号：US07013450B2

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

申请号：US10047982

申请日：2002-01-14

申请人： Steven Teig ,  Oscar Buset

发明人： Steven Teig ,  Oscar Buset

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

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

摘要： Some embodiments of the invention provide a method of routing several nets in a region of a design layout. Each net includes a set of pins in the region. In some embodiments, the method partitions the region into several sub-regions that have a number of edges between them. The method (1) for each particular edge, identifies an edge-intersect cost based on a set of potential routes for the nets that intersect the particular edge, and (2) selects routes for the nets based on the computed edge-intersect costs. A potential route for a particular net traverses the set of sub-regions that contain the particular net's set of pins. Also, different embodiments identify different edge-intersect costs. For instance, the edge-intersect cost of a particular edge (1) can be the number of routes that intersect the particular edge, (2) can be a edge-intersect probability that equals the number of routes that intersect the particular edge divided by the total number of routes, or (3) can be a cost derived from the edge-intersect probability. Other embodiments might define other edge-intersect costs. In other embodiments, the method partitions the region into several sub-regions that have a number of paths between them. The method next (1) for each particular path, identifies a path-use cost based on a set of potential routes for the nets that use the particular path, and (2) selects a route for each net based on the computed path-use costs. Different embodiments identify different path-use costs. For instance, the path-use cost of a particular path (1) can be the number of routes that use the particular path, (2) can be a path-use probability that equals the number of routes that use the particular path divided by the total number of routes, or (3) can be a cost derived from the path-use probability. Other embodiments might define other path-use costs.

摘要翻译： 本发明的一些实施例提供了在设计布局的区域中路由多个网络的方法。 每个网络包括该区域中的一组引脚。 在一些实施例中，该方法将区域划分成在它们之间具有多个边缘的若干子区域。 每个特定边缘的方法（1）基于与特定边缘相交的网络的一组潜在路线识别边缘相交成本，以及（2）基于所计算的边缘相交成本来选择网络的路线。 特定网络的潜在路径遍历包含特定网络引脚集合的子区域集合。 而且，不同的实施例识别不同的边缘相交成本。 例如，特定边缘（1）的边缘相交成本可以是与特定边缘相交的路由的数量，（2）可以是等于与特定边缘相交的路由的数量的边缘相交概率除以 路线总数，或（3）可以是从边缘相交概率导出的成本。 其他实施例可以定义其他边缘相交成本。 在其他实施例中，该方法将区域划分成在它们之间具有多个路径的若干子区域。 对于每个特定路径，接下来（1）的方法基于使用特定路径的网络的一组潜在路由来识别路径使用成本，以及（2）基于计算的路径使用为每个网络选择路由 费用 不同的实施例识别不同的路径使用成本。 例如，特定路径（1）的路径使用成本可以是使用特定路径的路由的数量，（2）可以是等于使用特定路径除以的路由的数量的路径使用概率 路线的总数，或（3）可以是从路径使用概率导出的成本。 其他实施例可以定义其他路径使用成本。

公开(公告)号：US07003754B2

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

申请号：US10013819

申请日：2001-12-07

申请人： Steven Teig ,  Oscar Buset ,  Etienne Jacques

发明人： Steven Teig ,  Oscar Buset ,  Etienne Jacques

IPC分类号： G06F17/50

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

摘要： The invention is directed towards routing method and apparatus. Some embodiments provide a routing method that uses diagonal routes. This method routes several nets within a region of a circuit layout. Each net includes a set of pins in the region. The method initially partitions the region into several sub-regions. For each particular net in the region, the method then identifies a route that connects the sub-regions that contains a pin from the set of pins of the particular net. Some of the identified routes have edges that are at least partially diagonal.

摘要翻译： 本发明涉及路由方法和装置。 一些实施例提供了使用对角线路由的路由方法。 该方法在电路布局区域内路由几个网络。 每个网络包括该区域中的一组引脚。 该方法最初将区域划分为几个子区域。 对于该区域中的每个特定网络，该方法然后识别连接包含特定网络的引脚组的引脚的子区域的路由。 一些所识别的路线具有至少部分对角线的边缘。

公开(公告)号：US06952815B2

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

申请号：US10047978

申请日：2002-01-13

申请人： Steven Teig ,  Oscar Buset

发明人： Steven Teig ,  Oscar Buset

IPC分类号： G06F17/50 ,  G11B7/085

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

摘要： Some embodiments of the invention provide a method of routing several nets in a region of a design layout. Each net includes a set of pins in the region. In some embodiments, the method partitions the region into several sub-regions that have a number of edges between them. The method (1) for each particular net and each particular edge, identifies an edge-intersect probability that specifies the probability that a set of potential routes for the particular net will intersect the particular edge, and (2) uses the identified edge-intersect probabilities to identify routes for the nets. A potential route for a particular net traverses the set of sub-regions that contain the particular net's set of pins.In other embodiments, the method partitions the region into several sub-regions that have a number of paths between them. The method (1) for each particular net and each particular path, identifies a path-use probability that specifies the probability that a set of potential routes for the particular net will use the particular path, and (2) uses the identified path-use probabilities to identify routes for the nets.

摘要翻译： 本发明的一些实施例提供了在设计布局的区域中路由多个网络的方法。 每个网络包括该区域中的一组引脚。 在一些实施例中，该方法将区域划分成在它们之间具有多个边缘的若干子区域。 每个特定网络和每个特定边缘的方法（1）识别边缘相交概率，其指定特定网络的一组潜在路由将与特定边缘相交的概率，以及（2）使用所识别的边缘相交 识别网络路由的概率。 特定网络的潜在路径遍历包含特定网络引脚集合的子区域集合。 在其他实施例中，该方法将区域划分成在它们之间具有多个路径的若干子区域。 每个特定网络和每个特定路径的方法（1）识别指定特定网络的一组潜在路由将使用特定路径的概率的路径使用概率，以及（2）使用所识别的路径使用 识别网络路由的概率。

公开(公告)号：US07073150B2

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

申请号：US10013813

申请日：2001-12-07

申请人： Steven Teig ,  Oscar Buset

发明人： Steven Teig ,  Oscar Buset

IPC分类号： G06F17/50

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

摘要： Some embodiments provide a hierarchical routing method that uses diagonal routes. This method routes a net within a particular region of an integrated circuit (“IC”) layout. This net includes several pins in the region. The method initially partitions the particular IC region into a first set of sub-regions. It then identifies a first route that connects a group of first-set sub-regions that contain the net's pins. The identified first route has an edge that is at least partially diagonal. The method next partitions the first-set sub-regions into a second set of smaller sub-regions. It then propagates the first route into the second-set sub-regions.

公开(公告)号：US06957410B2

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

申请号：US10013816

申请日：2001-10-19

申请人： Steven Teig ,  Oscar Buset

发明人： Steven Teig ,  Oscar Buset

IPC分类号： G06F17/50 ,  G11B7/085 ,  H01L21/82

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

摘要： Some embodiments provide a method of routing nets in a region of an integrated-circuit layout. This method initially identifies a characteristic of the region, and then selects a wiring model from a set of wiring models, based on the identified characteristic. Each wiring models specifies a set of routing directions. The method then routes the nets based on the selected wiring model.

摘要翻译： 一些实施例提供了在集成电路布局的区域中布线网络的方法。 该方法首先识别该区域的特征，然后基于所识别的特性从一组布线模型中选择布线模型。 每个接线模型指定一组路由方向。 然后，该方法将基于所选接线模型对网络进行路由。

公开(公告)号：US06931616B2

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

申请号：US10040963

申请日：2002-01-05

申请人： Steven Teig ,  Oscar Buset ,  Etienne Jacques

发明人： Steven Teig ,  Oscar Buset ,  Etienne Jacques

IPC分类号： G06F17/50 ,  G11B7/085

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

摘要： A routing method that uses diagonal routes. This method routes several nets within a region of a circuit layout. Each net includes a set of pins in the region. The method initially partitions the region into several sub-regions. For each particular net in the region, the method then identifies a route that connects the sub-regions that contains a pin from the set of pins of the particular net. Some of the identified routes have edges that are at least partially diagonal.

摘要翻译： 使用对角线路由的路由方法。 该方法在电路布局区域内路由几个网络。 每个网络包括该区域中的一组引脚。 该方法最初将区域划分为几个子区域。 对于该区域中的每个特定网络，该方法然后识别连接包含特定网络的引脚组的引脚的子区域的路由。 一些所识别的路线具有至少部分对角线的边缘。

公开(公告)号：US06915501B2

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

申请号：US10040948

申请日：2002-01-05

申请人： Steven Teig ,  Oscar Buset

发明人： Steven Teig ,  Oscar Buset

IPC分类号： G06F17/50 ,  G11B7/085

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

摘要： Some embodiments provide an LP method that identities routes. In some embodiments, this method is used by a router that defines routes for nets within a region of a design layout. Each net has a set of pins in the region. The method partitions the region into a set or sub-regions. For each particular net, the method identifies a set or route. Each route for a net traverses the sub-regions that contain the net's pins. Each route includes a set of route edge, and each route edge connects two sub-regions. Also, some of the identified routes have route edges that are at least partially diagonal. The method formulates a linear-programming (“LP”) problem based on the identified sets of routes for the nets. The method then solves the LP problem to identify one route for each net. In some embodiments, the formulated LP problem is an integer-linear-programming (“ILP”) problem, and solving the ILP problem returns integer solutions that specify one route for each net. In other embodiments, solving the LP problem returns real-numbered solutions. In some of these embodiments, the method converts the real-number solutions into integer solutions that specify one route for each net.

摘要翻译： 一些实施例提供了标识路由的LP方法。 在一些实施例中，该方法由定义设计布局区域内的网络路由的路由器使用。 每个网络在该地区有一组引脚。 该方法将该区域划分为一个集合或子区域。 对于每个特定的网络，该方法识别集合或路由。 网络的每个路由遍历包含网络引脚的子区域。 每个路由包括一组路由边缘，每个路由边缘连接两个子区域。 此外，一些所识别的路线具有至少部分对角线的路线边缘。 该方法基于所确定的网络路由组合线性规划（“LP”）问题。 然后，该方法解决了LP问题，以识别每个网络的一个路由。 在一些实施例中，配制的LP问题是整数线性规划（“ILP”）问题，并且解决ILP问题返回指定每个网络的一个路由的整数解。 在其他实施例中，解决LP问题返回实数解决方案。 在这些实施例中的一些实施例中，该方法将实数解转换成为每个网络指定一个路由的整数解。