Title :
Area(number)-balanced hierarchy of staircase channels with minimum crossing nets
Author :
Majumder, Subhashis ; Sur-Kolay, Susmita ; Bhattacharya, Bhargab B. ; Nandy, Subhas C.
Author_Institution :
Astralsys Software (India) Pvt Ltd., Calcutta, India
Abstract :
We address the problem of hierarchically partitioning a VLSI floorplan F using monotone staircase channels to aid global routing. Our problem is to identify a monotone staircase channel (ms-cut) from one corner of F to its opposite corner, such that (i) the number of nets crossing the ms-cut is minimized, and (ii) the area (or the number of the blocks) of both the partitions are nearly equal. The problem is shown to be NP-hard, and a maxflow-based heuristic is proposed
Keywords :
VLSI; circuit layout CAD; circuit optimisation; computational complexity; integrated circuit layout; network routing; network topology; NP-hard; VLSI floorplan; blocks; global routing; hierarchically partitioning; maxflow-based heuristic; minimum crossing nets; monotone staircase channels; ms-cut; Binary trees; Geometry; Optimization methods; Partitioning algorithms; Routing; Shape; Very large scale integration; Wire;
Conference_Titel :
Circuits and Systems, 2001. ISCAS 2001. The 2001 IEEE International Symposium on
Conference_Location :
Sydney, NSW
Print_ISBN :
0-7803-6685-9
DOI :
10.1109/ISCAS.2001.922068
