slides.tex (12954B)
1 \documentclass[aspectratio=169,xcolor=table]{beamer} 2 \usepackage{polyglossia} 3 \setdefaultlanguage{english} 4 \usetheme[numbers]{SaintPetersburg} 5 6 \usepackage{textcomp} 7 \usepackage{booktabs} 8 \usepackage{spbu-slides} 9 10 \setbeamertemplate{itemize items}[circle] 11 12 % metadata 13 \usepackage{textcomp} 14 \usepackage{hyperxmp} 15 \hypersetup{ 16 pdfcontactemail={i.gankevich@spbu.ru}, 17 pdfcontacturl={http://www.apmath.spbu.ru/en/staff/gankevich/index.html}, 18 pdfcontactaddress={Unversitetskii prospekt 35}, 19 pdfcontactcity={Petergof}, 20 pdfcontactregion={Saint Petersburg}, 21 pdfcontactpostcode={198504}, 22 pdfcontactcountry={Russia}, 23 pdflang={en}, 24 pdfmetalang={en}, 25 pdflicenseurl={http://creativecommons.org/licenses/by-sa/4.0/}, 26 pdfcopyright={Copyright \textcopyright{} 2021 Ivan Petriakov\xmpcomma{} Ivan Gankevich\xmpcomma{}}, 27 pdfsubject={Functional programming interface for parallel and distributed computing}, 28 } 29 30 \title{Functional programming interface\\for parallel and distributed computing} 31 \author{% 32 I.\:Petriakov \and 33 I.\:Gankevich 34 } 35 \institute{Saint Petersburg State University} 36 \date{September 2021} 37 38 % https://github.com/stuhlmueller/scheme-listings/blob/master/lstlang0.sty 39 \lstdefinelanguage{scheme}{ 40 morekeywords=[1]{define, define-syntax, define-macro, lambda, define-stream, stream-lambda, 41 define*,if,cons,car,cdr}, 42 morekeywords=[2]{begin, call-with-current-continuation, call/cc, 43 call-with-input-file, call-with-output-file, case, cond, 44 do, else, for-each, if, 45 let*, let, let-syntax, letrec, letrec-syntax, 46 let-values, let*-values, 47 and, or, not, delay, force, 48 quasiquote, quote, unquote, unquote-splicing, 49 syntax, syntax-rules, eval, environment, query, 50 car, cdr, cons}, 51 morekeywords=[3]{import, export}, 52 alsodigit=!\$\%&*+-./:<=>?@^_~, 53 sensitive=true, 54 morecomment=[l]{;}, 55 morecomment=[s]{\#|}{|\#}, 56 morestring=[b]", 57 basicstyle=\small\ttfamily, 58 keywordstyle={\bf\ttfamily\color[HTML]{4081ec}}, 59 commentstyle=\color[rgb]{0.33,0.33,0.33}, 60 stringstyle={\color[HTML]{00a000}}, 61 upquote=true, 62 breaklines=true, 63 breakatwhitespace=true, 64 literate=*{`}{{`}}{1}, 65 showstringspaces=false 66 } 67 68 \lstdefinelanguage{cpp}{ 69 morekeywords=[1]{class,struct,enum,public,private,protected,virtual,override,const, 70 void,int,new,delete,nullptr}, 71 morecomment=[l]{//}, 72 basicstyle=\small\ttfamily, 73 keywordstyle={\bf\ttfamily\color[HTML]{4081ec}}, 74 commentstyle=\color[rgb]{0.33,0.33,0.33}, 75 stringstyle={\color[HTML]{00a000}}, 76 escapeinside={LATEX}{END}, 77 } 78 79 \begin{document} 80 81 \frame{\maketitle} 82 83 \begin{frame}{Motivation} 84 \begin{itemize} 85 \item There is no universal low-level representation of distributed computations. 86 \item There is no high-level interface for distributed computing in functional languages. 87 \item Existing solutions do not provide automatic fault tolerance for both slave and master nodes. 88 \end{itemize} 89 \vfill 90 91 \textit{Parallel} --- several processor cores of single cluster node. 92 93 \textit{Distributed} --- several cluster nodes. 94 \end{frame} 95 96 \begin{frame}[fragile]{From sync. call stack to async. call stack (kernels)} 97 Kernel = data + code + result of the computation. 98 \begin{columns}[T] 99 \begin{column}{0.36\textwidth} 100 \begin{lstlisting}[language=cpp] 101 int nested(int a) { 102 return 123 + a; 103 } 104 \end{lstlisting} 105 \end{column} 106 \begin{column}{0.63\textwidth} 107 \begin{lstlisting}[language=cpp] 108 struct Nested: public Kernel { 109 int result; 110 int a; 111 Nested(int a): a(a) {} 112 void act() override { 113 result = a + 123; 114 LATEX{\color[HTML]{ac4040}\bf{}\ttfamily{}async\_return}END(); 115 } 116 }; 117 \end{lstlisting} 118 \end{column} 119 \end{columns} 120 \vfill\small 121 \begin{tabular}{ll} 122 \color[HTML]{ac4040}\bf\texttt{async\_call} & push child kernel to the queue \\ 123 \color[HTML]{ac4040}\bf\texttt{async\_return} & push current kernel to the queue \\ 124 \color[HTML]{ac4040}\bf\texttt{async\_message} & send a kernel to another one via the queue \\ 125 \end{tabular} 126 \end{frame} 127 128 \begin{frame}[fragile]{From sync. call stack to async. call stack (kernels)} 129 \begin{columns}[T] 130 \begin{column}{0.36\textwidth} 131 \begin{lstlisting}[language=cpp] 132 void main() { 133 // code before 134 int result = nested(); 135 // code after 136 print(result); 137 } 138 \end{lstlisting} 139 \end{column} 140 \begin{column}{0.63\textwidth} 141 \begin{lstlisting}[language=cpp] 142 struct Main: public Kernel { 143 void act() override { 144 // code before 145 LATEX{\color[HTML]{ac4040}\bf{}\ttfamily{}async\_call}END(new Nested); 146 } 147 void react(Kernel* child) override { 148 int result = ((Nested*)child)->result; 149 // code after 150 print(result); 151 LATEX{\color[HTML]{ac4040}\bf{}\ttfamily{}async\_return}END(); 152 } 153 }; 154 155 void main() { 156 LATEX{\color[HTML]{ac4040}\bf{}\ttfamily{}async\_call}END(new Main); 157 wait(); 158 } 159 \end{lstlisting} 160 \end{column} 161 \end{columns} 162 \end{frame} 163 164 \begin{frame}[fragile]{Cluster scheduler architecture} 165 \begin{columns}[T] 166 \begin{column}{0.40\textwidth} 167 \tikzset{Rect/.style={text width=1.70cm,draw,align=center,thick,rounded corners}} 168 \small 169 \textbf{Daemon process:}\strut{} 170 \begin{tikzpicture}[x=2.25cm,y=-1.10cm] 171 \node[Rect] (parallel) at (2,0) {Processor queue\strut}; 172 %\node[Rect] (timer) at (1,0) {Timer queue\strut}; 173 %\node[Rect] (disk) at (2,0) {Disk queue\strut}; 174 \node[Rect] (nic) at (4,0) {Network queue\strut}; 175 \node[Rect] (process) at (3,0) {Process queue\strut}; 176 \node[Rect] (cpu0) at (2,-1) {CPU 0\strut}; 177 \node[Rect] (cpu1) at (2,1) {CPU 1\strut}; 178 %\node[Rect] (disk0) at (2,-1) {Disk 0\strut}; 179 %\node[Rect] (disk1) at (2,1) {Disk 1\strut}; 180 %\node[Rect] (timer0) at (1,-1) {Timer 0\strut}; 181 \node[Rect] (nic0) at (4,-1) {NIC 0\strut}; 182 \node[Rect] (nic1) at (4,1) {NIC 1\strut}; 183 \node[Rect] (child) at (3,1) {Child\strut}; 184 \path[draw,thick] (parallel) -- (cpu0); 185 \path[draw,thick] (parallel) -- (cpu1); 186 %\path[draw,thick] (timer) -- (timer0); 187 %\path[draw,thick] (disk) -- (disk0); 188 %\path[draw,thick] (disk) -- (disk1); 189 \path[draw,thick] (nic) -- (nic0); 190 \path[draw,thick] (nic) -- (nic1); 191 \path[draw,thick] (process) -- (child); 192 \end{tikzpicture} 193 \vskip0.5\baselineskip\textbf{Application process:}\strut{} 194 \begin{tikzpicture}[x=2.25cm,y=-1.10cm] 195 \node[Rect] (parallel) at (2,0) {Processor queue\strut}; 196 \node[Rect] (process) at (3,0) {Process queue\strut}; 197 \node[Rect] (cpu0) at (2,-1) {CPU 0\strut}; 198 \node[Rect] (cpu1) at (2,1) {CPU 1\strut}; 199 \node[Rect] (parent) at (3,-1) {Parent\strut}; 200 \path[draw,thick] (parallel) -- (cpu0); 201 \path[draw,thick] (parallel) -- (cpu1); 202 \path[draw,thick] (process) -- (parent); 203 \end{tikzpicture} 204 \end{column} 205 \begin{column}{0.50\textwidth} 206 \vskip0.5\baselineskip 207 \begin{itemize} 208 \item Run applications in child processes. 209 \item Route kernels between application processes running on 210 different cluster nodes. 211 \item Maintain a list of available cluster nodes. 212 \end{itemize} 213 \vskip3\baselineskip\small\hspace{-2.0cm} 214 \begin{tabular}{lp{5.5cm}} 215 \texttt{async\_call} & push child kernel to the queue \\ 216 \texttt{async\_return} & push current kernel to the queue \\ 217 \texttt{async\_message} & send a kernel to another one via the queue \\ 218 \end{tabular} 219 \end{column} 220 \end{columns} 221 \end{frame} 222 223 \begin{frame}[fragile]{Fault tolerance} 224 \begin{itemize} 225 \item Assumption: \textit{main} kernel has only one child kernel at a time. 226 \item Every \textit{step} kernel (a child of \textit{main}) has a copy of the \textit{main}. 227 \item Scheduler ensures that \textit{main} and \textit{step} are on different cluster nodes. 228 \item Every \textit{step} is also appended to the local log file. 229 \end{itemize} 230 \vfill 231 \begin{columns}[T] 232 \begin{column}{0.25\textwidth} 233 \definecolor{mydark}{HTML}{E31A1C} 234 \definecolor{mylight}{HTML}{FB9A99} 235 \tikzset{Rect/.style={text width=1.50cm,rounded corners,draw,align=center,thick}} 236 \tikzset{Arrow/.style={draw,-latex}} 237 \tikzset{DotNoArrow/.style={draw,mydark,thick}} 238 \tikzset{Dot/.style={DotNoArrow,-latex}} 239 \begin{tikzpicture}[x=2.50cm,y=-1.5cm] 240 \node[Rect] (m0) at (0,-1) {Main kernel}; 241 \node[Rect] (m1) at (0,0) {Step kernel}; 242 \node[Rect] (m2) at (-0.5,1) {Child kernel 1}; 243 \node[Rect] (m3) at (0.5,1) {Child kernel 2}; 244 % solid arrows 245 \path[Arrow] (m1) -- (m0); 246 \path[Arrow] (m2) -- (m1); 247 \path[Arrow] (m3) -- (m1); 248 \end{tikzpicture} 249 \end{column} 250 \begin{column}{0.70\textwidth} 251 \begin{tabular}{ll} 252 Failure & Resolution \\ 253 \midrule 254 Child 1 & resend Child 1 to the remaining nodes \\ 255 Child 2 & resend Child 2 to the remaining nodes \\ 256 Step & resend Step to the remaining nodes \\ 257 Main & restore Main from the copy \\ 258 Main and Step & restore Main and Step from the log \\ 259 \end{tabular} 260 \vfill\tiny{} 261 \begin{itemize} 262 \item I. Gankevich, Yu. Tipikin, V. Korkhov 263 \href{http://dx.doi.org/10.1109/HPCS.2017.126}{Subordination: Providing resilience to simultaneous failure of multiple cluster nodes}, HPCS'17, 2017.\\ 264 \item I. Gankevich, Yu. Tipikin, V. Korkhov, V. Gaiduchok, A. Degtyarev, A. Bogdanov 265 \href{http://dx.doi.org/10.1504/IJBIDM.2017.10007764}{Master node fault tolerance in distributed big data processing clusters}, International Journal of Business Intelligence and Data Mining, 2017. 266 \end{itemize} 267 \end{column} 268 \end{columns} 269 \end{frame} 270 271 \begin{frame}[fragile]{Kernel and queue definition} 272 \begin{lstlisting}[language=cpp] 273 enum class states {upstream, downstream, point_to_point}; 274 275 class kernel { 276 public: 277 virtual void act(); 278 virtual void react(kernel* child); 279 virtual void write(buffer& out) const; 280 virtual void read(buffer& in); 281 kernel* parent = nullptr; 282 kernel* target = nullptr; 283 states state = states::upstream; 284 }; 285 286 class queue { 287 public: 288 void push(kernel* k); 289 }; 290 \end{lstlisting} 291 \end{frame} 292 293 \begin{frame}[fragile]{Automatic parallelism} 294 The idea: evaluate arguments in parallel (one kernel for each argument). 295 \begin{lstlisting}[language=Scheme] 296 (define (map proc lst) "Parallel map." 297 (if (null? lst) lst 298 (cons (proc (car lst)) (map proc (cdr lst))))) 299 (define (fold proc init lst) "Sequential fold." 300 (if (null? lst) init 301 (fold proc (proc (car lst) init) (cdr lst)))) 302 (define (do-fold-pairwise proc lst) 303 (if (null? lst) '() 304 (if (null? (cdr lst)) lst 305 (do-fold-pairwise proc 306 (cons (proc (car lst) (car (cdr lst))) 307 (do-fold-pairwise proc (cdr (cdr lst)))))))) 308 (define (fold-pairwise proc lst) "Parallel pairwise fold." 309 (car (do-fold-pairwise proc lst))) 310 \end{lstlisting} 311 \end{frame} 312 313 \begin{frame}{Guile with automatic parallelism (synthetic benchmark)} 314 \centering 315 \includegraphics[width=\textwidth]{build/gnuplot/results.eps} 316 \end{frame} 317 318 \begin{frame}{Conclusion and future work} 319 Kernels provide 320 \begin{itemize} 321 \item standard way of expressing parallel and distributed programme parts, 322 \item automatic fault tolerance for master and worker nodes and 323 \item automatic load balancing via cluster scheduler. 324 \end{itemize} 325 \vfill 326 Arguments-based parallelism provide 327 \begin{itemize} 328 \item high-level programming interface for clusters and single nodes, 329 \item conveniently hides the shortcomings of parallel and distributed computations. 330 \end{itemize} 331 \end{frame} 332 333 \begin{frame} 334 \tiny\vfill 335 Copyright \textcopyright{} 2021 Ivan Petriakov, Ivan Gankevich 336 \texttt{\href{mailto:i.gankevich@spbu.ru}{i.gankevich@spbu.ru}}. \\ 337 \vskip\baselineskip 338 \vskip\baselineskip 339 This work is licensed under a \textit{Creative Commons Attribution-ShareAlike 4.0 340 International License}. The copy of the license is available at 341 \url{https://creativecommons.org/licenses/by-sa/4.0/}. 342 \end{frame} 343 344 \end{document}