It is known that graphene nanoribbon (GNR) can be used as interconnects in nano-scale designs. To reduce the manufacturing cost in GNR routing, the constraint on the number of the used layers becomes more important. In this paper, given a set of GNR nets on a constrained set of routing layers inside a limited area, based on the concept of using GNR wires with CNT-via insertion in GNR routing, an efficient routing algorithm can be proposed to maximize the routability of the GNR nets and minimizing the total wirelength in assignment of the feasible routed paths with satisfying the non-crossing constraint on the GNR nets. Firstly, based on the construction of a crossing graph on the length-oriented consideration of the multiple-pin nets, all the intervals representing the GNR nets with covering compatibility can be assigned onto the minimized tracks and the represented intervals on the extra tracks can be reassigned onto the constrained tracks by using two separation-and-reassignment operations. Furthermore, based on the assignment result of the represented intervals on the constrained tracks and the hierarchical covering tree of the independent nets and the separated sub-nets on the constrained layers, the full and partial boundary-oriented paths of the GNR nets can be assigned on the constrained layers for routability and the assigned paths of the GNR nets can be modified to reduce the number of the used bends and the total wirelength of the GNR nets. Compared with the combination of Yen’s routing algorithm and the rip-up and reroute (RAR) process in layer-constrained GNR area routing with CNT-via insertion, the proposed algorithm can increase 2.1% of routability for 12 tested examples under 24 different constraints on the average. In addition, the proposed algorithm can reduce 31.6% of the number of the inserted CNT-vias, 5.5% of the number of the used bends and 2.3% of the total wirelength for 12 tested examples under 13 different constraints with 100% routability on the average.

It is known that rapid single-flux-quantum (RSFQ) circuit technology and its energy-efficient derivatives are considered as one promising technology in superconducting digital applications. In this article, given the placement result of a multiple-stage pipelined architecture with${n}$gate columns and${m}$gate components in an RSFQ circuit inside a rectangular layout, it is assumed that signals can be propagated from the primary inputs on the left boundary to the primary outputs on the right boundary. First, a lower bound on the routed width of one PTL region can be defined as the estimated width of one PTL region. Furthermore, the sum of the estimated widths of all the PTL regions in an RSFQ circuit can be defined as the estimated region width in an RSFQ circuit and the estimated width can be used as the objective function for the design of the clock distribution in an RSFQ circuit. Based on the flexibility of using the clock splitters (SPLs) inside the gate components for the propagation of clock signals, an iterative assignment algorithm can be proposed to complete the assignment of the tree-based clock connections with minimizing the estimated width of an RSFQ circuit. From viewpoint of numerical experiments, the experimental results show that the reduction of the estimated region width can lead to the reduction of the final width of the PTL regions in an RSFQ circuit. Compared with the design of Kito’s tree-based clock distribution for 5 tested RSFQ circuits, the experimental results show that the design of our proposed tree-based clock distribution with two capability parameters, 2 and 3, on a clock SPL can use reasonable CPU time to reduce 47.03% and 54.33% of the estimated region width and 44.83% and 45.25% of the final width for 5 tested RSFQ circuits on the average, respectively.

It is necessary for cost consideration to minimize the number of used layers in a PCB design. Traditionally, the number of used layers outside components in bus assignment depends on the locations of the bus pins inside components in escape routing in a PCB design. In this article, the concept of introducing the flexible escape directions in escape routing is considered in bus assignment outside components in a PCB design. Clearly, the flexible consideration of the escape directions inside components can lead to the reduction on the number of used layers in bus assignment outside components. Given a set of buses on a set of components in a PCB design, based on the introduction of the flexible escape directions in escape routing and the construction of the possible bus connections in bus assignment, the two upper bounds of the layer numbers inside and outside components can be first computed. By eliminating the redundant bus connections for the given buses, an integrated algorithm can be further proposed to minimize the number of used layers in a PCB design. Based on the assignment constraints from the intersection relations inside components, the physical connections of the given buses can be assigned onto a minimal set of used layers. Compared with the two-phase algorithm using Yan’s routing algorithm in direction-constrained rectangle escape routing and Yan’s assignment algorithm in bus assignment, the experimental results show that our proposed integrated algorithm uses reasonable CPU time to reduce 32.1% of the layer number for ten tested examples in a PCB design on the average.

It is known that rapid single-flux-quantum (RSFQ) circuit technology and its energy-efficient derivatives are considered promising technology in superconducting digital applications. Given an$n$-stage logical netlist with a set of logic gates and D-type flip-flops (DFFs) in an RSFQ circuit, based on the construction of three different gate components inside one gate column, the RSFQ circuit can be treated as a pipelined architecture with$m$gate components inside$n$gate columns. To minimize the routing area in the pipelined architecture of an RSFQ circuit, an efficient algorithm can be proposed to minimize the total vertical wirelength in a fixed-order placement. First, based on the construction of the initial fixed-order placement and the reduction of the total vertical minimum length using one upward-shifting operation, a propagation-based fixed-order placement (PFP) can be obtained by using an on-column placement process. Based on the determination of the available gate clusters inside the gate columns, an iterative matching-based shifting process can be further used to reduce the total vertical wirelength in a fixed-order placement. Finally, based on the determination of the available gate blocks in a modified fixed-order placement, an iterative shifting process can be used to reduce the total vertical wirelength in the modified fixed-order placement. Compared with the modified simulated-annealing (SA)-based algorithm with three initial temperatures, 100, 1000, and 100000, the experimental results show that our proposed algorithm can use 3.4%, 2.7%, and 2.1% of CPU time to reduce 3.5%, 0.5%, and 0.3% of the total vertical wirelength in a final fixed-order placement for five tested RSFQ circuits on the average, respectively. Clearly, the proposed algorithm is efficient in the construction of a fixed-order placement in an RSFQ circuit.

It is known that the pipelined architecture in a rapid single-flux-quantum (RSFQ) circuit can be constructed by inserting a set of path-balancing D-type flip-flops (DFFs) into some gate columns. Based on the assignment of the gates involving the splitters (SPLs) inside each gate column in the placement stage, the passive transmission line (PTL) region between two adjacent gate columns can be formed for a set of 2-pin connections in the routing stage. In this article, given a set of 2-pin connections with length-matching constraints inside one PTL region, based on the efficient utilization of available space in two routing layers, a new grid-based Manhattan routing model can be defined to use available space inside two routing layers for the insertion of the extension lengths on the given connections. To minimize the routing width inside one PTL region, a two-way track-assignment-based routing algorithm using the defined routing model can be first proposed to assign two partitioned sets of vertical intervals onto the used tracks inside two routing layers and connect the corresponding horizontal segments for the given connections with no extension length. Based on the definition of the available areas in the initial two-layer routing result, an iterative flow-based insertion algorithm can be further proposed to insert the feasible detouring paths onto the available areas for the extension lengths on the given connections. If there is no available area for the extension lengths on the unsatisfied connections, an efficient insertion algorithm can be proposed to insert the detouring paths onto one extra area for the extension lengths on the unsatisfied connections. Compared with Kito's routing algorithm and Cheng's routing algorithm in length-matching-constrained region routing, the experimental results show that our proposed routing algorithm can use reasonable CPU time to decrease 22.2% and 16.3% of the region width for 12 tested examples on the average, respectively.

