符号化矩在网状互连线电路线宽优化中的应用研究

摘要

随着芯片的尺寸越来越小，互连线延迟已经超越门延迟成为芯片延迟的主要部分。互连线已成为现在集成电路设计中主要的关注对象，在过去的几十年里，有大量的对互连线的研究，包括互连线的建模，分析，优化，制造等。随着电路复杂度的增加，更多的时候我们需要把互连线建模成网状结构。由于网状电路结构的复杂性，传统的对树状互连线电路的分析，优化方法对网状电路不再适用，因而需要寻求新的途径来处理网状电路。本文首先介绍了最近提出的符号化矩的计算方法，它用一种全新的数据结构，利用了二叉决策图的共享特性，表示了矩的计算过程。这种方法可以快速求解出网状电路的矩及其导数。接着我提出了基于符号化矩的线宽优化算法，该算法充分利用了符号化矩的优势，能非常有效的处理大规模网状电路。同时本文还实现了另一种基于对电路进行拆分的网状电路线宽优化算法，该算法把网状电路拆分成树状电路，再对拆分后的电路进行优化。通过对这两种算法的比较，我们发现基于符号化矩的优化算法在对电路性能参数的优化结果上要远远超过基于拆分的优化算法。

目录

摘要

ABSTRACT

第一章 绪论

1.1 互连线线宽优化背景, 发展

1.2 网状电路互连线线宽优化问题描述

1.2.1 线宽优化中的互连线模型

1.2.2 线宽优化问题定义

1.3 符号化分析方法

1.4 本文的主要内容及小结

第二章 符号化矩及其导数计算原理

2.1 电路的矩的定义及其数值求法

2.1.1 电路矩的定义

2.1.2 电路矩的数值迭代求法

2.2 树状电路符号化矩及其导数计算方法

2.2.1 矩决策图

2.2.2 矩决策图的构造方法

2.2.3 利用矩决策图求解k 阶矩

2.2.4 矩的符号化导数求解方法

2.3 网状电路符号化矩的计算方法

2.4 本章小结

第三章 网状电路线宽优化算法

3.1 基于拆分的网状电路线宽优化算法

3.1.1 拆分规则

3.1.2 网状电路的拆分算法

3.1.3 网状电路线宽优化

3.2 基于符号化矩的线宽优化算法

3.3 本章小结

第四章 实验结果与分析

4.1 电路节点延迟优化结果

4.2 网状电路基本参数优化结果

4.3 本章小结

第五章 总结与展望

参考文献

致谢

攻读硕士学位期间已发表或录用的论文