Switchbox routing by stepwise reshaping

Sabih H. Gerez, O.E. Herrmann

Research output: Contribution to journalArticleAcademic

13 Citations (Scopus)
55 Downloads (Pure)

Abstract

An algorithm for switchbox routing called PACKER is presented. In an initial phase, the connectivity of each net is established in a fast way without taking the other nets into account. In general, this gives rise to conflicts (short circuits). In the second stage the conflicts are removed iteratively using connectivity-preserving local transformations. They reshape a net by displacing one of its segments without disconnecting it from the net. The transformations are applied in a systematic way using a scan-line technique. During this process, a subset of the segments at the position of the scan line is densely packed in the (two) layers available for routing. The remaining segments are pushed to the next scan-line position. Scanning in the four available directions (left to right, right to left, top to bottom, and bottom to top) is performed until all conflicts have disappeared or no solution is found within a maximum number of iterations. It turns out that the new approach to routing, as implemented in PACKER, also has practical merits: most of the well-known benchmark examples are solved
Original languageUndefined
Pages (from-to)1350-1361
JournalIEEE transactions on computer-aided design of integrated circuits and systems
Volume8
Issue number12
DOIs
Publication statusPublished - 1989

Keywords

  • IR-55751

Cite this

@article{55e7dabbfa184c26b1e6e1c2d5357a4d,
title = "Switchbox routing by stepwise reshaping",
abstract = "An algorithm for switchbox routing called PACKER is presented. In an initial phase, the connectivity of each net is established in a fast way without taking the other nets into account. In general, this gives rise to conflicts (short circuits). In the second stage the conflicts are removed iteratively using connectivity-preserving local transformations. They reshape a net by displacing one of its segments without disconnecting it from the net. The transformations are applied in a systematic way using a scan-line technique. During this process, a subset of the segments at the position of the scan line is densely packed in the (two) layers available for routing. The remaining segments are pushed to the next scan-line position. Scanning in the four available directions (left to right, right to left, top to bottom, and bottom to top) is performed until all conflicts have disappeared or no solution is found within a maximum number of iterations. It turns out that the new approach to routing, as implemented in PACKER, also has practical merits: most of the well-known benchmark examples are solved",
keywords = "IR-55751",
author = "Gerez, {Sabih H.} and O.E. Herrmann",
year = "1989",
doi = "10.1109/43.44515",
language = "Undefined",
volume = "8",
pages = "1350--1361",
journal = "IEEE transactions on computer-aided design of integrated circuits and systems",
issn = "0278-0070",
publisher = "IEEE",
number = "12",

}

Switchbox routing by stepwise reshaping. / Gerez, Sabih H.; Herrmann, O.E.

In: IEEE transactions on computer-aided design of integrated circuits and systems, Vol. 8, No. 12, 1989, p. 1350-1361.

Research output: Contribution to journalArticleAcademic

TY - JOUR

T1 - Switchbox routing by stepwise reshaping

AU - Gerez, Sabih H.

AU - Herrmann, O.E.

PY - 1989

Y1 - 1989

N2 - An algorithm for switchbox routing called PACKER is presented. In an initial phase, the connectivity of each net is established in a fast way without taking the other nets into account. In general, this gives rise to conflicts (short circuits). In the second stage the conflicts are removed iteratively using connectivity-preserving local transformations. They reshape a net by displacing one of its segments without disconnecting it from the net. The transformations are applied in a systematic way using a scan-line technique. During this process, a subset of the segments at the position of the scan line is densely packed in the (two) layers available for routing. The remaining segments are pushed to the next scan-line position. Scanning in the four available directions (left to right, right to left, top to bottom, and bottom to top) is performed until all conflicts have disappeared or no solution is found within a maximum number of iterations. It turns out that the new approach to routing, as implemented in PACKER, also has practical merits: most of the well-known benchmark examples are solved

AB - An algorithm for switchbox routing called PACKER is presented. In an initial phase, the connectivity of each net is established in a fast way without taking the other nets into account. In general, this gives rise to conflicts (short circuits). In the second stage the conflicts are removed iteratively using connectivity-preserving local transformations. They reshape a net by displacing one of its segments without disconnecting it from the net. The transformations are applied in a systematic way using a scan-line technique. During this process, a subset of the segments at the position of the scan line is densely packed in the (two) layers available for routing. The remaining segments are pushed to the next scan-line position. Scanning in the four available directions (left to right, right to left, top to bottom, and bottom to top) is performed until all conflicts have disappeared or no solution is found within a maximum number of iterations. It turns out that the new approach to routing, as implemented in PACKER, also has practical merits: most of the well-known benchmark examples are solved

KW - IR-55751

U2 - 10.1109/43.44515

DO - 10.1109/43.44515

M3 - Article

VL - 8

SP - 1350

EP - 1361

JO - IEEE transactions on computer-aided design of integrated circuits and systems

JF - IEEE transactions on computer-aided design of integrated circuits and systems

SN - 0278-0070

IS - 12

ER -