基于MOGA/SOS的互连缓冲及线型优化算法

Buffer and wiresizing optimization based on MOGA/SOS

将互连延时、信号响应波形、布线面积作为互连优化的3个目标函数,把推导出的串扰下边界作为优化参量的限制条件,采用分布式RLC模型作为互连系统的近似解析模型,提出了一种基于单目标排序非支配集构造算法的多目标遗传算法,用于解决互连优化中的缓冲及线型优化问题.算法所得解为满足串扰限制条件且对信号延时、信号波形以及布线面积进行优化的折中解.测试结果表明所提算法对互连优化问题规模的适应性强,所得解的优化结果明显优于基于Elmore模型的优化结果,布线面积减少了30%,信号延时与串扰性能分别提高了25%和25.73%.

We present a new multi-objective genetic algorithm（MOGA） which uses a single objective sorting（SOS） method for constructing the non-dominated set to solve the multi-objective interconnect buffer and wiresizing optimization problem under a distributed RLC model. The optimal objective includes the interconnect delay, signal waveform and routing area. We use a new method to calculate the lower bound of crosstalk, and use it as a constraint. The MOGA/SOS optimal algorithm provides a smooth trade-off among signal delay, wave form, and routing area. Extensive experimental results show that our algorithm is scalable with the problem size. Furthermore, compared to the solution based on an Elmore delay model, our solution reduces the total routing area by up to 30%, and the delay to the critical sinks by up to 25%. At the same time it improves crosstalk up to 25.73% on average.