一种基于多级GRASP的VLSI电路划分方法

摘要

本发明提供一种基于多级贪心随机自适应过程(GRASP)的超大规模集成电路(VLSI)电路划分方法，属于VLSI设计自动化技术领域。该方法主要结合GRASP可以快速产生较好初始解的优势，对目前主流的多级划分方法进行了改进。技术方案要点如下：(1)在粗化阶段，设计了一种桶排序方法对顶点间的连接权重进行快速排序，在此基础上，用GRASP的思想构造初始匹配,并用短交替增广路(圈)局部改进匹配结果；(2)在初始划分阶段，并用GRASP的思想构造质量较好的初始划分集合；(3)在细化阶段，结合多样性机制不断减小划分集合规模。该方法可以提供高质量的划分结果，可适应目前VLSI的版图设计自动化的需求。

主权项

一种基于多级GRASP的VLSI电路划分方法，其特征在于包括如下步骤：(1)把电路表示为超图H0={V0,E0}；(2)计算当前超图Hi中所有顶点对的连接权重；(3)采用桶排序方法对顶点间的连接权重进行快速排序；在此基础上，用GRASP的思想构造初始匹配；(4)分别用长度为2,3的交替增广路和长度为4的交替增广圈局部改进步骤(3)的匹配结果；(5)根据匹配的结果，开始构造下一级超图Hi+1；(6)重复步骤(2)‑(5),直到超图的规模足够小；(7)用GRASP的思想对Hi进行初始划分，得到Hi的划分集合POPi;(8)采用多样性机制，更新POPi；(9)对POPi进行映射，得到的Hi‑1的初始划分集合POPi‑1;(10)用FM方法优化POPi‑1;(11)重复步骤(8)‑(10)，直到已经细化到原图H0；(12)对H0的划分进行V‑cycle改进,得到最后划分结果。