标准单元模式下的一种快速增量式布局算法

增量式布局是适应高性能设计要求的一种新的布局模式 .它针对电路更改 ,局部地调整单元位置 ,重新获得合理的布局 .本文提出了一种标准单元模式下的快速增量布局算法 .算法采用单元行划分的方法处理布局约束 ,然后将布局调整归结为单元依次插入单元行的问题 ,并构造了一个数学规划求解最佳的插入方案 .同时提出了复杂度为O(n)的双对角线搜索法求解这个特殊的数学规划 .实际电路测试表明算法高效而稳定 ,比简单的启发式算法快十倍 ,并使布局修改减少 2 0 %以上

A Fast Incremental Placement Algorithm for Standard-Cells

Incremental placement or ECO placement is a new field in VLSI layout to meet the demand of high performance design.It detects illegal cell positions and moves cells locally to find a feasible placement solution.This paper proposes an incremental placement algorithm for standard-cell design mode.It adopts row partitioning to cope with various placement constraints,and then inserts trouble cells one by one.An integer programming (IP) problem is constructed and solved to get the best solution of cell insertion.A dual diagonal searching (DDS) method is proposed to solve this special IP problem.We prove that DDS can always be the best solution and its time complexity is O(n).Experiments on a group of industrial test cases show that our algorithm is efficient and robust.It runs 10 times faster than a simple heuristic method and reduces more than 20 percent placement modification in average.