<filename>doc/IEEE/partial/experiment-cn.tex
\section{實驗結果} \label{sec:Experiment}

實驗主要分成以下三種：其一，測試分塊與未分塊之間的稀疏表，測試平行區間詢問的效能；
其二，增長後綴最大值詢問於不同的資料結構上的效能差異；最後，
計算不同資料結構應用在 VGLCS 計算上的效能差異。

我們實驗於 Intel Xeon E5-2620 2.4 Ghz 處理器，其包含 384K bytes 的 L1 快取、
1536K bytes 的 L2 快取、15M bytes 的 L3 快取。而 Intel CPU 支持「超執行緒」(hyper-threading)，
每一處理器包含 6 個核心。使用的作業系統為 Ubuntu 14.04，程序撰寫使用 C++ 和 OpenMP，
編譯器使用 gcc 以及相應的編譯參數 {\tt -O2} 和 {\tt -fopenmp} 進行實驗。

\subsection{分塊與未分塊稀疏表}

首先，我們比較未分塊稀疏表 (章節~\ref{sec:sparse-table} 所述) 
和分塊稀疏表 (章節~\ref{sec:blocked-sparse-table} 所述) 於平行區間詢問的效能。
在分塊稀疏表中，我們使用「右側棧出」編碼，而非查找 LCA 表，
因我們發現「右側棧出」編碼比 LCA 表來得更有效率。接續的實驗中，
我們實驗不同區間長度與不同元素個數 $N$ 的關係。

參照表~\ref{tlb:CORMQ} 比較分塊與未分塊的稀疏表在平行區間詢問的效率。
從實驗中，發現到使用右側棧出的分塊稀疏表比未分塊的版本來得快，
效能隨著 $N$ 增加而更加明顯。如在 $N$ 達到 $10^5$ 時，
分塊稀疏表相交於未分塊快上 $1.4$ 倍。

我們相信限制最大區間詢問的長度 (在表~\ref{tlb:CORMQ} 中的 $L$) 影響存取稀疏表的快取效能。
此外，當固定元素個數為 $N$ 時，隨著 $L$ 增加，加速比例越明顯，其原因可能為以下幾點所致：
當詢問的區間長度較大時，分塊稀疏表只需要在 $\log{\nicefrac{N}{s}}$ 層之間跳躍存取，
2 次超塊詢問以及 2 次 $O(s)$ 的塊內詢問。
相反地，未分塊稀疏表需要在 $\log{N}$ 層之間存取，因此在不同層數之間存取稀疏表的影響下，
易造成應答區間詢問時，大部分存取與先前不同的層，導致資料局部性下降而產生快取未中。
然而，上述的問題在 $N$ 小不會發生，唯有 $N$ 大到影響快取效能才使得分塊效益更為顯著。

\input{\TablePath/tlb-CORMQ.tex}

\subsection{「右側棧出」與「LCA 表」}

這一小節，我們比較四種資料結構解決「增長後綴詢問」({\em incremental suffix} query) 的能力，
這四個資料結構分別為並查集、未分塊稀疏表、使用右側棧出編碼的塊狀稀疏表以及使用 LCA 表的塊狀稀疏表。
使用並查集解決增長後綴詢問的細節請參照章節~\ref{sec:parallelRMQ}。
對於並查集的實作細節，使用「路徑壓縮」({\em path compression}) 和「秩合併」({\em merge-by-rank}) 的策略，
每個操作的攤銷時間複雜度為 $O(\alpha(n))$。在分塊稀疏表中，我們選用塊大小 $s$ 為 $8$，
所有稀疏表建造時皆以「行為主」(row-major manner) 的管理來減少快取未中，
請參照算法~\ref{alg:parallel-VGLCS} 和圖~\ref{fig:interval-decomposition} 的說明。

% Here we need a table of all complexity.

接下來的簡化案例中，我們交替使用「附加」({\em appending}) 
和「詢問區間」({\em range querying}) 操作，實驗中的長度和詢問位置皆採用均勻分布，
如圖~\ref{fig:fig-ISMQcmp} 說明四個不同資料結構在增長後綴詢問的效能。
其中，右側棧出編碼的分塊稀疏表快於其他的資料結構。
當 $n$ 達 $10^6$ 時，分塊稀疏表皆快於並查集。
而當 $n$ 達 $10^7$ 時，右側棧出編碼的稀疏表比並查集快上 $1.8$ 倍。

\begin{figure}[!thb]
  \centering
  \includegraphics[width=0.75\linewidth]{\GraphicPath/fig-ISMQ.pdf}
  \caption{
    不同資料結構在增長後綴最大值詢問的效能差異，實驗環境於 E5-2620 機器上}
  \label{fig:fig-ISMQcmp}
\end{figure}

