As the minimum feature size continues to scale to sub-22nm, the conventional 193nm optical photolithography technology is facing great challenge in manufacturing. In the longer future, i.e., for the logic node beyond 14nm, electric beam lithography (EBL) is promising candidate for lithographic processes. Even with decades of development, the key limitation of the EBL system has been and still is the low throughput. Recently, multi-column cell (MCC) system is proposed as an extension of conventional EBL system, where several independent character projections (CP) are used to further speed-up the writing process. Each CP is applied on one section of wafer, and all CPs can work parallelly to achieve better throughput. Due to the design complexity and cost consideration, different CPs share one stencil design. For modern design, because of the numerous distinct circuit patterns, only limited number of patterns can be employed on stencil. Therefore, the area constraint of stencil is the bottleneck. To improve the throughput, the stencil should be carefully designed/manufactured to contain the most repeated cells or patterns.

This paper presents E-BLOW, a high performance planner for OSP problem in MCC system. E-BLOW integrates several novel techniques to achieve near-optimal solution in reasonable time.

1. Proposes a simplified formulation for 1D-OSP, and proves its rounding lower bound theoretically.

2. A successive relaxation algorithm to find a near optimal solution.

3. KD-Tree based clustering algorithm for speedup in 2D-OSP.