Abstract
As the feature size further decreases, multiple patterning lithography (MPL) has been regarded as one of the most promising lithography solutions, along with extreme ultraviolet lithography (EUVL), directed self-assembly (DSA), and electron beam lithography (EBL). Besides, several different cell structures have been proposed. The cell structure with multiple layers is adopted to improve the intra-cell routability. The use of multi-row height cells has been taken into consideration for power, performance and area concerns. Therefore, the difficulty to refine a cell-based detailed placement increases because of not only the occurrence of new coloring conflicts during refinement but also the cell overlap while shifting multi-row height cells. In this thesis, we propose a method to refine a given placed design with multi-row height cells and make it have as few coloring conflicts as possible in every layer, while minimizing the total cell displacement. Furthermore, a concept of uncolored cell group (UCG) is presented, which is more important than coloring conflicts during refinement. By eliminating UCGs without generating any new coloring conflict, the number of UCGs strictly decreases in both local and global refinement stages of our method. The experimental results show that our method can eliminate almost all UCGs in a reasonable runtime.