交替型暗域相移掩模的并行算法

摘要

设计并实现了一种暗域相移掩模(PSM)问题的并行算法。首先根据"分而治之"的原则,将输入版图划分为若干尺寸较小的、易于解决的子版图;然后分配每个子版图给不同的进程,各个进程同时独立地消除子版图的相位冲突;最后将所有的子版图重新组合,生成没有相位冲突的相移掩模版图。实验结果表明,采用4进程的并行PSM算法,可以减少近64.3%的计算时间,获得2.8的加速比。算法还可以有效地减少冲突图中冲突的数目和边的数目。