随着集成电路的不断发展,电路特征尺寸不断缩小。在电路尺寸达到纳米量级的今天,设计与工艺的独立性被打破,引发了一系列可制造性设计问题与相关研究。交替移相掩模是一种通过对掩模版进行相位偏移而提高光刻分辨率的先进工艺技术,用来解决深亚波长光刻下由于衍射效应引起的图形失真问题。交替移相掩模技术的版图优化是可制造性设计领域的计算机辅助设计技术,用于对版图进行相应技术的修改。本文提出了一种交替移相掩模版图优化软件原型FDPSM(Fudan Phase ShiftMask),以及在FDPSM中应用的交替移相掩模技术版图优化的相关数据结构和算法,实现暗场条件下的相位冲突检测和相位分配。本文提出了一种基于三连通分支分解的相位分配算法TCDBPA(Triconnected-Component-Decomposition Based Phase Assignment)。由于版图庞大的数据量,已有的相位分配算法难以处理全芯片级的交替移相掩模问题。TCDBPA应用分而治之的思想,将相位冲突图分解成各个三连通分支,然后在传统算法基础上结合三连通分支的性质对各个分支进行求解,最后合理地合并各个解集并进行最终相位分配。由于有效地降低了问题规模,因此能够提高求解速度,从而该算法可以应用于规模巨大的全芯片级的移相掩模版图优化中。本文还提出了一种改进的动态优先搜索树数据结构,应用于冲突检测中以查询版图图形之间的冲突情况,加快相位冲突图的构建时间。相比于传统的动态优先搜索树,本文数据结构逻辑简单清晰,在数据量庞大、需要频繁进行数据插入与删除、而且查询的解个数较少的应用中优势突出,特别适用于集成电路物理设计方面的应用。