# Parallel Algorithm of SOI Layout Decomposition for Double Patterning Lithography on High-Performance Computer Platforms

Vladimir Verstov, Vadim Shakhnov, Lyudmila Zinchenko

► To cite this version:

Vladimir Verstov, Vadim Shakhnov, Lyudmila Zinchenko. Parallel Algorithm of SOI Layout Decomposition for Double Patterning Lithography on High-Performance Computer Platforms. 5th Doctoral Conference on Computing, Electrical and Industrial Systems (DoCEIS), Apr 2014, Costa de Caparica, Portugal. pp.543-550, 10.1007/978-3-642-54734-8_60. hal-01274821

HAL Id: hal-01274821

https://inria.hal.science/hal-01274821

Submitted on 16 Feb 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Parallel Algorithm of SOI Layout Decomposition for
Double Patterning Lithography on High-Performance
Computer Platforms

Vladimir Verstov, Vadim Shakhnov, Lyudmila Zinchenko

Ul.Baumanskays 2-ya, 5, 105005, Moscow, Russia
v.verstov@gmail.com, shakhnov@mail.ru, lyudmillaa@mail.ru

**Abstract.** In the paper silicon on insulator layout decomposition algorithms for the double patterning lithography on high performance computing platforms are discussed. Our approach is based on the use of a contradiction graph and a modified concurrent breadth-first search algorithm. We evaluate our technique on both real-world and artificial test cases including non-Manhattan geometry. Experimental results show that our soft computing algorithms decompose layout successfully and a minimal distance between polygons in layout is increased.

**Keywords:** VLSI, Layout, Double Patterning, Parallel Algorithms, High-Performance Computing, Radiation Hardening.

# 1 Introduction

Collective awareness systems for sustainability and social innovation are information and communications technology (ICT) platforms using electronic components and networks to drive social innovation. Chernobyl (1986) and Fukushima (2011) nuclear incidents demonstrate an increasing role of radiation hardening for emergency systems, especially for very-large-scale integration (VLSI) chips. Design of electronic devices resistant to damage caused by radiation requires new approaches. Reliability is the main silicon on insulator (SOI) technology advantage in a comparison with bulk-silicon technology [1]. However, floating body effect is the major parasitic effect in SOI technology. It results in circuit instabilities. In order to overcome this negative effect multi-gate transistors were proposed [2]. The use of pi-gate, sigma-gate transistors etc. results in non-Manhattan layout topology.

Currently, double and multiple patterning technologies play an important role because the extreme ultraviolet lithography (EUV) has been delayed for the emerging technology nodes. For the multiple patterning technologies layouts are decomposed into two or more masks. Fig. 1 demonstrates a layout decomposition case for double patterning. In [3] the sequential algorithms based on a conflict graph and integer linear programming were discussed. In [4] the sequential algorithms based on a contradiction graph and graph coloring were proposed. The contradiction graph
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** An example of the layout decomposition for double patterning technology. Layer 1 and Layer 2 are layout layers after decomposition.</figcaption></figure>

accumulates information about contradictions between requirements of minimal
distance between polygons and negative diffraction effects for adjacent objects. The
approach proposed in [4] was implemented in the TPLConverter program [5].
However, high-performance computing platforms are required for SOI layout
decomposition for double patterning technology because of non-Manhattan layout and
huge size of layout data file. However, the application of sequential algorithms for
high-performance computing platforms results in the decrease of computing
productivity [6]. Parallel algorithms are required for these computing systems.

In [7] concurrent algorithms of the VLSI layout decomposition for double patterning were proposed. However, these algorithms are valid for Manhattan layouts only.

In this article, we propose methods of SOI VLSI layout decomposition for double patterning. In comparison with the algorithms [7] these methods can be applied for both Manhattan and non-Manhattan layouts including H-transistors, O-transistors etc. The proposed algorithms were implemented in ParallelDPLayout Migrator software for high-performance computing systems. Preliminary experimental results for artificial and real-world tests are outlined.