It is necessary for reliability and yield to minimize the number of used vias on nets in printed circuit board (PCB) designs. To our knowledge, the proposed fuzzy-clustering-based algorithm is the first work for a general routing region with multiple-pin nets in k-layer circular topological via minimization (k-CTVM). In this article, given the topological connections in a set of routing nets and a set of k available layers in a routing plane, first, all the multipin nets can be transformed into a set of two-pin nets by introducing a set of preassigned vias onto the branch points on multipin nets and a conflict graph can be constructed for a final set of two-pin nets. Furthermore, the probabilistic similarity between two connected vertices using the same color can be computed for the constrained vertex-coloring problem with k colors in a conflict graph. Next, based on the definition of the clustering distance between two connected vertices in a conflict graph, fuzzy graph clustering can be developed to obtain a fuzzy matrix on k clusters. Finally, all the given nets can be assigned onto the k available layers by introducing a set of necessary vias on two-pin nets and eliminating the unnecessary preassigned vias on multipin nets. Compared with the combination of Cong's algorithm and an iterative net postassignment, NetInsertion1, in the k-CTVM problem, the experimental results show that our proposed fuzzy-clustering- based algorithm can use less CPU time to reduce 57.3% of the number of the total used vias for eight tested PCB designs. Compared with the combination of Yan's algorithm and an iterative net postassignment, NetInsertion2, in the k-CTVM problem, the experimental results show that our proposed fuzzy-clustering-based algorithm can reduce 34.0% of the number of the total used vias for eight tested PCB designs.

It is known that the pipelined architecture in a rapid single-flux-quantum (RSFQ) circuit can be constructed by inserting a set of path-balancing D-type flip-flops (DFFs) into some gate columns. Based on the assignment of the combined gates involving the splitters (SPLs) inside each gate column in the placement stage, the passive transmission line (PTL) region between two adjacent gate columns can be formed for a set of 2-pin connections in the routing stage. In this article, given a set of 2-pin connections with their length-matching constraints inside one PTL region, based on the concept of introducing a minimal set of vias in two available layers for single-flux-quantum (SFQ) pulse integrity, an efficient via-minimization-oriented routing algorithm can be proposed to minimize the routed width of one PTL region under length-matching constraint. By separating the wiring segments into sub-segments on some connections, the corresponding segments can be first assigned onto two available layers using a minimal set of vias. Furthermore, the introduced vias on the separated segments can be assigned onto feasible positions under the non-detouring and capacity constraints, and the monotonic river-routing process can be used to minimize the region width. Besides that, a set of flexible available areas can be constructed for the extension lengths on the given connections. Finally, one extra area can be accurately estimated and inserted for the extension lengths on the given connections and the zigzag detouring paths can be inserted into the available areas to satisfy the requirement of the extension lengths on the given connections. Compared with Kito's algorithm and Yan's algorithm in region routing under length-matching constraints, the experimental results show that our proposed routing algorithm can use reasonable CPU time to decrease 79.9% and 43.6% of the via number and 34.5% and 12.3% of the region width for 12 tested examples on average, respectively.

It is well known that interposer-based 2.5-D integrated circuit (IC) designs have become one of the most promising solutions for providing yield improvement, enhancing system performance, decreasing power consumption, and supporting heterogeneous integration. In this article, given a set of nets including some inter-chip or through-silicon buses between chips and package, inside a silicon interposer, a via-avoidance-oriented routing algorithm can be proposed to minimize the number of the used layers by satisfying the noncrossing constraint between two nets and the constraint of using no via on the inter-chip sub-nets and no vertical detour on the through-silicon sub-nets in multiple-layer interposer routing. The routing process in our proposed algorithm can be divided into two sequential steps: iterative routing step and refinement step. In the iterative routing step, the routing process of all the given nets can be completed for layer minimization in a top-down layer-by-layer manner. In each iteration, based on the definition of the obstacle-aware routing pattern for the inter-chip sub-net on one given net, the assignment of the obstacle-aware routing patterns can be firstly obtained in single-layer routing. Furthermore, the routing paths of some inter-chip sub-nets and the partial or full routing paths of some through-silicon sub-nets can be assigned and routed onto the available layer by using a maze routing process under the detour constraints. In the refinement step, based on the routing result of the given nets on the used layers, the detoured inter-chip or through-silicon sub-nets can be firstly reassigned and rerouted for the detour reduction of the given nets. Furthermore, a set of zigzag paths can be inserted onto some nets inside the given inter-chip or through-silicon buses for skew minimization. Compared with the combination of the iterative routing using Cadence’s automatic router and the detouring-path insertion on the number of the used layers, the experimental results show that our proposed routing algorithm can use reasonable CPU time and shorter wirelength to decrease 19.3% of the number of the used layers for eight tested examples on the average.

It is known that graphene nanoribbon (GNR) based devices and interconnects can be treated to be better alternative in nano-scale designs. In this paper, given a source pin and a set of target pins inside a GNR routing plane with a set of rectangular obstacles, based on the selection of the possible obstacle-avoiding delay-driven routing paths on the target pins, an efficient routing algorithm can be proposed to construct an obstacle-avoiding delay-driven GNR routing tree with minimizing the total wirelength for the target pins. Compared with Das's algorithm with obstacle avoidance on total wirelength and maximum source-to-target delay, the experimental results show that our proposed routing algorithm only uses 7.87% of the extra wirelength to reduce 23.42% of the maximum delay in the construction of an obstacle-avoiding delay-driven GNR routing tree for 6 tested examples on the average.

It is known that single-layer obstacle-aware substrate routing is necessary for modern IC/Package designs. In this article, given a set of two-pin nets and a set of rectangular obstacles inside a single-layer routing plane, a two-phase routing algorithm including an iterative routing phase and a rip-up-and-reroute phase can be proposed to maximize the number of the routed nets in single-layer obstacle-aware substrate routing. In the iterative routing phase, based on the pin and path distribution of the routing nets and the locations of the obstacles inside a single-layer routing plane, the start or target pins on some routing nets inside dense obstacle regions may be firstly reassigned to complete the partial wiring paths on the nets. Based on the region extraction of two intersected nets in single-layer routing, the private regions of some routing nets inside sparse obstacle regions can be extracted and the nets inside the extracted regions can be further routed by using maze routing. In the rip-up-and-reroute phase, the routability of the routing nets can be improved by ripping up some routed nets and rerouting the unrouted nets. Compared with Liu's modified algorithm and Yan's flow-based algorithm in single-layer obstacle-aware substrate routing, the experimental results show that the proposed algorithm can use less CPU time to increase 3.4% and 1.8% of the routability on the routing nets for eight tested examples on the average. Additionally, the percentage of the tested examples with the 100% routability of the routing nets on the eight tested examples has been improved from 25% to 62.5%.

