In this article we propose an effective algorithm flow to handle modern large-scale mixed-size placement, both with and without geometry constraints. The basic idea is to use floorplanning to guide the placement of objects at the global level. The flow consists of four steps: (1) The objects in the original netlist are clustered into blocks; (2) floorplanning is performed on the blocks; (3) the blocks are shifted within the chip region to further optimize the wirelength; (4) with large macro-locations fixed, incremental placement is applied to place the remaining objects. There are several advantages to handling placement at the global level with a floorplanning technique. First, the problem size can be significantly reduced. Second, exact Half-Perimeter WireLength (HPWL) can be minimized. Third, better object distribution can be achieved so that legalization only needs to handle minor overlaps among small objects in a block. Fourth, macro-rotation and various geometry constraints can be handled. To demonstrate the effectiveness of this new flow, we implement a high-quality and efficient floorplan-guided placer called FLOP . We also construct the Modern Mixed-Size (MMS) placement benchmarks that can effectively represent the complexities of modern mixed-size designs and the challenges faced by modern mixed-size placers. Compared with most state-of-the-art mixed-size placers and leading macroplacers, experimental results show that FLOP achieves the best HPWL and easily obtains legal solutions on all circuits with all geometry constraints satisfied.

This paper presents an efficient, scalable, and optimal slack-driven shaping algorithm for soft blocks in nonslicing floorplan. The proposed algorithm is called SDS. SDS is specifically formulated for fixed-outline floorplanning. Given a fixed upper bound on the layout width, SDS minimizes the layout height by only shaping the soft blocks in the design. Iteratively, SDS shapes some soft blocks to minimize the layout height with the guarantee that the layout width would not exceed the given upper bound. Rather than using some simple heuristic as in previous work, the amount of change on each block is determined by systematically distributing the global total amount of available slack to individual block. During the whole shaping process, the layout height monotonically reduces and eventually converges to an optimal solution. Two optimality conditions are presented to check the optimality of a shaping solution for fixed-outline floorplanning. In practice, to terminate the process of convergence early, we propose two different stopping criteria. We also extend SDS to handle other floorplanning problems, e.g., classical floorplanning. To validate the efficiency and effectiveness of SDS, comprehensive experiments are conducted on MCNC and HB benchmarks. Compared with previous work, SDS achieves the best experimental result with a significantly faster runtime.

This paper presents an efficient, scalable and optimal slack-driven shaping algorithm for soft blocks in non-slicing floorplan. The proposed algorithm is called SDS. Different from all previous approaches, SDS is specifically formulated for fixed-outline floorplanning. Given a fixed upper bound on the layout width, SDS minimizes the layout height by only shaping the soft blocks in the design. Iteratively, SDS shapes some soft blocks to minimize the layout height, with the guarantee that the layout width would not exceed the given upper bound. Rather than using some simple heuristic as in previous work, the amount of change on each block is determined by systematically distributing the global total amount of available slack to individual block. During the whole shaping process, the layout height is monotonically reducing, and eventually converges to an optimal solution. We also propose two optimality conditions to check the optimality of a shaping solution. To validate the efficiency and effectiveness of SDS, comprehensive experiments are conducted on MCNC and HB benchmarks. Compared with previous work, SDS is able to achieve the best experimental result with significantly faster runtime.

This paper presents a completely new approach to the problem of hypergraph clustering for wirelength-driven placement. The novel algorithm we propose is called SafeChoice (SC). Different from all previous approaches, SC is proposed based on a fundamental theorem, safe condition which guarantees that clustering would not degrade the placement wirelength. To mathematically derive such a theorem, we first introduce the concept of safe clustering, i.e., do clustering without degrading the placement quality. To efficiently check the safe condition for pair-wise clustering, we propose a technique called selective enumeration. SafeChoice maintains a global priority queue based on the safeness and area of potential clusters. Using a simple heuristic, it automatically stops clustering when generating more clusters would degrade the placement wirelength. Moreover, we extend SafeChoice to do clustering while considering the object physical locations, i.e., physical clustering. Finally, we apply SafeChoice into a two-phase placement framework and propose a high-quality analytical placement algorithm called SCPlace. Comprehensive experimental results show that the clusters produced by SC consistently help the placer to achieve the best wirelength among all other clustering algorithms, and SCPlace generates the best half-perimeter wirelength compared with all other state-of-the-art placers.