The rest of paper is structured as follows. The next Section reviews collective
awareness platforms features. Section 3 presents our methods for layout decomposition
for double patterning. We discuss our experimental results in Section 4. Finally,
conclusions are derived in Section 5.

## 2 Relationship to Collective Awareness Systems

The coming revolution in personal and community risk awareness is based on
collective awareness platforms. Chernobyl and Fukushima nuclear incidents showed a
danger of radiation for a person and a community. In addition, many radioactive
isotopes are used in industry and health care. A radiation level can be monitored by
individual devices and data about radiation are collected. Neris [8] project has started
in 2008. Safecast project [9] has started in 2011. In 2012 more 3 million radiation data
points were collected using individual devices.
However, commercial devices can be damaged or malfunctioned because of radiation. Special radiation hardened electronic devices have to be used in emerging collective awareness platforms. SOI [1] including silicon on sapphire (SOS) technologies were developed for radiation-hardened applications. SOI devices are more reliable for the applications in emerging systems. Another way to do radiation hardened circuits is redundancy. But this technique increases area of a chip design. However, some negative effects hinder their wide applications.

In particular, floating body effect results in variation of delay time, circuit parameters etc. In order to overcome these deficiencies multi-gate transistors are used. Many multi-gate transistors have non-Manhattan layouts that realize in a non-Manhattan layout of chips. In addition, layout data file size is increased that result in huge computational efforts to manipulate by the data. Some files to be processed have to be divided and special methods to verify, decompose or to migrate have to be used for these layouts.

High performance computing is one of promising solutions for the mentioned above problem. However, new methods to process layout and then modify them for a target technology are required.

In this paper our focus is on layout decomposition for double patterning technology while the proposed layout processing methods can be applied for VLSI routing, layout migration, verification etc.

# 3 Concurrent Algorithms for VLSI Layout Decomposition for Double Patterning

## 3.1 Concurrency during Layout Processing

Special techniques are requiring handling a non-Manhattan SOI layout including multi-gate transistors with circular structure. We propose a special data structure for the concurrent VLSI layout processing. Fig. 2 illustrates our approach for a layer of a circular structure transistor (O-transistor).

<figure><img src="image_3.png" /><figcaption>Fig. 2. An example of our data structure for the SOI VLSI layout processing.</figcaption></figure>
<figure><img src="image_4.png" /><figcaption>Fig. 3. An example for the two processors case.</figcaption></figure>

The VLSI layout represents a set of polygons. Each polygon consists of a set of segments. Each segment is stored as two references to boundary points. Every point is stored in the “events points” array. This data structure allows us to describe non-Manhattan layout.

Our algorithm assumes the high-performance computer (HPC) platform architecture to be a one-dimensional mesh of processors. Each layer splits to horizontal bars. The number of horizontal bars is equal to the number of processors. To avoid conflicts in adjacent bars they overlay each other. Therefore, one geometric object splits to two features and two overlapping ones are assigned to two different processors to be decomposed. Fig. 3 illustrates our approach for the test layer case including F- and O-transistors for two processors. We apply our approach for layout decomposition for double patterning. However, this approach can be expanded for compaction and verification of SOI VLSI layouts as well.

## 3.2 Constraint and Contradiction Graphs Construction

We propose a modified sweep line algorithm to construct constraint and contradiction graphs. Each vertex in constraint and contradiction graphs is crisp and corresponds to a polygon in a layout layer. Each edge in a constraint graph is crisp and depends from spacing constraints for objects in layers. A contradiction graph is a fuzzy graph [10]

$$ \sim G=(V, \sim E) \qquad (1) $$

where V is the node set, ~E is the fuzzy edge set, characterized by the matrix of membership functions depending from the double patterning technology parameter μE(x).