It is known that graphene nanoribbon (GNR)-based devices and interconnects can be treated to be a better alternative in nanoscale designs. In this article, given a source pin and a set of target pins inside a GNR grid-based routing plane, based on the consideration of the bending delay on one routing path, an integer linear programming (ILP)-based algorithm can be first proposed to minimize the total wirelength of a single-layer delay-driven GNR routing tree (DGNRRT). Furthermore, given a resource constraint in a single-layer DGNRRT and the connection defective rate on one routing segment, the other ILP-based algorithm can be proposed to insert a feasible set of yield-driven redundant paths to maximize the total yield gain of the inserted redundant paths under resource constraint. Finally, a feasible set of obstacle-aware redundant paths may be sequentially inserted to improve the connecting yield of a delay-driven GNR nontree routing (DGNRNTR) result under resource constraint. Compared with Das's algorithm in the construction of a GNR routing tree, the experimental results show that our proposed ILP-based algorithm uses reasonable CPU time to increase 2.50% of the wirelength and reduce 22.85% of the maximum delay for eight tested examples on the average. Compared with Yan's algorithm in the construction of a DGNRRT, the experimental results show that our proposed ILP-based algorithm uses reasonable CPU time to reduce 5.17% of the wirelength under the same maximum delay for eight tested examples on the average. Under two resource constraints as 50% and 65% in a DGNRNTR result, the experimental results show that the connecting yields of the eight tested DGNRRTs can be improved as 0.3939 and 0.5296 on the average by using our proposed ILP-based algorithm, respectively. Compared with the combination of the algorithm, PathInsertion, and our proposed algorithm, obstacle-aware path insertion (OAPI), the experimental results show that our proposed ILP-based algorithm can improve the connecting yields of the eight tested DGNRRTs as 0.067 and 0.0507 on the average under two resource constraints as 50% and 65%, respectively.

It is known that graphene nanoribbon (GNR)-based devices and interconnects can be a better alternative in nano-scale designs. In this article, given a set of GNR nets with delay constraints in a GNR routing plane, a delay-constrained routing algorithm can be proposed to minimize the number of the used layers with satisfying the non-crossing constraints between the two GNR nets and the delay constraints on the given GNR nets in multiple-layer delay-constrained GNR routing. The routing process in our proposed algorithm can be divided into two sequential steps: initial assignment and iterative routing. In the initial assignment step, based on the source-to-target transformation of the multiple-pin nets and the definition of the delay-constrained routing patterns on the GNR nets with the tight delay constraints, a set of necessary delay-constrained routing patterns on the GNR nets can be first assigned onto a minimal set of used layers and the remaining GNR nets can be further assigned onto the available layers. In the iterative routing step, based on the assignment result of the GNR nets, the assigned GNR nets can be routed by using one routability-driven obstacle-aware routing process without considering the delay constraints and the delay-violated GNR nets can be rerouted by using one iterative delay-constrained rip-up-and-rerouting process with considering the delay constraints. Compared with the combination of the source-to-target transformation of the multiple-pin nets and one multiple-layer planar routing process using two single-layer GNR routing algorithms, the experimental results show that our proposed delay-constrained algorithm can use less CPU time and reasonable wirelengths to decrease 38.6% and 35.0% of the number of used layers on the given GNR nets with two different sets of delay constraints for eight tested examples on the average, respectively.

It is necessary for cost consideration to minimize the number of the used layers in a high-speed printed circuit board (PCB) design. In this paper, any independent net cannot be treated as a bus-oriented net in a high-speed PCB design because of no timing-matching constraint on an independent net. Any independent net in a high-speed PCB design can be modeled to obey the via-count constraint as the maximum number of the permitted vias for signal integrity. Clearly, the introduction of the permitted vias onto the independent nets can lead to the reduction on the number of the used layers in a high-speed PCB design. Given a set of bus-oriented nets and a set of independent nets with a via-count constraint in a high-speed PCB design, by introducing virtual vias onto independent nets and eliminating redundant vias on any used layer, a generalized algorithm can be proposed to minimize the number of the used layers with satisfying the via-count constraint on any independent net and assign the given bus-oriented nets and the separated segments inside the given independent nets onto the used layers. Compared with Yan's algorithm with no via introduction on independent nets, the experimental results show that our proposed algorithm with ${c_{\max } = 1}$ , ${c_{\max } = 2}$ , ${c_{\max } = 3}$ , ${c_{\max } = 4}$ , and ${c_{\max } = 5}$ use reasonable CPU time to insert permitted vias to reduce 2.1, 2.8, 3.8, 4.4, and 4.6 used layers on the average for ten tested examples, respectively. Compared with a two-phase algorithm with via introduction on independent nets, the experimental results show that our proposed algorithm with ${c_{\max } = 1}$ , ${c_{\max } = 2}$ , ${c_{\max } = 3}$ , ${c_{\max } = 4}$ , and ${c_{\max } = 5}$ use less CPU time to reduce 1.6, 1.7, 1.7, 1.6, and 1.5 used layers on the average with increasing 13.3%, 16.3%, 10.6%, 4.2%, and 2.6% of the total used vias on the independent nets for ten tested examples, respectively.

As feature sizes in semiconductor technique scale down, traditional CMOS devices and interconnects are facing several challenges. Graphene nanribbon (GNR)-based devices and interconnects can be treated to be better alternative in nano-scale designs. In this paper, given a set of nets in a single-layer GNR routing (SGNRR) plane, an efficient routing algorithm can be proposed to maximize the number of the routed nets with minimizing the bending delay in SGNRR. The routing process in our proposed algorithm can be divided into three sequential steps: 1) routability-driven net assignment; 2) iterative diffusion-based transformation for delay reduction; and 3) iterative rip-up-and-reroute (IRUR) for delay reduction. In routability-driven net assignment, based on the transformation of multiple-pin nets and the region extraction of two intersected nets in single-layer routing, some detored nets can be selected and the remaining nets can be first routed inside their available regions. Furthermore, the detored nets can be routed by using single-layer obstacle-aware routing. In iterative diffusion-based transformation for delay reduction, the available empty space in an initial routing result can be further used to transform 120° bends into 60° bends. In IRUR process for delay reduction, the routing order of two adjacent nets may be further exchanged to reduce the bending delay if empty space is available. Compared with the combination of the transformation of multiple-pin nets and Yan's negotiated congestion-based algorithm in SGNRR, the experimental results show that our proposed algorithm can use less CPU time to decrease 11.1% of total bending delay with increasing 1.3% of total wirelength on the given nets with the same 100% routability for six tested examples on the average. Additionally, the experimental results show that our proposed algorithm can use less CPU time to increase 5.5% of routability on the given nets for six denser examples on the average.

It is known that one-sided net untangling can be used to untangle the twisted nets inside a bus for single-layer bus routing. However, limited space behind one pin-row may make one-sided net untangling unsuccessful for single-layer bus routing. In this article, the concept of using internal detours on untangled nets can be introduced into two-sided net untangling. Given a set of 2-pin nets inside a bus, based on two one-sided untangling results with internal detours on untangled nets [8], an efficient algorithm first uses a minimal set of internal detours to guarantee that the crossing conditions of the given nets inside the bus can be eliminated in one initial two-sided untangling result with no capacity constraint behind two pin-rows and between two adjacent pins inside any pin-row. Furthermore, based on the maintenance of the non-crossing constraint on any pair of nets and the capacity constraint behind two pin-rows in one initial two-sided untangling result, an iterative rip-up-and-reassign algorithm can be proposed to eliminate the possible capacity violations between two adjacent pins inside two pin-rows to route a maximal set of nets in two-sided net untangling. Compared with Yan's one-sided net untangling [8] for 12 tested examples with different capacity constraints, the experimental results show that our proposed two-sided untangling algorithm can improve 3.5% of routability and use the benefit of more routing space behind two pin-rows to reduce 86.4% of the used internal detours on average in reasonable CPU time. Compared with Yan's two-sided net untangling [9] for 12 tested examples with different capacity constraints, the experimental results show that our proposed two-sided untangling algorithm can improve 2.8% of routability by introducing some internal detours and using iterative rip-up-and-reassign on the average in reasonable CPU time.

