全局布局优化的一种增广拉格朗日方法.docVIP

全局布局优化的一种增广拉格朗日方法 摘要：如果忽略单元重叠，全局布局要计算出单元的最佳位置以最优化特定度量标准 (如, 线 长, 密度溢出)。全局布局影响到一个电路芯片的可布线性, 性能, 能耗等，是大规模集成电路物 理设计的一个关键环节。本文提出了一种增广拉格朗日方法来优化集成电路全局布局问题。该 方法采用了动态的密度惩罚因子放大策略来平衡线长与单元密度。将此方法与 NTUplace3 的 全局布局框架结合，并在 IBM 的混合单元测试例子进行试验。结果表明该方法能在合理时间 内得到质量更好的布局。 关键词：非线性优化；大规模集成电路；全局布局；增广拉格朗日方法 中图分类号： TN47; TP301.6 An Augmented Lagrangian Method for VLSI Global Placement Optimization Li Wei-Guo1, Chen Jian-Li2, Zhu Wen-Xing1,2 1 Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fuzhou 350002 2 College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108 Abstract: Ignoring some cell overlaps, global placement computes the best position for each cell to minimize some cost metric (e.g., total wirelength, density over?ow). It is a crucial step in very large scale integration(VLSI) physical design, since it a?ects routability, performance, and power consumption of a circuit. In this paper, we propose an Augmented Lagrangian method to solve the VLSI global placement. In this method, a cautious dynamic density weight increasing strategy is used to balance the wirelength and density constraint. We incorporated our method into NTUplace3’s global placement framework, and tested it on the IBM mixed-size benchmark circuits. Experimental results show that it obtains high-quality results in a reasonable running time. Key words: nonlinear optimization; VLSI; global placement; augmented lagrangian method -1- 0 Introduction The VLSI placement problem involves placing a set of cells into a ?xed die for a given netlist, such that there are no overlaps among objects and some cost metric (e.g., wirelength, density over?ow) is optimized [1]. Since the problem is NP-complete [2, 3], and designs with millions of cells are now common, it is a challenge to design e?cient algorithms for producing high quality placement solutions [4]. Since circuit performance heavily depends on placement results, the placement problem has attracted much att