In this paper, we study a cell-based row-structure layout decomposition problem for triple patterning lithography (TPL) which asks to minimize a weighted sum of coloring conflicts and stitches. We show how to extend a prior graph-based approach to solve the problem optimally under certain assumptions. Furthermore, several methods to substantially reduce the graph size and hence to accelerate the extended approach are presented. Experimental results show that our decomposer can significantly outperform a state-of-the-art work in terms of both solution quality and run time.

In this paper, we study row-based detailed placement refinement for triple patterning lithography (TPL), which asks to find a refined detailed placement solution as well as a valid TPL layout decomposition under the objective of minimizing the number of stitches and the half-perimeter wirelength. Our problem does not have precoloring solutions of cells as the input, and it allows using techniques, including white space insertion, cell flipping, adjacent-cell swapping, and vertical cell movement, to optimize the solution quality. We first present (resource-constrained) shortest-path-based algorithms for several TPL-aware single-row placement problems that allow or disallow perturbing a given cell ordering. Based on these algorithms, we then propose an approach to our TPL-aware detailed placement refinement problem, which first minimizes the number of stitches and then minimizes the wirelength. Finally, we report extensive experimental results to demonstrate the effectiveness and efficiency of our approach.

Redundant via insertion (RVI) has become an inevitable means adopted in the routing or post-routing stage to enhance chip reliability and yield as feature size shrinks down to nanometer scale. The remaining routing resources, however, could become so limited after RVI, and make engineering change order (ECO) routing during a pre-mask stage or even a post-mask stage difficult to complete. In this paper, we study an ECO routing problem where redundant vias are present in the given layout but can be considered for replacement or removal to increase the routability and improve the routing quality. To find an ECO routing path, we construct only the necessary part of the routing graph on-the-fly, and develop an A* search based algorithm for achieving efficient path finding. We also take redundant via replacement, removal, and insertion into account when formulating the routing cost, and apply a state-of-the-art method to perform redundant via replacement and insertion. Experiments show that our algorithm not only successfully routes all test cases but also efficiently produces high-quality solutions.

In this paper, we study a mask-cost-aware routing problem for engineering change order (ECO). By taking into account old routes for possible reuse, we present an approach for the problem. Encouraging experimental results are reported to demonstrate the effectiveness of our approach.