To satisfy the performance requirement in modern very large-scale integration designs, on-chip optical integration is a potential and developing technology in delay and power consideration. After completing the placement of the used optical devices in an optical layer, an optical routing plane can be divided into a set of horizontal or vertical optical channels. Based on the exploration of different routing geometries in optical planar routing, optical signal loss including length loss, bend loss, and crossing loss can be treated as the penalty of a routing result in optical planar routing. In this paper, a new grid-based non-Manhattan routing model is first proposed to assign the possible routing paths for optical interconnects. Furthermore, given a set of two-pin optical nets inside an optical channel in our proposed grid-based routing model, based on the optimality-oriented swap pass in Yan's hierarchical bubble sorting, an efficient channel router can be proposed to complete the connection of the given optical nets with minimizing the total signal loss on the given nets inside an optical channel. Compared with Condrat's swap-based channel router, the experimental results show that our proposed channel router decreases 41.08% of the total bend loss, 13.17% of the worst signal loss, and 23.57% of the total signal loss under the same total crossing loss on the average for ten tested examples in reasonable CPU time. Besides that, the experimental results show that our proposed channel router reduces 8.2% of the total wire length, 51.40% of the total routing tracks, and 9.98% of the total routing area for ten tested examples in reasonable CPU time.

Given a set of buses with available escape directions inside a chip, a two-phase algorithm is proposed to assign one feasible escape direction onto any bus such that the number of used layers is minimized and to allocate the pin rectangle and the projection rectangle of any escape bus onto the minimized layers in direction-constrained rectangle escape routing. In our proposed algorithm, based on the concept of two-dimensional maximum density inside a chip, the escape directions of the buses can be first assigned to minimize the number of the used layers by iteratively eliminating unnecessary escape directions for any bus inside a chip. Furthermore, based on the construction of the represented intervals and the assignment constraints for the escape buses, a modified left-edge algorithm can be used to allocate all the escape buses onto the minimized layers. Compared with Ma’s integer linear program (ILP)-based algorithm [10] using lp_solve and Gurobi in rectangle escape routing, the experimental results show that our proposed algorithm obtains the same results but reduces CPU time by 94.2% and 35.7% when using lp_solve and Gurobi for 16 tested examples with no direction constraint on average, respectively. Compared with the modified algorithm from Ma's ILP-based algorithm [10] using lp_solve and Gurobi in direction-constrained rectangle escape routing, the experimental results show that our proposed algorithm obtains the same results but reduces CPU time by 94.3% and 37.7% when using lp_solve and Gurobi for 16 tested examples with direction constraints on average, respectively. Besides that, compared with Yan’s iterative algorithm, the experimental results show that our proposed algorithm increases CPU time by 1.0% to reduce the number of used layers 11.1% for 16 tested examples on average.

It is known that it is necessary for single-layer bus routing to untangle all the twisted nets inside a single bus. In this paper, the concept of using internal detours on untangled nets can be introduced to solve the unroutable conditions in one-sided single-detour untangling. Based on the optimality-oriented swap passes in Yan's hierarchical bubble sorting, given a set of two-pin nets inside a single bus, the wiring capacities for all the pairs of two adjacent pins inside top or bottom pin-row and behind top or bottom pin-row, an efficient untangling algorithm is proposed to eliminate the crossing conditions of the given nets inside a single bus by untangling some nets into the region behind top or bottom pin-row with minimizing the number of the used internal detours and satisfying all the necessary capacity constraints. Compared with Yan's algorithm and Lin's algorithm in one-sided single-detour untangling, the experimental results show that our proposed algorithm can successfully untangle all the twisted nets inside a single bus for the tested examples in reasonable time.

It is important for cost and reliability consideration to minimize the number of the used layers in a PCB design. In this article, given a set of n circular escape buses with their escape directions between two adjacent components and a set of m consecutive constraints on the escape buses, the problem of assigning the given escape buses between two adjacent components onto the minimized layers is first formulated for bus-oriented escape routing. Furthermore, an efficient approach is proposed to minimize the number of the used layers for the given escape buses with the consecutive constraints and assign the escape buses onto the available layers. Compared with Yan's approach [Yan and Chen 2012] for the layer assignment of the linear escape buses with no consecutive constraint and Ma's approach [Ma et al. 2011a] for the layer assignment of the circular escape buses with consecutive constraints, the experimental results show that the proposed approach obtains the same optimal results on the number of the used layers and reduces 43.6% and 90.5% of CPU time for the tested examples on the average, respectively.

It is known that bus-oriented escape routing and area routing are necessary in a high-speed printed circuit board (PCB) design. In this paper, given a set of global routed buses in a high-speed PCB design, it is assumed that the routed nets in a single bus are represented as a bus-oriented net between two escaped boundary pins. Based on the construction of a virtual wall between two circuit components, the connection transformation of the given bus-oriented nets inside a closed region and the construction of a covering graph for the represented intervals, an iterative modified left-edge algorithm is proposed to minimize the number of the assigned layers and assign all the bus-oriented nets onto the available layers. Compared with Tsai's algorithm, the experimental results show that our proposed algorithm reduces 15.0% of the layer number and 21.9% of CPU time for six tested examples on the average, respectively. Compared with Chin's algorithm, the experimental results show that our proposed algorithm use less CPU time to reduce 15.0% of the layer number for six tested examples on the average.

Due to the inappropriate assignment of bump pads or the improper assignment of I/O buffers, the constructed buffered I/O signals in an area-I/O flip-chip design may yield longer maximum delay. In this article, the problem of assigning performance-driven buffered I/O signals in an area-I/O flip-chip design is first formulated. Furthermore, the assignment of the buffered I/O signals can be divided into two sequential phases: Construction of performance-driven I/O signals and Assignment of timing-constrained I/O buffers. Finally, an efficient matching-based approach is proposed to construct the performance-driven I/O signals for the given I/O pins and assign the timing-constrained I/O buffers into the constructed I/O signals in the assignment of the buffered I/O signals in an area-I/O flip-chip design. Compared with the experimental results of seven tested circuits in the Elmore delay model, the experimental results show that the matching-based assignment in our proposed approach can reduce 3.56% of the total path delay, 9.72% of the maximum input delay, 5.90% of the input skew, 5.64% of the maximum output delay, and 6.25% of the output skew on average by reassigning the I/O buffers. Our proposed approach can further reduce 38.89% of the total path delay, 44.00% of the maximum input delay, 49.13% of the input skew, 44.93% of the maximum output delay, and 50.82% of output skew on average by reconstructing the I/O signals and reassigning the I/O buffers into the I/O signals. Compared with the experimental results of seven tested circuits in Peng's [Peng et al. 2006] publication, the experimental results show that our proposed matching-based approach can further reduce 71.06% of the total path delay, 67.83% of the maximum input delay, 59.84% of the input skew, 68.87% of the maximum output delay, and 61.46% of the output skew on average. On the other hand, compared with the experimental results of five tested circuits in Lai's [Lai and Chen 2008] publication, the experimental results show that our proposed approach can further reduce 75.36% of the total path delay, 48.94% of the input skew, and 52.80% of the output skew on the average.

