一种随机并行算法及其在VLSI布图中的应用

在ＶＬＳＩ布图中，有许多可以归结为组合优化的问题，用传统方法解决这类问题时，很容易陷入局部极值．利用一种随机并行算法－Ａｌｏｐｅｘ算法，通过将ＶＬＳＩ布图中的一些问题公式化，并选择适当的退火策略和参数值来寻找一个代价函数的全局极值以得到最佳结果．通过实例进行了验证，得到了比较好的结果．

A Stochastic Parallel Algorithm and its Applications to VLSI Layout

There are some problems in VLSI layout that can be dealt with by combinatorial optimization; many among them are NP-complete problems. Using traditional algorithms. such as itcrative impproving,branch and bound, divide and conquer, we obtain too frequently only local minima. In this paper, we use a stochastic parallel algorithm to obtain optimal coveragein logic minimization which is a NP-complete problem in VLS layout. In implementing such an algorithm, careful consideration is given by the authors to the following three aspects: construction of objective functions. rule of choice of parameters, and choice of annealing schedule. We have used the algorithm to solve other VLSI layout problems,such as: circuit partition, assignment problem in gate array layout,gate sequencing in gate matrix layout and placement of blocks in building block layout. The results we obtain show that the algorithm bas low time complexity and low spare complexity with high parallelism and also that it is a good way to solve YLSI layout problems. It will be more effective if running on parallel computers.