On Refining Row-Based Detailed Placement for Triple Patterning Lithography

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.