基于分解成本最小化和合法化的三图样光刻布局分解方法

摘要

本发明涉及一种基于分解成本最小化和合法化的三图样光刻布局分解方法，该方法将三图样光刻布局分解问题分成两个阶段求解，首先将初始图样布局图转化为无向图，然后采用图缩减方法来缩小问题规模；第一阶段采用一个松弛优化模型对图样进行染色，第二阶段考虑引入缝合将一个图样分割成多个子图样的方式来消除尽可能多的冲突，实现最终染色。本发明的三图样光刻布局分解方法分解合理，高效快速，分解结果好。

主权项

一种基于分解成本最小化和合法化的三图样光刻布局分解方法，其特征在于包括以下步骤：步骤S1：将布局图转化为无向图；步骤S2：采用图缩减方法删除点，并将其存储；步骤S3：所述步骤S2中的图缩减方法第一步为删除度小于3的点；步骤S4：所述步骤S2中的图缩减方法第二步为删除内含点；步骤S5：所述步骤S2中的图缩减方法第三步为求解连通分支；步骤S6：重复所述步骤S3‑步骤S5三次，产生多个连通分支；步骤S7：采用面冲突投影方法检查每个点所代表的图样是否为冲突图样；步骤S8：对所有点赋权，冲突图样的点赋权为1，对非冲突图样的点赋权为α＝0.1；步骤S9：采用非线性0‑1整数规划模型求解点带权的连通分支子图的3染色解；步骤S10：对每一个未染色点代表的图样用缝合插入算法进行判断或插入缝合；步骤S11：对所述步骤S10中没有缝合可插入的图样所在的连通分支用回溯方法得到另一个更好的3染色解，返回所述步骤S10，直到该连通分支没有合法的松弛染色解；步骤S12：对所述步骤S3与步骤S4中删除的点进行染色。