随着集成电路特征尺寸的不断缩小，深亚微米波长光刻成为研究热点。传统的193nm波长光源难以直接用于22nm以下图形的光刻，单次曝光光刻达到了物理极限，并且由于光源功率、抗蚀剂和无缺陷掩膜板等因素影响，极紫外光刻也迟迟未能很好地应用于实际生产。双重版图技术(DPT，Double Patterning Technology)成为了进一步缩小光刻尺寸的最实用、最有前景的技术。目前Intel的22nm和16/14nm工艺、SAMSUNG的14nm工艺、Global Foundries的14nm工艺、TSMC的16nm工艺等，以及研发中的后续10nm、7nm工艺，甚至未来5nm工艺均使用双重/多重图形光刻的版图分解技术。　　双重版图技术将同一物理层的版图分解到两个掩膜板上，要求分解速度较快、图形切割(stitch)数量较少、分解得到的两张掩膜板的图形密度平衡、对电路可靠性和性能的影响较小等。本文首先研究和分析了目前双重图形光刻的版图分解技术的进展和现有的成果，比较了不同分解方法的优缺点，并在此基础上进行了以下工作。　　本文设计了用于双重图形光刻的版图分解基础算法，实现了对应的基础软件，包括初始化模块、查找和解决冲突环路模块、着色模块和颜色翻转模块等模块。其中，查找和解决冲突环路模块，是双重图形光刻版图分解的核心，将之前无法分配到两张掩膜板上的图形冲突环路切割，使这些图形可以被分配到两张掩膜板上;颜色翻转模块，根据着色的情况，对一些图形组进行颜色翻转，使图形切割数较少、图形分解均衡性好。测试结果表明，该软件能够按照双重图形光刻的制版要求正确的将同一物理层的版图分解到两个掩膜版上，并能够正确的标出版图设计中的原生冲突，便于版图设计者修改面向双重图形光刻工艺的版图。　　针对双重图形光刻的版图分解基础算法的运行速度问题，本文提出了自适应窗口无重叠版图划分技术，结合该版图分解基础算法，设计了一种双重图形光刻版图的快速分解算法，实现了对应的快速分解软件。与现有文献报道的双重光刻版图分解算法相比，该算法复杂度低。本文采用各种规模版图数据对该快速分解算法进行了实际测试。测试结果表明，该算法仅在单线程运行下就可以有效地提高双重版图分解的速度，与现有文献报道的多机集群并行计算的最优结果数据相比，其计算速度快35％以上。　　本文还提出了一种算法复杂度数值分析方法。该方法是通过实际测试数据对本文提出的快速分解算法的复杂度进行了分析。分析结果表明，该快速分解算法复杂度低。同时，分析结果数据和实测结果数据的一致性证明该分析方法正确。