曝光数据流优化问题的蒙特卡罗算法

集成工艺中控制图形发生器产生掩模图形的数据流文件的数据排列顺序优化,是一个其结点数可达数千个之多的大规模旅行商问题(从镜头架的位置,即每个矩形的矩心为结点),常规算法早已不适用。本文采用多阶段蒙特卡罗算法并加以改进,补充了“分层优化模式”,邻接结点的预合并和在各个阶段末提取共同子路径并删去相关结点等一系列逐步缩小问题规模的措施,形成了一个实用的优化算法。相应的软件已成功地应用于薄膜磁头的数据流文件的优化。

Monte Carlo Method for Optimization of Exposure Data Stream

The optimization of data stream exposure used to control pattern generator for mask pattern generation in IC technology is a large scale Traveling Salesman Prob-lem(TSP) with as many as thousands of nodes which are the center of each rectangle with respect to the position of the lens panel. Conventional algorithms for TSP are no longer valid due to the large scale of the problem. In this paper, a practical optimal algorithm is described, for which an improved multi-stage Monte Carlo algorithm is employed, and additional measures, such as "two layer optimizing model", the precombination of the adjacent nodes,and searching for common subpath and deleting relative nodes at the end of each stage, are taken, to decrease the number of the nodes step by step. A software using this method has been successfully applied to the optimization of data stream files for thin-film magnetic head masks.