Search

Random via failure is a major concern for post-fabrication reliability and poor manufacturing yield. A demanding solution to this problem is redundant via insertion during post-routing optimization. It becomes very critical when a multi-layer routing solution already incurs a large number of vias. Very few global routers addressed unconstrained via minimization (UVM) problem, while using minimal pattern routing and layer assignment of nets. It also includes a recent floorplan based early global routability assessment tool STAIRoute \cite{karb2}. This work addresses an early version of unconstrained via minimization problem during early global routing by identifying a set of minimal bend routing regions in any floorplan, by a new recursive bipartitioning framework. These regions facilitate monotone pattern routing of a set of nets in the floorplan by STAIRoute. The area/number balanced floorplan bipartitionining is a multi-objective optimization problem and known to be NP-hard \cite{majum2}. No existing approaches considered bend minimization as an objective and some of them incurred higher runtime overhead. In this paper, we present a Greedy as well as randomized neighbor search based staircase wave-front propagation methods for obtaining optimal bipartitioning results for minimal bend routing through multiple routing layers, for a balanced trade-off between routability, wirelength and congestion. Experiments were conducted on MCNC/GSRC floorplanning benchmarks for studying the variation of early via count obtained by STAIRoute for different values of the trade-off parameters ($\gamma, \beta$) in this multi-objective optimization problem, using $8$ metal layers. We studied the impact of ($\gamma, \beta$) values on each of the objectives as well as their linear combination function $Gain$ of these objectives., Comment: A draft aimed at ACM TODAES journal, 25 pages with 16 figures and 2 tables

Multiple design iterations are inevitable in nanometer Integrated Circuit (IC) design flow until desired printability and performance metrics are achieved. This starts with placement optimization aimed at improving routability, wirelength, congestion and timing in the design. Contrarily, no such practice exists on a floorplanned layout, during the early stage of the design flow. Recently, STAIRoute \cite{karb2} aimed to address that by identifying the shortest routing path of a net through a set of routing regions in the floorplan in multiple metal layers. Since the blocks in hierarchical ASIC/SoC designs do not use all the permissible routing layers for the internal routing corresponding to standard cell connectivity, the proposed STAIRoute framework is not an effective for early global routability assessment. This leads to improper utilization of routing area, specifically in higher routing layers with fewer routing blockages, as the lack of placement of standard cells does not facilitates any routing of their interconnections. This paper presents a generalized model for early global routability assessment, HGR, by utilizing the free regions over the blocks beyond certain metal layers. The proposed (hybrid) routing model comprises of (a) the junction graph model in STAIRoute routing through the block boundary regions in lower routing layers, and (ii) the grid graph model for routing in higher layers over the free regions of the blocks. Experiment with the latest floorplanning benchmarks exhibit an average reduction of $4\%$, $54\%$ and $70\%$ in netlength, via count, and congestion respectively when HGR is used over STAIRoute. Further, we conducted another experiment on an industrial design flow targeted for $45nm$ process, and the results are encouraging with $~3$X runtime boost when early global routing is used in conjunction with the existing physical design flow., Comment: A draft of 24 pages aimed at ACM-TODAES Journal, with 10 figures and 5 tables

With aggressively shrinking process nodes, physical design methods face severe challenges due to poor convergence and uncertainty in getting an optimal solution. An early detection of potential failures is thus mandated. This has encouraged to devise a feedback mechanism from a lower abstraction level of the design flow to the higher ones, such as placement driven synthesis, routability (timing) driven placement etc. Motivated by this, we propose an early global routing framework using pattern routing following the floorplanning stage. We assess feasibility of a floorplan topology of a given design by estimating routability, routed wirelength and vias count while addressing the global congestion scenario across the layout. Different capacity profiles for the routing regions, such as uniform or non-uniform different cases of metal pitch variation across the metals layers ensures adaptability to technology scaling. The proposed algorithm STAIRoute takes $O(n^2kt)$ time for a given design with $n$ blocks and $k$ nets having at most $t$ terminals. Experimental results on a set of floorplanning benchmark circuits show $100\%$ routing completion, with no over-congestion in the routing regions reported. The wirelength for the $t$-terminal ($t\geq$ 2) nets is comparable with the Steiner length computed by FLUTE. An estimation on the number of vias for different capacity profiles is also presented, along with congestion and runtime results., Comment: 26 pages, 12 Figures, Springer Book chapter format