摘要： 在超大规模集成电路设计中，一些特别重要的模块，像RAM、ROM和CPU等经常被优先放置，而其它模块则被两两互不重叠地放置在芯片的剩余区域。此类问题能被形式化为带有预放置模块的布局问题，关于此问题的求解方法多为随机优化方法。该文基于拟人的思想，提出了占角和最大穴度优先的放置策略，为该问题的快速求解提供了一种高效的启发式确定性算法。算法的高效性通过应用于标准电路MCNC得到了验证。

关键词: 预放置, 拟人策略, 占角动作, 穴度, 布局算法

Abstract: In very large scale integration (VSLI) design, the locations of some macro cells, such as RAM, ROM and CPU are often required to fix a priority and the other components are subject to be placed in the rest of the chip area without overlapping. These situations are formulated as the module placement with pre-placed modules. For solving the problem, the methods used are usually stochastic optimization placement algorithm. Based on the quasi-human strategy, this paper proposes the so-called corner-occupying and the largest cave degree first placement policy. An effective heuristic deterministic algorithm is presented, and the solution to this problem can be obtained quickly by applying this algorithm. Experimental results on MCNC benchmark circuits demonstrate that the algorithm is quite effective in solving the problem.

Key words: Pre-place, Quasi-human strategy, Corner-occupying action, Cave degree, Placement algorithm

中图分类号: 

• TP301