It is well known that single-layer routing is used for RDL routing in flip-chip designs and substrate routing in package designs. In this paper, given a set of two-terminal nets in a single-layer gridded routing plane, the routing regions of all the given nets can be initially constructed. Based on the routing constraints on different intersection conditions of two routing regions in a single layer, the wiring directions of the given nets can be further assigned. Finally, based on the assigned directions of the given nets, the wiring paths of the given nets onto the routing grids can be assigned by diffusing the overlapping paths and eliminating the unnecessary detours in single-layer routing. The experimental results show that our proposed approach can route 99.98% of the given nets in single-layer routing for 6 tested examples in reasonable CPU time on the average.

Spare cells have been widely used to realize design changes at post-placement stage for functional changes or timing violations. However, many prior works relative to spare cell utilization neglect the timing effect due to spare cell rewiring. In this paper, the problem of timing-constrained cell replacement using spare cells is firstly formulated to consider the timing effect of the rewiring result. Furthermore, a three-phase approach is proposed to replace the changed cells in a combinational circuit with available spare cells while the timing constraints on the changed cells are satisfied. Experimental results show that our approach can efficiently realize the functional changes under the timing constraints for 5 tested cases.

It is well known that clock skew minimization becomes critical in high-performance VLSI designs. In this paper, the assignment of adjustable delay buffers(ADBs) is applied to minimize the clock skew in a buffered clock tree in a multi-voltage mode design. Given a buffered clock tree, based on the assignment flexibility of the delay value on an ADB, bottom-up ADB assignment is firstly proposed to insert ADBs to minimize the clock skew by assigning the delay values of the inserted ADBs for each power mode. Furthermore, bottom-up ADB elimination is proposed to eliminate the redundant ADBs to minimize the number of the inserted ADBs in a multi-voltage mode design while maintaining the minimized clock skew. Compared with Su's heuristic algorithm and Lim's optimal algorithm, the experimental results show that our proposed algorithm uses less CPU time to reduces 9.3% of the used ADBs and 1.3%~1.6% of the average latency on the average, respectively.

In a complex sequential circuit, the problem of fixing min-delay violations becomes more and more important. To our knowledge, no efficient approach is proposed to eliminate the min-delay violations in a layout-level implementation. In this paper, the min-delay violations in a layout-level implementation are considered. By using the available space along the routing wires, redundant loads can be inserted into the space to increase the interconnect delay. Based on the insertion of the post-layout wires for redundant loads, a top-bottom-based insertion approach is proposed to insert post-layout redundant wires to fix the min-delay violations in a layout-level implementation. The experimental results show that our proposed approach only increases 0.84% of the total wirelength on the available space to insert post-layout redundant wires to fix 100% of the min-delay violations in a layout-level implementation for 6 tested circuits on the average in reasonable CPU time.

Given a set of n buses in a pin array, the layer assignment(LA) for rectangle escape routing can be divided into five different problems: LA-1, opposite LA-2, corner LA-2, LA-3 and LA-4 problems for rectangle escape routing. Based on the optimality of a left-edge algorithm for interval packing, the LA-1 problem can be transformed into an interval packing problem and optimally solved in O(nlogn) time. Furthermore, based on the definition of an exact low-bound and the concept of the density reduction, the opposite LA-2 problem can be optimally solved by using density-reduction-oriented layer assignment in O(nlogn) time. Finally, by using the optimal results in the LA-1 and opposite LA-2 problems, the corner LA-2, LA-3 and LA-4 problems can be solved by using two-phase density-reduction-oriented layer assignment in O(nlogn) time. Compared with Ma's approximation algorithm[6] for the LA-4 problem, the experimental results show that our proposed algorithm obtains the same optimal result but reduces 91.6% of CPU time for eight tested examples on the average.

It is important for a synchronous design to minimize the clock skew in a clock tree. In this paper, based on the length-matching benefit in exact routing, an efficient four-stage algorithm is further proposed to generate a symmetrical buffered clock tree with smaller clock skew under a given slew-rate constraint. For symmetrical buffered clock routing, compared with Shih's approach, the experimental results show that our proposed approach can use extra 2.54% of total resource to reduce 85.78% of clock skew in a symmetrical buffered clock tree with satisfying the slew-rate constraint for tested benchmarks in less CPU time on the average.

Based on the equilibrium concept of inserting load in a physical balance, the insertion of redundant wires can be used to minimize the clock skew in an OPE-predicted clock tree. For five tested benchmarks, the experimental results show that our proposed algorithm only increases 2.8% of the total load on the average for the insertion of OPE-predicted redundant wires and decreases 30.85 ps of the clock skew on the average to obtain the near zero-skew result in reasonable CPU time.

Compared with the traditional flow for IC designs, the assignment of inter-die signals is an important stage in a die-stacking SiP design. In this paper, firstly, a connection graph for all the pads in a boundary stack can be constructed and a set of dynamic tracks can be defined from the corresponding connection graph. Based on the definition of the dynamic tracks in a connection graph, a modified left-edge approach is proposed to iteratively assign the inter-die signals onto feasible pads under the constraints of the crossing and connection conditions. Compared with the published two-stage approach[5], the experimental results show that our proposed approach reduces 99% of CPU time and 0.9% of total wirelength to assign all the inter-die signals for the tested examples on the average.

Due to inappropriate assignment of bump pads or improper placement of I/O buffers, the configured delays of I/O signals may not satisfy the timing requirement inside die core. In this paper, the problem of timing-constrained I/O buffer placement in an area-IO flip-chip design is firstly formulated. Furthermore, an efficient two-phase approach is proposed to place I/O buffers onto feasible buffer locations between I/O pins and bump pads with the consideration of the timing constraints. Compared with Peng's SA-based approach, with no timing constraint, our approach can reduce 71.82% of total wirelength and 55.74% of the maximum delay for 7 tested cases on the average. Under the given timing constraints, our result obtains higher timing-constrained satisfaction ratio(TCSR) than the SA-based approach.

Based on the width determination of any current-driven connection for electromigration and IR-drop avoidance, an area-driven multiple-source routing tree can be firstly constructed to minimize the total wiring area with satisfying the current flow in Kirchhoff's current laws and the electromigration and IR-drop constraints. Furthermore, some Steiner points can be assigned onto feasible locations to reduce the total wiring area under the electromigration and IR-drop constraints. Finally, an obstacle-aware multiple-source rectilinear Steiner tree can be constructed by assigning the obstacle-aware minimum-length physical paths for all the connections. Compared with Lienig's multiple-source Steiner tree[7], the experimental results show that our proposed approach without any IR-drop constraint can reduce 10.5% of the total wiring area. Under 10%Vddand 5%VddIR-drop constraints, the experimental results show that our proposed approach can satisfy 100% electromigration and IR-drop constraints and reduce 7.5% and 4.9% of the original total wiring area on the average for tested examples, respectively.

In this paper, based on the optimal feature of a left-edge algorithm for interval packing, a modified left-edge algorithm is proposed to optimally solve the layer assignment problem for bus-oriented escape routing. Firstly, a set of assignment constraints for the overlapping relations of the left or right projection intervals and the crossing relations of all the buses between two adjacent pin arrays is generated. Furthermore, with the consideration of the assignment constraints, an optimal constraint-aware algorithm is proposed to minimize the number of assigned layers and assign all the buses onto the used layers. Compared with Kong's heuristic algorithm[4], it is proved that our proposed optimal algorithm guarantees that the number of assigned layers is minimized and the experimental results show that our proposed algorithm reduces 8.8% of assigned layers for eight tested examples on the average. Compared with Yan's O(n2.38) optimal algorithm[5], it is proved that our proposed optimal algorithm has better time complexity in O(n2) time and the experimental results show that our proposed algorithm reduces 33.6% of CPU time for eight tested examples on the average.

