TRIAD: A Triple Patterning Lithography Aware\\ Detailed Router
\aufnt{Yen-Hung Lin{{$^1$
%\alignauthor %Yen-Hung~Lin
% \affaddr{Dept. of Computer Science
%As minimum size further decreases, triple patterning lithography (TPL) becomes one possible solution for further process nodes. %Moreover, utilizing TG can enlarge the amount of potential stitch positions. %Greedy approaches can solve the TPL aware routing problem but easily generate unsolvable conflicts or introduce unnecessary stitches. %To facilitate TPL conflict detection, token graph (TG) is used to compact the coloring relation among wires through a graph reduction technique. %Previous works focus on TPL layout decomposition but not on TPL friendly routing and TPL conflict detection. %Moreover, the complexity of conflict graph (CG) impedes directly detecting TPL conflicts in CG. %This work proposes a token graph-embedded conflict graph (TECG) to enable detailed routers to effectively detect TPL conflicts. %This work develops the first TPL aware detailed routing (TRIAD) by applying TECG to a gridless router with a lazy %stitch-generation routing scheme. %Experimental results indicate that TRIAD generates no conflicts and introduces few stitches with an average 0.47\% wirelength %decrement at the cost of an reasonable runtime increment. TPL-friendly detailed routers require a systematic approach to detect TPL conflicts. However, the complexity of conflict graph (CG) impedes directly detecting TPL conflicts in CG. This work proposes a token graph-embedded conflict graph (TECG) to facilitate the TPL conflict detection while maintaining high coloring-flexibility. We then develop a TPL aware detailed router (TRIAD) by applying TECG to a gridless router with the TPL stitch generation. Compared to a greedy coloring approach, experimental results indicate that TRIAD generates no conflicts and few stitches with shorter wirelength at the cost of 2.41$\times$ of runtime.
ICCAD12_TRIAD.tex
%\documentclass[]{sig-alternate}
\documentclass[9pt,conference]{IEEEtran}
%\documentclass[10pt]{IEEEtran}
%\usepackage{latexsym}
%\usepackage{fontspec}
%\usepackage{graphics}
\usepackage[dvips]{graphicx}
\graphicspath{{./}}
\DeclareGraphicsExtensions{.eps}

\usepackage{amsmath}
\usepackage{times}	
\usepackage{color}
%\usepackage[boxed]{algorithm2e}
\usepackage[caption=false,font=footnotesize]{subfig}
\usepackage{cite}
\usepackage{multirow}
\usepackage{algorithm}
\usepackage{algorithmic}
%\usepackage{amsthm}
\usepackage[english]{babel}
\usepackage{multirow}
\usepackage{booktabs}


%\renewcommand{\baselinestretch}{1}
%\setlength{\tabcolsep}{.05in}
%\newtheorem{defi}{Definition}
\newtheorem{prob}{\textbf{Problem}}
\newtheorem{define}{\textbf{Definition}}

\begin{document}
%\conferenceinfo{DAC '12,}{Jun 05-03 2012, San Francisco, California, USA}

% --- Author Metadata here ---
\conferenceinfo{IEEE/ACM International Conference on Computer-Aided Design (ICCAD) 2012,}{November 5--8, 2012, San Jose, California, USA}
\CopyrightYear{2012} % Allows default copyright year (20XX) to be over-ridden - IF NEED BE.
\crdata{978-1-4503-1573-9/12/11}  % Allows default copyright data (0-89791-88-6/97/05) to be over-ridden - IF NEED BE.
% --- End of Author Metadata ---



\title{TRIAD: A Triple Patterning Lithography Aware\\ Detailed Router}

\author{\aufnt{Yen-Hung Lin{{$^1$}},Bei Yu{{$^2$}}, David Z. Pan{{$^2$}}, and Yih-Lang Li{{$^1$}}} \\
       \affaddr{{$^1$} \aufnt{Department of Computer Science, National Chiao Tung University, Hsinchu, Taiwan}}\\
       \affaddr{{$^2$} \aufnt{Department of ECE, University of Texas at Austin, Austin, TX, USA}} \\
       \email{\aufnt{homeryenhung@gmail.com, bei@cerc.utexas.edu, dpan@ece.utexas.edu, ylli@cs.nctu.edu.tw}}
       }

%\numberofauthors{4}
%\author{
%\alignauthor
%Yen-Hung~Lin\\
 %      \affaddr{Dept. of Computer Science}\\
 %      \affaddr{National Chiao Tung University}\\
%       \affaddr{Hsinchu, Taiwan}\\
%       \email{homeryenhung@gmail.com}
% \and
% 2nd. author
%\alignauthor
%Bei~Yu\\
%       \affaddr{Dept. of ECE}\\
%       \affaddr{University of Texas at Austin}\\
%       \affaddr{Austin, TX, USA}\\
%       \email{bei@cerc.utexas.edu}
% 3rd. author
%\and
%\alignauthor 
%David~Z.~Pan\\
%       \affaddr{Dept. of ECE}\\
%       \affaddr{University of Texas at Austin}\\
%       \affaddr{Austin, TX, USA}\\
%       \email{dpan@ece.utexas.edu}
%\and  % use '\and' if you need 'another row' of author names
% 4th. author
%\alignauthor 
%\and
%Yih-Lang Li\\
%       \affaddr{Dept. of Computer Science}\\
%       \affaddr{National Chiao Tung University}\\
%       \affaddr{Hsinchu, Taiwan}\\
%       \email{ylli@cs.nctu.edu.tw}
%}

\newcommand{\MG}[1]{{\color{red}{#1}}}




\maketitle



\input{doc/abstract}


%\iffalse
%\category{B.7.2}{Hardware, Integrated Circuit}{Design Aids}
%\terms{Algorithm, Design}
%\keywords{Triple Patterning, Detailed Routing, Gridless Model}
%\fi

\input{doc/Introduction.tex}

\input{doc/Preliminaries.tex}

\input{doc/TECG.tex}

\input{doc/TPLRoute.tex}

\input{doc/Experiment.tex}

\input{doc/conclusion.tex}


\bibliographystyle{IEEEtran}
\small
\bibliography{ref/DPL,ref/TPL,ref/Routing}

%\renewcommand{\baselinestretch}{1}

%\normalsize
%\clearpage
%\renewcommand{\thesection}{S}
%\renewcommand*\thesubsection{S.{\arabic{subsection}}}
%\setcounter{subsection}{0}
%\input{doc/supplement}
%\input{doc/supplement1}

\end{document}

TPLRoute.tex
\section{TRIAD}
\label{sec:tiara}

%\textcolor[rgb]{1.00,0.00,0.00}{EXACTLY FORMULATE THE ROUTING COST!}

The TPL aware detailed router (TRIAD) focuses on accomplishing detailed routing for all given nets and generating a highly decomposable routing outcome with low yield loss.
The routing model of NEMO is adopted here \cite{Routing_Li_TCAD07}\cite{Routing_Chang_ISPD08}.
This work proposes a technique to make TECG work on the routing model of NEMO.
With the aid of TECG, TRIAD can generate stitches which cannot be generated by adopting the conventional DPL stitch generation scheme.
%Moreover, a \textit{lazy stitch-generation routing scheme} is proposed to defer the stitch generation by estimating the lower bound of stitch penalty in routing cost, which can effectively accelerate the routing process.
Therefore, TRIAD can update the routing cost based on the number of stitches and TPL conflicts.
Figure \ref{fig:flow} shows the routing flow of TRIAD.
Firstly, all multi-pin nets are decomposed into two-pin nets.
%TPL-aware routing with lazy stitch-generation scheme is applied to route all two-pin nets.
A TPL-aware routing which allows the stitch generation at the cost of increasing routing cost is applied to route all two-pin nets.
If one two-pin net is routed without any conflicts, then the layout and TECG are updated.
Otherwise, TRIAD checks whether conflicts can be generated in current iteration while TRIAD is prohibited to generate TPL conflicts in the first few iterations.
If the TPL stitch generation is not allowed, TRIAD rips up routed nets to release the routing resource and then re-routes the two-pin net.
Otherwise, the layout and the TECG are directly updated.

\begin{figure}[bt!]
	\centering
	\includegraphics[width=0.45\textwidth]{fig/flow.eps}
	\caption{Overall flow of TRIAD.}
	\label{fig:flow}
\end{figure}

\subsection{TECG on the Gridless Routing Model}
%This work designs a TECG aware routing model to enable TECG works on detailed routing.
When constructing contours for routed wire segments, TRIAD also constructs \textit{shadows} for routed wire segments presented by vertices in $\mathcal{G^C}$.
One shadow denotes the TPL effect region of its attached routed wire segment.
TRIAD constructs shadows by extending routed nets by $hw_w+sp_{tp}$.
%Figure \ref{fig:rmodel}(a) illustrates the shadow construction.
Figure \ref{fig:rmodel}(a) shows three extracted PMTs with intersected shadows.
The vertices in $\mathcal{G^C}$ attached to the corresponding shadows assist TRIAD in detecting TPL conflicts when the potential routing wire segments pass through a PMT.
The CG vertex representing the potential routing wire segment connects to the CG vertices representing routed wire segments by passing through their corresponding shadows, and the path propagation of TRIAD thus becomes aware of TPL conflicts.
Figures \ref{fig:rmodel}(b)--(d) illustrate the path propagation of TRIAD.
Figure \ref{fig:rmodel}(b) shows five routed wire segments, a PMT with three shadows, and one TECG.
In Fig. \ref{fig:rmodel}(b), one routing wire segment passes through the PMT, sequentially inserting one vertex $F$ in $\mathcal{G^C}$ and one token $T_4$ in $\mathcal{G^T}$.
The routing wire segment represented by $F$ passes through three shadows of $A$, $B$, and $C$.
Therefore, TRIAD iteratively connects $F$ to $A$, $B$, and $C$.
After connecting $F$ to $A$ and $B$, $T_1$ and $T_3$ are merged into $T_5$ as shown in Fig. \ref{fig:rmodel}(c).
In Fig. \ref{fig:rmodel}(d), TRIAD detects one TPL conflict by connecting $F$ and $C$ because $token(F)$ and $token(C)$ equal $T_5$.

\begin{figure}[bt!]
	\centering
	\subfloat[]{\includegraphics[width=0.24\textwidth]{fig/routing_model0.eps}}
	\subfloat[]{\includegraphics[width=0.24\textwidth]{fig/routing_model2.eps}}

	\subfloat[]{\includegraphics[width=0.24\textwidth]{fig/routing_model4.eps}}
	\subfloat[]{\includegraphics[width=0.24\textwidth]{fig/routing_model5.eps}}
	\caption{TECG on routing model of NEMO: (a) TRIAD constructs shadows to represent TPL effect region of routed wire segments; (b) PMT contains three shadows of three routed wire segments with TECG, and TRIAD inserts one vertex $F$ in $\mathcal{G^C}$ and a token $T_4$ in $\mathcal{G^T}$ to represent the routing wire; (c) connecting $F$ to $A$ and $B$ iteratively merges $T_3$ and $T_4$ into $T_5$; (d) TRIAD detects one coloring conflict after connecting $F$ and $C$.}
	\label{fig:rmodel}
\end{figure}

\subsection{TPL Stitch Generation Scheme}
\label{sec:tiara_stitch}

After detecting TPL conflicts, TRIAD splits one of the terminal vertices of the conflicting edge to differ the assigned token by generating stitches, if possible.
The DPL stitch generation scheme inserts one stitch in one wire when the wire contains at least one segment that is not passed by shadows of other wire segments.
\textcolor[rgb]{0.00,0.00,0.00}{
Based on the DPL stitch generation scheme, in Fig. \ref{fig:rmodel}(d), no stitch can be inserted in the routing wire segment because the routing wire segment is entirely overlapped by the shadows of routed wire segments.
However, the TPL stitch generation scheme is quite different from the DPL stitch generation scheme.}
With the assistance of TECG, TRIAD can generate stitches at the wire segment even if which is entirely passed by shadows of other wires.
\textcolor[rgb]{0.00,0.00,0.00}{
%\textbf{The tokens attached to the shadows intersecting the wire segment to be split affect the number of required stitches.}
%To solve the conflicting edge $(C, U)$, one stitch is generated by splitting $U$ into $U^1$ and $U^2$ as shown in Fig. \ref{fig:tpl_st}(b).
%However, if $token(D)$ in Fig. \ref{fig:tpl_st} is assigned to $T_1$ as shown in Fig. \ref{fig:tpl_st}(c), the edge $(D, U^2)$ in Fig. \ref{fig:tpl_st}(b) becomes conflicting.
%Therefore, an additional stitch is generated to solve the newly introduced conflicting edge by splitting $U^2$ into $U^2$ and $U^3$ as shown in Fig. \ref{fig:tpl_st}(d).
%Moreover, one token that causes conflicting edges may belong to more than one SCC.
%Therefore, TRIAD comprises a systematic algorithm to minimize the number of stitches when solving conflicting edges.
Before introducing the proposed TPL stitch generation scheme, some definitions are given in the following.}

\textcolor[rgb]{0.00,0.00,0.00}{
\begin{define}[\textbf{Shadowy Interval}]
One shadowy interval, denoted as $\varphi$, is one interval of one wire segment, and one wire segment may contain several shadowy intervals.
Let $S^T_{shd}(\varphi)$ be the set of tokens represented by the shadow set passing through $\varphi$.
For any two adjacent shadowy intervals $\varphi_i$ and $\varphi_j$,  $S^T_{shd}(\varphi_i)$ and $S^T_{shd}(\varphi_j)$ cannot be identical.
\end{define}
}

\textcolor[rgb]{0.00,0.00,0.00}{
\begin{define}[\textbf{Splittable Shadowy Interval}]
Given one wire segment \textit{w} represented by one CG vertex $v^c$ and one SCC $scc \in S^{SCC}$ containing $token(v^c)$.
Let $\varphi_{i}$ and $\varphi_j$ be two adjacent shadowy intervals of $w$.
%Given one shadowy interval $\varphi_{adj}$ adjacent to another shadowy interval $\varphi$, and one $scc \in S^{SCC} such that 
%Let $S_{sub}^{SCC}$ be a SCC set such that $t \in S_{sub}^{SCC}$ where $t \in S^T_{shd}(\varphi)$ and $S_{sub}^{SCC} \subseteq S^{SCC}$ .
One shadowy interval $\varphi_i$ is called \textit{splittable} when $|S^T_{shd}(\varphi_i) \cap S^T_{shd}(\varphi_j) \cap scc| $ is less than two.% where $\forall scc \in S_{sub}^{SCC}$. 
\end{define}
}

\textcolor[rgb]{0.00,0.00,0.00}{
\begin{define}[\textbf{Splittable CG Vertex}]
Let $V_{adj}^\mathcal{C}(v^c)$ denote the adjacent vertex set of one vertex $v^c \in V^\mathcal{C}$.
Given one SCC $scc = (token(v^c), token(v_{ad1}), token(v_{ad2})) \in S^{SCC}$ where $v^c_{ad1} \in V_{adj}^\mathcal{C}(v^c)$, $v^c_{ad2} \in V_{adj}^\mathcal{C}(v^c)$, and $v^c_{ad1} \neq v^c_{ad2}$.
%CG Vertex $v^c$ is called splittable when $v^c$ can be split into a vertex set $V^{SPLIT}$ where $\forall v^s \in V^{SPLIT}, token(v^s)$ connects to at most two tokens of $scc$ in $\mathcal{G^T}$.
One CG Vertex $v^c$ is called \textit{splittable} when $v^c$ contains a set of splittable shadowy intervals that can split $v^c$ into a CG vertex set $V^\mathcal{C}_{SPLIT}$ where $\forall v^c_s \in V^\mathcal{C}_{SPLIT}, token(v^c_s)$ connects to at most two tokens of $scc$.% in $\mathcal{G^T}$.
\end{define}
}


\begin{algorithm}[bt]
\caption{TPL Stitch Generation}
\label{alg:st_gen}
\begin{algorithmic}[1]
  \REQUIRE One CG vertex $v^c$ to be split, one CG vertex set $V^\mathcal{C}_{c}(v^c)$ adjacent to $v^c$  where $\forall v^c_{adj} \in V^\mathcal{C}_{c}(v^c), token(v^c) = token(v^c_{adj}) = T_c$, one SCC $scc$ containing $T_c$%set $S_{sub}^{SCC}$ where $\forall scc \in S_{sub}^{SCC}, T_c \in scc$
  %\STATE Set of splittable shadowy interval $S^{SPLT} := \emptyset$;
  \STATE Compute shadowy intervals $S^{splt}$ in wire segments represented by $v^c$ for $scc$;
  \FORALL{Shadowy interval $\varphi \in S^{splt}$}
    \IF{$|S^T_{shd}(\varphi)|>2$}
      %\STATE Detect one unsolvable conflict;
      \STATE Increase the routing cost by one $penalty_{unsolvable}$;
      \STATE \textbf{break};
    \ENDIF
  \ENDFOR
  \STATE $num_{st} := 0$;
  \STATE $\varphi_{st\_cand} := \varphi_{st}$ := $NULL$;
  \STATE $S^T_{passed}$ := $\emptyset$;
  \STATE Topologically sort $S^{splt}$;
  \FORALL{Shadowy interval $\varphi \in S^{splt}$}
    \IF{$|S^T_{shd}(\varphi)| = 1$}
      \STATE $\varphi_{st\_cand} := \varphi$;
    \ENDIF
    \STATE $S^T_{passed} := S^T_{passed} \cup S^T_{shd}(\varphi)$;
    \IF{$|S^T_{passed}| > 2$}
     \STATE Generate one stitch at $\varphi_{st\_cand}$;
     \STATE $++num_{st}$;
     \STATE $S^T_{passed} := \emptyset$;
     \FORALL{Shadowy interval $\varphi_{passed}$ between $\varphi$ and $\varphi_{st}$}
       \STATE $S^T_{passed} := S^T_{passed} \cup S^T_{shd}(\varphi_{passed})$;
     \ENDFOR
     \STATE $\varphi_{st} := \varphi_{st\_cand}$;
    \ENDIF
  \ENDFOR 
  \STATE Increase the routing cost by $num_{st} \times penalty_{st}$;
\end{algorithmic}
\end{algorithm}



%There may exist more than one SCC in $S^{SCC}$ containing $T_c$.
One wire segment to be split represented by one CG vertex $v^c$ may contain several splittable shadowy intervals for one SCC.
Generating stitches at all splittable shadowy intervals introduces unnecessary stitches, sequentially degrading the yield.
To minimize the number of required stitches, the TPL stitch generation algorithm is proposed in Algorithm \ref{alg:st_gen}.
All shadowy intervals $S^{splt}$ in wire segments represented by $v^c$ are firstly computed (line 1).
%One unsolvable conflict is detected when one shadowy interval is passed by more than two shadows (lines 2--6), indicating that 
%Splitting one wire segment with one shadowy interval passed by more than two shadows cannot solve the conflicting edge because two adjacent CG vertices must be assigned to the same token (lines 2--6).
One conflicting edge cannot be solved by splitting one wire segment with one shadowy interval passed by more than two shadows because two adjacent CG vertices must be assigned to the same token after splitting.
After detecting one unsolvable conflicting edge, the routing cost is directly increased by one unsolvable penalty $penalty_{unsolvable}$ (lines 2--7).
One token set $S^T_{passed}$ is initially set as empty (line 10).
Before generating stitches based on $S^{splt}$, $S^{splt}$ is firstly topologically sorted (line 11), followed by sequentially checking the shadowy interval $\varphi \in S^{splt}$.
If $|S^T_{shd}(\varphi)|$ equals one, $\varphi$ is recorded as the potential position $\varphi_{st\_cand}$ to generate one stitch (lines 13--15).
Inserting $S^T_{shd}(\varphi)$ into $S^T_{passed}$ (line 16) may cause $|S^T_{passed}|$ to exceed two, requiring generating one stitch at $\varphi_{st\_cand}$ (lines 17--19).
Then $S^T_{passed}$ is set as empty, and the tokens attached to shadows passing through the shadowy intervals between $\varphi_{st}$ and $\varphi$ are inserted into $S^T_{passed}$ (lines 20--23).
Finally, $\varphi_{st}$ is set as $\varphi_{st\_cand}$ to record the latest stitch position (line 24).
After all shadowy intervals in $S^{splt}$ are checked, the routing cost is increased based on the number of generated stitches (line 27).
Notably, the token $T_c$ that causes conflicting edges may belong to more than one SCC.
Therefore, Algorithm \ref{alg:st_gen} is applied to each SCC that contains $T_c$ to generate necessary stitches.


Figures \ref{fig:tpl_st}(a) and \ref{fig:tpl_st}(c) show a small part of one TECG where CG vertices $A, B, C, D$ and $U$ represent four routed wire segments and one routing wire segment, respectively.
Notably, $token(A)$ equals $T_1$; $token(B)$ and $token(D)$ equal $T_2$/$T_1$; and $token(C)$ and $token(U)$ equal $T_3$ in Fig. \ref{fig:tpl_st}(a)/(c).
The routing wire segment in Fig. \ref{fig:tpl_st} contains seven shadowy intervals $\varphi_1, \varphi_2, \cdots,$ and $\varphi_7$, and Algorithm \ref{alg:st_gen} generates stitches by sequentially checking these shadowy intervals.
In Fig. \ref{fig:tpl_st}(a), $|S^T_{passed}|$ equals three when checking $\varphi_4$, resulting in generating one stitch at $\varphi_3$ as shown in Fig. \ref{fig:tpl_st}(b).
However, if $token(D)$ is assigned to $T_1$ as shown in Fig. \ref{fig:tpl_st}(c), the edge $(D, U^2)$ in Fig. \ref{fig:tpl_st}(b) becomes conflicting.
Similarly, for the TECG in Fig. \ref{fig:tpl_st}(c), one stitch is generated in $\varphi_3$ as shown in Fig. \ref{fig:tpl_st}(d) followed by setting $S^T_{passed}$ as $\{T_2, T_3\}$.
When checking $\varphi_7$, $S^T_{passed}$ equals $\{T_1, T_2, T_3\}$, requiring generating another stitch at $\varphi_5$ as shown in Fig. \ref{fig:tpl_st}(d).
To solve the conflicting edge in Fig. \ref{fig:rmodel}(d), one stitch is generating at the routing wire segment by splitting $F$ into $F^1$ and $F^2$ as shown in Fig. \ref{fig:tpl_st}(e).
%The routing cost is increased by one stitch penalty.


\begin{figure}[bt!]
	\centering
	\subfloat[]{\includegraphics[width=0.24\textwidth]{fig/st_1_bf.eps}}
	\subfloat[]{\includegraphics[width=0.24\textwidth]{fig/st_1_af.eps}}
	
	\subfloat[]{\includegraphics[width=0.24\textwidth]{fig/st_2_bf.eps}}
	\subfloat[]{\includegraphics[width=0.24\textwidth]{fig/st_2_af.eps}}

	\subfloat[]{\includegraphics[width=0.24\textwidth]{fig/stitch_generation.eps}}
	\caption{\textcolor[rgb]{0.00,0.00,0.00}{Example of TPL stitch generation schemes: (a)(c) DPL stitch generation scheme cannot insert any stitch; (b) generating one stitch can solve the conflict edge in (a); (d) generating two stitch can solve the conflict in (c); (e) TPL stitch generation of Fig. \ref{fig:rmodel}(d).}}
	\label{fig:tpl_st}
\end{figure}

%\subsection{Lazy Stitch-Generation Routing Scheme}
%\textcolor[rgb]{1.00,0.00,0.00}{
%\textbf{Q1. Table2 shows that there is only up to 1 stitch needed in each testcase! 
%Develop another algorithm that does not adopt lazy stitch generation to show its efficiency!}
%}
%
%
%\textcolor[rgb]{0.00,0.00,1.00}{
%TRIAD explores all potential solutions to accomplish detailed routing while stitch generation is one means to solve coloring conflicts.
%The efficiency of TRIAD is significantly affected by the times of stitch generation.
%For a two-pin net to be routed, it takes $m$ propagations to find a feasible connection from the source pin to the target pin without any stitches, and back-trace stage determines the exact wire segments by back tracing $n$ propagations.
%Assume that $(m-n)$ propagations detect coloring conflicts, sequentially requiring generating stitches to solve coloring conflicts in each propagation.
%As introduced in Section \ref{sec:tiara_stitch}, stitches are generated according to the intersected shadows.
%Therefore, the runtime of TRIAD could be dramatically increased by generating \textit{potential stitches} after detecting coloring conflict in each propagation.
%}
%
%
%To accelerate the routing process, \textit{lazy stitch-generation routing scheme} is proposed as shown in Algorithm \ref{alg:routing_scheme}.
%%After conflicts are detected in routing stage, \textit{pseudo stitch generation} is applied to estimate the lower bound of routing cost according to the number of conflicts, indicating the number of potential stitches (lines 19--22).
%\textcolor[rgb]{0.00,0.00,1.00}{
%%Solving one conflict requires at least one stitch by splitting one wire segment.
%Ideally, splitting one potential routing wire segment into two parts can solve all conflicts caused by this wire segment.
%Figure \ref{fig:ideal_stitch}(a) depicts that one potential routing wire segment represented by an undetermined vertex $D$ causes $n$ conflicts, and splitting $D$ into $D^1$ and $D^2$ by generating one stitch can solve all conflicts.
%\textit{Pseudo stitch generation} directly increases the routing cost by one stitch penalty to indicate that the detected conflicts can be ideally solved (lines 19--22).
%}
%\textit{True stitch generation} is postponed until the min-cost path $p$ contains any \textit{unsolved} conflict where stitches are practically generated according to the shadows of adjacent wire segments in terms of the connectivity of CG.
%In true stitch generation, 
%Then, the routing cost of $p$ is updated based on the number of stitches and unsolvable conflicts, followed by inserting $p$ into $H_p$ (lines 6--12).
%
%\begin{figure}[bt!]
%	\centering
%	\subfloat[]{\includegraphics[width=0.24\textwidth]{fig/ideal_stitch_bf.eps}}
%    %\hspace{0.005\textwidth}
%    \subfloat[]{\includegraphics[width=0.24\textwidth]{fig/ideal_stitch_af.eps}}
% 	\caption{Example of ideal stitch generation: (a) Undetermined vertex $D$ causes $n$ conflicts; (b) splitting $D$ into $D^1$ and $D^2$ can solve all conflicts.}
%	\label{fig:ideal_stitch}
%\end{figure}
%
%\begin{algorithm}[bt!]
%\caption{Lazy Stitch-Generation Routing Scheme}
%\label{alg:routing_scheme}
%\begin{algorithmic}[1]
%  \REQUIRE Two features $seg_{src}$ and $seg_{tar}$ to be connected
%  \STATE Path heap $H_p := \emptyset$;
%  \STATE Generate one path $p_{src}$ by $seg_{src}$;
%  \STATE Insert $p_{src}$ into $H_p$;
%  \WHILE{$H_p$ is non-empty}
%    \STATE Extract min-cost path $p$ from $H_p$;
%    \IF{$p$ contains \textit{unsolved} conflict $CE$}
%      \STATE Identify unsolvable conflict set $UCE \subset CE$;
%      \STATE Generate $m$ stitches to solve $\{{CE - UCE}\}$;
%      \STATE Increase routing cost of $p$ by $(m-1) \times cost_{stitch} + |UCE| \times cost_{conflict}$;
%      \STATE Insert $p$ into $H_p$;
%      \STATE \textbf{continue};
%    \ENDIF
%    \IF{$p$ contains $seg_{tar}$}
%      \STATE Back trace from $p$ to $p_{src}$ to determine the final routing wire segments;
%      \STATE \textbf{break};
%    \ENDIF
%    \FORALL{Adjacent routing unit of $p$}
%      \STATE Generate path $p_{ch}$;% with a CE set $CE_{ch}$, if any;
%      \IF {$p_{ch}$ detects a conflict set $CE_{ch}$}
%        \STATE Mark $p_{ch}$ containing $|CE_{ch}|$ unsolved conflicts;
%        \STATE Increase routing cost of $p_{ch}$ by $cost_{stitch}$;
%      \ENDIF
%      \STATE Insert $p_{ch}$ into $H_p$;
%    \ENDFOR
%  \ENDWHILE
%\end{algorithmic}
%\end{algorithm}


%\subsection{Coloring Assignment}
%Subsection text here. 

Experiment.tex
\section{Experimental Results}
\label{sec:experiment}


\begin{table}[bt!]
\centering
\caption{Statistics of benchmarks}
\label{tb:stat}
\begin{tabular}{|c||c|c|c|c|c|}
%\toprule [0.12em]
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
 \hline
 \multirow{2}{*}{Circuit} & \multirow{2}{*}{Size $(\mu m^2)$} &   \#    &   \#   &   \# 2Pin  &   \# \\
                         &                                 & Layer &    Net &    Net &   Pin \\
  \hline
  \hline
  s5378    & 217.5 $\times$ 119.5 & 3 & 1694 & 3124 & 4818 \\
  \hline
  s9234    & 202.0 $\times$ 112.5 & 3 & 1486 & 2774 & 4260 \\
  \hline
  s13207   & 330.0 $\times$ 182.5 & 3 & 3781 & 6995 & 10776 \\
  \hline
  s15850   & 352.5 $\times$ 194.5 & 3 & 4472 & 8321 & 12793 \\
  \hline
  s38417   & 572.0 $\times$ 309.5 & 3 & 11309 & 21035 & 32344 \\
  \hline
  s38584   & 647.5 $\times$ 336.0 & 3 & 14754 & 28177 & 42931 \\
  \hline
%\bottomrule [0.16em]
\end{tabular}
\end{table}

\begin{table*}[t]
\centering
\caption{Comparison between wirelength, stitches, conflicts, and runtime of the greedy approach (GREED) and TRIAD}
\label{tb:result}
\begin{tabular}{|c||c|c||c|c||c|c||c|c|}
%\toprule [0.12em]
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  \hline
   \multirow{2}{*}{Circuit} &  \multicolumn{2}{|c||}{ Wirelength ($nm$)} & \multicolumn{2}{|c||}{\# Stitch} & \multicolumn{2}{|c||}{\# Conflict} & \multicolumn{2}{|c|}{Runtime (\textit{s.})} \\
  \cline{2-9}
     & GREEDY & DPLAG & GREEDY & DPLAG & GREEDY & DPLAG & GREEDY & DPLAG \\
  \hline
  \hline
  s5378    & 382900 & 381170 & 165 & 0 & 0 & 0 & 9.47 & 14.36  \\
  \hline
  s9234    & 286503 & 284608 & 157 & 0 & 1 & 0 & 8.62 & 9.78  \\
  \hline
  s13207   & 910055 & 903705 & 405 & 1 & 2 & 0 & 25.38 & 49.11  \\
  \hline
  s15850   & 1131665& 1124715   & 371 &  0  & 2 &  0  & 40.83 & 95.80 \\
  \hline
  s38417   & 2457675& 2461940 & 1528 & 0 & 3 & 0 & 122.7 & 443.75 \\
  \hline
  s38584   & 3211985& 3204160   &   1264  &  2   &  2  &   0  &  168.97  &  660.38 \\
  \hline \hline
  Ave. &  100\% &  99.46\%   &  560.67  &  0.50  &  -  &  -  &  1   &  2.41\\
  \hline
%  \bottomrule [0.16em]
\end{tabular}
\end{table*}


%\textcolor[rgb]{1.00,0.00,0.00}{
%Q3.48577. The other issue with the paper is that the routing algorithm does not seem to be scalable. It takes much longer time to solve the largest testcase while they are still quite small.
%A3.1 Show these cases are hard to be routed even if they are small!
%A3.2 Speed up the algorithm!
%}

\textcolor[rgb]{0.00,0.00,0.00}{
The algorithm herein was implemented in C++ language on a workstation with 4-Core 2.4 GHz CPU and 82GB memory.}
A total six benchmarks \cite{Routing_MARS} are adopted in this work.
We scale all benchmarks, including routing area and features size, to approach the target process node.
Table \ref{tb:stat} shows the corresponding statistics.
\textcolor[rgb]{0.00,0.00,0.00}{
The minimum resolution (half-pitch) for pushing the 193\textit{nm} lithography's single exposure limit is around 40\textit{nm}. 
Thus, to print 20\textit{nm} half-pitch, we need double patterning, and to print 10\textit{nm} half-pitch, we need quadruple patterning.
The minimum coloring spacing for single exposure lithography is fixed, i.e., around 40\textit{nm}.
The purpose of multiple patterning is to push for smaller resolution (half-pitch). 
Therefore, to the first order, the minimum coloring spacing would be \textit{n} times minimum wire spacing (i.e., half-pitch) of the \textit{n} patterning lithography.
The minimum coloring spacing $sp_{tp}$ is set as three times of the minimum wire spacing.
}

%This is the first work on TPL aware detailed routing.
As there is no other TPL aware router published, to demonstrate the effectiveness of the proposed algorithm, a greedy approach (GREED) is developed based on TRIAD for comparison.
GREED only contains three colors for each layer and greedily determines the colors of routing wire segments.
In GREED, the colors of routed wire segments are fixed.
GREED adopts the same routing flow of TRIAD without TECG.
%, and the graph reduction of TECG is not applied to the greedy approach.
%The tokens of vertices in CG representing routed wire segments are fixed.
%When one vertex in CG is generated to represent one routing wire segment, its token is greedily determined.
Notably, TRIAD and GREED are prohibited to generate conflicts in the first fifteen iterations for fair comparison.
Table \ref{tb:result} shows the wirelength, the number of stitches (\# Stitch), the number of unsolvable conflicts (\# Conflict), and runtime of GREED and TRIAD.
\textcolor[rgb]{0.00,0.00,0.00}{
TRIAD produces no conflicts in all cases and only introduces one and two stitches in $s13207$ and $s38548$, respectively, while GREED only generates conflict-free results in one case with total 3890 stitches.
Moreover, the average wirelength of TRIAD is less than that of GREED by 0.54\% because GREED has to detour the routed colored wire segments to avoid generating TPL conflicts.
Thus, GREED requires more detours than TRIAD does.
Compared to GREED, TRIAD can generate conflict-free results in all cases at the cost of an average 2.41$\times$ of runtime.
For the largest case $s38584$, the runtime of TRIAD is less than four times of that of GREED.}
The most runtime spends of the graph reduction which provides TRIAD high coloring-flexibility to generate TPL-friendly results.

Preliminaries.tex
\section{Preliminaries and Problem Formulation}
\label{sec:preliminaries}

\subsection{Conflict Graph}
Kahng \textit{et al.} \cite{DPL_Kahng_TCAD10} first adopted a conflict graph (CG) to maintain the relationship among wire segments for the DPL layout decomposition.
A vertex in one CG represents one wire segment in a layout.
An edge between two vertices, $v_i$ and $v_j$, in one CG is generated when the minimum spacing between the wire segments represented by $v_i$ and $v_j$ is smaller than minimum coloring spacing, denoted as $sp_{dp}$.
One DPL coloring conflict occurs when there is an odd number of connected vertices in a cycle in one CG.
%, referred to as conflict cycle.
%Figure \ref{fig:cg}(a) the conflict graph of the layout while Fig. \ref{fig:DPL}(a).
%In Fig. \ref{fig:cg}(a), the bold lines represent a conflict cycle, and \textit{node splitting} is applied at the cost of generating one stitch to solve the conflict cycle, as shown in Fig. \ref{fig:cg}(b).
%However, the inability of node splitting to identify a wire segment satisfying overlay margin in a conflict cycle results in an unresolvable conflict cycle.
%After generating one stitch, the layout can be colored as shown in Fig \ref{fig:DPL}(b).

%\begin{figure}[bt]
%	\centering
%	\subfloat[]{\includegraphics[height=0.08\textheight]{fig/org_cg1.eps}}
%    \hspace{0.1\textwidth}%
%	\subfloat[]{\includegraphics[height=0.08\textheight]{fig/org_cg2.eps}}
%	\caption{Conflict Graph: (a) conflict graph of layout in Fig. \ref{fig:DPL}(a); (b) node splitting.}
%	\label{fig:cg}
%\end{figure}

%Lin and Li \cite{DPL_Lin_DAC10} proposed an \textit{innovative conflict graph} (ICG) based on \cite{DPL_Kahng_TCAD10} to enable detailed routers to escape the suboptimum of coloring caused by a greedy assignment.
%ICG contains \textit{determined} and \textit{undetermined vertices} to represent routed and routing wire segments, respectively.
%An edge in ICG indicates the spacing of the wire segments represented by its terminal vertices is smaller than $sp_dp$.
%Notably, there are \textit{determined} and \textit{undetermined edges} in ICG to represent the DPL relation between routed/routing and routed/routed wire segments.
%Each determined vertex is assigned a pseudo color to represent the potential color.
%An ICG comprises several innovative conflict subgraphs (ICSGs), and two ICSGs have no determined and undetermined edges between them.
%An odd-length cycle in ICG indicates a coloring conflict.
%Figure \ref{fig:icg} shows a routing result and its ICG where solid/dashed border rectangles represent routed/routing wires, solid/dashed border circles represent determined/undetermined vertices, and solid/dashed lines represent determined/undetermined edges.
%Each determined vertex is assigned a pseudo color to represent the potentially final color.

%\begin{figure}[bt]
%	\centering
%	\subfloat[]{\includegraphics[width=0.19\textwidth]{fig/ICG_layout.eps}}
%    \hspace{0.08\textwidth}
%	\subfloat[]{\includegraphics[width=0.16\textwidth]{fig/ICG.eps}}
%	\caption{Example of ICG \cite{DPL_Lin_DAC10}: (a) layout contains three routed wires and one routing wire; (b) ICG of (a).}
%	\label{fig:icg}
%\end{figure}

\subsection{Routing Model}
The detailed routing can be classified into grid-based one and gridless one based on the utilized routing models.
%Lee algorithm \cite{Routing_LEE} is the most well known routing method to find a connection from a source point to a target point.
%Lee algorithm-based routers contain two main stages for each route: \textit{propagation} and \textit{retracing}.
%In the propagation stage, the router iteratively explores adjacent routing units to approach the target point.
%Each propagation step also records the routing cost.
%After reaching the target point, the routing connection is generated by retracing the propagation order on the grid map.
While utilizing the routing resources in a dense layout better than the conventional grid-based routers do, the gridless routers construct more complex data structures than grid-based routers owing to the ability to accommodate the routing rules in the routing graph.
Besides, to fit the demand of regular layout designs, gridless routers can also generate on-grid routing wires with an on-grid feature.
Two conventionally adopted gridless routers are tile-based one and implicit connection graph-based one, which possess the advantages of low path propagation complexity and fast routing graph construction, respectively \cite{Routing_TILER} \cite{Routing_DUNE}.

NEMO \cite{Routing_Li_TCAD07}\cite{Routing_Chang_ISPD08} is an implicit connection graph-based router with both the benefits of tile-based and implicit connection graph-based routers.
%NEMO deals with tile propagation on a non-uniform grid map.
%For each net, NEMO constructs a routing graph.
Before each routing, NEMO expands each obstacle and routed net by half of a wire width $hw_w$ and one wire spacing $sp_w$ to generate contours as shown in Fig. \ref{fig:nemo}(a).
NEMO constructs the implicit connection graph by extracting all borders of contours (the dotted lines in Fig. \ref{fig:nemo}(b)).
In the propagation stage, NEMO performs the path propagation by identifying the adjacent \textit{pseudo-maximum horizontally/vertically stripped tiles} (PMTs) of the last PMT in the minimum-cost path and then expanding the connected PMT list.
The path propagation is repeated until the PMT containing the target is reached.
Accordingly, NEMO generates routing wire segments by retracing the routing result and then places new wire segments on the layout.
In Fig. \ref{fig:nemo}(b), three PMTs are passed from $S$ to $T$, and NEMO traces them to construct the final routing result.
%Figure \ref{fig:nemo} illustrates an example of constructing a routing graph.
%NEMO expands all routed nets by $hw_w+sp_w$ to generate contours as shown in Fig. \ref{fig:nemo}(a).
%The routing graph is then constructed as shown in the dashed lines of Fig. \ref{fig:nemo}(b).


\begin{figure}[bt]
	\centering
	\subfloat[]{\includegraphics[width=0.23\textwidth]{fig/NEMO1.eps}}
    \hspace{0.01\textwidth}
	\subfloat[]{\includegraphics[width=0.23\textwidth]{fig/NEMO2.eps}}
	\caption{Routing graph construction of NEMO \cite{Routing_Li_TCAD07}\cite{Routing_Chang_ISPD08}: (a) contour generation for each routed wire; (b) routing graph construction and PMT extraction.}
	\label{fig:nemo}
\end{figure}

\subsection{Problem Formulation}
%\textit{\textbf{TPL aware detailed routing problem}: A triple-patterning spacing $sp_{tp}$ indicates that two wire segments need to be assign to different masks when their spacing is smaller than $sp_{tp}$. Given a netlist and $sp_{tp}$, detailed routing is performed to minimize the number of stitches and coloring conflicts.}

\begin{prob}[\textbf{TPL Aware Detailed Routing Problem}]
The minimum coloring spacing of TPL $sp_{tp}$ indicates that two wire segments need to be assigned to different masks when their spacing is smaller than $sp_{tp}$.
Given a netlist and $sp_{tp}$, the detailed routing for all nets is performed to minimize the number of stitches and TPL conflicts.
\end{prob} 
supplement.tex
\section{Supplemental Material}


\subsection{Details of Detailed Routing}
 Lee algorithm \footnote{\small{C. Y. Lee, "An Algorithm for Path Connection and its Application," \textit{IRE Trans. on Electronic Computers}, EC-10, 1961.}} is the most well known routing method to find a connection from a source point to a target point.
 Lee algorithm-based routers contain two main stages for each route: \textit{propagation} and \textit{retracing}.
 In the propagation stage, the router iteratively explores adjacent routing units to approach the target point.
 Each propagation step also records the routing cost.
 After reaching the target point, the routing connection is generated by retracing the propagation order on the grid map.

\subsection{Innovative Conflict Graph}
Lin and Li \cite{DPL_Lin_DAC10} proposed an \textit{innovative conflict graph} (ICG) based on \cite{DPL_Kahng_TCAD10} to enable detailed routers to escape the suboptimum of coloring caused by a greedy assignment.
ICG contains \textit{determined} and \textit{undetermined vertices} to represent routed and routing wire segments, respectively.
An edge in ICG indicates the spacing of the wire segments represented by its terminal vertices is smaller than $sp_dp$.
Notably, there are \textit{determined} and \textit{undetermined edges} in ICG to represent the DPL relation between routed/routing and routed/routed wire segments.
Each determined vertex is assigned a pseudo color to represent the potential color.
An ICG comprises several innovative conflict subgraphs (ICSGs), and two ICSGs have no determined and undetermined edges between them.
An odd-length cycle in ICG indicates a coloring conflict.
Figure \ref{fig:icg} shows a routing result and its ICG where solid/dashed border rectangles represent routed/routing wires, solid/dashed border circles represent determined/undetermined vertices, and solid/dashed lines represent determined/undetermined edges.
Each determined vertex is assigned a pseudo color to represent the potentially final color.
This work adopts the concept of ICG to implement the insertion of vertices and edges in TECG caused by routing wire segments.

\begin{figure}[h]
	\centering
	\subfloat[]{\includegraphics[width=0.18\textwidth]{fig/ICG_layout.eps}}
    \hspace{0.04\textwidth}
	\subfloat[]{\includegraphics[width=0.18\textwidth]{fig/ICG.eps}}
	\caption{Example of ICG: (a) layout contains three routed wires and one wire to be routed; (b) ICG of (a).}
	\label{fig:icg}
\end{figure}

Introduction.tex
\section{Introduction}


As manufacturing process node enters the nano-meter era, the gap between the illumination wavelength of 193\textit{nm} and the target process node becomes increasingly larger.
The semiconductor industry encounters the limitation of manufacturing sub-22\textit{nm} due to the delay of the next generation lithograph (NGL) such as extreme ultraviolet (EUV) and E-beam direct write \cite{Du2012}.
To bridge the gap, double patterning lithography (DPL) is adopted, which decomposes a single layer into two masks (colors) to increase the pitch and enhance the resolution \cite{Kahng_SSDRC_07}.

%DPL introduction
Deploying DPL involves two challenges.
\textit{Layout decomposition} requires assigning two features to opposite colors (masks) if their spacing is less than a specific spacing, denoted as $sp_{dp}$.
One \textit{coloring conflict} occurs when two features whose spacing is less than $sp_{dp}$ cannot be assigned to different masks.
\textit{Stitch generation}, as the second challenge, is used to solve the coloring conflicts at the cost of yield loss due to the high sensitivity of stitches due to the overlay error.
However, some coloring conflicts cannot be solved even after the stitch generation, e.g., native conflicts.
Figure \ref{fig:DPL} shows that one un-decomposable layout (Fig. \ref{fig:DPL}(a)) becomes decomposable after generating one stitch (Fig. \ref{fig:DPL}(b)).
Figure \ref{fig:DPL}(c) depicts one layout containing native conflicts in which the spacing between arbitrary two features is less then $sp_{dp}$.




%TPL introduction
To further shrink the process nodes below 22\textit{nm}, the paradigm of DPL can be extended to the triple patterning lithography (TPL) to compensate the delay of NGL.
If single exposure half-pitch is about 40\textit{nm}, the 193\textit{nm} lithography could be used to manufacture the 11\textit{nm} process node \cite{TPL_Yan_SW}.
Compared to DPL, TPL contains one additional mask and can easily solve the native conflicts of DPL.
In the example of Fig. \ref{fig:DPL}(c), TPL assigns the three features to three masks, respectively.


%Introduce TPL related works on layout decomposition
Successfully carrying out the layout decomposition requires layouts containing no native conflicts.
Considering DPL in the layout synthesis, especially in the detailed routing stage, facilitates generating layouts without native conflicts.
Cho \textit{et al.} \cite{DPL_Cho_ICCAD08} developed the first DPL-friendly detailed routing approach which greedily determined the masks of routed wire segments to avoid generating layouts with native conflicts.
Gao and Macchiarulo \cite{DPL_Gao_DATE2010} proposed lazy color decision and last conflict segment recording to enhance the DPL-aware detailed routing based on \cite{DPL_Cho_ICCAD08}.
Lin and Li \cite{DPL_Lin_DAC10} developed a deferred coloring assignment-based gridless detailed routing flow to escape from the suboptimum that may be reached by adopting the greedy coloring strategy.
Yuan and Pan \cite{DPL_WISDOM} spread wires to simultaneously minimize the number of conflicts and stitches, while introducing as less the layout perturbation as possible.
On TPL, previous researches only focus on the layout decomposition.
Cork \textit{et al.} \cite{TPL_Cork} applied a SAT solver to decompose layouts into three colors.
Bei \textit{et al.} \cite{TPL_Bei_ICCAD11} proposed a novel vector programming formulation for TPL decomposition and applied a semidifinite programming (SDP) to solve the problem effectively.
Chen \textit{et al.} \cite{TPL_LD_SATP} and Mebarki \textit{et al.} \cite{TPL_LD_Mebarki} proposed a self-aligned triple patterning (SATP) process to extend the 193\textit{nm} immersion lithography to half-pitch 15\textit{nm} patterning.

\begin{figure}[b!]
	\centering
	\subfloat[]{\includegraphics[height=0.09\textheight]{fig/DPLLayout.eps}}
    \hspace{0.04\textwidth}
	\subfloat[]{\includegraphics[height=0.09\textheight]{fig/DPLDecomposedLayout.eps}}
	\hspace{0.08\textwidth}
    \subfloat[]{\includegraphics[height=0.09\textheight]{fig/DPL3.eps}}
	\caption{Challenges of DPL: (a) layout cannot be directly decomposed into two masks; (b) layout becomes decomposable after splitting one feature by generating one stitch; (c) layout contains native conflict.}
	\label{fig:DPL}
\end{figure}

Similar to DPL, generating TPL-friendly layouts, especially in the detailed routing stage, becomes urgent as TPL is being considered and adopted in the industry \cite{Lucas2012}.
Generating TPL-friendly layouts is more difficult than the TPL layout decomposition while the TPL decomposition has been shown as a NP-complete problem \cite{TPL_Bei_ICCAD11}.
The DPL coloring conflicts can be easily detected by finding an odd-length cycle in a conflict graph (CG) \cite{DPL_Kahng_TCAD10}\cite{DPL_Lin_DAC10}\cite{DPL_Gao_DATE2010}, which cannot be applied to detect TPL coloring conflicts.
The greedily coloring approach such as \cite{DPL_Cho_ICCAD08} can be directly applied to generate TPL-friendly layouts.
However, greedily determining the colors of routed wire segments significantly sacrifices the flexibility of coloring assignment, which may result in generating native conflicts and introducing unnecessary stitches.
Moreover, the complexity of CG impedes directly detecting TPL coloring conflicts with high flexibility of coloring assignment in one CG.
Figure \ref{fig:motivation}(a) depicts one layout with eight features.
One greedy coloring approach sequentially colors features ($A$, $B$, $C$, $D$, $E$, $F$, $G$, $H$) in Fig. \ref{fig:motivation}(a) with colors ($c_1$, $c_2$, $c_3$, $c_1$, $c_2$, $c_3$, $c_1$, $c_2$).
Figure \ref{fig:motivation}(b) displays the coloring result, in which $G$ and $H$ become un-colorable.
Nevertheless, the layout can be colored without any un-colorable feature as shown in Fig. \ref{fig:motivation}(c).
Therefore, a TPL conflict detection with \textit{high coloring-flexibility} and \textit{low detection-complexity} is desired in a correct-by-construction approach.

\begin{figure}[bt]
	\centering
	\subfloat[]{\includegraphics[width=0.14\textwidth]{fig/motivation_layout.eps}}
    \hspace{0.02\textwidth}
	\subfloat[]{\includegraphics[width=0.14\textwidth]{fig/motivation_greedy.eps}}
	\hspace{0.02\textwidth}
    \subfloat[]{\includegraphics[width=0.14\textwidth]{fig/motivation_opt.eps}}
	\caption{Effects of coloring ordering to TPL coloring result: (a) layout contains eight features; (b) sequentially coloring ($A$, $B$, $C$, $D$, $E$, $F$, $G$, $H$) with colors ($c_1$, $c_2$, $c_3$, $c_1$, $c_2$, $c_3$, $c_1$, $c_2$) causes $G$ and $H$ un-colorable; (c) coloring result without conflicts exists.}
	\label{fig:motivation}
\end{figure}

% Summarize the contributions of this work
In this work, a \textit{token graph-embedded conflict graph} (TECG), comprising a token graph (TG) and a conflict graph (CG), is proposed to enable detailed routers to generate TPL-friendly layouts by a correct-by-construction approach.
One TG is used to maintain the coloring relation among different vertex sets in one CG.
In one TG, one \textit{strictly colored component} (SCC) is constructed to fix the coloring relation among certain vertex sets in one CG.
We apply the proposed TECG to a detailed routing model \cite{Routing_Li_TCAD07}\cite{Routing_Chang_ISPD08} to implement a \textit{triple patterning lithography aware detailed router} (TRIAD).
During the path searching, TRIAD adopts the TECG to detect if any TPL conflict occurs by the current routing wire segment.
After detecting solvable TPL conflicts, TRIAD utilizes the TECG to generate stitches in wire segments.
\textcolor[rgb]{0.00,0.00,0.00}{
With the assistance of TECG, TRIAD can generate stitches which cannot be generated by adopting the conventional DPL stitch generation scheme.
}
Notably, the TPL stitch generation scheme can split one wire segment into several segments even when the wire is entirely intersected by the TPL effect regions of other wire segments.
%Moreover, a \textit{lazy stitch-generation routing scheme} is proposed to accelerate the routing process when TPL conflicts are detected.
%After detecting TPL conflicts, the routing cost is directly increased by the number of TPL conflicts times the stitch penalty cost to indicate the lower bound of stitch cost.
%The true stitch generation is postponed until the path searching with TPL conflicts has the minimum routing cost.


The main contribution of this paper is to realize a TPL aware detailed router TRIAD with the following two novel techniques:
\begin{itemize}
	\item A TECG is proposed to assist detailed routers in detecting the TPL conflicts in a correct-by-construction approach while keeping high coloring-flexibility.
    %\item The first TPL aware detailed router TRIAD is implemented.
    \item A TPL stitch generation scheme is proposed to generate stitches which may not be generated by adopting the conventional DPL stitch generation scheme.
    %\item Lazy stitch-generation routing scheme is proposed to accelerate routing process.
    %\item Coloring assignment after detailed routing to minimize the number of stitches and coloring conflicts.
\end{itemize}


The remainder of the paper is organized as follows: Section \ref{sec:preliminaries} presents the basic concepts and the problem formulation.
Sections \ref{sec:TECG} and \ref{sec:tiara} introduce the proposed TECG and TRIAD, respectively.
Next, Section \ref{sec:experiment} summarizes the experimental results.
Brief conclusions are drawn in Section \ref{sec:conclusion}. 
abstract.tex
\begin{abstract}

%As minimum size further decreases, triple patterning lithography (TPL) becomes one possible solution for further process nodes.
%Moreover, utilizing TG can enlarge the amount of potential stitch positions.

%Greedy approaches can solve the TPL aware routing problem but easily generate unsolvable conflicts or introduce unnecessary stitches.
%To facilitate TPL conflict detection, token graph (TG) is used to compact the coloring relation among wires through a graph reduction technique.

%Previous works focus on TPL layout decomposition but not on TPL friendly routing and TPL conflict detection.
%Moreover, the complexity of conflict graph (CG) impedes directly detecting TPL conflicts in CG.
%This work proposes a token graph-embedded conflict graph (TECG) to enable detailed routers to effectively detect TPL conflicts.
%This work develops the first TPL aware detailed routing (TRIAD) by applying TECG to a gridless router with a lazy %stitch-generation routing scheme.
%Experimental results indicate that TRIAD generates no conflicts and introduces few stitches with an average 0.47\% wirelength %decrement at the cost of an reasonable runtime increment.

TPL-friendly detailed routers require a systematic approach to detect TPL conflicts.
However, the complexity of conflict graph (CG) impedes directly detecting TPL conflicts in CG.
This work proposes a token graph-embedded conflict graph (TECG) to facilitate the TPL conflict detection while maintaining high coloring-flexibility.
We then develop a TPL aware detailed router (TRIAD) by applying TECG to a gridless router with the TPL stitch generation.
Compared to a greedy coloring approach, experimental results indicate that TRIAD generates no conflicts and few stitches with shorter wirelength at the cost of 2.41$\times$ of runtime.

\end{abstract} 
TECG.tex
\section{TECG}
\label{sec:TECG}
One conflict graph (CG) is used to maintain the \textit{physical} coloring relations among all wire segments.
The higher routed ratio, the higher complexity of CG.
In Fig. \ref{fig:motivation}(c), the decomposable layout is acquired only when $D$, $G$, and $H$ are assigned to the identical color, which indicates that maintaining the consistent coloring relations among disconnected vertices in one CG can assist detailed routers in generating TPL-friendly results.
However, maintaining certain coloring relations among non-adjacent vertices in one CG is quite difficult.
Therefore, one \textit{token graph} (TG) is proposed to maintain the \textit{logical} coloring relation among sets of wire segments.
Before introducing the proposed TG, the terminology of CG is defined as follows.

\begin{define}[\textbf{CG}]
A CG $\mathcal{G^C}$ = ($V^\mathcal{C}, E^\mathcal{C}$) contains a vertex set $V^\mathcal{C}$ representing all wire segments in one layer and an edge set $E^\mathcal{C}$ representing the minimum distance of two vertices, $v^c_i \in V^\mathcal{C}$, $v^c_j \in V^\mathcal{C}$, and $i \neq j$, is smaller than $sp_{tp}$.
%Each vertex $v^c \in V^\mathcal{C}$ is assigned a token, denoted as $token(v^c)$, to represent its potential color.
\end{define}

\begin{define}[\textbf{Token}]
A token represents a potential color.
Each vertex $v^c_i \in V^\mathcal{C}$ is assigned a token $T$ to represent its potential color, denoted as $token(v^c_i) = T$.
Each token $T$ contains a CG vertex set, denoted as $V_t^\mathcal{C}(T) \subset V^\mathcal{C}$ where $\forall v^c_j \in V_t^\mathcal{C}(T), token(v^c_j) = T$, to indicate all vertices in $V_t^\mathcal{C}(T)$ is assigned to $T$.
\end{define}

\begin{define}[\textbf{TG}]
A TG $\mathcal{G^T}$ = ($V^\mathcal{T}, E^\mathcal{T}$) comprises a vertex set $V^\mathcal{T}$ representing all tokens in one layer and an edge set $E^\mathcal{T}$.
Each edge in $E^\mathcal{T}$ between two tokens, $T_i \in V^\mathcal{T}, T_j \in V^\mathcal{T}$ and $i \neq j$, represents that there exists at least one edge in $\mathcal{G^C}$ between $V_t^\mathcal{C}(T_i)$ and $V_t^\mathcal{C}(T_j)$.
\end{define}

\begin{define}[\textbf{Strictly Colored Component (SCC)}]
One SCC is defined as one three-tuple $(T_i, T_j, T_k)$ where $T_i \in V^\mathcal{T}, T_j \in V^\mathcal{T}$, and $T_k \in V^\mathcal{T}$ comprise one three-clique in $\mathcal{G^T}$.
TG may contain a set of SCCs.
\end{define}

\begin{define}[\textbf{TECG}]
A TECG $\mathcal{G^{TC}}$ comprises one CG $\mathcal{G^C}$ and one TG $\mathcal{G^T}$.
A CG/TG may comprise several connected components, and each component is a subgraph of CG/TG and named as CSG/TSG.
TPL conflict can be detected by finding a conflicting edge $e^c \in E^\mathcal{C}$ between $v^c_i \in V^\mathcal{C}$ and $v^c_j \in V^\mathcal{C}$ where $token(v^c_i) = token(v^c_j)$.
\end{define}

The proposed TG enables detailed routers to maintain high coloring-flexibility.
Instead of assigning physical colors into wire segments, tokens are used to represent the potential colors.
Therefore, one TG may contain more than three tokens even when TPL provides only three colors in each layer.
Figures \ref{fig:tecg} depicts the TECG of the layout in Fig. \ref{fig:motivation}(c).
In Fig. \ref{fig:tecg}(a), $A$ and $C$ are assigned to $T_1$; $B$ and $E$ are assigned to $T_2$; $D$, $G$, and $H$ are assigned to $T_3$; and $F$ is assigned to $T_4$.
The corresponding TG as shown in Fig. \ref{fig:tecg}(b) contains four tokens, $T_1$, $T_2$, $T_3$, and $T_4$, and one SCC $scc=(T_1, T_2, T_3)$.
Therefore, the coloring result in Fig. \ref{fig:motivation}(c) can be obtained by assigning $T_1$, $T_2$, and $T_3$ to $c_1$, $c_2$, and $c_3$, respectively, while $T_4$ can be assigned to $c_1$ or $c_2$.
Notably, the number of vertices and edges of TG is much less than that of CG.

\begin{figure}[bt!]
	\centering
	\subfloat[]{\includegraphics[width=0.2\textwidth]{fig/cg_tecg1.eps}}
    \hspace{0.04\textwidth}
	\subfloat[]{\includegraphics[width=0.13\textwidth]{fig/tg_tecg1.eps}}
	\caption{TECG of layout in Fig. \ref{fig:motivation}(c): (a) CG; (b) TG.}
	\label{fig:tecg}
\end{figure}

\subsection{Token Graph Reduction}
The coloring relation between non-adjacent tokens may become consistent after inserting an edge in one TG.
Merging these tokens can effectively compact TG to facilitate TPL conflict detection.
Two disconnected tokens $T_w \in V^\mathcal{T}$ and $T_x \in V^\mathcal{T}$ are merged when there exists one SCC $scc=(T_x, T_y, T_z)$ in $\mathcal{G^T}$ where $T_y$ and $T_z$ connect to $T_w$.
After merging $T_w$ and $T_x$, the adjacent tokens of $T_w$ and $T_x$ connect to the merged token, which conduces to further graph reduction.

Algorithm \ref{alg:tg_update} depicts the algorithm of TG\_Update with two connected tokens $T_i$ and $T_j$.
TG\_Update finds if there exists one $scc_i = (T_i, T_{i1}, T_{i2}) \in S^{SCC}$ where $T_j$ connects to $T_{i1}$ but not $T_{i2}$.
If $scc_i$ exists, $T_j$ and $T_{i2}$ are merged (lines 1--3).
Otherwise, TG\_Update tries to merge $T_i$ with one token in an existing SCC in a similar scenario (lines 5--7).
When the above two conditions cannot be met, TG\_Update finds if any SCC, such as $scc_{com} = (T_i, T_j, T_k) \in S^{SCC}$, contains $T_i$ and $T_j$.
If $scc_{com}$ exists and $T_i$ and $T_j$ have an other common adjacent token $T_{com}$, $T_k$ and $T_{com}$ are merged (lines 9--11).
If no tokens can be merged and $T_i$ and $T_j$ have one common adjacent token $T_{com}$, TG\_Update generates one SCC, and recursively calls itself until no more tokens/SCCs can be merged/generated (lines 12--16).

\begin{algorithm}[bt!]
\caption{TG\_Update}
\label{alg:tg_update}
\begin{algorithmic}[1]
  \REQUIRE Two connected tokens $T_i \in V^\mathcal{T}$ and $T_j \in V^\mathcal{T}$, one SCC set $S^{SCC}$
  \STATE Find $scc_i = (T_i, T_{i1}, T_{i2}) \in S^{SCC}$ such that $T_j$ connects to $T_{i1}$ but not $T_{i2}$;
  \IF{$scc_i$ exists}
    \STATE Token\_Merging($T_j$, $T_{i2}$);
  \ELSE
    \STATE Find $scc_j$ = $(T_j, T_{j1}, T_{j2}) \in S^{SCC}$ such that $T_i$ connects to $T_{j1}$ but not $T_{j2}$;
    \IF{$scc_j$ exists}
      \STATE Token\_Merging($T_i$, $T_{j2}$);
    \ELSE
      \STATE Find $scc_{com} = (T_i, T_j, T_k) \in S^{SCC}$;
      \IF{$scc_{com}$ exists \AND $T_i$ and $T_j$ have one common adjacent token $T_{com} \neq T_k$}
        \STATE Token\_Merging($T_k$, $T_{com}$);
      \ELSIF {$T_i$ and $T_j$ have one common adjacent token $T_{com}$}
        \STATE Generate $scc_{new} = (T_i, T_j, T_{com})$;
        \STATE $S^{SCC} := S^{SCC} \cup {scc_{new}}$;
        \STATE TG\_Update($T_i$, $T_j$);
      \ENDIF
    \ENDIF
  \ENDIF
%  \STATE Generate implicit TG edge set $ITEG$, if necessary.
%  \FORALL{$ie \in ITEG$}
%    \STATE Update TG based on $ie$.
%  \ENDFOR
\end{algorithmic}
\end{algorithm}


Assume that $T_w$ and $T_x$ are merged into $T_{mrg}$.
Let $V_{ad}^\mathcal{T}(T_w)$ and $V_{ad}^\mathcal{T}(T_x)$ be the adjacent vertex sets of $T_w$ and $T_x$ in $\mathcal{G^T}$, respectively.
After merging $T_w$ and $T_x$, the adjacent vertex set of $T_{mrg}$ is $V_{ad}^\mathcal{T}(T_{mrg}) = V_{ad}^\mathcal{T}(T_w) \cup V_{ad}^\mathcal{T}(T_x)$.
Therefore, token merging reduces $|V^\mathcal{T}|$ and $|E^\mathcal{T}|$ by one and $|V_{ad}^\mathcal{T}(T_w)| + |V_{ad}^\mathcal{T}(T_x)|-|V_{ad}^\mathcal{T}(T_{mrg})|$, respectively.
Notably, some redundant TG edges are removed after token merging, and the inserted edges of the merged token can further benefit in simplifying TG.
Algorithm \ref{alg:token_merging} displays the algorithm of merging two tokens $T_w$ and $T_x$.
Merging $T_w$ and $T_x$ into $T_{mrg}$ requires $scc \in S^{SCC}$ being updated by replacing $T_w$ or $T_x$ by $T_{mrg}$ (lines 1--5).
The replacement may cause two SCCs to contain the same tokens, resulting in redundant SCCs.
After updating SCCs, the redundant SCCs are removed, if any (line 7).
The additional edges of the merged token can further assist in graph reduction. (lines 8--10).

\begin{algorithm}[bt!]
\caption{Token\_Merging}
\label{alg:token_merging}
\begin{algorithmic}[1]
  \REQUIRE $T_w \in V^\mathcal{T}$, $T_x \in V^\mathcal{T}$, one SCC set $S^{SCC}$
    \STATE Merge $T_w$ and $T_x$ into $T_{mrg}$;
    \FORALL {$scc \in S^{SCC}$}
      \IF{$scc$ contains $T_w$ or $T_x$}
        \STATE Update $scc$ by replacing $T_w$ or $T_x$ by $T_{mrg}$;
      \ENDIF
    \ENDFOR
    \STATE Remove redundant SCC from $S^{SCC}$;
    \FORALL {token $t \in \{V_{ad}^\mathcal{T}(T_{mrg})-\{V_{ad}^\mathcal{T}(T_w) \cap V_{ad}^\mathcal{T}(T_{x})\}\}$}
      \STATE TG\_Update($T_{mrg}$, $t$);
    \ENDFOR
\end{algorithmic}
\end{algorithm}


\subsection{TECG Update}
In the routing stage, the vertices representing routing wire segments are inserted into one CG, and new tokens are generated in one TG to represent the potential colors of routing wire segments.
When $v^c_i \in V^\mathcal{C}$ and $v^c_j \in V^\mathcal{C}$ are connected by an edge, an edge in one TG between $token(v^c_i)$ and $token(v^c_j)$ needs to be generated, if necessary.
Algorithm \ref{alg:tecg_update} shows TECG\_Update by connecting  $v^c_i \in V^\mathcal{C}$ and $v^c_j \in V^\mathcal{C}$.
Firstly, $v^c_i$ and $v^c_j$ are connected (line 1).
One TPL conflict is detected when $token(v^c_i)$ and $token(v^c_j)$ are identical (lines 2--3).
If $token(v^c_i)$ and $token(v^c_j)$ in the TG are disconnected, $token(v^c_i)$ and $token(v^c_j)$ are connected, and then \textit{TG\_Update} is used to compact the TG, if possible (lines 4--6).

\begin{algorithm}[bt!]
\caption{TECG\_Update}
\label{alg:tecg_update}
\begin{algorithmic}[1]
  \REQUIRE $\mathcal{G^{TC}}$, $v^c_i \in V^\mathcal{C}$ and $v^c_j \in V^\mathcal{C}$ to be connected
  \STATE Connect $v^c_i$ and $v^c_j$ in $\mathcal{G^C}$;
  \IF{$token(v^c_i) = token(v^c_j)$}
    \STATE Detect one TPL conflict;
  \ELSIF{$token(v^c_i)$ and $token(v^c_j)$ are disconnected in $\mathcal{G^T}$}
    \STATE Connect $token(v^c_i)$ and $token(v^c_j)$;
    \STATE TG\_Update($token(v^c_i)$, $token(v^c_j)$);
  \ENDIF
\end{algorithmic}
\end{algorithm}

Figure \ref{fig:tecg_update}(a) depicts one TECG with one CG containing seven vertices, one TG containing seven vertices and ten edges, and two SCC $scc_1 = (T_1, T_2, T_7)$ and $scc_2=(T_3, T_4, T_5)$.
Connecting $C$ and $G$ (the dashed line) in the CG generates the connection between $T_3$ and $T_7$ (the dashed line) in the TG.
Therefore, TG\_Update$(T_3, T_7)$ merges $T_1$ and $T_3$ into $T_{1'}$, and the two SCCs are updated by replacing $T_1$ and $T_3$ with $T_{1'}$ as shown in Fig. \ref{fig:tecg_update}(b).
Next, because $T_5$ is not a common adjacent token of $T_1$ and $T_3$ in Fig. \ref{fig:tecg_update}(a), TG\_Update$(T_{1'}, T_5)$ merges $T_2$ and $T_5$ into $T_{2'}$ followed by updating SCCs by replacing $T_2$ and $T_5$ with $T_{2'}$ as shown in Fig. \ref{fig:tecg_update}(c).
Similarly, $T_4$ is not a common adjacent token of $T_2$ and $T_5$ in Fig. \ref{fig:tecg_update}(c) so TG\_Update$(T_4, T_{2'})$ updates TG as shown in Fig. \ref{fig:tecg_update}(d).
Notably, after replacing $T_4$ and $T_7$ with $T_{3'}$, the three tokens of two SCCs become identical, requiring removing one redundant SCC.
Therefore, one SCC is removed as shown in Fig. \ref{fig:tecg_update}(d).
Finally, TG\_Update$(T_{2'}, T_6)$ is called because $T_6$ is not a common adjacent token of $T_2$ and $T_5$ in Fig. \ref{fig:tecg_update}(b).
Figures \ref{fig:tecg_update}(e) depicts the updated TECG with one SCC $(T_{1'}, T_{2'}, T_{4'})$ where the assigned token of each vertex in CG is also updated.
Notably, before connecting $C$ and $G$ in the CG, the number of TG vertices, TG edges, and SCCs are seven, ten, and two, respectively.
After connecting $C$ and $G$ in CG, the number of TG vertices, TG edges, and SCCs are reduced by four, seven, and one, respectively, which indicates the proposed graph reduction technique effectively reduces the complexity of the TG.
Therefore, the graph reduction technique of TECG can significantly reduce the complexity of the TPL conflict detection.


\begin{figure}[bt!]
  \centering
  %\subfloat[]{\includegraphics[height=0.11\textheight]{fig/tecg_update_bf.eps}}
  \subfloat[]{\includegraphics[width=0.285\textwidth]{fig/tecg_update_bf.eps}}
  %\hspace{0.02\textwidth}
  %\subfloat[]{\includegraphics[width=0.22\textwidth]{fig/tg_update_0.eps}}
  
  %\subfloat[]{\includegraphics[height=0.11\textheight]{fig/tecg_update_af.eps}}
  \subfloat[]{\includegraphics[width=0.13\textwidth]{fig/tg_update_1.eps}}
  \hspace{0.16\textwidth}
  \subfloat[]{\includegraphics[width=0.13\textwidth]{fig/tg_update_2.eps}}
  
  \subfloat[]{\includegraphics[width=0.13\textwidth]{fig/tg_update_3.eps}}
  \hspace{0.01\textwidth}
  %\subfloat[]{\includegraphics[width=0.23\textwidth]{fig/tg_update_4.ps}}
  %\subfloat[]{\includegraphics[height=0.11\textheight]{fig/tecg_update_af.eps}}
  \subfloat[]{\includegraphics[width=0.285\textwidth]{fig/tecg_update_af.eps}}
  \caption{\textcolor[rgb]{0.00,0.00,0.00}{
      Example of TECG update:
      (a) TECG before connecting $C$ and $G$ in CG with two SCCs $(T_1, T_2, T_7)$ and $(T_3, T_4, T_5)$;
      (b) updated TG after merging $T_1$ and $T_3$ in (a) into $T_{1'}$; 
      (c) updated TG after merging $T_2$ and $T_5$ in (b) into $T_{2'}$; 
      (d) updated TG after merging $T_4$ and $T_7$ in (c) into $T_{3'}$; 
      (e) updated TECG after merging $T_{3'}$ and $T_6$ in (d) into $T_{4'}$.
    }
  }
  \label{fig:tecg_update}
\end{figure}



\subsection{Implicit Edge in TG}
%\textcolor[rgb]{1.00,0.00,0.00}{Q10. Is this one the only case?}
%Two disconnected vertices in TG need to be assigned to different colors when the certain topology appears in TG as shown in Fig. \ref{fig:itge}(a).
%TG is used to maintain the coloring relation among tokens.
Two tokens cannot be assigned to the same color when they connect to each other in one TG.
We observe that two non-adjacent vertices in one TG cannot be assigned to one color when certain topology appears in TG.
Notably, there might be other patterns that are not observed.
%Otherwise, no feasible coloring result exists in the TG.
An \textit{implicit TG edge} between two non-adjacent tokens, such as $T_i$ and $T_j$, is generated when all the following conditions are satisfied:
\begin{enumerate}
  \item TG contains two SCCs $(T_x, T_y, T_z)$ and $(T_p, T_q, T_r)$, where
  \item $T_x$ and $T_p$ connect to each other;
  \item $T_i$ connects to both $T_y$ and $T_q$; and
  \item $T_j$ connects to both $T_z$ and $T_r$.
\end{enumerate}

Without loss of generality, there are three colors $(c_1, c_2, c_3)$ can be used to color all tokens in one TG.
Figure \ref{fig:itge}(a) depicts one TG contains the specific topology with two SCCs $scc_1 = (T_3, T_4, T_5)$ and $scc_2 = (T_6, T_7, T_8)$.
Suppose that $T_1$ and $T_2$ are assigned to $c_1$.
Notably, $T_4$/$T_5$ and $T_7$/$T_8$ can only be assigned to $c_2$ and $c_3$ due to the connection to $T_1$/$T_2$, resulting in that $T_3$/$T_6$ must be assigned to $c_1$.
However, there exists one edge between $T_3$ and $T_6$.
Therefore, $T_1$ and $T_2$ must be assigned to different colors, and one implicit edge is generated between $T_1$ and $T_2$ as shown in Fig. \ref{fig:itge}(b).
In TECG\_Update, after TG\_Update (Algorithm \ref{alg:tecg_update}: line 6),a set of implicit TG edges $IE$ is generated by checking if the above conditions are satisfied.
For each implicit edge $ie \in IE$, TG\_Update checks if the TG can be further reduced by inserting $ie$.

\begin{figure}[bt!]
	\centering
	\subfloat[]{\includegraphics[width=0.18\textwidth]{fig/itge1.eps}}
    \hspace{0.04\textwidth}
    \subfloat[]{\includegraphics[width=0.18\textwidth]{fig/itge2.eps}}
	\caption{Example of implicit TG edge: (a) $T_1$ and $T_2$ are disconnected in TG; (b) implicit TG edge between $T_1$ and $T_2$ is inserted to indicate that colors of $T_1$ and $T_2$ must differ.}
	\label{fig:itge}
\end{figure} 

supplement1.tex
\subsection{Rip-up Operation of TECG}

Rip-up and re-route is a necessary means to accomplish detailed routing when some nets cannot be routed successfully.
Due to the page limitation, we skip the rip-up operation of TECG in the main article.
Detailed routers rip up routed wire segments to release routing resource for unroutable nets.
After ripping up one wire segment, the corresponding vertex $v^c$ in CG needs to be removed from CG, which requires disconnecting $v^c$ and $v^c_i \in V^\mathcal{C}_{ad}(v^c)$.
Without loss of generality, two disconnected tokens $T_w \in V^\mathcal{T}$ and $T_x \in V^\mathcal{T}$ are merged into $T_{mrg}$ when the following two conditions are satisfied.
\begin{enumerate}
  \item There exists one SCC $scc = (T_x, T_y, T_z)$ in $\mathcal{G^T}$, and
  \item $T_w$ connects to $T_y$ and $T_z$.
\end{enumerate}
Then $scc$ is updated as $scc_{mrg} = (T_{mrg}, T_y, T_z)$.
Disconnecting two vertices in CG may break one of the two merging conditions, resulting in \textit{token splitting}.
Figure \ref{fig:s_tecg_ripup}(a) depicts one TECG containing one SCC $scc=(T_2, T_3, T_4)$.
Connecting $A$ and $B$ makes $T_1$ and $T_4$ be merged into $T_5$ as shown in Fig. \ref{fig:s_tecg_ripup}(b).
After disconnecting $B$ and $C$, $token(B) = T_2$ and $token(C) = T_3$ is also disconnected in TG, resulting in the destruction of $scc$.
Notably, $token(A)$ and $token(D)$ are identical due to the appearance of $scc$.
When $scc$ is destructed, $token(A)$ and $token(D)$ differ by splitting $T_5$ into $T_6$ and $T_7$ as shown in Fig. \ref{fig:s_tecg_ripup}(c).
To facilitate token splitting, \textit{merging edges} in CG are generated when two tokens are merged.
The merging edge generation and removal are introduced followed by token splitting.

\begin{figure}[tb!]
	\centering
	\subfloat[]{\includegraphics[width=0.15\textwidth]{fig/s_tecg_bf_ripup0.eps}}
	%\subfloat[]{\includegraphics[height=0.08\textheight]{fig/s_tecg_bf_ripup0.eps}}
    %\hspace{0.001\textwidth}
	\subfloat[]{\includegraphics[width=0.15\textwidth]{fig/s_tecg_bf_ripup.eps}}
	%\subfloat[]{\includegraphics[height=0.08\textheight]{fig/s_tecg_bf_ripup.eps}}
    %\hspace{0.001\textwidth}
	\subfloat[]{\includegraphics[width=0.15\textwidth]{fig/s_tecg_af_ripup.eps}}
	%\subfloat[]{\includegraphics[height=0.08\textheight]{fig/s_tecg_af_ripup.eps}}
	\caption{TECG after rip-up: (a) TECG before connecting $A$ and $B$ in CG; (b) updated TECG; (c) TECG after disconnecting $B$ and $C$ in CG.}
	\label{fig:s_tecg_ripup}
\end{figure}


\subsubsection{Merging Edge Generation}
Merging two tokens $T_w \in V^\mathcal{T}$ and $T_x \in V^\mathcal{T}$ into $T_{mrg}$ reassigns $token(v^c)$ as $T_{mrg}$ where $v^c \in V^\mathcal{C}_t(T_w) \cup V^\mathcal{C}_t(T_x)$.
Before merging $T_w$ and $T_x$, \textit{merging edges} are generated between $V^\mathcal{C}_t(T_w)$ and $V^\mathcal{C}_t(T_x)$.
Before introducing merging edge generation, \textit{merging pattern} is firstly defined as follows.

\begin{define}[\textbf{Merging Pattern}]
%Assume that $T_w$ and $T_x$ are being merged into $T_{mrg}$ with one SCC $scc = (T_x, T_y, T_z)$.
A merging pattern in CG is defined as a four-tuple $(v^c_{cnt1}$, $v^c_{cnt2}$, $v^c_{brdg1}$, $v^c_{brdg2})$ where $token(v^c_{cnt1})$ = $T_w$ and $token(v^c_{cnt2})$ = $T_x$ are being merged, $token(v^c_{brdge1}) = T_y$, $token(v^c_{brdge2})$ = $T_z$, and there exists one SCC $scc = (token(v^c_{cnt2})$, $token(v^c_{brdg1})$, $token(v^c_{brdg2}))$ in TG.
\end{define}

%A merging pattern indicates that $token(v^c_{cnt1})$ and $token(v^c_{cnt2})$ are merged because $v^c_{cnt1}$ and $v^c_{cnt2}$ connect to $v^c_{brdg1}$ and $v^c_{brdg2}$.

Algorithm \ref{alg:s_MP_generation} shows the algorithm of merging pattern generation before two tokens $T_w$ and $T_x$ are merged.
Firstly, a merging pattern set $S^{MP}$ is set as empty.
Each vertex $v^c_w \in V^\mathcal{C}_t(T_w)$ tries to generate merging patterns with vertex $v^c_x \in V^\mathcal{C}_t(T_x)$.
Two adjacent vertices of $v^c_w$, such as $v^c_{ad1} \in V^\mathcal{C}_{ad}(v^c_w)$ and $v^c_{ad2} \in V^\mathcal{C}_{ad}(v^c_w)$ where $token(v^c_{ad1}) = T_y$ and $token(v^c_{ad2}) = T_z$, are identified.
Then the adjacent vertex of $v^c_{ad1}$, such as $v^c_{adx} \in V^\mathcal{C}_{ad}(v^c_{ad1})$ where $token(v^c_{adx}) = T_x$, is found to generate one merging pattern with $v^c_w$, $v^c_{ad1}$, and $v^c_{ad2}$ (lines 2--9).
%Similarly, Each vertex $v^c_x \in V^\mathcal{C}_t(T_x)$ tries to generate one merging pattern with vertex $v^c_w \in V^\mathcal{C}_t(T_w)$ (lines 10--17).


\begin{algorithm}[bt!]
\caption{Merging Pattern Generation}
\label{alg:s_MP_generation}
\begin{algorithmic}[1]
  \REQUIRE Two tokens $T_w \in V^\mathcal{T}$ and $T_x \in V^\mathcal{T}$ to be merged, one SCC $scc$ = $(T_x, T_y, T_z)$
  \STATE Merging pattern set $S^{MP} := \emptyset$;
  \FORALL {$v^c_w \in V^\mathcal{C}_t(T_w)$}
    \FORALL {$v^c_{ad1} \in V^\mathcal{C}_{ad}(v^c_w)$, $v^c_{ad2} \in V^\mathcal{C}_{ad}(v^c_w)$ where $token(v^c_{ad1})$ = $T_y$, $token(v^c_{ad2})$ = $T_z$}
      \FORALL {$v^c_{adx} \in V^\mathcal{C}_{ad}(v^c_{ad1})$ where $token(v^c_{adx})$ = $T_x$}
        \STATE Generate one merging pattern $mp$ = $(v^c_w$, $v^c_{adx}$, $v^c_{ad1}$, $v^c_{ad2})$;
        \STATE $S^{MP} := S^{MP} \cup \{ mp \}$;
      \ENDFOR
    \ENDFOR
  \ENDFOR
  \RETURN $S^{MP}$;
\end{algorithmic}
\end{algorithm}


One merging pattern $mp$ = $(v^c_{cnt1}$, $v^c_{cnt2}$, $v^c_{brdg1}$, $v^c_{brdg2})$ generates one merging edge, denoted as $e^c_{mrg}(T_mrg)$ between $v^c_{cnt1}$ and $v^c_{cnt2}$ where $T_{mrg}$ is the merging token.
Notably, $v^c_{brdg1}$ and $v^c_{brdg2}$ are called the bridge vertices of $e^c_{mrg}(T_{mrg})$.
Each vertex $v^c \in \mathcal{G^C}$ contains a merging edge set, denoted as $E_{BRDG}(v^c)$, to represent the set of merging edges where $v^c$ is one bridge vertex of $e^c_{mrg} \in E_{BRDG}(v^c)$.
Figure \ref{fig:s_ME}(a) depicts the TECG with merging edges of that in Fig. \ref{fig:s_tecg_ripup}(b) before merging $T_1$ and $T_4$.
After one merging pattern $mp = (A, D, B, C)$ is generated, one merging edge $e_{mrg}$ is generated between $A$ and $D$.
Notably, $B$ and $C$ are the bridge vertices of $e_{mrg}$, resulting in $E_{BRDG}(B) = E_{BRDG}(B) \cup \{e_{mrg}\}$ and $E_{BRDG}(C) = E_{BRDG}(C) \cup \{ e_{mrg}\}$.
Then $T_1$ and $T_4$ are merged into $T_5$ as shown in Fig. \ref{fig:s_ME}(b).


\begin{figure}[bt!]
	\centering
	%\subfloat[]{\includegraphics[height=0.14\textheight]{fig/s_ME_bf.eps}}
    \subfloat[]{\includegraphics[width=0.23\textwidth]{fig/s_ME_bf.eps}}
    %\hspace{0.01\textwidth}
	%\subfloat[]{\includegraphics[height=0.14\textheight]{fig/s_ME_af.eps}}
	\subfloat[]{\includegraphics[width=0.23\textwidth]{fig/s_ME_af.eps}}
	\caption{Merging pattern and merging edge generation: (a) TECG before merging $tokne(A)$ and $token(D)$; (b) TECG after merging $tokne(A)$ and $token(D)$ into $T_5$.}
	\label{fig:s_ME}
\end{figure}


\subsubsection{Merging Edge Removal}

Removing one vertex $v^c \in V^\mathcal{C}$ requires disconnecting $v^c$ and $v^c_{ad} \in V^\mathcal{C}_{ad}(v^c)$.
One merging pattern  $mp$ = $(v^c_{cnt1}$, $v^c_{cnt2}$, $v^c_{brdg1}$, $v^c_{brdg2})$ is removed when the connection between any vertex pair in $mp$ is removed, if any.
After one merging pattern is removed, the corresponding merging edge is also removed from CG.
Figure \ref{fig:s_MEV}(a)/(b) depicts that the merging edge between $A$ and $D$ in Fig. \ref{fig:s_ME}(b) is removed after disconnecting $A$/$B$ and $C$.

\begin{figure}[bt!]
	\centering
    \subfloat[]{\includegraphics[width=0.16\textwidth]{fig/s_MERV1.eps}}
    \hspace{0.04\textwidth}
	\subfloat[]{\includegraphics[width=0.16\textwidth]{fig/s_MERV2.eps}}
	\caption{Merging edge removal: (a) disconnecting $A$ and $C$ removes the merging edge between $A$ and $D$ in Fig. \ref{fig:s_ME}(b); (b) disconnecting $B$ and $C$ removes the merging edge between $A$ and $D$ in Fig. \ref{fig:s_ME}(b).}
	\label{fig:s_MEV}
\end{figure}



\subsubsection{Token Splitting}


\begin{algorithm}[bt!]
\caption{Token Splitting}
\label{alg:s_TSPLIT}
\begin{algorithmic}[1]
  \REQUIRE One TECG $\mathcal{G^{TC}}$ with TG $\mathcal{G^T}$ and CG $\mathcal{G^C}$, token $T_{victim}$ to be split
  \FORALL{$T_{ad} \in V^\mathcal{T}_{ad}(T_{victim})$}
    \STATE $V^\mathcal{T}_{ad}(T_{ad}) := V^\mathcal{T}_{ad}(T_{ad}) - \{T_{victim}\}$;
  \ENDFOR
  \STATE Apply BFS to find the connected component set $S^{CONNECT} \in V^\mathcal{C}_t(T_{victim})$ connected by merging edges of $T_{vicrim}$;
  \FORALL{Connected component $cc \in S^{CONNECT}$}
    \STATE Generate and insert one token $T_{extra}$ in $\mathcal{G^T}$;
    \STATE $V^\mathcal{C}_t(T_{extra}) := \emptyset$;
    \STATE $V^\mathcal{T}_{ad}(T_{extra}) := \emptyset$;
    \FORALL{ CG vertex $v^c \in cc$}
      \STATE $token(v^c) := T_{extra}$;
      \STATE $V^\mathcal{C}_t(T_{extra}) := V^\mathcal{C}_t(T_{extra}) \cup \{v^c\}$;
      \FORALL{Adjacent CG vertex $v^c_{ad}$ of $v^c$}
        \STATE $V^\mathcal{T}_{ad}(T_{extra}) := V^\mathcal{T}_{ad}(T_{extra}) \cup \{token(v^c_{ad})\}$;
        \STATE $V^\mathcal{T}_{ad}(token(v^c_{ad})) := V^\mathcal{T}_{ad}(token(v^c_{ad})) \cup \{T_{extra}\}$;
      \ENDFOR
    \ENDFOR
  \ENDFOR
  \STATE Remove $T_{victim}$ from $\mathcal{G^T}$;
\end{algorithmic}
\end{algorithm}

\begin{figure}[bt!]
	\centering
    %\subfloat[]{\includegraphics[width=0.25\textwidth]{fig/s_TSPIT1.eps}}
    %\subfloat[]{\includegraphics[width=0.15\textwidth]{fig/s_TSPIT1T.eps}}
	%\subfloat[]{\includegraphics[width=0.25\textwidth]{fig/s_TSPIT2.eps}}
	%\subfloat[]{\includegraphics[width=0.15\textwidth]{fig/s_TSPIT2T.eps}}
	%\subfloat[]{\includegraphics[width=0.25\textwidth]{fig/s_TSPIT3.eps}}
	%\subfloat[]{\includegraphics[width=0.15\textwidth]{fig/s_TSPIT3T.eps}}	
    \subfloat[]{\includegraphics[width=0.37\textwidth]{fig/s_TSPLIT1.eps}}
	
    \subfloat[]{\includegraphics[width=0.37\textwidth]{fig/s_TSPLIT2.eps}}
	
    \subfloat[]{\includegraphics[width=0.38\textwidth]{fig/s_TSPLIT3.eps}}
	\caption{Token splitting: (a) one TECG where $A$, $D$, and $G$ are connected by merging edges due to $T_1$; (b) disconnecting $I$ and $H$ removes the merging edge between $A$ and $G$; (c) disconnecting $A$ and $C$ removes the merging edge between $A$ and $D$, resulting in $token(A)$ must differ from $token(G)$ and $token(D)$.}
	\label{fig:s_TSPLIT}
\end{figure}

For each token $T_i \in V^\mathcal{T}$, any two vertices, such as $v^c_i \in V^\mathcal{C}_t(T_i)$ and $v^c_j \in V^\mathcal{C}_t(T_i)$, connect to each other by merging edges of $T_i$.
When $v^c_i$ and $v^c_j$ cannot connect to each other by merging edges of $T_i$ after removing edges in CG, $T_i$ needs to be split into at least two tokens.
The connectivity of merging edges can be checked by applying depth-first search (BFS).
Algorithm \ref{alg:s_TSPLIT} shows the algorithm of token splitting.
Firstly, the adjacent token $T_{ad} \in V^\mathcal{T}_{ad}(T_{victim})$ and $T_{victim}$ is disconnected (lines 1--3).
BFS is then applied to find the connected component set $S^{CONNECT}$ where all vertices in each component $cc \in S^{CONNECT}$ are connected by merging edges of $T_i$ (line 4).
%Then, $T_{victim}$ is split into $|S^{CONNECT}|$ tokens.
For each connected component $cc \in S^{CONNECT}$, one extra token $T_{extra}$ is generated and inserted in TG.
For each CG vertex $v^c \in cc$, $token(v^c)$ is assigned to $T_{extra}$ (lines 5--11).
The adjacent tokens of $T_{extra}$ is updated based on the tokens of all adjacent vertices of $v^c$ (lines 12--15).
Finally, $T_{victim}$ is removed from TG (line 18).


Figure \ref{fig:s_TSPLIT}(a) depicts one TECG containing one CG with nine vertices, fifteen edges, and three merging edges of $T_1$ and one TG with seven tokens and nine edges.
$A$, $D$, and $G$ connect to each other by the three merging edges of $T_1$ because they are assigned to $T_1$.
After disconnecting $H$ and $I$, the merging edge of $T_1$ between $A$ and $G$ is removed, and $T_6$ and $T_7$ are also disconnected as shown in Fig. \ref{fig:s_TSPLIT}(b).
$A$, $D$, and $G$ still connect to each other by the remaining two merging edges of $T_1$.
Then, disconnecting $A$ and $C$ removes the merging edge of $T_1$ between $A$ and $D$, sequentially generating two connected component in terms of the connectivity of merging edges of $T_1$.
Therefore, $T_1$ is split into $T_8$ and $T_9$, resulting in that $A$ is reassigned to $T_8$ while $D$ and $G$ are reassigned to $T_9$.
The adjacent tokens of $T_8$ and $T_9$ are updated according to the connection in CG.
Figure \ref{fig:s_TSPLIT}(c) displays the TECG after splitting $T_1$ into $T_8$ and $T_9$.








conclusion.tex
\section{Conclusion}
\label{sec:conclusion}

The detailed routing is a key optimization stage for TPL.
To effectively detect TPL conflicts with high coloring-flexibility, this work proposes a token graph-embedded conflict graph (TECG) with a graph reduction technique.
%This work develops the first TPL aware detailed router (TRIAD) and proposes a lazy stitch-generation routing scheme to accelerate the routing process.
\textcolor[rgb]{0.00,0.00,-.00}{
This work develops a TPL aware detailed router (TRIAD) with the TPL stitch generation to solve TPL conflicts..
With the aid of TECG, TRIAD can generate stitches in one wire even when the wire is entirely intersected by the TPL effect regions of other wires.
Experimental results show that the routing results have no TPL conflicts and introduces total three stitches for two cases with 0.54\% decrement in wirelength at the cost of 2.41$\times$ of runtime.}
The future work focuses on the density-driven TPL aware detailed routing. 

ICCAD12_TRIAD.bbl
% Generated by IEEEtran.bst, version: 1.13 (2008/09/30)
\begin{thebibliography}{10}
\providecommand{\url}[1]{#1}
\csname url@samestyle\endcsname
\providecommand{\newblock}{\relax}
\providecommand{\bibinfo}[2]{#2}
\providecommand{\BIBentrySTDinterwordspacing}{\spaceskip=0pt\relax}
\providecommand{\BIBentryALTinterwordstretchfactor}{4}
\providecommand{\BIBentryALTinterwordspacing}{\spaceskip=\fontdimen2\font plus
\BIBentryALTinterwordstretchfactor\fontdimen3\font minus
  \fontdimen4\font\relax}
\providecommand{\BIBforeignlanguage}[2]{{%
\expandafter\ifx\csname l@#1\endcsname\relax
\typeout{** WARNING: IEEEtran.bst: No hyphenation pattern has been}%
\typeout{** loaded for the language `#1'. Using the pattern for}%
\typeout{** the default language instead.}%
\else
\language=\csname l@#1\endcsname
\fi
#2}}
\providecommand{\BIBdecl}{\relax}
\BIBdecl

\bibitem{Du2012}
Y.~Du, H.~Zhang, M.~D.~F. Wong, and K.-Y. Chao, ``Hybrid lithography
  optimization with e-beam and immersion processes for 16nm {1D} gridded
  design,'' in \emph{17th Asia and South Pacific Design Automation Conference
  (ASP-DAC)}, Feb. 2012, pp. 707--712.

\bibitem{Kahng_SSDRC_07}
A.~B. Kahng, ``Key directions and a roadmap for electrical design for
  manufacturability,'' in \emph{37th European Solid State Device Research
  Conference}, Sept. 2007, pp. 83--88.

\bibitem{TPL_Yan_SW}
Y.~Borodovsky, ``Lithography 2009 overview of opportunities,'' in \emph{Semicon
  West}, San Francisco, CA, USA, July 2009.

\bibitem{DPL_Cho_ICCAD08}
M.~Cho, Y.~Ban, and D.~Z. Pan, ``Double patterning technology friendly detailed
  routing,'' in \emph{Proc. of Intel. Conf. on Computer-Aided Design}, 2008,
  pp. 506--511.

\bibitem{DPL_Gao_DATE2010}
X.~Gao and L.~Macchiarulo, ``Enhancing double-patterning detailed routing with
  lazy coloring and within-path conflict avoidance,'' in \emph{Proc. of Conf.
  on Design, Automation and Test in Europe}, 2010, pp. 1279--1284.

\bibitem{DPL_Lin_DAC10}
Y.-H. Lin and Y.-L. Li, ``Double patterning lithography aware gridless detailed
  routing with innovative conflict graph,'' in \emph{Proc. of Design Automation
  Conference}, 2010, pp. 398--403.

\bibitem{DPL_WISDOM}
K.~Yuan and D.~Z. Pan, ``{WISDOM}: Wire spreading enhanced decomposition of
  masks in double patterning lithography,'' in \emph{Proc. of Intel. Conf. on
  Computer-Aided Design}, 2010, pp. 32--38.

\bibitem{TPL_Cork}
C.~Cork, J.-C. Madre, and L.~Barnes, ``Comparison of triple-patterning
  decomposition algorithms using aperiodic tiling patterns,'' in
  \emph{Photomask and Next-Generation Lithography Mask Technology XV}, 2008.

\bibitem{TPL_Bei_ICCAD11}
B.~Yu, K.~Yuan, B.~Zhang, D.~Ding, and D.~Z. Pan, ``Layout decomposition for
  triple patterning lithography,'' in \emph{Proc. of Intel. Conf. on
  Computer-Aided Design}, 2011, pp. 1--8.

\bibitem{TPL_LD_SATP}
{Y. Chen, P. Xu, L. Miao \em et al.}, ``Self-aligned triple patterning for
  continuous ic scaling to half-pitch 15nm,'' in \emph{SPIE}, 2011.

\bibitem{TPL_LD_Mebarki}
{B. Mebarki, H. D. Chen, Y. Chen \em et al.}, ``Innovative self-aligned triple
  patterning for 1x half pitch using single "spacer deposition-spacer etch"
  step,'' in \emph{SPIE}, 2011.

\bibitem{Lucas2012}
K.~Lucas, C.~Cork, B.~Yu, G.~Luk-Pat, B.~Painter, and D.~Z. Pan, ``Implications
  of triple patterning for 14nm node design and patterning,'' in \emph{SPIE
  Advanced Lithography Symposium Design for Manufacturability through
  Design-Process Integration VI}, 2012.

\bibitem{DPL_Kahng_TCAD10}
A.~B. Kahng, C.-H. Park, X.~Xu, and H.~Yao, ``Layout decomposition approaches
  for double patterning lithography,'' \emph{IEEE Trans. on Computer-Aided
  Design of Integrated Circuits and Systems}, vol.~29, no.~6, pp. 939--952,
  June 2010.

\bibitem{Routing_Li_TCAD07}
Y.-L. Li, H.-Y. Chen, and C.-T. Lin, ``{NEMO}: A new implicit-connection
  -graph-based gridless router with multilayer planes and pseudo tile
  propagation,'' \emph{IEEE Trans. on Computer-Aided Design of Integrated
  Circuits and Systems}, vol.~26, no.~4, pp. 705--718, April 2007.

\bibitem{Routing_Chang_ISPD08}
Y.-N. Chang, Y.-L. Li, W.-T. Lin, and W.-N. Cheng, ``Non-slicing
  floorplanning-based crosstalk reduction on gridless track assignment for a
  gridless routing system with fast pseudo-tile extraction,'' \emph{ACM Trans.
  on Design Automation of Electronic Systems}, vol.~16, no.~2, March 2011.

\bibitem{Routing_TILER}
A.~Margarino, A.~Romano, A.~De~Gloria, F.~Curatelli, and P.~Antognetti, ``A
  tile-expansion router,'' \emph{IEEE Trans. on Computer-Aided Design of
  Integrated Circuits and Systems}, vol.~6, no.~4, pp. 507--517, July 1987.

\bibitem{Routing_DUNE}
J.~Cong, J.~Fang, and K.~Khoo, ``{DUNE}: A multilayer gridless routing
  system,'' \emph{IEEE Trans. on Computer-Aided Design of Integrated Circuits
  and Systems}, vol.~20, no.~5, pp. 633--646, May 2001.

\bibitem{Routing_MARS}
J.~Cong, J.~Fang, M.~Xie, and Y.~Zhang, ``{MARS} - a multilevel full-chip
  gridless routing system,'' \emph{IEEE Trans. on Computer-Aided Design of
  Integrated Circuits and Systems}, vol.~24, no.~3, pp. 382--394, March 2005.

\end{thebibliography}
