In this paper, we present an agglomeratively multilevel floorplanning/placement framework based on the B -tree representation called MB- tree to handle the floorplanning and packing for large-scale building modules. The MB-tree adopts a two-stage technique, i.e., clustering followed by declustering. The clustering stage iteratively groups a set of modules based on a cost metric guided by area utilization and module connectivity and at the same time establishes the geometric relations for the newly clustered modules by constructing a corresponding B -tree for them. The declustering stage iteratively ungroups a set of the previously clustered modules (i.e., perform tree expansion) and then refines the floorplanning/placement solution by using a simulated annealing scheme. In particular, the MB-tree preserves the geometric relations among modules during declustering, which makes the MB-tree an ideal data structure for the multilevel floorplanning/placement framework. Experimental results show that the MB-tree obtains significantly better silicon area and wirelength than previous works. Further, unlike previous works, the MB-tree scales very well as the circuit size increases.

In this paper, we investigate thermal via (T-via) planning during three-dimensional (3-D) floorplanning. First, we consider the temperature constrained T-via planning (TVP) problem on a given 3-D floorplan. Second, we integrate dynamic TVP into 3-D floorplanning process. Our main contribution and results can be summarized as follows. We solve the temperature constrained TVP problem by solving a sequence of simplified interlayer and intralayer TVP subproblems. Each subproblem is formulated as convex programming problem and we derive nearly optimal solution for detailed T-via distribution. Based on the TVP solution, we implement the integrated TVP and 3-D floorplanning algorithm in a two-stage approach. Before floorplanning, blocks are assigned into different layers by solving a sequence of knapsack problems. During floorplanning, T-vias are allocated with white space redistribution to optimize T-via insertion. Experimental results show that our TVP approach can reduce T-vias by 12% compared with a recent published work (J. Cong and Y. Zhang, "Thermal via planning for 3-D ICs," in Proc. Int. Conf. Comput.-Aided Des., Nov. 2005, pp.745-752). Compared with the postfloorplanning optimization approach, integrating TVP into floorplanning process can reduce T-vias by 16% with 21% runtime overhead

Incorporating thermal vias into 3D ICs is a promising way to reduce circuit temperature by lowering down the thermal resistances between device layers. In this paper, we integrate dynamic thermal via planning into 3D floorplanning process. Our 3D floorplanning and thermal via planning approaches are implemented in a two-stage approach. Before floorplanning, the temperature-constrained vertical thermal via planning is formulated as a convex programming problem. Based on the analytical solution, blocks are assigned into different layers by solving a sequence of knapsack problems. Then a SA engine is used to generate floorplans of all these layers simultaneously. During floorplanning, thermal vias are distributed horizontally in each layer with white space redistribution to optimize thermal via insertion. Experimental results show that compared to a recent published result from [14], our method can reduce thermal vias by 15% with 38% runtime overhead.

New three-dimensional (3D) floorplanning and thermal via planning algorithms are proposed for thermal optimization in two-stacked die integration. Our contributions include (1) a two-stage design flow for 3D floorplanning, which scales down the enlarged solution space due to multidevice layer structure; (2) an efficient thermal-driven 3D floorplanning algorithm with power distribution constraints; (3) a thermal via planning algorithm considering congestion minimization. Experiments results show that our approach is nine times faster with better solution quality compared to a recent published result. In addition, the thermal via planning approach is proven to be very efficient to eliminate localized hot spots directly.

As microprocessor technology continues to scale into the nanometer regime, recent studies show that interconnect delay will be a limiting factor for performance, and multiple cycles will be necessary to communicate global signals across the chip. Thus, longer interconnects need to be pipelined, and the impact of the extra latency along wires needs to be considered during early micro-architecture design exploration. In this paper, we address this problem and make the following contributions: (1) a oor plan-driven micro-architecture evaluation methodology considering interconnect pipelining at a given target frequency by selectively optimizing architecture level critical paths. (2) use of micro-architecture performance sensitivity models to weight micro-architectural critical paths during oor planning and optimize them for higher performance. (3) a methodology to study the impact of frequency scaling on micro-architecture performance with consideration of interconnect pipelining.For a sample micro-architecture design space, we show that considering interconnect pipelining can increase the estimated performance against a no-wire-pipelining approach between 25% to 45%. We also demonstrate the value of the methodology in exploring the target frequency of the processor.

