In double patterning lithography (DPL) layout decomposition for 45 nm and below process nodes, two features must be assigned opposite colors (corresponding to different exposures) if their spacing is less than theminimum coloring spacing. However, there exist pattern configurations for which pattern features separated by less than the minimum coloring spacing cannot be assigned different colors. In such cases, DPL requires that a layout feature be split into two parts. We address this problem using two layout decomposition approaches based on aconflict graph. First, node splitting is performed at all feasible dividing points. Then, one approach detects conflict cycles in the graph which are unresolvable for DPL coloring, and determines the coloring solution for the remaining nodes using integer linear programming (ILP). The other approach, based on a different ILP problem formulation, deletes some edges in the graph to make it two-colorable, then finds the coloring solution in the new graph. We evaluate our methods on both real and artificial 45 nm testcases. Experimental results show that our proposed layout decomposition approaches effectively decompose given layouts to satisfy the key goals of minimized line-ends and maximized overlap margin. There are no design rule violations in the final decomposed layout.

In double patterning lithography (DPL) layout decomposition for 45nm and below process nodes, two features must be assigned opposite colors (corresponding to different exposures) if their spacing is less than the minimum coloring spacing [11, 9, 5]. However, there exist pattern configurations for which pattern features separated by less than the minimum color spacing cannot be assigned different colors. In such cases, DPL requires that a layout feature be split into two parts. We address this problem using a layout decomposition algorithm that includes graph construction, conflict cycle detection, and node splitting processes. We evaluate our technique on both real-world and artificially generated testcases in 45nm technology. Experimental results show that our proposed layout decomposition method effectively decomposes given layouts to satisfy the key goals of minimized line-ends and maximized overlap margin. There are no design rule violations in the final decomposed layout.

As advanced technologies in wafer manufacturing push patterning processes toward lower subwavelength printing, lithography for mass production potentially suffers from decreased patterning fidelity. This results in the generation of manyhotspots, which are actual device patterns with relatively large critical-dimension and image errors with respect to on-wafer targets. Hotspots can be formed under a variety of conditions such as the original design being unfriendly to the resolution enhancement technique that is applied, unanticipated pattern combinations in rule-based optical proximity correction (OPC), or inaccuracies in model-based OPC. When these hotspots fall on locations that are critical to the electrical performance of a device, device performance and parametric yield can be significantly degraded. The golden verification signoff tool using a simulation-based approach has occupied the mainstream and has been able to accurately detect hotspots. However, this approach represents a runtime-quality tradeoff point that is high in quality but also high in runtime. There is also little point in trying to replace the golden signoff tool. We are motivated to develop a low-runtime ldquoprefilterrdquo that reduces the amount of layout area to be analyzed by the golden tool, without compromising the overall quality of hotspot finding. In this paper, we first describe a novel detection algorithm for hotspots induced by lithographic uncertainty. Our goal is to rapidly detect all lithographic hotspots without significant accuracy degradation. In other words, we propose a filtering method: as long as there are no ldquofalse negatives,rdquo i.e., we reliably obtain a superset of actual hotspots, then our method can dramatically reduce the layout area processed by golden hotspot analysis. Our hotspot detection algorithm includes layout graph construction, graph planarization, three-level bridging hotspot detection, and necking hotspot detection. We have tested our flow on several industry test cases. The experimental results show that our method is promising: for benchmark designs in 90-nm and 65-nm technologies, 100% of bridging and open hotspots are detected with few falsely detected hotspots. The average runtime of our method is more than 496 faster compared to the commercial tool.

Nanometer VLSI systems demand robust clock distribution network design for increased process and operating condition variabilities. In this paper, we propose minimum clock distribution network augmentation for guaranteed skew yield. We present theoretical analysis results on an inserted link in a clock network, which scales down local skew and skew variation, but may not guarantee global skew and skew variation reduction in general. We propose a global minimum clock network augmentation algorithm, which inserts links simultaneously between all nearest sink pairs, apply rule-based link removal, and perform link consolidation by Steiner minimum tree construction for wirelength reduction with guaranteed clock skew yield. Our experimental results show that our proposed algorithm achieves dominant clock network augmentation solutions, e.g., an average of 16% clock skew yield improvement, 9% maximum skew reduction, and 25% reduction of clock skew variation standard deviation with identical wirelength compared with previous best clock network link insertion methods [11].

