hpcs-17-subord

slides.tex (16024B)

---

 % Created 2017-07-14 Пт 11:23
 % Intended LaTeX compiler: pdflatex
 \documentclass[12pt,aspectratio=169]{beamer}
 \usepackage{graphicx}
 \usepackage{booktabs}
 \usepackage{amsmath}
 \usepackage{amssymb}
 \usepackage{hyperref}
 \usepackage{tikz}
 \usetikzlibrary{shapes}
 \usepackage{cite}
 \usepackage{url}
 \usepackage{polyglossia}
 \input{preamble}
 \AtBeginSection[]{\frame{\sectionpage}}
 \usetheme{SaintPetersburg}
 
 \author{I.\,Gankevich \quad Yu.\,Tipikin \quad V.\,Korkhov}
 \date{July, 2017}
 \title{Subordination: Providing resilience to simultaneous failure of multiple cluster nodes}
 \institute{Saint Petersburg State University}
 \setdefaultlanguage{english}
 
 
 \definecolor{spbuGreen}{RGB}{40,160,40}
 \definecolor{spbuBlue}{RGB}{40,40,160}
 
 % physical layer
 \tikzset{Node/.style={rectangle,draw=spbuDarkGray,line width=3pt}}
 \tikzset{Switch/.style={circle,draw=gray,fill=gray,line width=7pt,solid}}
 \tikzset{PhysicalLink/.style={draw=gray,line width=7pt,solid}}
 \tikzset{NetworkLink/.style={draw=black,line width=3pt,dashed}}
 
 % logical layer
 \tikzset{Daemon/.style={ellipse,draw=spbuBlue,line width=3pt,solid,scale=0.65}}
 \tikzset{DaemonLink/.style={draw=spbuBlue,line width=3pt,solid}}
 
 % application layer
 \tikzset{Process/.style={ellipse,draw=spbuGreen,line width=3pt,solid}}
 \tikzset{ProcessEdge/.style={draw=spbuGreen,line width=3pt,solid,->}}
 
 
 \tikzset{Node/.style={rectangle,draw=spbuDarkGray,thick}}
 \tikzset{Task/.style={
 	ellipse,
 	draw=spbuGreen,
 	line width=3pt,
 	dashed,
 	anchor=center,
 	text=spbuGreen
 }}
 \tikzset{Kernel/.style={Task,solid,line width=2pt}}
 \tikzset{TaskEdge/.style={
 	ProcessEdge,
 	draw=spbuGreen,
 	solid,
 	->,
 	line width=2pt
 }}
 \tikzset{PseudoKernelEdge/.style={draw=spbuGreen,line width=3pt,dashed}}
 \tikzset{Label/.style={label distance=0.1cm,text=spbuTerracotta}}
 \tikzset{TaskLabel/.style={label distance=0.1cm,text=spbuGreen}}
 \tikzset{KernelPool/.style={
 	rectangle,
 	draw=spbuDarkGray,
 	minimum width=4.7cm,
 	minimum height=0.9cm,
 	line width=2pt,
 	thick
 }}
 
 \begin{document}
 
 \maketitle
 
 \begin{frame}{Motivation}
 	Looking for ways to develop fault-tolerant HPC applications without
 	checkpoints.
 	\vfill\pause
 	The outcome:
 
 	a scheduler with C++ API which replaces both batch job scheduler and
 	message passing interface.
 \end{frame}
 
 \begin{frame}{System architecture}
 	\begin{columns}[T]
 		\begin{column}{0.2\textwidth}
 			\input{tex/cluster-0}
 		\end{column}
 		\begin{column}{0.2\textwidth}
 			\input{tex/frame-0}
 		\end{column}
 		\begin{column}{0.2\textwidth}
 			\input{tex/frame-3}
 		\end{column}
 		\begin{column}{0.2\textwidth}
 			\input{tex/frame-4}
 		\end{column}
 	\end{columns}
 	\vfill
 	\begin{center}
 		\input{tex/legend}
 	\end{center}
 \end{frame}
 
 \begin{frame}{Application architecture}
 	\centering
 	\includegraphics{build/ppl.pdf}
 \end{frame}
 
 \section{Node discovery algorithm}
 
 \begin{frame}{Hierarchy of cluster nodes}
 	\begin{equation*}
 		\forall n_1 \forall n_2 \in \mathcal{N},
 		\forall f \colon \mathcal{N} \rightarrow \mathcal{R}^n 
 		\Rightarrow (f(n_1) < f(n_2) \Leftrightarrow \neg (f(n_1) \geq f(n_2)))
 	\end{equation*}
 	Here \(n\) is node rank~--- node's position in the network IP-address
 	range.
 	\vfill
 	\begin{columns}[T]
 		\begin{column}{0.35\textwidth}
 			\begin{itemize}
 				\item Strict total order.
 				\item Static node positions in the hierarchy.
 			\end{itemize}
 		\end{column}
 		\begin{column}{0.55\textwidth}
 			\begin{tikzpicture}[x=2.5cm,y=-1cm]
 				\node[Node] (M) at (2,0) {\texttt{10.0.0.1}};
 				\node[Node] (S1) at (1.25,1) {\texttt{10.0.0.2}};
 				\node[Node] (S2) at (2.75,1) {\texttt{10.0.0.3}};
 				\node[Node] (S3) at (0.75,2) {\texttt{10.0.0.4}};
 				\node[Node] (S4) at (1.75,2) {\texttt{10.0.0.5}};
 				\node[Node] (S5) at (2.75,2) {\texttt{10.0.0.6}};
 				\path[thick] (M) edge (S1);
 				\path[thick] (M) edge (S2);
 				\path[thick] (S1) edge (S3);
 				\path[thick] (S1) edge (S4);
 				\path[thick] (S2) edge (S5);
 			\end{tikzpicture}
 			\begin{center}
 				\texttt{fanout=2, nodes=6}
 			\end{center}
 		\end{column}
 	\end{columns}
 \end{frame}
 
 \begin{frame}{Example}
 	\framesubtitle{\texttt{fanout=2, nodes=100, network=10.0.0.0/8}}
 	\centering
 	\includegraphics<1>[width=0.9\linewidth]{build/graph.eps}
 	\includegraphics<2>[width=0.9\linewidth,trim={20cm 10cm 10cm 5cm},clip]{build/graph.eps}
 \end{frame}
 
 \begin{frame}{Performance of node discovery algorithm}
 	\framesubtitle{4 physical nodes, 400 virtual nodes, fanout=2}
 	\centering
 	\includegraphics[width=0.8\linewidth]{figures/node-discovery.eps}
 \end{frame}
 
 \begin{frame}{Node discovery algorithm: summary}
 	\begin{itemize}
 		\item Arranges cluster nodes into the hierarchy with strict total
 			order.
 		\item Scalable to a large number of cluster nodes.
 		\item Simple and reliable.
 	\end{itemize}
 	\vfill
 	\begin{center}
 		The purpose of node hierarchy is to distribute the load on the cluster.
 	\end{center}
 \end{frame}
 
 \section{Kernel processing algorithm}
 
 \begin{frame}{Example}
 	\begin{tikzpicture}[x=3cm,y=-0.9cm]
 		\node (dummy) at (0,0) {};
 
 		\node<1-5> (kernellabel) at (2,-1) {Kernels};
 		\node<1-5> (kernelpoollabel) at (4,-1) {Kernel pool};
 
 		\node<1-5>[Kernel] (task1) at (2,0) {task1};
 		\node<1>[KernelPool] (pool0) at (4,0) {\small\texttt{task1.act()}};
 		\node<1>[KernelPool] (pool1) at (4,1) {};
 		\node<1>[KernelPool] (pool2) at (4,2) {};
 		\node<1>[KernelPool] (pool3) at (4,3) {};
 		\node<1>[KernelPool] (pool4) at (4,4) {};
 
 		\node<2-5>[Kernel] (sub1) at (1.25,1.5) {sub1};
 		\node<2-4>[Kernel] (sub2) at (2.75,1.5) {sub2};
 		\path<2-5>[TaskEdge] (task1) edge (sub1);
 		\path<2-4>[TaskEdge] (task1) edge (sub2);
 		\node<2>[KernelPool] (pool0) at (4,0) {\small\texttt{sub1.act()}};
 		\node<2>[KernelPool] (pool1) at (4,1) {\small\texttt{sub2.act()}};
 		\node<2>[KernelPool] (pool2) at (4,2) {};
 		\node<2>[KernelPool] (pool3) at (4,3) {};
 		\node<2>[KernelPool] (pool4) at (4,4) {};
 
 		\node<3-4>[Kernel] (subsub1) at (0.75,3) {subsub1};
 		\node<3-4>[Kernel] (subsub2) at (1.75,3) {subsub2};
 		\path<3-4>[TaskEdge] (sub1) edge (subsub1);
 		\path<3-4>[TaskEdge] (sub1) edge (subsub2);
 		\node<3>[KernelPool] (pool0) at (4,0) {\small\texttt{sub2.act()}};
 		\node<3>[KernelPool] (pool1) at (4,1) {\small\texttt{subsub1.act()}};
 		\node<3>[KernelPool] (pool2) at (4,2) {\small\texttt{subsub2.act()}};
 		\node<3>[KernelPool] (pool3) at (4,3) {};
 		\node<3>[KernelPool] (pool4) at (4,4) {};
 
 		\path<4>[TaskEdge] (subsub1) edge[bend left] (sub1);
 		\path<4>[TaskEdge] (subsub2) edge[bend right] (sub1);
 		\path<4>[TaskEdge] (sub2) edge[bend right] (task1);
 		\node<4>[KernelPool] (pool0) at (4,0) {\small\texttt{task1.react(sub2)}};
 		\node<4>[KernelPool] (pool1) at (4,1) {\small\texttt{sub1.react(subsub1)}};
 		\node<4>[KernelPool] (pool2) at (4,2) {\small\texttt{sub1.react(subsub2)}};
 		\node<4>[KernelPool] (pool3) at (4,3) {};
 		\node<4>[KernelPool] (pool4) at (4,4) {};
 
 		\path<5>[TaskEdge] (sub1) edge[bend left] (task1);
 		\node<5>[KernelPool] (pool0) at (4,0) {\small\texttt{task1.react(sub1)}};
 		\node<5>[KernelPool] (pool1) at (4,1) {};
 		\node<5>[KernelPool] (pool2) at (4,2) {};
 		\node<5>[KernelPool] (pool3) at (4,3) {};
 		\node<5>[KernelPool] (pool4) at (4,4) {};
 
 		\node<6> (task1) at (2,0) {Programme ends};
 
 	\end{tikzpicture}
 	\note<1>{
 		\begin{itemize}
 			\item Left --- kernels, right --- execution queue (pool). Animation shows how kernels create subordinates and collect results from them.
 			\item The main difference compared to the jobs is that a task completes only when all its subordinates complete (it can not complete earlier). So, this model is more like asynchronous execution of subroutines (coroutines), but coroutines also do not have hierarchy.
 		\end{itemize}
 	}
 \end{frame}
 
 \begin{frame}{Kernel processing algorithm: summary}
 	\begin{itemize}
 		\item Kernels are like procedure calls, but asynchronous.
 		\item The number of kernels is decoupled from the number of cluster
 			nodes to aid in load balancing.
 	\end{itemize}
 	\vfill
 	\begin{center}
 		The purpose of kernel hierarchy is to determine who is responsible for
 		re-executing kernels from failed cluster nodes.
 	\end{center}
 \end{frame}
 
 \section{Recovery from master node failure}
 
 \begin{frame}
 	\frametitle{Handling master node failure}
 	\centering
 	\begin{tikzpicture}[remember picture,x=3cm,y=-3cm]
 		\node[Node] (A1) at (0,0) {A};
 		\node[Node] (B1) at (1,0) {B};
 		\node[Node] (C1) at (0,1) {C};
 		\node[Node] (D1) at (1,1) {D};
 	\end{tikzpicture}
 	\begin{tikzpicture}[remember picture,overlay]
 		\path[thick] (A1) edge (B1);
 		%\path[thick] (A1) edge (C1);
 		%\path[thick] (A1) edge (D1);
 		\path[thick] (B1) edge (C1);
 		\path[thick] (B1) edge (D1);
 		%\path[thick] (C1) edge (D1);
 	\end{tikzpicture}
 	\only<2->{%
 		\begin{tikzpicture}[remember picture,overlay]
 			\node[Task,label={[TaskLabel]90:Master\vphantom{p}}] (Master) at (A1.center) {\phantom{A}};
 		\end{tikzpicture}%
 	}
 	\only<3->{%
 		\begin{tikzpicture}[remember picture,overlay]
 			\node[Task,label={[TaskLabel]90:Backup}] (MasterCopy) at (B1.center) {\phantom{A}};
             \path[TaskEdge] (Master) edge (MasterCopy);
         \end{tikzpicture}%
     }
     \only<4->{%
         \begin{tikzpicture}[remember picture,overlay]
             \node[Task,label={[TaskLabel]0:Task1}] (Task1) at (B1.center) {\phantom{A}};
         \end{tikzpicture}%
     }
     \only<5->{%
         \begin{tikzpicture}[remember picture,overlay]
             \node[Task,label={[TaskLabel]180:Sub1}] (Sub1) at (A1.center) {\phantom{A}};
             \node[Task,label={[TaskLabel]180:Sub2}] (Sub2) at (C1.center) {\phantom{A}};
             \node[Task,label={[TaskLabel]0:Sub3}] (Sub3) at (D1.center) {\phantom{A}};
             \path[TaskEdge] (Task1) edge[bend left] (Sub1);
             \path[TaskEdge] (Task1) edge (Sub2);
             \path[TaskEdge] (Task1) edge (Sub3);
         \end{tikzpicture}%
     }
     \note<5>{
         \begin{itemize}
             \item Here A, B, C, D --- cluster nodes and Master, Backup, Task1, Sub1, Sub2, Sub3 --- tasks.
             \item Backup is a copy of Master which is sent along with Task1 to the subordinate node.
             \item Task1 represent one sequential step of a programme. There can be any number of seq. steps in a programme, and when Backup node fails, the current step is restarted from the beginning.
             \item When node B, C or D fails, corresponding master task restarts failed subordinates (Task1 restart Sub1, Master restarts Task1 etc.). When node A fails, Master task is recovered from Backup (its copy).
         \end{itemize}
     }
 \end{frame}
 
 \begin{frame}{Case study: ARMA ocean wavy surface generator}
 	\begin{columns}[T]
 		\begin{column}{0.25\textwidth}
 			MA model:
 			\begin{equation*}
 				\zeta_{\vec{x}} =
 				\sum\limits_{\vec{y}=\vec{0}}^{N}
 				\Theta_{\vec{y}}\,\epsilon_{\vec{x} - \vec{y}}
 			\end{equation*}
 			\vskip1cm
 			MA coefficients:
 			\begin{equation*}
 				K_{i,j,k} = 
 				\left[
 					\displaystyle
 					\sum\limits_{l=i}^{q_1}
 					\sum\limits_{m=j}^{q_2}
 					\sum\limits_{n=k}^{q_3}
 					\Theta_{l,m,n}\Theta_{l-i,m-j,n-k}
 				\right]
 				\sigma_\epsilon^2
 			\end{equation*}
 		\end{column}
 		\begin{column}{0.65\textwidth}
 			\vskip1cm
 			\includegraphics[width=\linewidth]{figures/wavy.eps}
 		\end{column}
 	\end{columns}
 \end{frame}
 
 \begin{frame}{Performance with master node failure (ARMA)}
 	\centering
 	\begin{columns}
 		\begin{column}{0.49\textwidth}
 			\includegraphics[width=\linewidth]{figures/performance-arma.eps}
 		\end{column}
 		\begin{column}{0.49\textwidth}
 			\includegraphics[width=\linewidth]{figures/overhead-arma.eps}
 		\end{column}
 	\end{columns}
 \end{frame}
 
 \begin{frame}
 	\frametitle{Case study: NDBC dataset preprocessing}
 	\begin{center}
 		\begin{tabular}{ll}
 			\toprule
 			Dataset size & 144MB \\
 			Dataset size (uncompressed) & 770MB \\
 			No.~of wave stations & 24 \\
 			Time span & 3 years (2010--2012) \\
 			Total no.~of spectra & 445422 \\
 			\bottomrule
 		\end{tabular}
 	\end{center}
 	\vfill
 	Spectrum reconstruction formula:
 	\begin{equation*}
 		S(\omega, \theta) = \frac{1}{\pi}\!
 		\left[
 			\frac{1}{2} + 
 			r_1 \cos \left( \theta - \alpha_1 \right) +
 			r_2 \sin \left( 2 \left( \theta - \alpha_2 \right) \right)
 		\right]\!
 		S_0(\omega).
 	\end{equation*}
 	\note{
 		Master node fail over technique is evaluated on the example of wave energy spectra processing application. This programme uses NDBC (\href{http://www.ndbc.noaa.gov/}{National Data Buoy Center}) dataset to reconstruct frequency-directional spectra from wave rider buoy measurements and compute variance. Each spectrum is reconstructed from five variables using the following formula.
 		\begin{equation*}
 			S(\omega, \theta) = \frac{1}{\pi}
 			\left[
 				\frac{1}{2} + 
 				r_1 \cos \left( \theta - \alpha_1 \right) +
 				r_2 \sin \left( 2 \left( \theta - \alpha_2 \right) \right)
 			\right]
 			S_0(\omega).
 		\end{equation*}
 		Here $\omega$ denotes frequency, $\theta$ is wave direction, $r_{1,2}$ and $\alpha_{1,2}$ are parameters of spectrum decomposition and $S_0$ is non-directional spectrum; $r_{1,2}$, $\alpha_{1,2}$ and $S_0$ are acquired through measurements. Properties of the dataset which is used in evaluation are listed in Table.
 	}
 \end{frame}
 
 \begin{frame}{Performance with master node failure (NDBC)}
 	\centering
 	\begin{columns}
 		\begin{column}{0.49\textwidth}
 			\includegraphics[width=\linewidth]{figures/performance-ndbc.eps}
 		\end{column}
 		\begin{column}{0.49\textwidth}
 			\includegraphics[width=\linewidth]{figures/overhead-ndbc.eps}
 		\end{column}
 	\end{columns}
 \end{frame}
 
 \begin{frame}{Recovery from master node failure: summary}
 	\centering
 	Works only when master kernel has at most one subordinate at a time.
 	\vfill
 	How to adapt it for multiple node failures?
 \end{frame}
 
 \section{Recovery from multiple node failures}
 
 \begin{frame}[t]
 	\frametitle{Transform kernel hierarchy}
 	\vskip1cm
 	\begin{tikzpicture}[x=2cm,y=-1.5cm]
 		\node[Kernel] (task1) at (2,0) {task1};
 		\node[Kernel] (sub1) at (1,1) {sub1};
 		\node[Kernel] (sub2) at (2,1) {sub2};
 		\node[Kernel] (sub3) at (3,1) {sub3};
 		\path[TaskEdge] (task1) edge (sub1);
 		\path[TaskEdge] (task1) edge (sub2);
 		\path[TaskEdge] (task1) edge (sub3);
 		\node<2->[
 			single arrow,
 			fill=spbuGray,
 			minimum height=1.5cm,
 			minimum width=0.5cm
 		] at (4,0.5) {};
 		\node<2->[Kernel] (xtask1) at (6,0) {task1};
 		\node<2->[Kernel] (xsub1) at (5,1) {sub1};
 		\node<2->[Kernel] (xsub2) at (6,1.5) {sub2};
 		\node<2->[Kernel] (xsub3) at (7,2) {sub3};
 		\path<2->[TaskEdge] (xtask1) edge (xsub1);
 		\path<2->[TaskEdge] (xsub1) edge[bend right] (xsub2);
 		\path<2->[TaskEdge] (xsub2) edge[bend right] (xsub3);
 		\path<2->[PseudoKernelEdge] (xtask1) edge (xsub2);
 		\path<2->[PseudoKernelEdge] (xtask1) edge (xsub3);
 	\end{tikzpicture}
 	\begin{center}
 		\only<3>{\alert{Very inefficient}}
 		\only<4->{%
 			Solution: infer relationship between subordinate kernels by
 			recording IP-addresses of cluster nodes they were sent to.
 		}
 	\end{center}
 \end{frame}
 
 \begin{frame}{Overhead of recovery from multiple node failures}
 	\begin{columns}[T]
 		\begin{column}{0.45\textwidth}
 			\vskip-1cm
 			\includegraphics[width=\linewidth]{test-1-phys}\newline\vspace{-1cm}
 			\includegraphics[width=\linewidth]{test-2-phys}
 		\end{column}
 		\begin{column}{0.45\textwidth}
 			\vskip-1cm
 			\includegraphics[width=\linewidth]{test-1-virt}\newline\vspace{-1cm}
 			\includegraphics[width=\linewidth]{test-2-virt}
 		\end{column}
 	\end{columns}
 \end{frame}
 
 \begin{frame}{Conclusions}
 	\begin{itemize}
 		\item Having hierarchy (strict total order) between tasks (kernels) is
 			sufficient to devise algorithms for recovery from cluster node
 			failures.
 		\item Each cluster node having an IP-address (or any other unique
 			identifier) is the only assumption of these algorithms.
 		\item The whole system acts as the router for kernels which
 			reconfigures itself upon node failures.
 	\end{itemize}
 \end{frame}
 
 \begin{frame}
 	\centering%
 	\vspace{1.0cm}%
 	\Large\textbf{Thank you for attention!}
 \end{frame}
 
 \end{document}