Abstract: Multilevel-based VLSI partitioner is proposed and implemented，named MVP.The MVP’s framework，flow，composition modules as well as their functions are described.The multilevel partitioner of MVP achieves the better partitioning of weighted undirected graph by introducing the graph core during the coarsening phase，the spectral graph theory during the initial partitioning phase and swarm intelligence during the refinement phase.The characteristic of MVP is the conversion from netlist to weighted undirected graph and its objective is to improve the efficiency of VLSI partitioner by avoiding partitioning netlist directly.The experiment and analysis show that the multilevel partitioner of MVP can find the better partitioning and MVP can improve the performance of VLSI partitioner.

Key words: multilevel method, Very-Large-Scale Integration（VLSI）, partitioning, Electronic Design Automation（EDA）, weighted undirected graph

摘要： 基于多水平方法，设计并实现了一种VLSI剖分系统（Multilevel-based VLSI Partitioner，MVP）。介绍了MVP系统的结构框图、处理流程及模块功能。MVP系统的多水平剖分程序引入图核到粗化阶段，谱图论到初始剖分阶段，群智能到投影优化阶段，得到了无向赋权图更优的剖分。MVP系统特点体现在VLSI线网到无向赋权图的转换，避免了剖分算法直接在VLSI线网上进行剖分，提高了VLSI剖分的效率。实验及分析表明MVP系统的多水平剖分程序能找到更优的图剖分，以及MVP系统找到比现有技术更优的VLSI剖分，提高了VLSI剖分的性能。

关键词: 多水平方法, 超大规模集成电路, 剖分, 电子设计自动化, 无向赋权图