This paper presents SafeChoice (SC), a novel clustering algorithm for wirelength-driven placement. Unlike all previous approaches, SC is proposed based on a fundamental theorem, safe condition which guarantees that clustering would not degrade the placement wirelength. To derive such a theorem, we first introduce the concept of safe clustering, i.e., do clustering without degrading the placement quality. To check the safe condition for pair-wise clustering, we propose selective enumeration technique. SC maintains a global priority queue (PQ) based on the safeness and area of potential clusters. Iteratively the cluster at the top of the PQ is formed. SC automatically stops clustering when generating more clusters would degrade the placement wirelength. To achieve other clustering objectives, e.g., any target clustering ratio, SC is able to perform under three different modes. Comprehensive experimental results show that the clusters produced by SC consistently help the placer to achieve the best wirelength among all other clustering algorithms.

In this paper, we present DeFer-a fast, high-quality, scalable, and nonstochastic fixed-outline floorplanning algorithm.DeFergenerates a nonslicing floorplan by compacting a slicing floorplan. To find a good slicing floorplan, instead of searching through numerous slicing trees by simulated annealing as in traditional approaches, DeFer considers only one single slicing tree. However, we generalize the notion of slicing tree based on the principle of deferred decision making (DDM). When two subfloorplans are combined at each node of the generalized slicing tree,DeFer does not specify their orientations, the left-right/top-bottom order between them, and the slice line direction. DeFer even does not specify the slicing tree structure for small subfloorplan. In other words, we are deferring the decisions on these factors, which are specified arbitrarily at an early step in traditional approaches. Because of DDM, one slicing tree actually corresponds to a large number of slicing floorplan solutions, all of which are efficiently maintained in one single shape curve. With the final shape curve, it is straightforward to choose a good floorplan fitting into the fixed outline. Several techniques are also proposed to further optimize the wirelength. For both fixed-outline and classical floorplanning problems, experimental results show that DeFer achieves thebestsuccess rate, the best wirelength, the best runtime, and the best area on average compared with all other state-of-the-art floorplanners.

In this paper, we propose an effective algorithm flow to handle large-scale mixed-size placement. The basic idea is to use floorplanning to guide the placement of objects at the global level. The flow consists of four steps: 1) The objects in the original netlist are clustered into blocks; 2) Floorplanning is performed on the blocks; 3) The blocks are shifted within the chip region to further optimize the wirelength; 4) With big macro locations fixed, incremental placement is applied to place the remaining objects. There are several advantages of handling placement at the global level with a floorplanning technique. First, the problem size can be significantly reduced. Second, exact HPWL can be minimized. Third, precise object distribution can be achieved so that legalization only needs to handle minor overlaps among small objects in a block. Fourth, rotation and various placement constraints on macros can be handled. To demonstrate the effectiveness of this new flow, we implement a high-quality floorplan-guided placer called FLOP. We also construct the Modern Mixed-Size (MMS) placement benchmarks which can effectively represent the complexities of modern mixed-size designs and the challenges faced by modern mixed-size placers. Compared with state-of-the-art mixed-size placers and leading macro placers, experimental results show that FLOP achieves the best wirelength, and easily obtains legal solutions on all circuits.

In this paper, we present DeFer - a fast, high-quality and non-stochastic fixed-outline floorplanning algorithm. DeFer generates a non-slicing floorplan by compacting a slicing floorplan. To find a good slicing floorplan, instead of searching through numerous slicing trees by simulated annealing as in traditional approaches, DeFer considers only one single slicing tree. However, we generalize the notion of slicing tree based on the principle of deferred decision making (DDM). When two subfloorplans are combined at each node of the generalized slicing tree, DeFer does not specify their orientations, the left-right/top-bottom order between them, and the slice line direction. DeFer even does not specify the slicing tree structures for small subfloorplans. In other words, we are deferring the decisions on these factors, which are specified arbitrarily at an early step in traditional approaches. Because of DDM, one slicing tree actually corresponds to a huge number of slicing floorplan solutions, all of which are efficiently kept in one single shape curve. With the final shape curve, it is straightforward to choose a good floorplan fitting into the fixed outline. Several techniques are also proposed to further optimize the wirelength. Experimental results on benchmarks with only hard blocks and with both hard and soft blocks show that DeFer achieves the best success rate, the best wirelength and the best runtime on average compared with other state-of-the-art floorplanners.