论文部分内容阅读
布图规划是VLSI布图设计中的关键环节,通常采用随机优化算法,而布图结构的编码表示（或称布图表示）是基于随机优化方法的布局算法的关键.提出一种新的布图表示-角模块序列（CBL）,并从理论上证明它具有O（n）的布局评估算法计算复杂性和较小的解空间.在布图设计中,部分模块的位置需要满足一定的约束条件,边界约束就是其中常见的一种.通过边界约束可以将特定模块的位置限制在指定的边界上,从而有利于模块与I/O端口的互连.基于角模块表示,推导出满足边界约束布局的充分必要条件,并结合模拟退火过程,通过修正中间解使受约束模块满足约束条件,从而实现了基于CBL模型的边界约束布图规划算法.将代价函数惩罚方法和启发式方法相结合,设计了边界约束的惩罚项,能够合理准确地衡量约束满足的情况,从而有效地控制模拟退火的进度,以保证最终布局满足所有约束.对MCNC的标准例子的测试结果表明算法是十分有效的.
Layout planning is the key link in VLSI layout design, usually using stochastic optimization algorithm, and the coding representation of layout structure is the key of layout algorithm based on stochastic optimization method.A new cloth The diagram shows the angular module sequence (CBL), and theoretically proves that it has the computational complexity and the smaller solution space of O (n) layout evaluation algorithm. In the layout design, the position of some modules needs to satisfy some constraints Boundary constraint is one of the most common types of constraints.Based on the boundary constraint, the position of a specific module can be limited to the specified boundary, which is conducive to the interconnection between the module and the I / O port.According to the angle module representation, The necessary and sufficient conditions of the layout, and combined with simulated annealing process, the constrained module is modified by solving the intermediate solution to satisfy the constraint conditions, thus the CBL model-based boundary constrained layout planning algorithm is realized.Combining the cost function penalty method and the heuristic method, The penalty item of the boundary constraint is designed to measure the constraint satisfaction rationally and accurately so that the progress of simulated annealing can be controlled effectively to ensure the final cloth Satisfies all the constraints. The test results for the standard example of the MCNC show that the algorithm is very effective.