【作者】 刘涛；

【导师】 吴为民；

【作者基本信息】 清华大学 ， 计算机科学与技术， 2005， 硕士

【摘要】 纳米技术的飞速发展对超大规模集成电路(VLSI)设计技术提出了越来越大的挑战。物理设计是集成电路设计的重要组成部分,而布局是物理设计中最重要的一环。集成电路布局问题是一个非常复杂的组合优化问题,已被证明是NP-Hard问题。基于最小自由度优先原则(LFF)的布局算法是一种确定性的布局算法,它具有多项式的时间复杂度,该算法的实验结果在面积优化方面优于基于随机优化方法的布局算法。为适应技术的发展,需要对算法做出改进和扩展,本文的工作也是围绕这方面的内容展开。首先LFF算法采用了kd-tree作为基本数据结构,而且设计了对应于kd-tree结构的自由度评测方法。尽管kd-tree是一种有效的数据结构,但是具体到LFF的算法过程上,我们期望能进一步减小算法的复杂度。同时,由于LFF算法是一种确定性的布局算法,因此我们希望LFF算法的确定性步骤能够更科学和有效。因此本文着重对LFF算法的数据结构、决策方法进行改善,以期得到更好的结果。其次,对于LFF算法首先应用在了2D直角模块的布局上,但是随着新技术的发展,新的六边形电路的出现能够为布局算法带来了新的挑战。将LFF算法应用到新的六边形/三角形布局将是这篇论文的另一个方向。更多还原

【Abstract】 With the rapid development of nanometer technology, the design of VLSI meets a great deal challenge. Physical design is an important step of IC layout manufacturing and placement is one of the key technologies in VLSI physical design. VLSI placement is a quite complicated combination optimization problem, which is proved to be a NP-Hard problem.The deterministic placement algorithm based on Less Flexibility First (LFF) Principles has polynomial complexity. The results of the algorithm present the better performance on area usage than the stochastic optimization algorithm. In order to meet the requirements of the further developments, improvements and extension are definitely necessary to this algorithm. And that’s the essence of this article.First of all LFF algorithm uses the KD-Tree as the basic data structure and correspondingly designs the whole fitness evaluation based on KD-Tree. Though KD-Tree is an efficient data structure we still don’t think it’s performance is good enough for LFF flow. We plan to reduce the time complexity more. At the same time since LFF is a deterministic placement algorithm we hope the every deterministic step of LFF can be more rational and efficient. So this article focuses on improving the data structure and decisive evaluation on the purpose of the better results.Secondly the original LFF algorithm was applied to 2D rectilineal placement in the beginning. With the new development, the brand new hexagon circuit was presented by far which bring the new challenges to placement algorithm. It’s the other subject of this article to apply the improved LFF algorithm to Hexagon/Triangle placement.更多还原