ECO algorithms for removing overlaps between power rails and signal wires

Hua Xiang; Kai Yuan Chao; D. F. Wong

doi:10.1145/774572.774582

ECO algorithms for removing overlaps between power rails and signal wires

Hua Xiang, Kai Yuan Chao, D. F. Wong

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

4 Citations (Scopus)

Abstract

Design ECO commonly happens in industry due to constraints or target changes from manufacturing, marketing, reliability, or performance. At each step, designers usually want to modify the existing solution incrementally and keep the design as close as possible to the existing one. In this paper, we address the PSO (Power rail - Signal wire Overlap) problem which solves overlaps between power rails and signal wires due to the changes in power rail design on the top layer of a multiple layer routing region. PSO problems are frequently caused by changes from power delivery system or package design. The new routing solution satisfies the following constraints: 1) Keep the routing of power rails in the new design unchanged. 2) Only the routing of the top two layers is changed. 3) Horizontal (vertical) signal wire segments on the top layer can only move up/down (left/right). At the same time, the new routing solution keeps the routing pattern unchanged. This requires: a) If one end point of a horizontal (vertical) wire segment on the top layer is a fixed pin, this segment can not move. b) if vertical (horizontal) projections of two horizontal (vertical) signal wire segments have overlaps, then the up/down (left/right) relationship should not be changed. c) If two horizontal (vertical) segments belonging to different nets are on the same track, their left/right (up/down) relationship should not be changed as long as the two segments still exist in the new solution. 4) For each signal wire segment, the deviation (i.e., the difference between its new position and the old one) should not exceed the user-defined allowable deviation bound. Different bounds can be set on different segments. We propose two algorithms to solve the PSO problem. Both algorithms guarantee to find a feasible solution as long as one exists. One is faster, while the other makes effort to minimize the total deviation as well as the max deviation. According to time and quality requirements, users can choose an appropriate algorithm to solve the problem. For a set of industrial test circuits, we were able to remove all overlaps between power rails and signal wires with minimal wire deviation.

Original language	English
Title of host publication	Proceedings of The IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2002
Place of Publication	United States
Publisher	Association for Computing Machinery (ACM)
Pages	67-74
Number of pages	8
ISBN (Print)	9780780376076
DOIs	https://doi.org/10.1145/774572.774582
Publication status	Published - Nov 2002
Event	2002 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2002 - San Jose, United States Duration: 10 Nov 2002 → 14 Nov 2002 https://dl.acm.org/doi/proceedings/10.1145/774572 (Conference proceedings)

Publication series

Name	Proceedings of the IEEE/ACM international conference on Computer-aided design, ICCAD
ISSN (Print)	1092-3152

Conference

Conference	2002 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2002
Country/Territory	United States
City	San Jose
Period	10/11/02 → 14/11/02
Internet address	https://dl.acm.org/doi/proceedings/10.1145/774572 (Conference proceedings)

Scopus Subject Areas

Software
Computer Science Applications
Computer Graphics and Computer-Aided Design

Access to Document

10.1145/774572.774582

Cite this

Xiang, H., Chao, K. Y., & Wong, D. F. (2002). ECO algorithms for removing overlaps between power rails and signal wires. In Proceedings of The IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2002 (pp. 67-74). (Proceedings of the IEEE/ACM international conference on Computer-aided design, ICCAD). Association for Computing Machinery (ACM). https://doi.org/10.1145/774572.774582

Xiang, Hua ; Chao, Kai Yuan ; Wong, D. F. / ECO algorithms for removing overlaps between power rails and signal wires. Proceedings of The IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2002. United States : Association for Computing Machinery (ACM), 2002. pp. 67-74 (Proceedings of the IEEE/ACM international conference on Computer-aided design, ICCAD).