If a distance x between two segments related to different polygons is smaller than the double pattern technology parameter the correspondent edge and its value defined by the membership function μE(x) are added to a contradiction graph.
<figure><img src="image_5.png" /><figcaption>Fig 4. An example of the contradiction graph construction flow.</figcaption></figure>

The contradiction graph accumulates an information about all contradictions in a given layout and a level of the contradiction according to the membership function for double patterning technology. Fig. 4 illustrates our approach for our test layer case including F- and O-transistors.

## 3.3 Parallel Layout Decomposition Algorithm

The parallel algorithm for the layout layer decomposition is discussed below. This algorithm based on testing bipartiteness for α-cuts family of the contradiction graph

$$ \mu_E(x) \geq \alpha, \qquad (2) $$

where the α-cut of a contradiction graph is the crisp graph.

If the corresponding crisp graph is bipartite this layer could be decomposed into two new ones for the current α-cut.

We propose a modified concurrent breadth-first search algorithm to test bipartiteness of the α-cut of a contradiction graph. For the current α we can find either two-coloring for the graph or an odd cycle for non-bipartite graph in linear time. If the algorithm did not find an odd cycle, then the α-cut of the graph is bipartite according to [11].

Our algorithm is given below.

Input: A graph ~G, α_min, α_max.

Output: All design alternatives, a coloring of the α-cut of ~G and α.

Begin

Step 1. α = α_min.

Repeat
Step 2. The crisp graph G is constructed for the current $\alpha$. The current color is equal to 1. Assign 1 color to the source vertex.

Repeat

Color all the neighbors with 2 color.

Color all neighbor's neighbor with 1 color.

If an edge from i to j exists and destination j is colored with the same color as i

Then design alternatives for the current $\alpha$-cut are collected and $\alpha$ is increased.

Else

Until all vertices are colored. If all vertices are colored Then Step 3.

Until $\alpha < \alpha_{max}$

Step 3. Our algorithm stops when a design decision for double patterning technology is found or $\alpha=\alpha_{max}$. In the last case, recommendations for multi-patterning technology are given according to the found minimal number of the required colors.

End

Fig. 5 illustrates our approach for one design alternative. The metal layer for the 4AND cell layout and the corresponding crisp graph are shown on Fig. 5, a. Fig. 5, b shows the corresponding crisp graph that has been colored using two colors. Fig. 5, c shows the metal layer of the 4AND element layout after decomposition. The first layer polygons are shown as grey objects, while the second layer polygons are shown as black objects.

## 4 Experimental Results

The proposed approaches were implemented using C++ programming language on Cent OS 5.5 operating system. Additionally, we use Boost libraries and OpenMP framework.

<figure><img src="image_6.png" /><figcaption>**Fig 5.** The 4AND element metal layer decomposition for double patterning: a – the layout layer and the $\alpha$-cut of the contradiction graph; b – the $\alpha$-cut of the contradiction graph after coloring; c – two new layout layers (the first layer is shown as grey objects, the second layer is given as black objects).</figcaption></figure>
Table 1 summarizes our simulation results for our artificial and real-world tests. We evaluate our solutions with respect with solution quality. We use the relative minimal distance between the polygons after the decomposition that is calculated as the ratio of the minimal distance between the polygons of the layer *i* (*i* = 1, 2) after the decomposition to the minimal distance in the critical layer before the decomposition [7].

<table><caption>**Table 1.** Test cases parameters.</caption><thead><tr><th>Layout</th><th>Polygons, total/<br>Layer 1/Layer 2</th><th>Relative minimal<br>distance, Layer 1</th><th>Relative minimal<br>distance, Layer 2</th></tr></thead><tbody><tr><td>Multiplexer</td><td>18 / 13 / 5</td><td>1,15</td><td>3,68</td></tr><tr><td>4AND</td><td>8 / 4 / 4</td><td>1,65</td><td>2,18</td></tr><tr><td>4NOR</td><td>7 / 5 / 2</td><td>1,27</td><td>6,35</td></tr><tr><td>XNOR</td><td>9 / 7 / 2</td><td>1,15</td><td>1,18</td></tr><tr><td>Memory Cell</td><td>278 / 249 / 29</td><td>1,10</td><td>1,24</td></tr><tr><td>4xAdder</td><td>79 / 58 / 21</td><td>1,80</td><td>2,05</td></tr><tr><td>Total</td><td>67 / 56 / 11</td><td>1,35</td><td>2,78</td></tr></tbody></table>

