Sponsored By:
ASP-DAC 2006 Archives
2C-1
| Title | A Robust Detailed Placement for Mixed-Size IC Designs |
| Author | Jason Cong, *Min Xie (University of California, Los Angeles, United States) |
| Abstract | The rapid increase in IC design complexity and wide spread use of intellectual property (IP) blocks have made the so called mixed-size placement a very important topic in recent years. Although several algorithms have been proposed for mixed-sized placements, most of them primarily focus on the global placement aspect. In this paper we propose a three-step approach, named XDP, for mixed-size detailed placement. First, a combination of constraint graph and linear programming is used to legalize macros. Then, an enhanced greedy method is used to legalize the standard cells. Finally, a sliding-window based cell swapping is applied to further reduce wirelength. The impact of individual techniques is analyzed and quantified. Experiments show that when applied to the set of global placement results gen? erated by APlace [1], XDP can produce wirelength comparable to the native detailed placement of APlace, and 3% shorter wire? length compared to Fengshui 5.0 [2]. When applied to the set of global placements generated by mPL6 [3], XDP is the only de? tailed placement that successfully produces legal placement for all the examples, while APlace and Fengshui fail for 4/9 and 1/3 of the examples. For cases where legal placements can be compared, the wirelength produced by XDP is shorter by 3% on average compared to APlace and Fengshui. Furthermore, XDP displays a higher robustness than the other tools by covering a broader spectrum of examples by different global placement tools. |
| Slides (pdf file) | 2C-1 |
2C-2
| Title | FastPlace 2.0: An Efficient Analytical Placer for Mixed-Mode Designs |
| Author | *Natarajan Viswanathan, Min Pan, Chris Chu (Iowa State University, United States) |
| Abstract | In this paper, we present FastPlace 2.0 - an extension to the efficient analytical standard-cell placer - FastPlace, to address the mixed-mode placement problem. The main contributions of our work are: (1) Extensions to the global placement framework of FastPlace to handle mixed-mode designs. (2) An efficient and optimal minimum perturbation macro legalization algorithm that is applied after global placement to resolve overlaps among the macros. (3) An efficient legalization scheme to legalize the standard cells among the placeable segments created after fixing the movable macros. On the ISPD 02 Mixed-Size placement benchmarks, our algorithm is 16.8X and 7.8X faster than state-of-the-art academic placers Capo 9.1 and Fengshui 5.0 respectively. Correspondingly, we are on average, 12% and 3% better in terms of wirelength over the respective placers. |
| Slides (pdf file) | 2C-2 |
2C-3
| Title | Timing-Driven Placement Based on Monotone Cell Ordering Constraints |
| Author | Chanseok Hwang, *Massoud Pedram (University of Southern California, United States) |
| Abstract | In this paper, we present a new timing-driven placement algorithm, which attempts to minimize zigzags and crisscrosses on the timing-critical paths of a circuit. We observed that most of the paths that cause timing problems in the circuit meander outside the minimum bounding box of the start and end nodes of the path. To limit this undesirable behavior, we impose a physical constraint on the placement problem, i.e., we assign a preferred signal direction to each critical path in the circuit. Starting from an initial placement solution, by using a move-based optimization strategy, these preferred directions force cells to move in a direction that maximizes the monotonic behavior of the timing-critical paths in the new placement solution. To make the direction assignment tractable, we implicitly group all circuit paths into a set of input-output conduits and assign a unique preferred direction to each such conduit. We integrated this idea into a recursive bipartitioning-based placement framework with a min-cut objective function. Experimental results on a set of standard placement benchmarks show that this approach improves the result of a state-of-the-art industrial placement tool for all the benchmark circuits while increasing the wire length by a tolerable amount. |
| Slides (pdf file) | 2C-3 |
2C-4
| Title | Constraint Driven I/O Planning and Placement for Chip-package Co-design |
| Author | *Jinjun Xiong (University of California at Los Angeles, United States), Yiu-Chung Wong, Egino Sarto (Rio Design Automation, United States), Lei He (University of California at Los Angeles, United States) |
| Abstract | System-on-chip and system-in-package result in increased number of I/O cells and complicated constraints for both chip designs and package designs. This renders the traditional manually tuned and chip-centered I/O designs suboptimal in terms of both turn around time and design quality. In this paper we formally introduce a set of design constraints suitable for chip-package co-design. We formulate a constraint-driven I/O planning and placement problem, and solve it by a multi-step algorithm based upon integer linear programming. Experiment results using real industry designs show that the proposed algorithm can effectively find a large scale I/O placement solution and satisfy all given design constraints in less than 10 minutes. In contrast, the state-of-the-art without considering those design constraints simply cannot meet all design constraints by relying solely upon the conventional iterative approach. |
| Slides (pdf file) | 2C-4 |
2C-5
| Title | Simultaneous Block and I/O Buffer Floorplanning for Flip-Chip Design |
| Author | *Chih-Yang Peng, Wen-Chang Chao, Yao-Wen Chang (National Taiwan University, Taiwan), J.-H. Wang (Faraday Technology Corp., Taiwan) |
| Abstract | The flip-chip package gives the highest chip density of any packaging method to support the pad-limited ASIC design. One of the most important characteristics of flip-chip designs is that the input/output buffers could be placed anywhere inside a chip. In this paper, we first introduce the floorplanning problem for the flip-chip design and formulate it as assigning the positions of input/output buffers and first-stage/last-stage blocks so that the path length between blocks and bump balls as well as the delay skew of the paths are simultaneously minimized. We then present a hierarchical method to solve the problem. We first cluster a block and its corresponding buffers to reduce the problem size. Then, we go into iterations of the alternating and interacting global optimization step and the partitioning step. The global optimization step places blocks based on simulated annealing using the B*-tree representation to minimize a given cost function. The partitioning step dissects the chip into two subregions, and the blocks are divided into two groups and are placed in respective subregions. The two steps repeat until each subregion contains at most a given number of blocks, defined by the ratio of the total block area to the chip area. At last, we refine the floorplan by perturbing blocks inside a subregion as well as in different subregions. Compared with the B*-tree based floorplanner alone, our method is more efficient and obtains significantly better results, with an average cost of only 51.8\% of that obtained by using the B*-tree alone, based on a set of real industrial flip-chip designs provided by leading companies. |
| Slides (pdf file) | 2C-5 |