This paper presents algorithms for a constrained version of the "modern" floorplanning problem proposed by Kahng in "Classical Floorplanning Harmful?" (Kahng, 2000). Specifically, the constrained modern floorplanning problem (CMFP) is suitable when die-size is fixed, modules are permitted to have rectilinear shapes and, in addition, the approximate relative positions of the modules are known. This formulation is particularly useful in two scenarios: 1) assisting an expert floorplan architect in a semiautomated floorplan methodology and 2) in incremental floorplanning. CMFP is shown to be negative-positive hard. An algorithm based on a max-flow network formulation quickly identifies input constraints that are impossible to meet, thus permitting the floorplan architect to modify these constraints. Three algorithms [Breadth First Search (BFS), Improved BFS (IBFS), Compromise BFS (CBFS)] based on using BFS numbers to assign costs in a min-cost max-flow network formulation are presented. Experiments on standard benchmarks demonstrate that IBFS is fast and effective in practice.

We present in this paper a multilevel floorplanning/placement framework based on the B*-tree representation, called MB*-tree, to handle the floorplanning and packing for large-scale building modules. The MB*-tree adopts a two-stage technique, clustering followed by declustering. The clustering stage iteratively groups a set of modules based on a cost metric guided by area utilization and module connectivity, and at the same time establishes the geometric relations for the newly clustered modules by constructing a corresponding B*-tree for them. The declustering stage iteratively ungroups a set of the previously clustered modules (i.e., perform tree expansion) and then refines the floorplanning/placement solution by using a simulated annealing scheme. In particular, the MB*-tree preserves the geometric relations among modules during declustering, which makes the MB*-tree an ideal data structure for the multilevel floorplanning/placement framework. Experimental results show that the MB*-tree obtains significantly better silicon area and wirelength than previous works. Further, unlike previous works, MB*-tree scales very well as the circuit size increases.

This paper presents algorithms for a constrained version of the "modern" floorplanning problem proposed by Kahng in "Classical Floorplanning Harmful?" [1]. Specically, the constrained modern floorplanning problem (CMFP) is suitable when die-size is fixed, modules are permitted to have rectilinear shapes, and, in addition, the approximate relative positions of the modules are known. This formulation is particularly useful in two scenarios: (1) assisting an expert floorplan architect in a semi-automated floorplan methodology and (2) in incremental floorplanning. CMFP is shown to be NP hard. An algorithm based on a max-flow network formulation quickly identifies input constraints that are impossible to meet, thus permitting the floorplan architect to modify these constraints. Three algorithms (BFS, IBFS, CBFS) based on using BFS numbers to assign costs in a min-cost max-flow network formulation are presented. Experiments on standard benchmarks demonstrate that BFS and IBFS are fast and obtain zero whitespace floorplans.

A new approach to the interconnect-driven floorplanning problem integrates bus planning and is intended for bus-based designs where each bus consists of a large number of wires. The floorplanner optimizes the timing and ensures routability by generating the exact location and shape of interconnects above and between the circuit blocks. Experiments with Microelectronics Center of North Carolina benchmarks clearly show the advantage of integrated floorplanning over the classical floorplan-analysis-and-then-refloorplan approach. Our floorplans are routable, meet all timing constraints, and are on average 12%-13% smaller in area as compared to traditional floorplanning algorithms.

A new approach to the interconnect-driven floorplanning problem that integrates bus planning with floorplanning is presented. The integrated floorplanner is intended for bus-based designs. Each bus consists of a large number of wires. The floorplanner ensures routability by generating the exact location and shape of interconnects (above and between the circuit blocks) and optimizes the timing. Experiments with MCNC benchmarks clearly show the superiority of integrated floorplanning over the classical floorplan-analyze-and-then-re-floorplan approach. Our floorplans are routable, meet all timing constraints, and are on average 12-13% smaller in area as compared to the traditional floorplanning algorithms.