It should be mentioned that one of the simplest DFM rules is an increase of the minimal distance between polygons [12]. In average, the minimal distance between the polygons in the layer for all our tests is increased above 35%. It is obvious that the reproducibility of the critical layout layer will be better in a comparison with the initial design. However, this improvement strongly varies for several test cases, from the minimum of 10% for the memory cell to 80% for the adder. In addition, this parameter varies for layers (Layer 1 and Layer 2) that were created after layout decomposition for double patterning. This deficiency has to be overcome to increase yield.

## 5 Conclusion

We have proposed a novel layout decomposition algorithm to address design needs for radiation hardened layout design. Our approach practically and effectively improves layout quality. It has been implemented using the contradiction graph and our modified concurrent breadth-first search algorithm. Our soft computing approach to manage contradictions in the layouts is novel and has advantage in terms of adaptability. Another aspect of our research is the use of high performance computing platforms for our design iterations. Our experiments using artificial and real-world test cases indicate that minimal distance is increased for all test cases.

Our ongoing research is in the following directions. The irregularity of layouts after decomposition results in lower yield. In order to overcome this deficiency optimization techniques will be used.

Our results can be used in design flow of radiation hardened electronics for several applications including space industry, collective awareness systems, emerging systems etc.
**Acknowledgments.** This study was partially supported by the Program of the President of the Russian Federation for the Support of Leading Scientific Schools, project LS-2903.2014.9 and Russian Fund for Basic Research, project 13-07-0073-a.

References

1. Bernstein, K., Rohrer, N. J.: SOI Circuit Design Concepts. Kluwer Academic Publishers, London (2003).

2. Colinge, J.: Multi-gate SOI MOSFETs, Solid-State Electronics. 48, 897--905 (2004)

3. Kahng, A. B., Park, C.-H. et al.: Layout Decomposition for Double Patterning Lithography. In: Proc. IEEE Intl. Conf. on Computer-Aided Design (2008)

4. Shakhnov, V.A., Zinchenko, L.A., Rezchikova, E.V., Averyanikhin, A.E.: Algorithms of the VLSI layout decomposition. Vestn. Mosk. Gos. Tekh. Univ., 1, 76--87 (2011)

5. Zinchenko, L.A., Averyanikhin, A.E.: The Software for VLSI Layout Decomposition for Double Patterning. Program. Produkty Sist., 1, 7--10 (2011)

6. Shakhnov, V.A., Zinchenko L.A.: Features of Application of Computing Systems in Nanoengineering CADs, Vestn. Mosk. Gos. Tekh. Univ., spec. issue "Nanoinzheneriya" (Nanoengineering), 100--109 (2010)

7. Shakhnov, V.A., Zinchenko, L.A., Verstov, V.A.: Topological Transformation of Submicron VLSIs for Double Lithographical Mask Technology. Russian Microelectronics, 42, 6, 427--439 (2013)

8. Neris Project, http://www.eu-neris.net

9. Safecast Project, http://safecast.org

10. Zinchenko, L. A., Kureichik, V. M., Redko, V. G. et al.: Bionic Information Systems and their Practical Applications. Fizmatlit, Moscow (2011)

11. Kleinberg, J., Tardos, É.: Algorithm Design. Addison Wesley (2006)

12. De Dood, P.: Impact of DFM and RET on Standard Cell Design Methodology. In.: Proc. EDP Workshop (2003)