commit 3b7625d1ec34b96fc3e5f411bed14052209a877d
parent 492f9cb2b2734fb5cd600ee265c19553679a6a8a
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Sat, 15 Jul 2017 12:37:59 +0300
Add fancy diagram.
Diffstat:
| slides.tex | | | 101 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------------------- |
1 file changed, 77 insertions(+), 24 deletions(-)
diff --git a/slides.tex b/slides.tex
@@ -29,9 +29,18 @@
\tikzset{Task/.style={Process,anchor=center,draw=spbuGreen,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.5cm,minimum height=0.9cm,line width=2pt,thick}}
+\tikzset{KernelPool/.style={
+ rectangle,
+ draw=spbuDarkGray,
+ minimum width=4.7cm,
+ maximum width=4.7cm,
+ minimum height=0.9cm,
+ line width=2pt,
+ thick
+}}
\begin{document}
@@ -117,46 +126,49 @@
\begin{frame}{Example}
\begin{tikzpicture}[x=3cm,y=-0.9cm]
- \node (dummy) at (0,0) {};
+ \node (dummy) at (0.5,0) {};
- \node<1-5>[Kernel] (task1) at (2,0) {Task1};
- \node<1>[KernelPool] (pool0) at (4,0) {Task1::act()};
+ \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};
+ \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) {Sub1::act()};
- \node<2>[KernelPool] (pool1) at (4,1) {Sub2::act()};
+ \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};
+ \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) {Sub2::act()};
- \node<3>[KernelPool] (pool1) at (4,1) {SubSub1::act()};
- \node<3>[KernelPool] (pool2) at (4,2) {SubSub2::act()};
+ \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) {Task1::react(Sub2)};
- \node<4>[KernelPool] (pool1) at (4,1) {Sub1::react(SubSub1)};
- \node<4>[KernelPool] (pool2) at (4,2) {Sub1::react(SubSub2)};
+ \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) {Task1::react(Sub1)};
+ \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) {};
@@ -175,12 +187,14 @@
\begin{frame}{Kernel processing algorithm: summary}
\begin{itemize}
- \item It is like procedure calls, but asynchronous.
+ \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 decouple the number of parallel
- tasks from the number of cluster nodes.
+ The purpose of kernel hierarchy is to determine who is responsible for
+ re-executing kernels from failed cluster nodes.
\end{center}
\end{frame}
@@ -240,7 +254,7 @@
\end{frame}
\begin{frame}{Case study: ARMA ocean wavy surface generator}
- \begin{columns}
+ \begin{columns}[T]
\begin{column}{0.25\textwidth}
MA model:
\begin{equation*}
@@ -248,8 +262,8 @@
\sum\limits_{\vec{y}=\vec{0}}^{N}
\Theta_{\vec{y}}\,\epsilon_{\vec{x} - \vec{y}}
\end{equation*}
- \vfill
- Coefficients:
+ \vskip1cm
+ MA coefficients:
\begin{equation*}
K_{i,j,k} =
\left[
@@ -263,6 +277,7 @@
\end{equation*}
\end{column}
\begin{column}{0.65\textwidth}
+ \vskip1cm
\includegraphics[width=\linewidth]{figures/wavy.eps}
\end{column}
\end{columns}
@@ -319,6 +334,42 @@
\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}
@@ -339,8 +390,10 @@
\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 IP-address (or any other unique
+ \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}