#%$& (' ) * + , . /'0* 1 2 * 34 657 8* 2 8* 9 /':; : 6 * ?6@8AB *1 1 0* %* C= 8 0 ?D':1 ? E3F * +G'H ?D'0* IJ ?6@ K'0? ?L > M 2 4 0NO ? 8 (P> Q -A : A )7R-SJ$& *F+='T'Q?U'V : > M 2 4 0N * A : AXW-S0YM$(A2!> , [Z \* :MC= 8 '0?D:6* + F M ?D'0* / ]'0 ?D':^3F+ (+] E* % Z 'K' ?D'0 :H > `_ 2 [ . 0NTC 8 ?U'0 )a* + K [ /':% > M 2 -NT * M+ 'M K' 8* * _b 8* 9C 8 ?U'0 D :c *(''-? ?6@]IJ @d Z>_ 2 IJ Ae#1 0 VIJ /)F* + 1 D 9'0?D \*9 G \@ \* K'V* D H3f' @;* ? IJ .* + ` : \* d ? g (+c K'0: * M -N4 > `_ 2 [ h 0NO [* T ^'M: IJ 9C= 8 ?D'LAi H* + F ='0 2 /) 34 E 8*T' ?D E@8 [*h [57 * IJ E D /'.* :6 ('K'0* 4 0I 8*r Q 8* AOx 0 '.y y0_b ?D 8 (Pcz/R0Y,_b [*F ? ) 3X , / / K 8* hNu { 0I W0y`+ 4* `? F* +='0 ^R-SM D > * A 1. INTRODUCTION n| * +H},qr! a* -?D -:-@H 8* :Q* + E 1 c ! #%$ [ (' )r I> E'V . /'0? / c /3F * 9 K'-? ? E ~ = % ?D'/ c'V* '0 ^ IJ h ':9 /Z * @8Af#1 '83F+ ? )73F 6* + * + /'0 0No h ~ ) fNu [* D f'V h 8* :0 ('0* / K >* T D tAih? ? * + E : [ G},qr! , +>@ /'0?4 [_ : %v6z/S>) „0wAak /34 IJ /)J3F 6* +`* & 0 X+> / a -N7* + 'i -N 8* [*f H \*('0 = 'V ( _b ? ?2 0 4Np ?D?6_b \*  : H'0Nu* [ F 6 _ * L ='V * * : ) 8* *r ?D':F L* _b : A # '8@cC= 8 '-? : 0 6* + )i ? = :% ? D D : '= G _ ? : )7+ '/IJ E 2 2 / ^ ='\*k /' Mv6z-z )Oz  )tW>)2‘>)7’>) RVw)> *a* + @` D ` 0*&*('0PJ F >* [ *& ?D'0 :E D 8* Q'>* Z *9v W/wA € ;v WVw)&ƒX+ d *M'-? A1 8* :0 ('0* C= 8 0 ?D':%'0 = “ D >*M 8* [*. ?U'0 D : Ac!> D IJ [ @d3F 6 :% I-'-? ='V_ * 9 \* K X'Q ?D [_ :[* @`: ? ='-?2 * /)1v W/w7 /'9 ?6@ 8 f > ('V* _b ~ / * ? \* , A : ATz S S-SM [* [$a *X3F ? ?7 -* 2 “ D >*Q* -?DI 9 ?D 6* +]IJ [ @c?D'V : K * ? \* 1 -A : A z/S0Y” [* [$(A,x * + 0 )ˆv WVwa 'K+ \* M:-?D ='0?o * [ * K /m8 8* D'-? ?6@^ * M:-? ='0?O >* [ * )7* + Q 2 [ Np K'0 -NO3F+ [+1 2 f 1* + , 0 ( : -NO * f* . 2 , * / tA c [Z \* :]C 8 ?D'0 :;'0? : 6* + . ?D'V* / Š'_ '-? :h3F+ [+ / r* T Z '&'F?D'0 :4 > . 2 [ r 0N C 8 ?D'0 ) * + f /':E . 2 o -N7 [* i+ 'i K' 4 >* [ * _b >* C= 8 0 ?D': *(''-? ?6@ IJ @. Z 2 IJ Ao € `* + i ='0 2 /) 34 c >*1'‰ D ? %@J * 57 * IJ c D /'G* ˆ :6 c 8* Š'Œ :-? ˆ */A•…X Nu ‰::|* + G * ) . ?6* _* '-?o * E'0 M * 9*€3X -_* ='0? [* A …X = / _ :M+8@ 2 [ :('+ _* -_b:0 ('+%* ('\Np 0 K'0* . / d* % I K* + K \* ('8*.Np 0 _ ? 6*Q D ‰'^ ?D 8 (P2A l4+ E *, / * %* (+ Um8 . ,IJ @% [57 * IJ A.! 2 M34 '0 h: IJ H' ? ‹3F 6* +1R-S ? 8 [P> f'0 = 9W-S0YŽ [* AiTNu* [ f * / * t)834 , 'K+='/IJ h'0*f \*,zVW-R-SQ * h p3F+ [+9 X* + h /'3F+ `34 F+ 'VI f * i 2 *€3X K'-? ? ='6 i -Nt ? 8 (P> [$(Aal4+ Q'H :6 * )-Np 0 F', _ ? •3F * +Œy y ? 8 [P> '0 = ŠzVRVY† * )&* + HC 8 ?U'0 D :G'0?D:-_ 6* +  D cv WVwr* 8 -PH 0 k* +='0 ^W0y.+ f* M 1 H* + , 0 D:='-? * ? \*/)& ** 8 Pc? M* + '‰R0S% > * '0Nu* [ ` [*M / * LA #1 '83F+ ? )k3X c 8*H'] %'('V* c:-?D ='0?, * [ HNu 3F 6 :^ I '0?D '0* d D * + E ='0 2 /A nG . qL'-:('0 :U'0 G ?D'0Z>_ 'V* .* (+ Dm> &* h \@ \* K'0* /'-? ?6@Q * X: ? '-? D 8* * ) * @ :,* E D ~ 4* + f K'0Z . ŽI> D -?D'0* 9'-: '\*&* + 4 * _ :k Ail4+ D q'%: IJ ‰C 8 ?U'0 LA‰l4+ H 7 'V* H 0N,qL'-:('0 :U'0 b2 b5