Alternating-aperture phase shift masking (AAPSM), a form of strong resolution enhancement technology, will be used to image critical features on the polysilicon layer at smaller technology nodes. This technology imposes additional constraints on the layouts beyond traditional design rules. Of particular note is the requirement that all critical features be flanked by opposite-phase shifters while the shifters obey minimum width and spacing requirements. A layout is called phase assignable if it satisfies this requirement. Phase conflicts have to be removed to enable the use of AAPSM for layouts that are not phase assignable. Previous work has sought to detect a suitable set of phase conflicts to be removed as well as correct them. This paper has two key contributions: 1) a new computationally efficient approach to detect a minimal set of phase conflicts, which when corrected will produce a phase-assignable layout, and 2) a novel layout modification scheme for correcting these phase conflicts with small layout area increase. Unlike previous formulations of this problem, the proposed solution for the conflict detection problem does not frame it as a graph bipartization problem. Instead, a simpler and more computationally efficient reduction is proposed. This simplification greatly improves the runtime while maintaining the same improvements in the quality of results obtained in Chiang (Proc. DATE, 2005, p. 908). An average runtime speedup of 5.9times is achieved using the new flow. A new layout modification scheme suited for correcting phase conflicts in large standard-cell blocks is also proposed. The experiments show that the percentage area increase for making standard-cell blocks phase assignable ranges from 1.7% to 9.1%

Signal-integrity effects have significant impacts on very large-scale-integration performance variation and must be taken into account in statistical timing analysis. In this paper, we study the signal-propagation-delay variation that is induced by crosstalk aggressor signals. We establish a functional relationship between the signal propagation delay and the crosstalk aggressor signal alignment by deterministic circuit simulation and derive closed-form formulas for the statistical distributions of output signal arrival times. Our proposed method can be smoothly integrated into a static timing analyzer, wherein runtime is dominated by sampling the deterministic delay calculation, while probabilistic computation and updating take constant time. Experimental results based on the 1000- global interconnect structures in Berkeley Predictive Technology Model 70-nm technology and industry designs in 130-nm technology show that lack of statistical crosstalk aggressor signal alignment consideration could lead to up to 114.65% (71.26%) differences in interconnect-delay means (standard deviations) and 159.4% (147.4%) differences in gate-delay means (standard deviations). By contract, the method in our earlier work gives within 1.28% (3.38%) mismatch in interconnect output signal arrival time means (standard deviations) and within 2.57% (3.86%) mismatch in gate output signal arrival time means (standard deviations), respectively.

The aggressive scaling of very large-scale integration feature size and the pervasive use of advanced reticle enhancement technologies lead to dramatic increases in mask costs, pushing prototype and low-volume production designs to the limit of economic feasibility. Multiproject wafers (MPWs), or “shuttle” runs, provide an attractive solution for such designs by providing a mechanism to share the cost of mask tooling among up to tens of designs. However, MPW reticle floorplanning and wafer dicing introduce complexities that are not encountered in typical single-project wafers. Recent works on wafer dicing adopt one or more of the following assumptions to reduce problem complexity: 1) equal production volume requirement for all designs; 2) same dicing plan used for all wafers or for all rows/columns of reticle images on a wafer; 3) unrealistic wafer models such as a rectangular array of projections; and 4) fixed wafer shot-map. Although using one or more of the aforementioned assumptions makes the problem solvable, the performance of the solutions is degraded. In this paper, a comprehensive MPW flow aimed at minimizing the number of wafers needed to fulfill given die production volumes is proposed. The proposed flow includes two main steps: 1) multiproject reticle floorplanning and 2) wafer shot-map and dicing plan definition. For each of these steps, improved algorithms are proposed as follows. The proposed reticle floorplanner uses a hierarchical quadrisection combined with simulated annealing to generate “diceable” floorplans, observing given maximum reticle sizes. The proposed dicing planner allows multiple side-to-side dicing plans for different wafers and different reticle projection rows/columns within a wafer and further improves the dicing yield by partitioning each wafer into a small number of parts before individual die extraction. A wafer shot-map definition heuristic is also proposed in order to fully utilize round wafer real estate by extracting the maximum number of functional dies from both fully and partially printed reticle images. Experiments on industry test cases show that the proposed methods outperform significantly not only previous methods in the literature but also reticle floorplans manually designed by experienced engineers.

We study gate delay variation caused by crosstalk aggressor alignment, i.e., difference of signal arrival times in coupled neighboring interconnects. This effect is as significant as multiple-input switching on gate delay variation [2]. We establish a functional relationship between driver gate delay and crosstalk alignment by deterministic circuit simulation, and derive closed form formulas for statistical distributions of driver gate delay and output signal arrival time.Our proposed method can be smoothly integrated into a static timing analyzer, which runtime is dominated by sampling deterministic delay calculation, while probabilistic computation and updating take constant time. Our experimental results on 70nm technology global interconnect structures and 130nm technology industry designs show respectively 159:4% and 147:4% differences in mean and standard deviation of gate delay without crosstalk aggressor alignment consideration, while our method gives within 2:57% and 3:86% offset in gate output signal arrival time mean and standard deviation, respectively.

