作为第三次产业革命的一块重要基石,在过去的半个多世纪中,集成电路工业飞速发展。集成电路芯片集成度按照摩尔定律的预测不断提高,工艺节点持续下降,并且由于研究人员的不断努力,进入新世纪后这一趋势仍然得以保持。但是,由于电路特征尺寸已经越来越接近物理极限,这一前进脚步已经变得缓慢,其中一项重要标志就是光刻胶的边缘解析度在45纳米工艺节点下开始变得模糊不清。为了突破集成电路生产过程中光刻阶段的这一瓶颈,相应地出现了以超紫外线曝光光源、高折射率液体浸润式光刻和双重图案光刻技术为代表的制造工艺改进,以及为双重图案光刻服务的双重图案划分这一设计方法学革新。随着集成电路设计方法学逐步转入以可制造性设计为中心的第三代设计方法,如何更好地进行双重图案划分,开始得到学术界越来越多的重视。在双重图案光刻过程中,同一版图上的版图图案被分为两组依次进行曝光,使得原本临近的图案处于不同掩膜版上,以达到减小掩膜版相邻窗口间光照干涉效应的最小化,进而提高光刻阶段曝光图案密度的目的。而双重图案划分方法需要解决的问题是如何通过版图图案的切割和掩膜版分配,使得结果中无解双重图案冲突数目和由版图图案切割引入的缝合点数量最少。现有的双重图案划分工作通常着眼于即将投入生产的已经确定的集成电路版图,通过利用贪婪算法、奇数环消去法、最大割方法或其他优化方法对单层版图进行双重图案划分。虽然这些用于解决双重图案划分问题的方法都是启发式算法,双重图案划分问题的理论复杂度也普遍被认为是NP完全问题,但其NP完全性至今仍然没有得到证明。另外,对于现代集成电路中的多层金属互连线工艺,布线后层分配这一重要阶段可以决定各层版图图案,进而对于双重图案划分具有巨大影响,在以往的双重图案划分方法中尚未能得到重视。如果将其用于双重图案划分问题的优化,有可能得到良好的划分结果。在本文中通过在多层互连线版图中利用布线后层分配来帮助双重图案划分的优化,第一次提出了多层版图双重图案层分配问题的定义。该问题以及原有的单层版图双重图案划分问题也第一次被证明是NP完全性问题。针对多层版图双重图案层分配问题,我们提出了一套能够有效求解的启发式算法。该算法共包含三个主要阶段,分别为最小化双重图案危险的多层版图层分配、分层进行的单层版图双重图案划分以及通孔最小化层分配。另外,由于盲目的布线后层分配有可能破坏在布线过程中已经得到保证的时序性能,我们提出的算法也通过考虑时序关键路径上总线长和耦合电容,保证了在算法运行后电路中关键路径的时序性能不会下降。另外,本文采用较为完整的数值实验验证了以上算法的有效性。