In floorplanning, it is common that a designer wants to have certain modules abutting with one another in the final packing. The problem of controlling the relative positions of an arbitrary number of modules in floorplan design is nontrivial. Slicing floorplan has an advantageous feature in which the topological structure of the packing can be found without knowing the module dimensions. This feature is good for handling placement constraints in general. In this paper, we make use of it to solve the abutment problem in the presence of L- and T-shaped modules. This is done by a procedure which explores the topological structure of the packing and finds the neighborhood relationship between every pair of modules in linear time. Our main contribution is a method that can handle abutment constraints in the presence of L- or T-shaped modules in such a way that the shape flexibility of the soft modules can still be fully exploited to obtain a tight packing. We tested our floorplanner with some benchmark data and the results are promising.

In floorplanning, it is important to allow users to specify placement constraints. Floorplanning with preplaced constraint was considered recently in Murata et al. (1997) and Young and Wong (1998). In this paper, we address a more general kind of placement constraint called range constraint in which a module must be placed within a given rectangular region in the floorplan. This is a more general formulation of the placement constraint problem and any preplaced constraint can be written as a range constraint. We extend the Wong-Liu algorithm (1986) to handle range constraint. Our main contribution is a novel shape curve computation which takes range constraint into consideration. Experimental results show that the extended floorplanner performs very well and, in particular, it out-performs the floorplanner proposed by Young and Wong (1998) when specialized to handle preplaced modules.

VLSI fabrication has entered the deep sub-micron era and communication between different components has significantly increased. Interconnect delay has become the dominant factor in total circuit delay. As a result, it is necessary to start interconnect planning as early as possible. We propose a method to combine interconnect planning with floorplanning. Our approach is based on the Wong-Liu (1986) floorplaning algorithm. When the positions, orientations, and shapes of the cells are decided, the pin positions and routing of the interconnects are decided as well. We use a multi-stage simulated annealing approach in which different interconnect planning methods are used in different ranges of temperature to reduce running time. A temperature adjustment scheme is designed to give smooth transitions between different stages of simulated annealing. Experimental results show that our approach performs well.

In floorplanning of very large scale integration design, it is useful if users are allowed to specify some placement constraints in the packing. One particular kind of placement constraints is to pack some modules on one of the four sides: on the left, on the right, at the bottom, or at the top of the final floorplan. These are called boundary constraints. In this paper, we enhanced a well-known slicing floorplan algorithm to handle these boundary constraints. Our main contribution is a necessary and sufficient characterization of the Polish expression, a representation of the intermediate solutions in the simulated annealing process, so that we can check these constraints efficiently and can fix the expression in case the constraints are violated. We tested our algorithm on some benchmark data and the performance is good.

