| Popis: |
With 20nm production becoming a reality, research has started to focus on the technology needs for 14nm. The LELE double patterning used in 20nm production will not be able to resolve M1 for 14nm. Main competing enabling technologies for the 14nm M1 are SADP, EUV, and LELELE (referred as LE3 thereafter) triple patterning. SADP has a number of concerns of 1. density, as a layout geometry needs to stay complete as a whole, and can not be broken; 2. the complexity in SADP mask generation and debug feedback to designers; 3. the subtraction nature of the trim mask further complicates OPC and yield. While EUV does not share those concerns, it faces significant challenges on the manufacturing equipment side. Of the SADP concerns, LE3 only shares that of complexity involved in mask generation and intuitive debug feedback mechanism. It does not require a layout geometry to stay as a whole, and it benefits from the affinity to LELE which is being deployed for 20nm production. From a process point of view, this benefit from affinity to LELE is tremendous due to the data and knowledge that have been collected and will be coming from the LELE deployment. In this paper, we first recount the computational complexity of the 3-colorability problem which is an integral part of a LE3 solution. We then describe graph characteristics that can be exploited such that 3-colorability is equivalent under divide-and-conquer. Also outlined are heuristics, which are generally applied in solving computationally intractable problems, for the 3-colorability problem, and the importance in choosing appropriate worst-case exponential runtime algorithms. This paper concludes with a discussion on the new hierarchical problem that faces 3-colorability but not 2-colorability and proposals for non-3-colorability feedback mechanism. |