在另一個複雜的案例中，我們討論在動態規劃上的一些變因如何影響效能，
這些變因包含插入值分布、最大區間詢問的分布以及插入與詢問之間的比例。
為方便討論，我們使用 $p$ 表示插入比前一個更大的元素機率、
$q$ 表示插入一個零元素的機率和 $L$ 表示詢問區間的最大長度。
在我們的實驗中，我們固定元素個數 $N$ 為 $10^7$，詢問區間最大長度 $L$ 為 $4$ 到 $16$ 之間，
$p$ 和 $q$ 之間的機率於 $0 \%$ 到 $100 \%$ 且詢問次數為插入次數的 10 倍。

如圖~\ref{fig:fig-ISMQcmp}，我們觀察到分塊稀疏表比並查集或者未分塊都來得好，
所以我們著重要塊狀稀疏表的實作，意即我們先前討論的右側棧出和 LCA 表的實作方式，
而右側棧出編碼對於增長詢問很容易地想到，只需要對最後一個塊直接添加資訊即可。

表~\ref{tlb:ISMQcmp} 比較「右側棧出編碼」與「LCA 表」解決增長後綴區間詢問的運行時間，
特別注意到 LCA 表的方法提供理論上攤銷時間 $O(1)$ 的時間，而先前的實驗中，
右側棧出編碼明顯地快於LCA 表 $1.5$ 之多，我們相信有以下兩個原因導致這個現象：
其一，LCA 表需要更多的指令來計算出卡塔蘭索引值，相反地，右側棧出編碼只需要維護推出次數；
其二，根據理論~\cite{Fischer2006TheoreticalAP} 選擇塊大小 $s$ 為 $\frac{\log n}{4}$，
這影響到無法使用太大 $s$，因為 LCA 表所造成的空間過大，越大則造成更多的快取未中問題發生。

\input{\TablePath/tlb-ISMQcmp-new.tex}

我們觀察到機率 $p$ 將影響「偷看」技術中的改善效能比例。
當 $p$ 越接近 $1$，則偷看技術越能帶來更多的效能改善。
偷看操作也依賴塊的大小，而我們也知道右側棧出編碼能使用的塊大於 LCA 表的版本，
故改善情況的程度幅度不盡相同。

我們觀察到機率 $q$ 越接近 $1$，則右側棧出編碼與 LCA 表的效能差意越不明顯，
這可以明白 LCA 表在計算卡塔蘭索引值上的問題。
當 $q$ 越接近 $1$，卡塔蘭索引值將會重複計算更多次，
因此效能會越接近右側棧出編碼的版本。

在區間詢問的長度 (表~\ref{tlb:ISMQcmp} 中的 $L$) 影響到右側棧出的稀疏表，
卻不影響 LCA 表的效能，其原因在於算法~\ref{alg:cartesian64bits-query} 的內層迴圈，
將運行最多 $s$ 次，而實作採用 $s$ 為 $16$，將造成詢問長度增加而效能下降。
在另一方面查找 LCA 表皆為 $O(1)$ 操作，效能不受 $L$ 增長而改變。

\subsection{可變的間隙限制最長共同子序列}

我們接下來比較四種資料結構的組合於 VGLCS 的問題上，並統計它們的運行效能。
第一種採用 Peng 算法的循序版本，其採用並查集於兩個階段，
由於並查集只支持增長後綴最大值詢問，因此兩階段接使用後綴最大值詢問。
除了第一種外，另外三種組合皆以平行方式運行。
第二種 {\em DS-ST} 採用並查集和未分塊稀疏表，分別於算法的第一階段和第二階段。
而第三種 {\em DS-BST} 採用並查集和塊狀稀疏表，分別於算法的第一階段和第二階段。
同理，第四種 {\em BST2} 在兩階段皆使用塊狀稀疏表。
特別注意到，上述的塊狀稀疏表皆使用「右側棧出」編碼。

圖~\ref{fig:fig-parallel} 展示四種不同組合的資料結構對於不同問題大小的效能，
輸入字串使用字母集 $\{A, T, C, G\}$ 隨機產生，因為這是生物學常用的幾個字母。
我們從實驗中發現 {\em BST2} 遠比其他平行版本來得好。
圖~\ref{fig:fig-parallel-scala} 展示我們提出最好的 {\em BST2} 資料結構，
在 6 核心且支持超執行緒的環境下，提供至少 8 倍快的效能改善。

\begin{figure}[!thb]
  \centering
  \subfigure[四種不同組合的運行時間]{
    \includegraphics[width=0.45\linewidth]{\GraphicPath/fig-parallel-n.pdf}
    \label{fig:fig-parallel}
  }
  \subfigure[右側棧出編碼的規模伸縮性]{
    \includegraphics[width=0.45\linewidth]{\GraphicPath/fig-parallel-p.pdf}
    \label{fig:fig-parallel-scala}
  }
  \caption{實驗於 E5-2620 主機，其包含 2 個 6 核心處理器且支持超執行緒技術}
\end{figure}