Previous results show that node replication can be used to reduce the number of cut edges substantially in a partitioned circuit. The node replication approach is particularly useful for fully utilizing pin-limited devices such as multiple field-programmable gate array. Hwang and El Gamal [1992, 1995] formulated the min-cut replication problem, which is to determine min-cut replication sets for the components of a k-way partition such that the cut size of the partition is minimized after the replication. They gave an optimal algorithm for finding min-cut replication sets for a k-way partitioned digraph. However their optimal min-cut replication algorithm does not guarantee min-cut replication sets of minimum sizes. Furthermore, their algorithm is not optimal for hypergraphs. In this paper, we optimally solve the min-area min-cut replication problem on digraphs, which is to find min-cut replication sets with the minimum sizes. More important, we give an optimal solution to the hypergraph min-area min-cut replication problem using a much smaller flow network model. We implemented our algorithms in a package called Hyper-MAMC, and interfaced Hyper-MAMC to the TAPIR package. We compared the replication results by Hyper-MAMC with those obtained by MC-Rep in the TAPIR package on the exact same initial partitions of a set of MCNC Partition93 benchmark circuits. On average, Hyper-MAMC produces 57.3% fewer cut nets and runs much faster than MC-Rep.

We consider the problem of circuit partitioning for multiple-chip implementations. One motivation for studying this problem is the current need for good partitioning tools for implementing a circuit on multiple field programmable gate array (FPGA) chips. We allow duplication of logic gates as it could be used to reduce circuit delay. Circuit partitioning with duplication of logic gates is also called circuit clustering. In this paper, we present a circuit clustering algorithm that minimizes circuit delay subject to both area and pin constraints on each chip, using the general delay model. We develop a repeated network cut technique for finding a cluster that is bounded by both area and pin constraints. Our algorithm achieves optimal delay under either the area constraint only or the pin constraint only. Under both area and pin constraints, our algorithm achieves optimal delay in most cases. We outline the condition under which the nonoptimality occurs, and we show that the condition rarely occurs in practice. We tested our algorithm on a set of benchmark circuits, and consistently obtained optimal or near-optimal delays.

A planar monotone circuit (PMC) is a Boolean circuit that can be embedded in the plane and that contains only AND and OR gates. Goldschlager, Dymond, Cook, and others have developed $NC^2 $ algorithms to evaluate a special layered form of a PMC. These algorithms require a large number of processors $\Omega (n^6 )$, where n is the size of the input circuit). Yang and, more recently, Delcher and Kosaraju have given NC algorithms for the general planar monotone circuit value problem. These algorithms use at least as many processors as the algorithms for the layered case. This paper gives an efficient parallel algorithm that evaluates a general PMC of size n in polylog time using only a linear number of processors on an exclusive read exclusive write parameter random-access machine (BREW PRAM). This parallel algorithm is the best possible to within a polylog factor and is a substantial improvement over the earlier algorithms for the problem. The algorithm uses several novel techniques to perform the evaluation, including the use of the dual of the plane embedding of the circuit to determine the propagation of values within the circuit.

We consider the problem of bipartitioning a circuit into two balanced components that minimizes the number of crossing nets. Previously, Kernighan and Lin type (K&L) heuristics, simulated annealing approach, and analytical methods were given to solve the problem. However, network flow (max-flow min-cut) techniques were overlooked as viable heuristics to min-cut balanced bipartition due to their high complexity. In this paper we propose a balanced bipartition heuristic based on repeated max-flow min-cut techniques, and give an efficient implementation that has the same asymptotic time complexity as that of one max-flow computation. We implemented our heuristic algorithm in a package called FBB. The experimental results demonstrate that FBB outperforms K&L heuristics and analytical methods in terms of the number of crossing nets, and our efficient implementation makes it possible to partition large circuit netlists with reasonable runtime. For example, the average elapsed time for bipartitioning a circuit S35932 of almost 20 K gates is less than 20 min on a SPARC10 with 32 MB memory.

Hwang and El Gamal (1992, 1995) formulated the min-cut replication problem, which is to determine min-cut replication sets for the components of a k-way partition such that the cut size of the partition is minimized after the replication. They gave an optimal algorithm for finding min-cut replication sets for a k-way partitioned digraph. However, their optimal min-cut replication algorithm does not guarantee min-cut replication sets of minimum sizes. Furthermore, their algorithm is not optimal for hypergraphs. In this paper, we optimally solve the min-area min-cut replication problem on digraphs, which is to find min-cut replication sets with the minimum sizes. More importantly, we give an optimal solution to the hypergraph min-area min-cut replication problem using a much smaller flow network model. We implemented our algorithms in a package called Hyper-MAMC, and interfaced Hyper-MAMC to the TAPIR package. On average, Hyper-MAMC produces 57.3% fewer cut nets and runs much faster than MO-Rep in the TAPIR package, on the same initial partitions of a set of MCNC Partition93 benchmark circuits.