@inproceedings{350678ac55ef4ac28e7d3f5e800b31a8,

title = "ECO algorithms for removing overlaps between power rails and signal wires",

abstract = "Design ECO commonly happens in industry due to constraints or target changes from manufacturing, marketing, reliability, or performance. At each step, designers usually want to modify the existing solution incrementally and keep the design as close as possible to the existing one. In this paper, we address the PSO (Power rail - Signal wire Overlap) problem which solves overlaps between power rails and signal wires due to the changes in power rail design on the top layer of a multiple layer routing region. PSO problems are frequently caused by changes from power delivery system or package design. The new routing solution satisfies the following constraints: 1) Keep the routing of power rails in the new design unchanged. 2) Only the routing of the top two layers is changed. 3) Horizontal (vertical) signal wire segments on the top layer can only move up/down (left/right). At the same time, the new routing solution keeps the routing pattern unchanged. This requires: a) If one end point of a horizontal (vertical) wire segment on the top layer is a fixed pin, this segment can not move. b) if vertical (horizontal) projections of two horizontal (vertical) signal wire segments have overlaps, then the up/down (left/right) relationship should not be changed. c) If two horizontal (vertical) segments belonging to different nets are on the same track, their left/right (up/down) relationship should not be changed as long as the two segments still exist in the new solution. 4) For each signal wire segment, the deviation (i.e., the difference between its new position and the old one) should not exceed the user-defined allowable deviation bound. Different bounds can be set on different segments. We propose two algorithms to solve the PSO problem. Both algorithms guarantee to find a feasible solution as long as one exists. One is faster, while the other makes effort to minimize the total deviation as well as the max deviation. According to time and quality requirements, users can choose an appropriate algorithm to solve the problem. For a set of industrial test circuits, we were able to remove all overlaps between power rails and signal wires with minimal wire deviation.",

author = "Hua Xiang and Chao, {Kai Yuan} and Wong, {D. F.}",

note = "Funding information: This work was partially supported by the National Science Foundation under grant CCR-9912390. Publisher copyright: {\textcopyright} 2002 ACM; 2002 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2002 ; Conference date: 10-11-2002 Through 14-11-2002",

year = "2002",

month = nov,

doi = "10.1145/774572.774582",

language = "English",

isbn = "9780780376076",

series = "Proceedings of the IEEE/ACM international conference on Computer-aided design, ICCAD",

publisher = "Association for Computing Machinery (ACM)",

pages = "67--74",

booktitle = "Proceedings of The IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2002",

address = "United States",

url = "https://dl.acm.org/doi/proceedings/10.1145/774572",

}

Xiang, H, Chao, KY & Wong, DF 2002, ECO algorithms for removing overlaps between power rails and signal wires. in Proceedings of The IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2002. Proceedings of the IEEE/ACM international conference on Computer-aided design, ICCAD, Association for Computing Machinery (ACM), United States, pp. 67-74, 2002 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2002, San Jose, California, United States, 10/11/02. https://doi.org/10.1145/774572.774582

ECO algorithms for removing overlaps between power rails and signal wires. / Xiang, Hua; Chao, Kai Yuan; Wong, D. F.
Proceedings of The IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2002. United States: Association for Computing Machinery (ACM), 2002. p. 67-74 (Proceedings of the IEEE/ACM international conference on Computer-aided design, ICCAD).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - ECO algorithms for removing overlaps between power rails and signal wires

AU - Xiang, Hua

AU - Chao, Kai Yuan

AU - Wong, D. F.

PY - 2002/11

Y1 - 2002/11