Given a set of IO connections between IO buffers and bump balls in a re-distribution routing layer, an efficient router is proposed to route all the IO connections for pre-assignment RDL routing in an area-IO flip-chip design. Based on the simplification of net renumbering and the extraction of the maximal net sequence for all the IO connections, all the connections can be firstly divided into local and global connections. After routing the global wires of all the local connections, the global wires of all the global connections are further assigned under the capacity constraint for RDL global routing. Finally, the global wires of all the IO connections are routed for RDL detailed routing by assigning feasible crossing points and physical paths. The experimental results show that our proposed pre-assignment RDL router can maintain 100% routability in 7 tested industrial circuits. Compared with Yan's pre-assignment RDL router[4] in total wirelength and CPU time, our proposed approach saves 3.7% of total wirelength and 27.0% of CPU time on the average.

As clock frequency increases, signal propagation delay on PCBs is requested to meet the timing specification with very high accuracy. Generally speaking, the net length in a single layer can estimate the routing delay in a single-layer net. In this paper, given a set of r single-layer nets in a bus with their length constraints inside mxn routing grids with s obstacle grids, based on obstacle-aware region partition inside routing grids, obstacle-aware shortest path generation and two detouring operations, R-flip and C-flip, an efficient O(mn+s3) algorithm is proposed to generate the length-matching paths for obstacle-aware bus routing. Compared with the published CAFE router, our proposed routing algorithm can save 80.5% of CPU time to complete obstacle-aware length-matching bus routing with no length error for tested examples on the average.

Given a set of IO buffers and a set of bump balls with the capacity constraints between two adjacent bump balls, based on the construction of the Delaunary triangulation and a Manhattan Voronoi diagram, an O( n 2 ) assignment algorithm is proposed to assign all the IO connections in a single redistribution layer for IO connection assignment, where n is the number of bump balls in a flip-chip design. Furthermore, based on the computation of the probabilistic congestion for the assigned IO connections, an O( n 2 ) routing algorithm is proposed to minimize the total wirelength to route all the assigned IO connections while satisfying the capacity constraints for single-layer RDL routing. Compared with the combination of a greedy IO assignment and our RDL routing, our IO assignment reduces the total wirelength by 9.9% and improves the routability by 8.8% on the average for 6 tested circuits. Compared with the combination of a greedy IO assignment, the single-layer BGA global router [Tomioka and Takahashi 2006] and our RDL detailed routing, our IO connection assignment and RDL routing reduces the total wirelength by 12.9% and improve the routability by 10.2% on the average for 6 tested circuits. Besides that the experimental results show that our IO connection assignment and RDL routing can reduce 52.1% of the total wirelength on the average to achieve 100% routability for 12 tested industrial circuits under reasonable CPU time.

As the clock frequency increases, signal propagation delays on PCBs are requested to meet the timing specifications with very high accuracy. Generally speaking, the length controllability of a net decides the routing delay of the net. If a routing result has the higher length controllability, the routing delay will be obtained with higher accuracy. In this paper, given a start terminal, S, and a target terminal, T, in mxn routing grids with obstacles, based on the rectangular partition in routing grids and the analysis of unreachable grids in rectangular pattern detouring, an efficient O(mnlog(mn)) algorithm is proposed to generate the longest path in routing grids from S to T. Compared with the US routing[5], our proposed routing approach can achieve longer paths for tested examples in less CPU time.

In this paper, based on the optimality of hierarchical bubble sorting, the problem of two-sided single-detour untangling for single-layer bus routing is firstly formulated. Compared with an optimal O(n3) algorithm[4] for one-sided single-detour untangling without capacity consideration, an optimal O(n2) algorithm is proposed to solve the two-sided single-detour untangling problem without capacity consideration. For two-sided single-detour untangling with capacity consideration, an efficient O(n2) algorithm is proposed and the experimental results show that our proposed algorithm can successfully untangle all the twisted nets for the tested examples in less CPU time.

For timing-driven or yield-driven designs, non-tree routing has become more and more popular and additional loops provide the redundant paths to protect against the effect of the open defects. Based on the assumption of a single wiring open in a signal net, it is known that the non-tree interconnection of a signal net has no adjacent loop. In this paper, based on the concept of splitting a time-equivalent node or edge in a cyclic connection for timing analysis, a 0-1 integer linear programming(ILP) formulation for resource-constrained timing-driven link insertion is proposed to insert timing-driven links to maximize the reduced delay of the critical path in a rectilinear Steiner tree under a given resource constraint. The experimental results show that our proposed algorithm has the 21.0% and 23.5% reduction of the critical delay on the average for the tested trees in reasonable CPU time under the 10% and 20% resource constraint of the total wirelength, respectively.

For board-level routing, ordered escape routing is a key problem. In this paper, based on the optimality of hierarchical bubble sorting, the process of assigning routability-driven pins is done for single-layer routing. Furthermore, an efficient routing approach with the consideration of variable capacity is proposed to solve the ordered escape routing problem. The experimental results show that our proposed approach achieves 100% routability for the tested examples in reasonable CPU time. Compared with the SAT-based approach[6] for the tested examples with the capacity 1, our proposed approach reduces the CPU time by 77.7% on the average. For the tested examples with the capacity 2, our proposed approach can achieve 100% routability in reasonable CPU time.

The concept of merging some 1-bit flip-flops into a multi-bit flip-flop is applied to reduce dynamic clock power and decrease the total flip-flop area in a synchronous design. To acquire these advantages, the design must be guaranteed to satisfy certain physical constraints in the merging process. In this paper, given a set of 1-bit flip-flops with the input and output timing constraints, the area constraint inside any partitioned bin and the capacity constraint on any bin edge in a placement plane, an efficient routability-driven approach is proposed to merge 1-bit flip-flops into some multi-bit flip-flops for clock power reduction. The experimental results show that our proposed approach reduces 37.4% of the flip-flop area to maintain the synchronous design and saves 24.82% of the clock power for five examples in reasonable CPU time on the average.

With the use of non-tree topology in signal nets, the delay issue in non-tree topologies has become an important problem. In this paper, based on the transformation-based timing analysis for a non-tree interconnection, an iterative wire-sizing approach is proposed to assign feasible widths onto the wire segments to minimize the timing delay in the critical path for a non-tree interconnection under a maximum-width constraint Compared with the original non-tree interconnection with the assignment of minimum width, the experimental results show that our proposed approach achieves 15.6%, 19.6% and 22.1% of delay reduction on the average under 0.36μm, O.S4μm and ft 72fan maximum-width constraints, respectively.

Based on the simplification of the addition operations in a low-power bypassing-based multiplier, a low-cost low-power bypassing-based multiplier is proposed Compared with row-bypassing multiplier, column-bypassing multiplier and 2-dimensional bypassing-based multiplier for 20 tested examples, the experimental results show that our proposed low-cost low-power multiplier saves 15.1% of hardware cost and reduces 29.6% of the power dissipation on the average for 4×4, 8×8 and 16×16 multipliers.