Depth of focus is the major contributor to lithographic process margin. One of the major causes of focus variation is imperfect planarization of fabrication layers. Presently, optical proximity correction (OPC) methods are oblivious to the predictable nature of focus variation arising from wafer topography. As a result, designers suffer from manufacturing yield loss as well as loss of design quality through unnecessary guardbanding. In this paper, the authors propose a novel flow and method to drive OPC with a topography map of the layout that is generated by chemical-mechanical polishing simulation. The wafer topography variations result in local defocus, which the authors explicitly model in the OPC insertion and verification flows. In addition, a novel topography-aware optical rule check to validate the quality of result of OPC for a given topography is presented. The experimental validation in this paper uses simulation-based experiments with 90-nm foundry libraries and industry-strength OPC and scattering bar recipes. It is found that the proposed topography-aware OPC (TOPC) can yield up to 67% reduction in edge placement errors. TOPC achieves up to 72% reduction in worst case printability with little increase in data volume and OPC runtime. The electrical impact of the proposed TOPC method is investigated. The results show that TOPC can significantly reduce timing uncertainty in addition to process variation

DNA probe arrays, or DNA chips, have emerged as a core genomic technology that enables cost-effective gene expression monitoring, mutation detection, single nucleotide polymorphism analysis, and other genomic analyses. DNA chips are manufactured through a highly scalable process called very large-scale immobilized polymer synthesis (VLSIPS) that combines photolithographic technologies adapted from the semiconductor industry with combinatorial chemistry. Commercially available DNA chips contain more than half a million probes and are expected to exceed 100 million probes in the next generation. This paper is one of the first attempts to apply very large scale integration (VLSI) computer-aided design methods to the physical design of DNA chips, where the main objective is to minimize total border cost (i.e., the number of nucleotide mismatches between adjacent sites). By exploiting analogies between manufacturing processes for DNA arrays and for VLSI chips, the authors demonstrate the potential for transfer of methodologies from the 40-year-old field of electronic design automation to the newer DNA array design field. The main contributions of this paper are the following. First, it proposes several partitioning-based algorithms for DNA probe placement that improve solution quality by over 4% compared to best previously known methods. Second, it gives a new design flow for DNA arrays, which enhances current methodologies by adding flow awareness to each optimization step and introducing feedback loops. Third, it proposes solution methods for new formulations integrating multiple design steps, including probe selection, placement, and embedding. Finally, it introduces new techniques to experimentally evaluate the scalability and suboptimality of existing and newly proposed probe placement algorithms. Interestingly, the authors find that DNA placement algorithms appear to have better suboptimality properties than those recently reported for VLSI placement algorithms [C.C. Chang et al., Optimality and scalability study of existing placement algorithms, Proc. Asia South-Pacific Design Automation Conf., Kitakyushu, Japan, p.621-7, Jan. 2003; J. Cong et al., Optimality, scalability and stability study of partitioning and placement algorithms, Proc. Int. Symp. Physical Design (ISPD), Monterey, CA, p.88-94, 2003]

As feature sizes shrink, it will be necessary to use AAPSM (alternating-aperture phase shift masking) to image critical features, especially on the polysilicon layer. This imposes additional constraints on the layouts beyond traditional design rules. Of particular note is the requirement that all critical features be flanked by opposite-phase shifters, while the shifters obey minimum width and spacing requirements. A layout is called phase-assignable if it satisfies this requirement. If a layout is not phase-assignable, the phase conflicts have to be removed to enable the use of AAPSM for the layout. Previous work has sought to detect a suitable set of phase conflicts to be removed, as well as correct them. The contributions of this paper are the following: (1) a new approach to detect a minimal set of phase conflicts (also referred to as AAPSM conflicts), which when corrected will produce a phase-assignable layout; (2) a novel layout modification scheme for correcting these AAPSM conflicts. The proposed approach for conflict detection shows significant improvements in the quality of results and runtime for real industrial circuits, when compared to previous methods. To the best of our knowledge, this is the first time layout modification results are presented for bright-field AAPSM. Our experiments show that the percentage area increase for making a layout phase-assignable ranges from 0.7-11.8%.

