\chapter{Detailed results of the scalability experiment}
\label{app:Scalability}

In \autoref{sec:ScalabilityPhase2} we describe phase 2 of the scalability experiments, where we determine $T(n,p)$ and $S(n,p)$ for several ISCAS benchmark circuits using four distinct schemes for setting $\delta$. In this section we will reproduce the concrete results. For each problem instance there are two figures: one shows $T(n,p)$ and $SU(n)$, the other shows $S(n,p)$. \autoref{tab:ScalabilityPhase2ResultsFigures} shows which figure corresponds to which problem instance.

\begin{table}[htb]
	\sffamily
	\begin{center}
		\begin{tabular}{|l|l|l|l|}
			\hline
				\textbf{ISCAS circuit} & \textbf{No.\ of genes $n$} & \textbf{Graph of $T(n,p)$} & \textbf{Graph of $S(n,p)$} \\
			\hline
				\texttt{c17}		& 10	& \autoref{fig:ScalabilityPhase2RuntimeComb01}	& \autoref{fig:ScalabilityPhase2SpeedupComb01} \\
			\hline
				\texttt{c432}		& 72	& \autoref{fig:ScalabilityPhase2RuntimeComb02}	& \autoref{fig:ScalabilityPhase2SpeedupComb02} \\
			\hline
				\texttt{c880}		& 120	& \autoref{fig:ScalabilityPhase2RuntimeComb04}	& \autoref{fig:ScalabilityPhase2SpeedupComb04} \\
			\hline
				\texttt{c1908}	& 66	& \autoref{fig:ScalabilityPhase2RuntimeComb06}	& \autoref{fig:ScalabilityPhase2SpeedupComb06} \\
			\hline
				\texttt{c2670}	& 466	& \autoref{fig:ScalabilityPhase2RuntimeComb07}	& \autoref{fig:ScalabilityPhase2SpeedupComb07} \\
			\hline
				\texttt{c3540}	& 100	& \autoref{fig:ScalabilityPhase2RuntimeComb08}	& \autoref{fig:ScalabilityPhase2SpeedupComb08} \\
			\hline
				\texttt{c5315}	& 356	& \autoref{fig:ScalabilityPhase2RuntimeComb09}	& \autoref{fig:ScalabilityPhase2SpeedupComb09} \\
			\hline
				\texttt{c6288}	& 64	& \autoref{fig:ScalabilityPhase2RuntimeComb10}	& \autoref{fig:ScalabilityPhase2SpeedupComb10} \\
			\hline
				\texttt{c7552}	& 414	& \autoref{fig:ScalabilityPhase2RuntimeComb11}	& \autoref{fig:ScalabilityPhase2SpeedupComb11} \\
			\hline
		\end{tabular}
		\caption{ISCAS'85 benchmark circuits and their scalability graphs.}
		\label{tab:ScalabilityPhase2ResultsFigures}
	\end{center}
\end{table}


%%% Figures showing runtimes and speedup for each circuit
\begin{figure}[htbp]
  \sffamily
  \centering
  \subfloat[Execution time $T(n,p)$.]{
    \includegraphics[width=0.49\textwidth]{scalability/phase2_time_comb01}
    \label{fig:ScalabilityPhase2RuntimeComb01}
  }
  \subfloat[Speedup $S(n,p)$.]{
    \includegraphics[width=0.49\textwidth]{scalability/phase2_speedup_comb01}
    \label{fig:ScalabilityPhase2SpeedupComb01}
  }
  \caption[Execution time $T(n,p)$ and speedup $S(n,p)$ of PSG for different combinations of $p$ and $\delta$ on ISCAS circuit \texttt{c17}.]
          {Execution time $T(n,p)$ and speedup $S(n,p)$ of PSG for different combinations of $p$ and $\delta$ on ISCAS circuit \texttt{c17}. In the left figure, the black asterisk denotes $SU(n)$, the time taken by the sequential implementation. In the right figure, the dotted line denotes the theoretical linear speedup $S(n,p)=p$.}
  \label{fig:ScalabilityPhase2Comb01}
\end{figure}

\begin{figure}[htbp]
  \sffamily
  \centering
  \subfloat[Execution time $T(n,p)$.]{
    \includegraphics[width=0.49\textwidth]{scalability/phase2_time_comb02}
    \label{fig:ScalabilityPhase2RuntimeComb02}
  }
  \subfloat[Speedup $S(n,p)$.]{
    \includegraphics[width=0.49\textwidth]{scalability/phase2_speedup_comb02}
    \label{fig:ScalabilityPhase2SpeedupComb02}
  }
  \caption[Execution time $T(n,p)$ and speedup $S(n,p)$ of PSG for different combinations of $p$ and $\delta$ on ISCAS circuit \texttt{c432}.]
          {Execution time $T(n,p)$ and speedup $S(n,p)$ of PSG for different combinations of $p$ and $\delta$ on ISCAS circuit \texttt{c432}. In the left figure, the black asterisk denotes $SU(n)$, the time taken by the sequential implementation. In the right figure, the dotted line denotes the theoretical linear speedup $S(n,p)=p$.}
  \label{fig:ScalabilityPhase2Comb02}
\end{figure}

\begin{figure}[htbp]
  \sffamily
  \centering
  \subfloat[Execution time $T(n,p)$.]{
    \includegraphics[width=0.49\textwidth]{scalability/phase2_time_comb04}
    \label{fig:ScalabilityPhase2RuntimeComb04}
  }
  \subfloat[Speedup $S(n,p)$.]{
    \includegraphics[width=0.49\textwidth]{scalability/phase2_speedup_comb04}
    \label{fig:ScalabilityPhase2SpeedupComb04}
  }
  \caption[Execution time $T(n,p)$ and speedup $S(n,p)$ of PSG for different combinations of $p$ and $\delta$ on ISCAS circuit \texttt{c880}.]
          {Execution time $T(n,p)$ and speedup $S(n,p)$ of PSG for different combinations of $p$ and $\delta$ on ISCAS circuit \texttt{c880}. In the left figure, the black asterisk denotes $SU(n)$, the time taken by the sequential implementation. In the right figure, the dotted line denotes the theoretical linear speedup $S(n,p)=p$.}
  \label{fig:ScalabilityPhase2Comb04}
\end{figure}

\begin{figure}[htbp]
  \sffamily
  \centering
  \subfloat[Execution time $T(n,p)$.]{
    \includegraphics[width=0.49\textwidth]{scalability/phase2_time_comb06}
    \label{fig:ScalabilityPhase2RuntimeComb06}
  }
  \subfloat[Speedup $S(n,p)$.]{
    \includegraphics[width=0.49\textwidth]{scalability/phase2_speedup_comb06}
    \label{fig:ScalabilityPhase2SpeedupComb06}
  }
  \caption[Execution time $T(n,p)$ and speedup $S(n,p)$ of PSG for different combinations of $p$ and $\delta$ on ISCAS circuit \texttt{c1908}.]
          {Execution time $T(n,p)$ and speedup $S(n,p)$ of PSG for different combinations of $p$ and $\delta$ on ISCAS circuit \texttt{c1908}. In the left figure, the black asterisk denotes $SU(n)$, the time taken by the sequential implementation. In the right figure, the dotted line denotes the theoretical linear speedup $S(n,p)=p$.}
  \label{fig:ScalabilityPhase2Comb06}
\end{figure}

\begin{figure}[htbp]
  \sffamily
  \centering
  \subfloat[Execution time $T(n,p)$.]{
    \includegraphics[width=0.49\textwidth]{scalability/phase2_time_comb07}
    \label{fig:ScalabilityPhase2RuntimeComb07}
  }
  \subfloat[Speedup $S(n,p)$.]{
    \includegraphics[width=0.49\textwidth]{scalability/phase2_speedup_comb07}
    \label{fig:ScalabilityPhase2SpeedupComb07}
  }
  \caption[Execution time $T(n,p)$ and speedup $S(n,p)$ of PSG for different combinations of $p$ and $\delta$ on ISCAS circuit \texttt{c2670}.]
          {Execution time $T(n,p)$ and speedup $S(n,p)$ of PSG for different combinations of $p$ and $\delta$ on ISCAS circuit \texttt{c2670}. In the left figure, the black asterisk denotes $SU(n)$, the time taken by the sequential implementation. In the right figure, the dotted line denotes the theoretical linear speedup $S(n,p)=p$.}
  \label{fig:ScalabilityPhase2Comb07}
\end{figure}

\begin{figure}[htbp]
  \sffamily
  \centering
  \subfloat[Execution time $T(n,p)$.]{
    \includegraphics[width=0.49\textwidth]{scalability/phase2_time_comb08}
    \label{fig:ScalabilityPhase2RuntimeComb08}
  }
  \subfloat[Speedup $S(n,p)$.]{
    \includegraphics[width=0.49\textwidth]{scalability/phase2_speedup_comb08}
    \label{fig:ScalabilityPhase2SpeedupComb08}
  }
  \caption[Execution time $T(n,p)$ and speedup $S(n,p)$ of PSG for different combinations of $p$ and $\delta$ on ISCAS circuit \texttt{c3540}.]
          {Execution time $T(n,p)$ and speedup $S(n,p)$ of PSG for different combinations of $p$ and $\delta$ on ISCAS circuit \texttt{c3540}. In the left figure, the black asterisk denotes $SU(n)$, the time taken by the sequential implementation. In the right figure, the dotted line denotes the theoretical linear speedup $S(n,p)=p$.}
  \label{fig:ScalabilityPhase2Comb08}
\end{figure}

\begin{figure}[htbp]
  \sffamily
  \centering
  \subfloat[Execution time $T(n,p)$.]{
    \includegraphics[width=0.49\textwidth]{scalability/phase2_time_comb09}
    \label{fig:ScalabilityPhase2RuntimeComb09}
  }
  \subfloat[Speedup $S(n,p)$.]{
    \includegraphics[width=0.49\textwidth]{scalability/phase2_speedup_comb09}
    \label{fig:ScalabilityPhase2SpeedupComb09}
  }
  \caption[Execution time $T(n,p)$ and speedup $S(n,p)$ of PSG for different combinations of $p$ and $\delta$ on ISCAS circuit \texttt{c5315}.]
          {Execution time $T(n,p)$ and speedup $S(n,p)$ of PSG for different combinations of $p$ and $\delta$ on ISCAS circuit \texttt{c5315}. In the left figure, the black asterisk denotes $SU(n)$, the time taken by the sequential implementation. In the right figure, the dotted line denotes the theoretical linear speedup $S(n,p)=p$.}
  \label{fig:ScalabilityPhase2Comb09}
\end{figure}

\begin{figure}[htbp]
  \sffamily
  \centering
  \subfloat[Execution time $T(n,p)$.]{
    \includegraphics[width=0.49\textwidth]{scalability/phase2_time_comb10}
    \label{fig:ScalabilityPhase2RuntimeComb10}
  }
  \subfloat[Speedup $S(n,p)$.]{
    \includegraphics[width=0.49\textwidth]{scalability/phase2_speedup_comb10}
    \label{fig:ScalabilityPhase2SpeedupComb10}
  }
  \caption[Execution time $T(n,p)$ and speedup $S(n,p)$ of PSG for different combinations of $p$ and $\delta$ on ISCAS circuit \texttt{c6288}.]
          {Execution time $T(n,p)$ and speedup $S(n,p)$ of PSG for different combinations of $p$ and $\delta$ on ISCAS circuit \texttt{c6288}. In the left figure, the black asterisk denotes $SU(n)$, the time taken by the sequential implementation. In the right figure, the dotted line denotes the theoretical linear speedup $S(n,p)=p$.}
  \label{fig:ScalabilityPhase2Comb10}
\end{figure}

\begin{figure}[htbp]
  \sffamily
  \centering
  \subfloat[Execution time $T(n,p)$.]{
    \includegraphics[width=0.49\textwidth]{scalability/phase2_time_comb11}
    \label{fig:ScalabilityPhase2RuntimeComb11}
  }
  \subfloat[Speedup $S(n,p)$.]{
    \includegraphics[width=0.49\textwidth]{scalability/phase2_speedup_comb11}
    \label{fig:ScalabilityPhase2SpeedupComb11}
  }
  \caption[Execution time $T(n,p)$ and speedup $S(n,p)$ of PSG for different combinations of $p$ and $\delta$ on ISCAS circuit \texttt{c7552}.]
          {Execution time $T(n,p)$ and speedup $S(n,p)$ of PSG for different combinations of $p$ and $\delta$ on ISCAS circuit \texttt{c7552}. In the left figure, the black asterisk denotes $SU(n)$, the time taken by the sequential implementation. In the right figure, the dotted line denotes the theoretical linear speedup $S(n,p)=p$.}
  \label{fig:ScalabilityPhase2Comb11}
\end{figure}

