集成电路互连时序优化算法研究-微电子学与固体电子学专业毕业论文.docx

ClassifiedIndex:::LiuXingchunSupervisor::MasterofEngineeringSpeciality:Microelectronics and Solid StateElectronicsAffiliation:SchoolofInformationandElectricalEngineeringDateofDefence:July,2012Degree-Conferring-Institution:HarbinInstituteofTechnology摘 要随着集成电路工艺的发展,互连线延时增大,而门延时逐渐减小,有研究表明,当工艺特征尺寸减小到180纳米以下时,互连线延时甚至可以占整个系统延时的50%以上,因此,互连线延时优化在大规模集成电路设计中变得至关重要。在互连线延时优化中,论文通过缓冲器插入及尺寸调整和互连线线宽调整两个方面来优化互连线的延时。首先研究已有的缓冲器插入及尺寸调整算法和互连线线宽调整算法,分析它们的时间复杂度和运算速度的瓶颈,然后改进已有算法。针对缓冲器插入及尺寸调整和互连线线宽调整两种优化方法,分别提出了相应的改进算法。论文基于VanGinneken算法提出了一种新的缓冲器插入及尺寸调整算法。VanGinneken算法是一种非常典型的缓冲器插入及尺寸调整优化算法并且它的时间复杂度为O(b2n²),b为缓冲器的种类数,n为候选缓冲器插入点个数。新算法中提出了一种快速冗余判别方法,并且使用红黑树结构保存候选解,从而可以利用红黑树操作时间复杂度为O(log2n)的优势。经过改进,新算法的时间复杂度降至理论上为O(b2n(log2n)2)。利用标准测试电路ISCAS89对算法进行测试,测试结果表明,新算法相对于VanGinneken算法的运算速度优势随着电路规模的变大而变大,同时随着候选缓冲器种类数的增加而增大,当仅有1种缓冲器可选时,%,而如果有8种和20种缓冲器可选,%%。本文提出的线宽调整算法是在有效集合算法的基础上提出的一种新算法,有效集合算法是解决二次规划问题非常有效的方法,而线宽调整问题实际上就是凸二次规划问题。新算法利用线宽调整问题中系数矩阵是对称可分解矩阵的特点,实现逆矩阵的快速求解;并且本问题中的不等式约束条件非常特殊,如果某一个约束条件是有效的,那么其对应的变量等于零,所以可以直接删除这个变量,从而减少变量数。通过使用上述两个技巧使得新算法的时间复杂度最坏情况下可从O(n4)降为O(n3),最好情况下从O(n3)降为O(n2)。根据标准测试电路ISCAS89布局布线后线长的分布情况和已有的研究成果,选择一组典型线长对算法性能进行测试。测试结果表明随着互连线长度增加,新算法的运行时间减小,新算法相对于有效集合算法的运算速度优势减小,并且互连线超过一定长度后,新算法的运算速度优势不再改变;对于固定长度的互连线,新算法相对于有效集合算法的运算速度优势随着候选线宽个数的增加而增大。关键词:时序优化;缓冲器插入及尺寸调整;线宽调整;红黑树;凸二次规划;对称可分解矩阵AbstractWiththedevelopmentofintegratedcircuittechnology,%,,studytheexistingbufferinsertion/sizingalgorithmsandwiresizingalgorithms,putingspeed,thenproposetwonewalgorithmsthro