Given a set of IO buffers and bump balls with the capacity constraints between bump balls, an O(n2) IO assignment and RDL routing algorithm is proposed to assign all the IO connections and minimize the total wirelength with satisfying the capacity constraints and guarantee 100% routability if the capacity constraint is permitted, where n is the number of bump balls in a flip-chip design. Compared with the combination of the greedy IO assignment and our RDL routing, our IO assignment reduces the global wirelength by 7.6% after global routing and improves the routability by 8.8% after detailed routing on the average. Compared with the combination of our IO assignment, the single-layer BGA global router[8] and our detailed routing phase, our RDL routing reduces the global wirelength by 15.9% after global routing and improve the routability by 10.6% after detailed routing on the average for some tested circuits in reasonable CPU time.

Based on the concept of net renumbering and recovery to simplify the complexity of the global and detailed routing, an efficient RDL pre-assignment routing algorithm is proposed to maximize the number of routed nets with the minimization of total wirelength under the crossing and capacitance constraints for a flip-chip design. Compared with the combination of the single-layer BGA global router[6] and our detailed routing, our RDL pre-assignment router reduces the global wirelength by 12.8% after global routing and improve the routability by 14.7% after detailed routing on the average for some tested circuits in reasonable CPU time.

Based on the insertion of internal and external redundant wires into L-type and U-type wires, an efficient two-phase reliability-driven insertion algorithm is proposed to insert redundant wires to construct local cycles and protect the failure of any wire or via for yield improvement. For tested benchmarks, the experimental results show that our proposed insertion approach increases the extra wirelength of internal and external redundant wires by 18.3% and 6.3% to increase the reliability of 56.9% and 5.2% and improve the chip yield by 0.106 and 0.032 on the average in reasonable CPU time, respectively.

Designs with non-tree consideration have been proven to improve the yield and reliability in modern chips. In this paper, an efficient three-phase approach for transformation-based timing analysis is proposed to transform a cyclic graph into an acyclic graph by using the node-splitting operation and compute the delay of the transformed tree-based circuit in an Elmore delay model. Compared with the timing analysis in the Spice tool, the experimental results show that our proposed three-phase approach completes the accurate timing analysis for any tested RC non-tree circuit in less CPU time under a reasonable delay error.

It is well known that the problem of constructing a timing-driven rectilinear Steiner tree for any signal net is important in performance-driven designs and has been extensively studied. Until now, many efficient approaches have been proposed for the construction of a timing-driven rectilinear Steiner tree. As technology process advances, +45° and −45° diagonal segments can be permitted in an octilinear routing model. To our knowledge, no approach is proposed to construct a timing-driven octilinear Steiner tree for any signal net. In this paper, given a rectilinear Steiner tree for any signal net, we propose an efficient transformation-based approach to construct a timing-driven octilinear Steiner tree based on the computation of the octilinear distance and the concept of Steiner-point reassignment and path reconstruction in an octilinear routing model. The experimental results show that our proposed transformation-based approach can use reasonable CPU time to construct a TOST, and a 10%--18% improvement in timing delay and a 5%--14% improvement in total wire length in the original RSTs are obtained in the construction of TOSTs for the tested signal nets.

In this paper, based on a flexible decap estimation model to predict the allocated decap of any circuit module in a given floorplan, an area-driven allocation approach is proposed to integrate the decap estimation and allocation to assign feasible decaps around or near all the circuit modules to release all the IR-drop noises in the floorplan. The experimental results show that our proposed area-driven allocation approach obtains very promising timing and area results for MCNC benchmark circuits.

In this paper, given a rectilinear Steiner tree (RST) with a source and a set of sinks, it is assumed that any sink in the RST has its timing constraint. Based on the concept of timing-consistent wire widening for any wire segment, the width of any wire segment may be replaced with its timing-consistent width without destroying the timing constraint of any sink. Furthermore, according to a given particle defect size, the widths of all the wire segments are reassigned to minimize total critical area of the RST by running a timing-constrained wire sizing process. The experimental results show that our proposed timing-constrained yield-driven wire sizing (TYWS) approach increase about 50% routing area to reduce 80%/spl sim/90% critical area for the tested routing nets.

In this paper, given a set of timing-driven routing trees for all the interconnection nets, a new multilevel timing-constrained full-chip routing (MTFR) in a dynamic hierarchical quad-grid model is proposed to complete full-chip routing in reasonable time. The experimental results show that the proposed MTFR approach uses less CPU time to obtain 100% timing-constrained routing results for all the tested benchmark circuits.

In this paper, given a set of parallel wires between a pair of adjacent P/G lines, according to the definition and computation of the inductive noise and the classification of violation wires, an O(n) optimal approach is proposed to insert shields into these parallel wires for the avoidance of inductive noise, where n is the number of a set of given parallel wires. The experimental results show that our proposed approach can use less CPU time to minimize the number of inserted shields for the avoidance of inductive noise.

In this paper, based on an equivalent circuit model for any noise-aware power network, an accurate estimation uses an exponential discharge style in the equivalent RC circuit to predict the decoupling capacitance(decap) size of any circuit module in a given floorplan. Furthermore, a floorplan-aware budgeting approach is proposed to assign feasible decaps onto all the circuit modules to release all the IR-drop noises in the floorplan. The experimental results show that our proposed budgeting approach based on an accurate estimation obtains very promising results for MCNC benchmark circuits.

It is well known that a nonManhattan channel router can use fewer routing tracks, and is never worse than a Manhattan router in a channel. To my knowledge, a three-layer bubble-sorting-based nonManhattan channel routing problem is always solved by the solution in a two-layer bubble-sorintg-based nonManhattan channel routing problem. Recently, an O ( kn 2 ) heuristic algorithm [Chaudhary et al. 1991] and an O ( kn 2 ) optimal algorithm [Chen et al. 1994] have been proposed, where k is the number of two-layer routing tracks and n is the number of terminals in a bubble-sorintg-based nonManhattan channel. In this paper we propose an optimal three-layer bubble-sorintg-based nonManhattan routing algorithm to minimize the number of three-layer routing tracks. Furthermore, the time complexity of theis optimal algorithm is proven to be in O ( hn ) time, where h is the number of three-layer routing tracks and n is the number of terminals in a bubble-sorting-based nonManhattan channel.

It is well known that a non-Manhattan channel router always uses fewer routing tracks than a Manhattan router in a channel. To our knowledge, for a bubble-sorting-based non-Manhattan channel routing (BSNMCR) problem, Chaudhary's O(kn/sup 2/) heuristic algorithm (1991) and Chen's O(k/sup 2/n) optimal algorithm (1994) have been, respectively, proposed, where it is the number of terminals and k is the number of routing tracks in a channel. However, the time complexity of the two algorithms is in O(n/sup 3/) time in the worst case. In this paper, based on optimality-oriented swap-direction selection in an optimal bubble-sorting solution, an improved optimal algorithm for a BSNMCR problem is proposed, and the time complexity of the proposed algorithm is proven to be in O(kn) time and in O(n/sup 2/) time in the worst case.