Alternating-aperture phase shift masking (AAPSM), a form of strong resolution enhancement technology (RET) is used to image critical features on the polysilicon layer at smaller technology nodes. This technology imposes additional constraints on the layouts beyond traditional design rules. Of particular note is the requirement that all critical features be flanked by opposite-phase shifters, while the shifters obey minimum width and spacing requirements. A layout is called phase-assignable if it satisfies this requirement. Phase conflicts between shifters have to be removed to enable the use of AAPSM for layouts that air not phase-assignable. Previous work has sought to detect a suitable set of phase conflicts to be removed, as well as correct them as well as correct them. This paper has two key contributions: (1) a new computationally efficient approach to detect a minimal set of phase conflicts, which when corrected produces a phase-assignable layout; (2) a novel layout modification scheme for correcting these phase conflicts in standard-cell blocks. Unlike previous formulations of this problem, the proposed solution for the conflict detection problem does not frame it as a graph bipartization problem. Instead, a simpler and more computationally efficient reduction is proposed. This simplification greatly improves the runtime, while maintaining the same improvements ill the quality of results. An average runtime speedup of 5.9/spl times/ is achieved using the new flow. A new layout modification scheme for correcting phase conflicts in large standard-cell blocks is also proposed. The proposed layout modification scheme can handle all phase conflicts in large standard-cell blocks with small increases in area. Our experiments show that the percentage area increase for making typical standard-cell blocks phase-assignable ranges from 3.4-9.1%.

Multi-project Wafers (MPW) are an efficient way to share the rising costs of mask tooling between multiple prototype and low production volume designs. Packing the different die images on a multi-project reticle leads to new and highly challenging floorplanning formulations, characterized by unusual constraints and complex objective functions. In this paper we study multi-project reticle floorplanning and wafer dicing problems under the prevalent side-to-side wafer dicing technology. Our contributions include practical mathematical programming algorithms and efficient heuristics based on interval-graph coloring which find side-to-side wafer dicing plans with maximum yield for a fixed multi-project reticle floorplan and given per-die maximum dicing margins. We also give novel shelf packing and simulated annealing reticle floorplanning algorithms for maximizing wafer-dicing yield. Experimental results show that our algorithms improve wafer-dicing yield significantly compared to existing industry tools and academic min-area floorplanners.

Traditional multilevel partitioning approaches have shown good performance with respect to cutsize, but offer no guarantees with respect to system performance. Timing-driven partitioning methods based on iterated net reweighting, partitioning, and timing analysis have been proposed (Ababei et al., 2002), as well as methods that apply degrees of freedom such as retiming (Cong et al., 2000), (Cong et al., 2002). In this paper, we identify and validate a simple approach to timing-driven partitioning based on the concept of "V-shaped nodes." We observe that the presence of V-shaped nodes can badly impact circuit performance, as measured by maximum hopcount across the cutline or similar path delay criteria. We extend traditional the Fiduccia-Mattheyses (FM) variant of the Kernighan-Lin (Kernighan and Lin, 1970) algorithm approaches to directly eliminate or minimize "distance-k V-shaped nodes" in the bipartitioning solution, achieving an attractive tradeoff between cutsize and path delay. Experiments show that in comparison to MLPart (Caldwell et al., 2000), our method can reduce the maximum hopcount by 39% while only slightly increasing cutsize and runtime. No previous method improves path delay in such a transparent manner. The new partitioner is incorporated into a placer (http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/Placement/Capo/) and circuit delay is evaluated by a commercial static timing analyzer (http://www.ece.uci.edu/eceware/cadence/spl I.bar/docs/pearluser/). The empirical results show that the delay is significantly reduced, at the cost of very acceptable impacts on wirelength and runtime.

DNA probe arrays have recently emerged as one of the core genomic technologies. Exploiting analogies between manufacturing processes for DNA arrays and for VLSI chips, we demonstrate the potential for transfer of methodologies from the 40-year old field of electronic design automation to the newer DNA array design field. Our main contributions are the following. (1) We give a new design flow for DNA arrays which enhances current methodologies by adding flow-awareness to each optimization step and introducing feedback loops. (2) We propose solution methods for new formulations integrating multiple design steps, including probe selection, placement, and embedding. (3) We give results of a comprehensive experimental study showing that significant improvements in solution quality can be achieved by using the enhanced methodologies.

Traditional multilevel partitioning approaches have shown good performance with respect to cutsize, but offer no guarantees with respect to system performance. Timing-driven partitioning methods based on iterated net reweighting, partitioning and timing analysis have been proposed [2], as well as methods that apply degrees of freedom such as retiming [7] [5]. In this work, we identify and validate a simple approach to timing-driven partitioning, based on the concept of “V-shaped nodes”. We observe that the presence of V-shaped nodes can badly impact circuit performance, as measured by maximum hopcount across the cutline or similar path delay criteria. We extend traditional KLFM approaches to directly eliminate or minimize “distance-k Vshaped nodes ” in the bipartitioning solution, achieving a smooth trade-off between cutsize and path delay. Experiments show that in comparison to MLPart [4], our method can reduce the maximum hopcount by 39 % while only slightly increasing cutsize and runtime. No previous method improves path delay in such a transparent manner.