赋权超图划分算法在电路实验中的对比研究：效率与可行性

本文主要探讨了赋权超图在电路划分领域的应用及其优化算法的研究。电路划分在计算机工程与应用中扮演着关键角色，特别是在VLSI设计过程中，如设计封装、综合、设计优化、FPGA划分以及模拟和测试等方面，通过将逻辑门或标准单元划分为子集，可以降低复杂性并提升性能。Lengauer和Alpert-Kahng的工作奠定了基于图论和组合理论的电路划分数学模型的基础，他们分别使用了带权值的无向图、交点图和有向图作为描述工具。 孙凌宇等人针对电路划分提出了赋权超图划分算法，这是一种扩展了传统图模型的方法，通过赋予节点和边权重来更好地反映电路的实际特性和优化需求。文章的核心内容聚焦于两种主要的划分策略：迁移方法和多水平方法。迁移方法在粗化阶段涉及不同的结点匹配策略，而迁移优化阶段则探讨了不同的结点迁移优化策略，旨在提高划分的质量和效率。 实验部分以ISPD98电路测试基准为例，共进行了18组对比实验。首先，作者对比了迁移方法和多水平方法的效果，结果显示多水平方法在处理这类问题时展现出更好的可行性和效率。其次，作者还深入研究了五种结点匹配策略和三种结点迁移优化策略的组合对划分性能的影响，这有助于设计者根据具体应用选择最优化的算法配置。 通过对大量实验数据的分析和验证，本文强调了赋权超图划分算法在电路划分中的实用价值，并为实际VLSI设计提供了一种有效的优化工具。本文的贡献在于不仅理论阐述了赋权超图模型，而且通过实证研究证明了其在实际问题解决中的优越性，对于从事计算机工程设计和优化的工程师来说，具有重要的参考价值。