%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Chapter 8. Shortest Path Case
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Case Study: Dijkstra's Shortest Path Algorithm}\label{ch:Dijkstra}
\section{Dijkstra's Shortest Path Algorithm}
\begin{figure}[h]
\centering
\includegraphics[width=0.5\textwidth]{./dijkstra/figure/DijkstraExample.eps}
\caption{The shortest path solved by the Dijkstra's algorithm.}
\label{fig:DijkstraExample}
\end{figure}
The Dijkstra's shortest path algorithm solves the shortest path problem that has one starting point and non-negative
path costs. The input graph contains one starting node, one ending node and other intermediate nodes. Each edge connects
two nodes in the graph and has a distance cost.
The algorithm finds a path with the lowest cost from the starting node to the ending one.
Figure~\ref{fig:DijkstraExample} illustrates how Dijkstra's algorithm solves the shortest path problem for a graph with
7 nodes and 10 edges.
\begin{enumerate}
  \item Set the node \keyword{Start} to be the first node. From this node, calculate the distance to node \keyword{A}
  (path cost = 3) and the distance to node \keyword{B} (path cost = 5). As node \keyword{A} has the shortest distance,
  it is set to be the next node.
  \item Start from node \keyword{A} and calculate the distances of its neighbouring nodes. The distance to node
  \keyword{D} (through node \keyword{A}) is 7 ($3+4$), and the distance to node \keyword{C} is 5 ($3+2$). As the path to
  node \keyword{C} through node \keyword{A} has the shortest path cost, node \keyword{C} is set to be the
  next node.
  \item From node \keyword{C}, the direct path to node \keyword{End} (path cost = 11) has lower cost than the indirect
  path through node \keyword{D} (path cost = 13). Thus, the shortest path from node \keyword{Start} to node \keyword{End}
   is through node \keyword{A} and node \keyword{C} with the lowest path cost of 11.
\end{enumerate}
\section{JStar Dijkstra Program}
The JStar Dijkstra program implements the Dijkstra's algorithm to find the shortest path to every node of a random
connected graph.
The source code of the JStar Dijkstra program is shown in the Listing~\ref{sourcecodeofdijkstra} of
Appendix~\ref{ch:dijkstracase}.
This program is a typical two-phase task: the graph generation and the shortest-path algorithm.
We chose this case study because the shortest path phase has dynamically varying amounts of available parallelism that
are dependent on the shape of the graph and the lengths of edges, so static scheduling strategies are not adequate.
The graph generation creates a directed graph with one million vertices and two million edges where each edge has a
random cost ranging from 1 to 10. The Dijkstra's algorithm finds the shortest path from the vertex (0) to every vertex
of the graph.
The procedure of the JStar Dijkstra program is described as follows:
\begin{enumerate}
\item Graph Generation Phase:\\
For each vertex $V_{1}\in 1\dots1,000,000$, randomly choose another vertex $V_{2}\in 0\dots(V_{1}-1)$.
Then create an edge $(V_{1},V_{2})$ with a random length ($1\dots10$).
Repeat this step until the
graph forms a connected tree with one million vertices and one million edges.
Generate another one million random edges
between the vertices. Randomly choose two vertices from the tree and connect them with a directed and random length
edge. Repeat this step until another one million edges are added to the tree. Note that the tree contains one million
vertices and two million edges.
\item Shortest Path Phase:\\
Use Dijkstra's algorithm to find the shortest path from the initial node (Vertex = 0) to the every other node.
\end{enumerate}
\begin{figure}[h]
\centering
\includegraphics[height=0.5\textheight]{./dijkstra/figure/Dijkstra.TableSchema.eps}
\caption{Table schema of the JStar Dijkstra program.}
\label{fig:DijkstraTableSchema}
\end{figure}
\par The table schema of the JStar Dijkstra program is shown in Figure~\ref{fig:DijkstraTableSchema}. The
\class{CmdLineArg} tuple defines the graph size and creates the \class{GenerateGraph} tuples, generating the random
connected graph with one million vertices and two million edges. The \class{Vertex} and the \class{Edge} tables store
the vertices and the edges respectively, and are read-only during the shortest path phase.
Each \class{Done} tuple stores the current node for one iteration. For each
current node, the \class{Estimate} tuple calculates the distances for all its neighboring and unvisited nodes and sets
the next current node which has the lowest path cost. The \class{PrintGraph} tuple prints out the graph.
\section{Benchmark Configuration}
\begin{table}[h!]
\centering
\subfloat[Hardware specification]{
\begin{tabular}{| l | c |}
\toprule
\multicolumn{2}{|>{\columncolor[gray]{.8}}c|}{NeSI compute-b1-002-p}\\
\midrule
CPU &  Intel\textsuperscript{\textregistered} Xeon\textsuperscript{\textregistered} CPU E5-2680 @ 2.70 GHz\\
& (total of 16 cores)\\\hline
L1 cache & 32K\\\hline
L2 cache & 256K\\\hline
L3 cache & 20480K\\\hline
RAM & 126GB RAM \\\hline
Disk & 200 TB shared GPFS\\\hline
OS & 64-Bit Linux operating system \\
& (kernel version 2.6.32-279.14.1.el6.x86\_64)\\\hline
JAVA & 64-Bit JRE version 1.7.0\_17\\
\bottomrule
\end{tabular}
\label{tab:Dijkstra_hardware}
}\quad
\subfloat[Java Virtual Machine options]{
\begin{tabularx}{0.95\textwidth}{|X|}
\toprule
\multicolumn{1}{|c|}{\cellcolor[gray]{0.8}JVM options}\\
\midrule
\flag{-Xmx8G} sets the maximum Java heap size to be 8 GB.\\\hline \flag{-verbose:gc} enable verbose garbage
collector.\\\hline
\flag{-Xbatch} stops the program while the hot spot compiler is recompiling/optimising the
code.\\\hline
\flag{-XX:+PrintCompilation} prints the message when one method is compiled.\cite{website:javahotspotvm}\\\hline
\flag{-XX:+PrintTenuringDistribution} prints the tenuring age information.\cite{website:javahotspotvm}\\\hline
\flag{-XX:+PrintGCDetails} print messages at the garbage collection.\cite{website:javahotspotvm}\\\hline
\flag{-XX:+UseCondCardMark} avoids the false sharing at the card tables in the garbage collection.\cite{website:UseCondCardMark}
\\\hline
\flag{-XX:BiasedLockingStartupDelay=0} enables the objects in the HotSpot by default to be created with biased
locking at the JVM startup.\cite{website:BiasedLockingStartupDelay}\\\bottomrule
\end{tabularx}
\label{tab:DijkstraJVM}
}
\caption{Benchmark configuration of the JStar Dijkstra program.}
\label{tab:Dijkstra_BenchmarkConfig}
\end{table}
The benchmark experiments were conducted on one of computing nodes (compute-b1-002-p) in the NeSI Pan cluster.
The detailed hardware specification is shown in Table~\ref{tab:Dijkstra_BenchmarkConfig}\subref{tab:Dijkstra_hardware}.
And the JVM Arguments for benchmarking the JStar Dijkstra program are shown in the
Table~\ref{tab:Dijkstra_BenchmarkConfig}\subref{tab:DijkstraJVM}. The standard operation procedure of job submission to
the Pan cluster in described in Appendix~\ref{ch:NeSISOP}.
To improve the performance of the Java garbage collector, we benchmarked the parallel JStar Dijkstra program with two
additional JVM options:\keyword{UseCondCardMark} and \keyword{BiasedLockingStartupDelay}.
\section{Performance Tuning Process}
This section describs how we tuned the performance of the JStar Dijkstra program and implemented the efficient data
structures. All the speedups are based on the average execution time of the sequential optimized JStar Dijkstra program.
\subsection{In-lining Tuples}\label{sec:DijkstraInlineTuples}
\begin{figure}[h]
	\centering
	\subfloat[The naive program]{
		\includegraphics[width=0.45\textwidth]{./dijkstra/figure/dependency_native.eps}
		\label{fig:DijkstraNativeDependency}
	}\quad
	\subfloat[The optimized program]{
		\includegraphics[width=0.45\textwidth]{./dijkstra/figure/dependency_optimized.eps}
		\label{fig:DijkstraOptimizedDependency}
	}\\
	\subfloat{
	\begin{tabular}{c}
	\hfill TRIGGER(Rule):$\boldsymbol{\longrightarrow}$\hspace{5mm}PUT(Gamma Database):{\color{red}${-\rightarrow}$}\\
	\hfill PUT(Delta Tree):{\color{red}$\longrightarrow$}\hspace{5mm}GET(Gamma Database):{\color{blue}$-\rightarrow$}\\
	\end{tabular}
	}
	\caption[Task dependency graph of the JStar Dijkstra programs.]
{Task dependency graph of naive and optimized JStar Dijkstra programs.}
\label{fig:Dijkstradependency}
\end{figure}
The task dependency of the naive JStar Dijkstra program is shown in
Figure~\ref{fig:Dijkstradependency}\subref{fig:DijkstraNativeDependency}.
The \class{Estimate} tuples are the only tuple kind which will trigger the other rule (\method{Rule4}), and thus the
\flag{noDelta} optimisation can be applied on all the other tables, including \class{CmdLineArg}, \class{GenerateGraph},
\class{Vertex}, \class{Edge} and \class{Done}. The \flag{noGamma} optimisation can also be applied to all the tables,
except for the \class{Done} and the \class{Edge} tables because they will be served as the query tables for the rules in
the program. The task dependency of the optimized JStar Dijkstra program is shown in Fig.~\ref{fig:Dijkstradependency}
\subref{fig:DijkstraOptimizedDependency}.
Note that the \class{PrintGraph} tuples are not shown in the graph as they are served as the debugger in this program.
And we will ignore all the debuggers and tracers to get the \keyword{unbiased} results when benchmarking the JStar program.
\begin{table}[h]
\centering
\begin{tabular}{|c|c|c|}
\toprule
\textbf{Tuple} & \textbf{Delta Tree} & \textbf{Gamma Database}\\
\midrule
CmdLineArgs   & $\surd$ & $\times$ \\
GenerateGraph & $\times$ & $\times$\\
Vertex        & $\times$ & $\times$\\
Edge          & $\times$ & $\surd$\\
PrintGraph    & $\times$ & $\times$\\
Estimate      & $\surd$ & $\times$ \\
Done          & $\times$ & $\surd$\\
\bottomrule
\end{tabular}
\caption{The inline tuple list of JStar Dijkstra program.}
\label{tab:DijkstraInlineTable}
\end{table}
\par Table~\ref{tab:DijkstraInlineTable} is the tuple table list after we apply both of the \flag{noDelta} and the
\flag{noGamma} optimisation on the JStar Dijkstra program. It shows that the optimized program will put the
\class{Estimate} tuples into the Delta tree, and insert the \class{Edge} and the \class{Done} tuples into the tables in
the Gamma database. All the other tuples will not kept in the data storage but discarded immediately after triggering
their associative rules.
\subsection{Improving the Parallelism}
The JStar Dijkstra program is composed of two phase: the graph generation and the shortest path.
The graph generation phase is a bottleneck that downgrades the overall performance of the JStar Dijkstra program.
By printing out the JVM information with the profile flag (\flag{-Xprof}), We found out that the sequential naive
implementation of the JStar Dijkstra program spent most of its running time generating the random graph. Thus, at this
phase we parallelized the graph creation task with 24 separate \class{GeneratingGraph} tuples, each generating
$^1/_{24}$ of the whole graph.
\par The shortest path phase is implemented by putting the \class{Estimate} tuples recursively. The \class{Estimate}
tuple takes the current node to calculate all the path costs of its adjacent nodes. Then it chooses the node with the
lowest cost to be the next starting node and then puts the current node with the path cost to the \class{Done} table.
If the next node is not the ending node, then it puts another \class{Estimate} tuple to continue finding the shortest
path. In this phase, the \class{Estimate}, \class{Done} and \class{Edge} are the only three tuple kinds which are
inserted or queried during the execution of the program. According to the task dependency graph in
Section~\ref{sec:DijkstraInlineTuples}, the parallelism of these tuples can be optimized by inlining the
\class{Estimate} tuples in the Gamma database and omitting the insertion of the \class{Done} and \class{Edge} tuples
into the Delta tree.
\begin{figure}
\centering
\includegraphics[width=0.95\textwidth]{./dijkstra/figure/Benchmark.Dijkstra.Optimisation.Speedup.eps}
\caption[Speedups of the optimized JStar Dijkstra program.]
{Speedups of the JStar Dijkstra program with the \flag{noDelta} and \flag{noGamma} optimisations
on a dual-CPU Intel Xeon E5-2680 (total of 16 cores).}
\label{fig:Benchmark.Dijkstra.Optimisation}
\end{figure}
\par We applied the above two optimisation strategies on the JStar Dijkstra program and measured the speedups which are
compared with the naive sequential implementation. The benchmark results in
Figure~\ref{fig:Benchmark.Dijkstra.Optimisation} show that our strategy can improve and scale the
performance with the maximum speedups of 6.37 (15 cores) that are not very scalable.
\par The goal of the next benchmark experiments is to find the most efficient data structures to make the optimized
JStar Dijkstra program to gain the best speedup. The experiments design focuses on the data structure of the Delta
tree and that of the Gamma database.
The benchmark experiments measure the speedup of the optimized JStar Dijkstra program with/varying the data structures
and the number of threads. The experiments are described in the following subsections:
\subsection{Optimizing the Delta Tree Data Structures}\label{sec:deltatreebenchmarks}
This benchmark experiment finds the efficient data structure for the Delta tree.
After optimizing the program, we found out that the \class{Estimate} tuple is the only one tuple kind in the Delta tree.
When a \class{Estimate} tuple is put into the Delta tree, it will insert this tuple to the data storage of the
\class{DeltaNodeInt} node with its \keyword{vertex} value as the key. As the number of tuples increases, the efficiency
and scalabilty of the \keyword{DeltaNodeInt} implementations can limit the speedup of the Delta tree. As a result, we
may upgrade the performance of the Delta tree by varying the data structures of the \class{DeltaNodeInt} nodes.
\par The benchmark experiment creates the integer Delta nodes with three kinds of implementations: the \class{DeltaNodeInt},
\class{ParallelDeltaNodeInt} and \allowbreak\class{ParallelDeltaNodeIntRange}. As the \class{DeltaNodeInt} does not support the
multi-threading, its average execution time is used as the base to calculate the absolute speedup for the other two
implementations. The relative speedup is the speedup relative to the parallel JStar Dijkstra program running with
one thread.
\begin{figure}[h]
\centering
\includegraphics[width=0.95\textwidth]{./dijkstra/figure/Benchmark.Dijkstra.DeltaTree.Speedup.eps}
\caption[Speedups of the \class{DeltaNodeInt} data structures.]
{Speedups of the optimized JStar Dijkstra program with the \flag{noDelta} and \flag{noGamma} optimisations and
varying the \class{DeltaNodeInt} data structure on a dual-CPU Intel Xeon E5-2680 (total of 16 cores).}
\label{fig:Benchmark.Dijkstra's.DeltaTree}
\end{figure}
\par Figure~\ref{fig:Benchmark.Dijkstra's.DeltaTree} is the benchmark results of the Delta tree data structures. It show
that the \class{ParallelDeltaNodeIntRange} has a slightly good but similar speedup as the \class{ParallelDeltaNodeInt}
with maximum absolute speedup of 6.41 (14 cores). But it has the poorer scalability and worse performance on the 15
cores with the absolute speedup of 4.67. As the \class{ParallelDeltaNodeInt}
is the naive data structure for the Delta tree, varying the Delta tree data structures in this case does not improve the
performance.
\subsection{Optimizing the \class{Done} Gamma Table}
After profiling the optimized JStar Dijkstra program, we found out that most of the time was spent on processing the
queries of the \class{Done} and the \class{Edge} tuples. The \class{Edge} Gamma table stores the path cost for each edge
in the graph. And the \class{Done} table stores the \keyword{visited} nodes whose shortest path has been found.
Thus, the JStar Dijkstra program will use the \class{Done} and \class{Edge} tables to estimate the shortest path for
each \keyword{unvisited} node in the graph. As the graph contains a large number of nodes and edges, querying tuples
from these two Gamma tables puts a heavy burden on the program.
\par The \class{Done} table contains only two integer field values, so we can simply use a one-dimensional \class{Array}
to store the \class{Done} tuples in Gamma. But as the Java array is not supported by the naive Gamma table (uses the
 \class{NavigableSet}), we created an implementation to make use of our new data structure. The benchmark
experiments in this subsection uses the \class{CHMDoneTable}, an alternative \class{Done} Gamma table, to improve the
efficiency of the Gamma database. And optimizing the data structures for the \class{Edge} table will be discussed in the
following subsection.
\begin{spacing}{1.0}
\begin{lstlisting}[label=sourcecodeofCHMDoneTable, caption=The Source Sode of \class{CHMDoneTable}]
package jstar.examples.dijkstra;
import ...
public class CHMDoneTable extends AbstractDoneTable{
	private int[] mGamma;
	...
	public Done moveToGamma(final Done done) {
		int vertex = done.getVertex();
		assert vertex != Integer.MIN_VALUE;  // cannot store this special value
		mGamma[vertex] = done.getDistance();
		return done;
	}
	...
	@Override
	public Done queryUnique(final int vertex) {
		int val = mGamma[vertex];
		if (val == Integer.MIN_VALUE) {
			throw new RuntimeException("CHMDoneTable.queryUnique(" + vertex + ")");
		}
		return new Done(vertex, mGamma[vertex]);
	}
	...
}
\end{lstlisting}
\end{spacing}
The \class{CHMDoneTable} is the customized \class{Done} table to enhance the performance of the JStar Gamma database.
Instead of using the Java \class{NavigableSet} implementation, the \class{CHMDoneTable} uses a one-dimensional integer
array to store the \class{Done} tuples in Gamma. The index of this array is defined as the node number and thus the
array length is equal to the total number of the nodes in the program. Each \keyword{element} is the shortest distance
(from the starting node) to its node number (the index). The source code of the \class{CHMDoneTable} is shown in the
List~\ref{sourcecodeofCHMDoneTable}. When a \class{Done} tuple is moved to the \class{CHMDoneTable}, the JStar runtime
accesses this array and assigns the tuple's \keyword{distance} to the element whose index is the tuple's
\keyword{vertex}. And the shortest distance of a node can be retrieved from the array by its \keyword{vertex}.
\begin{figure}[h]
\centering
\includegraphics[width=0.95\textwidth]{./dijkstra/figure/Benchmark.Dijkstra.CHMDoneTable.Speedup.eps}
\caption[Speedups of the \class{CHMDoneTable} data structures.]
{Speedups of the optimized JStar Dijkstra Program with the \class{CHMDoneTable} and \class{ParallelDeltaNodeInt} data
structures on a dual-CPU Intel Xeon E5-2680 (total of 16 cores).}
\label{fig:DijkstraCHMDoneTable}
\end{figure}
\par Figure~\ref{fig:DijkstraCHMDoneTable} is the benchmark results of the \class{CHMDoneTable} and the naive
implementation (\class{ConcurrentSkipListSet}). The speedup is relative to the total execution time of the sequential
optimized JStar Dijkstra program. The results show that \class{CHMDoneTable} has the better performance than the naive
one with maximum speedup of 10 (15 cores) and it also provides the scalability upto 9 threads.
\subsection{Optimizing the \class{Edge} Gamma Table}
We found out that the \method{Lookup} method of the \class{Edge} Gamma table slowed down the performance after profiling
the JStar Dijkstra program. To improve the efficiency of \class{Edge} Gamma table, we implemented the
\class{EdgeHashTable} to make use of Java array.
Because the \class{Edge.from} are dense ($0\dots999,999$) and because every query specifies \class{Edge.from}, we can
use an array to store the \class{Edge.from} as the index. But we can have several \class{Edge} tuples with the same
\class{from} values, so each entry in this array must be a \class{Set}.
\par This experiment creates the \class{Edge} table with 3 Java concurrent implementations: \class{ConcurrentSkipList},
\class{ConcurrentHashMap} and \class{ConcurrentHashMapV8}. Based on the previous experiments, the 
\class{ParallelDeltaNodeInt} is chosen to be data structure of the Delta tree and the \class{CHMDoneTable} is used
to create the \class{Done} table in the Gamma database.
\begin{figure}[h]
\centering
\includegraphics[width=0.95\textwidth]{./dijkstra/figure/Benchmark.Dijkstra.AbsoluteSpeedup.eps}
\caption[Speedups of the \class{Edge} data structures.]
{Speedups of the optimized JStar Dijkstra program with the \class{CHMDoneTable} and \class{ParallelDeltaNodeInt} and
varying the \class{Edge} Gamma table data structures on a dual-CPU Intel Xeon E5-2680 (total of 16 cores).}
\label{fig:Benchmark.Dijkstra}
\end{figure}
\par The speedup results are shown in Figure~\ref{fig:Benchmark.Dijkstra}. The speedup is the absolute speedup relative
to the sequential optimized JStar Dijkstra program, \begin{inparaenum}[\itshape a\upshape)] \item inlining the tuples,
\item using the \class{TreeSet} to create the \class{Done} and \class{Edge} table in Gamma, and \item using the
\class{DeltaNodeInt} (\class{TreeSet}) to create the Delta nodes for the \class{Estimate} tuples.
\end{inparaenum}
Benchmark results show that the speedups of \class{ConcurrentHashMap} and \class{ConcurrentHashMapV8} are double those
of \class{ConcurrentSkipList} from 1 to 10 cores. And \class{ConcurrentHashMapV8} has the maximum speedup of 20.6 with
10 cores while the \class{ConcurrentHashMap} has the best speedup of 19.94 with 10 cores. 
Regarding the scalability, these data structures fail to scale up the performance from 11 to 15 cores, except that
\class{ConcurrentSkipList} slightly increases the speedups. To achieve the best performance, \class{ConcurrentHashMapV8}
is recommended to implement the \class{Edge} table in the Gamma database.
\section{Conclusion}
In the Dijkstra's shortest path case study, we learned:
\begin{itemize}
  \item By using appropriate data structures for the Gamma tables (hand-written in this case, but with the potential to
  be automatically generated), the JStar Dijkstra program achieves a good speedup up to 10 cores with a maximum speedup
  of 20.6 compared to the sequential optimized JStar Dijkstra program.
  \item This program has complex structures to parallelize. It is not embarrassingly parallel but Delta tree dependent
  because at least 2 million \class{Estimate} tuples must be sorted in the Delta tree.
\end{itemize}
\cleardoublepage