N2 - Design ECO commonly happens in industry due to constraints or target changes from manufacturing, marketing, reliability, or performance. At each step, designers usually want to modify the existing solution incrementally and keep the design as close as possible to the existing one. In this paper, we address the PSO (Power rail - Signal wire Overlap) problem which solves overlaps between power rails and signal wires due to the changes in power rail design on the top layer of a multiple layer routing region. PSO problems are frequently caused by changes from power delivery system or package design. The new routing solution satisfies the following constraints: 1) Keep the routing of power rails in the new design unchanged. 2) Only the routing of the top two layers is changed. 3) Horizontal (vertical) signal wire segments on the top layer can only move up/down (left/right). At the same time, the new routing solution keeps the routing pattern unchanged. This requires: a) If one end point of a horizontal (vertical) wire segment on the top layer is a fixed pin, this segment can not move. b) if vertical (horizontal) projections of two horizontal (vertical) signal wire segments have overlaps, then the up/down (left/right) relationship should not be changed. c) If two horizontal (vertical) segments belonging to different nets are on the same track, their left/right (up/down) relationship should not be changed as long as the two segments still exist in the new solution. 4) For each signal wire segment, the deviation (i.e., the difference between its new position and the old one) should not exceed the user-defined allowable deviation bound. Different bounds can be set on different segments. We propose two algorithms to solve the PSO problem. Both algorithms guarantee to find a feasible solution as long as one exists. One is faster, while the other makes effort to minimize the total deviation as well as the max deviation. According to time and quality requirements, users can choose an appropriate algorithm to solve the problem. For a set of industrial test circuits, we were able to remove all overlaps between power rails and signal wires with minimal wire deviation.

AB - Design ECO commonly happens in industry due to constraints or target changes from manufacturing, marketing, reliability, or performance. At each step, designers usually want to modify the existing solution incrementally and keep the design as close as possible to the existing one. In this paper, we address the PSO (Power rail - Signal wire Overlap) problem which solves overlaps between power rails and signal wires due to the changes in power rail design on the top layer of a multiple layer routing region. PSO problems are frequently caused by changes from power delivery system or package design. The new routing solution satisfies the following constraints: 1) Keep the routing of power rails in the new design unchanged. 2) Only the routing of the top two layers is changed. 3) Horizontal (vertical) signal wire segments on the top layer can only move up/down (left/right). At the same time, the new routing solution keeps the routing pattern unchanged. This requires: a) If one end point of a horizontal (vertical) wire segment on the top layer is a fixed pin, this segment can not move. b) if vertical (horizontal) projections of two horizontal (vertical) signal wire segments have overlaps, then the up/down (left/right) relationship should not be changed. c) If two horizontal (vertical) segments belonging to different nets are on the same track, their left/right (up/down) relationship should not be changed as long as the two segments still exist in the new solution. 4) For each signal wire segment, the deviation (i.e., the difference between its new position and the old one) should not exceed the user-defined allowable deviation bound. Different bounds can be set on different segments. We propose two algorithms to solve the PSO problem. Both algorithms guarantee to find a feasible solution as long as one exists. One is faster, while the other makes effort to minimize the total deviation as well as the max deviation. According to time and quality requirements, users can choose an appropriate algorithm to solve the problem. For a set of industrial test circuits, we were able to remove all overlaps between power rails and signal wires with minimal wire deviation.

UR - http://www.scopus.com/inward/record.url?scp=0036911942&partnerID=8YFLogxK

U2 - 10.1145/774572.774582

DO - 10.1145/774572.774582

M3 - Conference proceeding

AN - SCOPUS:0036911942

SN - 9780780376076

T3 - Proceedings of the IEEE/ACM international conference on Computer-aided design, ICCAD

SP - 67

EP - 74

BT - Proceedings of The IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2002

PB - Association for Computing Machinery (ACM)

CY - United States

T2 - 2002 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2002

Y2 - 10 November 2002 through 14 November 2002

ER -

Xiang H, Chao KY, Wong DF. ECO algorithms for removing overlaps between power rails and signal wires. In Proceedings of The IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2002. United States: Association for Computing Machinery (ACM). 2002. p. 67-74. (Proceedings of the IEEE/ACM international conference on Computer-aided design, ICCAD). doi: 10.1145/774572.774582

ECO algorithms for removing overlaps between power rails and signal wires

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this