Because definition of L-shaped channels in a floorplan graph breaks all the cyclic precedence constraints in a building block layout, routing space in a layout can be fully separated and defined as straight and L-shaped channels to guarantee a safe routing ordering. However, L-shaped channel routing is more difficult than straight channel routing. Hence, it is necessary for the completion of detailed routing to minimize the number of L-shaped channels in channel definition of a floorplan graph. In this paper, based on a geometrical topology of a floorplan graph and precedence relations in a channel precedence graph, cuts in a floorplan graph are classified into S-cuts, redundant L-cuts, balanced L-cuts, nonminimal L-cuts, noncritical L-cuts and critical L-cuts. An efficient cut-based algorithm on minimizing the number of L-shaped channels in channel definition of a floorplan graph is proposed, and the time complexity of our cut-based algorithm is proved to be in O(n) time, where n is the number of line segments in a floorplan graph. Finally, several examples have been tested on Dai's algorithm [1985], Cai's algorithm [1993] and our cut-based algorithm, respectively. The experimental results show that our cut-based algorithm defines fewer L-shaped channels in a floorplan graph than Dai's algorithm and Cai's algorithm to guarantee a safe routing ordering.

Standard cell design style has been widely applied for the design automation of VLSI circuits because of the easy implementation of the layout design. Since the aim of most of standard cell design systems is to minimize the utilization of chip area, the number of feedthrough cells in a standard cell layout will be further minimized to reduce the layout site. In this paper, first, we model a row assignment problem to minimize the number of feedthrough cells in a standard cell placement. Furthermore, an integer linear programming (ILP) optimal approach is proposed to minimize the number of feedthrough cells for the row assignment in a standard cell placement. Finally, two standard cell benchmarks, Primary1 and Primary2, have been tested on the proposed ILP approach for the assignment of different number of rows, and the experimental results show that the ILP approach is efficient for the assignment of cell rows.

For a building block placement, the routing space will be fully defined into channels and switchboxes because the definition of switchboxes releases all the cycles in a channel precedence graph and further yields a safe routing ordering. However, switchbox routing is more difficult than channel routing. Due to the requirements in the routing phase, it is important for us to minimize the number of switchboxes in the definition of channels and switchboxes. In this paper, a region definition and ordering assignment (RDAOA) algorithm on minimizing the number of switchboxes is proposed. First, the routing space is modeled as a floorplan graph. According to the routing precedence in one "T" type junction, the graph is further transformed into a channel precedence graph. Hence, the problem of minimizing the number of switchboxes in region definition will correspond to the minimum feedback vertex set (MFVS) problem in the channel precedence graph. Second, based on the cyclic properties in a channel precedence graph, the MFVS problem is solved by the minimal-cycle phase and the long-cycle phase. All the minimal cycles and most of the long cycles are broken in the minimal-cycle phase, and the remaining long cycles are further broken in the long-cycle phase. As a result, fewer switchboxes are defined, and these channels and switchboxes are assigned to guarantee a safe routing ordering. The time complexity of the algorithm is proved to be in O(n) time, where n is the number of line segments in a given floorplan graph. Finally, several examples have been tested on the proposed algorithm and other published algorithms, and the experimental results show that our algorithm defines fewer switchboxes than other algorithms.

No abstract available.

Standard cell design style has been widely applied for the design automation of VLSI circuits because of the easy implementation of the layout design. Since the aim of most standard cell design systems is to minimize the utilization of chip area, the number of feedthrough cells in a standard cell layout will be further minimized to reduce the layout size. In this paper, first, we model a row assignment problem to minimize the number of feedthrough cells in a standard cell placement. Furthermore, an efficient heuristic approach is proposed to minimize the number of feedthrough cells in standard cell placement. The time complexity of the heuristic approach is further proved to be in O(|E|log|E|) time, where |E| is the number of edges in a separation graph. Finally, two standard cell benchmarks, Primary1 and Primary2, have been tested on the proposed approach for the assignment of different number of rows.

In this paper, we firstly propose a k-way connection-oriented net model, chain net model, to generalize the cut analysis for k-way circuit partitioning and to reduce the complexity of edges for the representation of a multiple-pin net between the transformation of a hypergraph and an edge-weighted graph. Furthermore, based on the techniques of fuzzy c-means clustering, we develop and propose fuzzy c-means graph clustering to obtain k groups of fuzzy memberships for the vertices in the mapped graph according to the global information of all the net connections. Finally, by the area information of any cell in the circuit netlist, these k groups of fuzzy memberships will lead to a cut-driven or balance-driven k-way circuit partitioning. As a result, k-way circuit partitioning has been implemented for testing MCNC circuit benchmarks and the experimental results show that the proposed partitioning approach generates effective results on the partitioning cut and the partitioning balance for these benchmarks.

In this paper, based on the assumptions of the geometrical topology in a floorplan graph and the precedence relations in a channel precedence graph, the cuts are further classified into S-cuts, redundant L-cuts, balanced L-cuts, non-minimal L-cuts, non-critical L-cuts and critical L-cuts. An efficient cut-based algorithm on minimizing the number of L-shaped channels is proposed. The time complexity of the algorithm is proved to be in O(n) time, where n is the number of line segments in a floorplan graph. Finally, several examples have been tested on Dai's and Cai's algorithms and the proposed algorithm. The experimental results show that the proposed algorithm defines fewer L-shaped channels than Dai's and Cai's algorithms in the definition of straight and L-shaped channels for the assignment of safe routing ordering.

In this paper, two routability crossing distribution problems based on the non-crossing relations, vertical constraint relations and geometry relations are proposed to improve routing performance of one T-type junction region. For the routability problem, a routability ordering graph can be built to decide a net ordering on the boundary in O(n/sup 2/) time. Furthermore, for the routability quota problem, if the number of crossings for the routability problem is more than the quota, the net ordering in the routability problem must be adjusted by a net interchange operation to satisfy the quota requirement in the routability quota problem in O(n) time. Since a net ordering is obtained in the routability problem or the routability quota problem, the global nets will be assigned onto the boundary in O(n) time by interleaving vacant terminals between any pair of global nets for the floating terminal assignment of the boundary.>

We present a new efficient algorithm for both two and three-layer over-the-cell channel routing in the standard cell design technology. Our approach considers both density distribution in the channel and longest path in vertical constraint graph. Besides, we use vacant terminals to eliminate cycles in the vertical constraint graph as well as to reduce the maximum cliques in the horizontal constraint graph for selecting net segments to be routed over the cells. For the PRIMARY 1 benchmark examples, our router reduced the total channel height by 39.1% and 61.0% for two-layer and three-layer routing model, respectively.>

For a building block placement, the routing space can be partitioned into channels and switchboxes. The definition of switchboxes can release the cyclic channel precedence constraints and further yield a safe routing ordering process. However, switchbox routing is always more difficult than channel routing. In this paper, an O(nlogN) region definition and ordering assignment algorithm is proposed to minimize the number of switchboxes, where N is the number of vertices in a channel precedence graph. Several examples have been tested on this algorithm, the experimental results are listed and compared.>

An efficient algorithm for over-the-cell routing in the standard cell layout design technology is presented. Two variations are discussed: one aims to minimize the channel density with fewest tracks over the cells while the other aims to minimize the final channel width. The algorithm can fit both the two-layer and three-layer routing models. With the two-layer model, there is a single routing layer over the cells for intercell connections. With the three-layer model, there are two disjoint routing layers over the cells for intercell connections. In this approach, the problem is decomposed into two phases: (1) over-the-cell routing and (2) conventional channel routing. The over-the-cell routing phase, which is executed iteratively, consists of two steps, routing over the cells and choosing net segments within the channel. For each iteration in the over-the-cell routing phase, the algorithm removes a net or a subnet which intersects the column with the highest column density and routes it over the cells according to some prioritized criteria. In comparison with the previous researches, this approach achieved the best effectiveness and has used the least CPU-time.>