4种VLSI标准单元初始布局生成算法及其比较

Four kinds of VLSI standard cell initial placement algorithm and their comparison

由于超大规模集成电路(VLSI)标准单元布局问题的高度复杂性,选择适当的初始布局生成算法成为能否在合理的运行时间内获得高质量布局结果的关键因素之一.首先介绍了VLSI标准单元布局问题和优化目标的数学模型.在此数学模型的基础上,给出了4种标准单元初始布局生成算法基本思想及其详细的步骤.对这4种初始布局算法在标准测试例子上的实验结果进行比较,分析它们作为启发式算法初始种群的有效性.

Due to the complexity of very large scale integrated-circuit（VLSI） standard cell placement problem,one of the key factors is the initial placement algorithm which affects the final placement results and running time.We first introduce the mathematical model of VLSI standard cell placement problem and its optimization objective.Based on the mathematical model,we develop four kinds of VLSI standard cell initial placement algorithm in detail,respectively.According to the experimental results generated by the four different algorithms on standard cell benchmarks,we conclude whether each initial placement algorithm can be used in heuristic algorithm for VLSI standard cell placement effectively or not.