commit db56d797a1bedd3b3ec7390bf35a4e75d23d9d87
parent 060977952b39bfc36025f9374a98e212c2b8bd5a
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Thu, 23 Mar 2017 16:12:43 +0300
Discuss linear search complexity.
Diffstat:
| src/body.tex | | | 52 | +++++++++++++++++++++++++++++++++++++++------------- |
1 file changed, 39 insertions(+), 13 deletions(-)
diff --git a/src/body.tex b/src/body.tex
@@ -300,16 +300,15 @@ code increases linearly with the number of nodes
(Figure~\ref{fig:test-3-phys-ndebug-226}), however, its absolute value is small
compared to the programme run time. Linear increase in overhead is attributed
to the fact that for each subordinate kernel linear search algorithms are used
-when sending or receiving it from other node to maintain a list of its
+when sending or receiving it from other node to maintain an array of its
neighbours. When subordinate kernel is sent to remote node, all its left
-neighbours IP addresses are added to the neighbours list without duplication,
+neighbours IP addresses are added to the neighbours array without duplication,
and the kernel itself is appended to the global internal map which stores
principal kernels and theirs subordinates; when subordinate kernel returns from
-the remote node, it is removed from the list of its principal subordinates
-(retrieved from the internal map), which also requires linear search. Linear
-complexity can be avoided by replacing lists with sets or maps, but the total
-overhead is small, so we deemed this optimisation unnecessary complication of
-the source code.
+the remote node, it is removed from the array of its principal subordinates
+(retrieved from the internal map), which also requires linear search. So, the
+second experiment showed that for real-world programme overhead of multiple
+node failure handling is small.
%\begin{figure}
% \centering
@@ -323,10 +322,9 @@ the source code.
\begin{figure}
\centering
\includegraphics{test-3-phys-ndebug-226-real}
- \caption{Overhead of failure handling code for different
- number of physical cluster nodes (real run, only overhead was measured, no
- debug output, cluster
- 226).\label{fig:test-3-phys-ndebug-226}}
+ \caption{Overhead of failure handling code for different number of physical
+ cluster nodes (real run, only overhead was measured, no debug output,
+ cluster 226).\label{fig:test-3-phys-ndebug-226}}
\end{figure}
\begin{figure}
@@ -334,12 +332,40 @@ the source code.
\includegraphics{test-3-virt-ndebug-226}
\caption{Overhead of failure handling code for different
number of virtual cluster nodes (dry run, only overhead was measured, no
- debug output, cluster
- 226).\label{fig:test-3-virt-ndebug-226}}
+ debug output, cluster 226).\label{fig:test-3-virt-ndebug-226}}
+\end{figure}
+
+\begin{figure}
+ \centering
+ \includegraphics{test-3-phys-ndebug-226-ppn}
+ \caption{Overhead of failure handling code for different number of physical
+ cluster nodes (real run, only overhead was measured, no debug output,
+ cluster 226, multiple procs per
+ node).\label{fig:test-3-phys-ndebug-226-ppn}}
\end{figure}
\section{Discussion}
+Linear complexity in multiple node failure handling code can be avoided by
+replacing arrays with sets or maps, but the total overhead is small, so we
+deemed this optimisation unnecessary complication of the source code. Moreover,
+in real-world scenario it is probably impractical to copy principal kernel
+state to each subordinate node, and minimal number of copies may be configured
+in the programme instead. In this case using maps and sets over arrays may
+incur more overhead as they require certain amount of elements to make
+searching for an element more efficient than in
+arrays~\cite{lemiere-or-straustrup-TODO}. There is no such thing as minimal
+number of object copies that ensures fault-tolerance in HPC, but for parallel
+file systems there is a number of replicas. This number is typically set to 2
+or 3 depending on the particular site. We believe that there is no need to set
+number of object copies more than that, as it allows to tolerate simultaneous
+failure of 2 and 3 nodes respectively: it should be more than enough to
+tolerate node failures which are common at large
+scale~\cite{mean-time-between-failures-darpa-TODO}. So, using arrays with
+linear search complexity is more efficient than maps and sets, because the
+number of elements in them is small, and linear search takes less time than
+fixed time hash-based lookup.
+
% Brainstorming results (various random thoughts).
There are two scenarios of failures. Failure of more than one node at a time
