论文部分内容阅读
随着芯片技术的不断发展,超大规模集成电路(Very Large Scale Integration,VLSI)在生产中起着越来越重要的作用。通道布线作为VLSI的一个关键环节,其性能优化和改善对提高VLSI芯片质量起着重要的影响。
本文介绍了VLSI通道布线问题与图着色问题的内在联系,提出了一种新型的基于种群竞争的遗传算法。遗传算法是模拟自然遗传学机理和生物进化理论而形成的一种全局并行地随机搜索方法,具有强鲁棒性,并具有收敛到全局最优的能力。但在实际应用中,传统遗传算法存在收敛过早,精度不够等问题;为此本文提出了基于种群竞争的改进型遗传算法,其主要思想是在初始阶段产生多个种群,在各自遗传进化过程中,同时根据设定参数进行群之间的竞争和优化,并交换优劣个体,直至求得最优解。基于种群竞争的遗传算法在解决收敛性的问题上比传统遗传算法有了较大的改进。
基于种群竞争的遗传算法具有很强的并行性,本文针对问题规模较大的情况提出了并行设计的思想,并结合并行的基本模型设计了应用于VLSI通道布线问题的并行算法。本文展示了部分实验数据和结果,并对所用算法进行了性能分析,提出了改进性能的建议。
本文所做的主要贡献有:(1)提出了基于种群竞争的遗传算法,并应用于VLSI通道布线问题,有效地改进了传统遗传算法的性能(2)对基于种群的遗传算法进行并行设计和优化(3)对实验结果进行性能分析和评估,并提出了改进建议。