Given an instance of channel routing problem (CRP) in VLSI design, the number of tracks used in a solution for the instance is called the channel height of the solution. The objective of CRP is to minimize the channel heights, that is, to find a solution with minimum channel height. In an instance of CRP, HCG and VCG denote the horizontal and vertical constraint graphs, respectively. Let GM be the graph obtained from HCG by adding edges whose ends are connected by a directed path in VCG. Pal et al. first gave lower bounds on the channel heights in terms of the clique number of GM, and presented algorithms to find such lower bounds. In this paper, we find some interesting theoretic properties, about the structure of the cliques in GM, which can be used to improve Pal’s algorithms. So far, little is known about upper bounds on the channel heights. We find that CRP can be translated into an orientation problem on HCG with arcs in VCG oriented and keeping directed acyclic, and it is also proved that the channel height is determined by the longest directed path in the orientation. Moreover,we show that a lemma on the lower bound in  is incorrect and thus another lemma is given to modify it.
Weitere Kapitel dieses Buchs durch Wischen aufrufen
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
- Channel Height Estimation for VLSI Design
- Springer Berlin Heidelberg
ec4u, Neuer Inhalt/© ITandMEDIA