commit 9f4f35cd7c7dd78545e043c1c9192af47383c1e4
parent 789b3fe86068bcb325ee1598a056bd4680ebee06
Author: Ivan Gankevich <i.gankevich@spbu.ru>
Date: Wed, 21 Apr 2021 11:49:42 +0300
repl
Diffstat:
| main.bib | | | 13 | +++++++++++++ |
| main.tex | | | 64 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-- |
2 files changed, 75 insertions(+), 2 deletions(-)
diff --git a/main.bib b/main.bib
@@ -273,3 +273,16 @@
institution = {NDBC},
year = {1996}
}
+
+@Article{ hutton-fold,
+ title = {A tutorial on the universality and expressiveness of fold},
+ volume = {9},
+ doi = {10.1017/S0956796899003500},
+ number = {4},
+ journal = {Journal of Functional Programming},
+ publisher = {Cambridge University Press},
+ author = {Hutton, Graham},
+ year = {1999},
+ pages = {355--372}
+}
+
diff --git a/main.tex b/main.tex
@@ -9,6 +9,35 @@
\usepackage{listings}
\usepackage{tikz}
+% https://github.com/stuhlmueller/scheme-listings/blob/master/lstlang0.sty
+\lstdefinelanguage{scheme}{
+ morekeywords=[1]{define, define-syntax, define-macro, lambda, define-stream, stream-lambda,
+ define*},
+ morekeywords=[2]{begin, call-with-current-continuation, call/cc,
+ call-with-input-file, call-with-output-file, case, cond,
+ do, else, for-each, if,
+ let*, let, let-syntax, letrec, letrec-syntax,
+ let-values, let*-values,
+ and, or, not, delay, force,
+ quasiquote, quote, unquote, unquote-splicing,
+ syntax, syntax-rules, eval, environment, query },
+ morekeywords=[3]{import, export},
+ alsodigit=!\$\%&*+-./:<=>?@^_~,
+ sensitive=true,
+ morecomment=[l]{;},
+ morecomment=[s]{\#|}{|\#},
+ morestring=[b]",
+ basicstyle=\small\ttfamily,
+ keywordstyle=\bf\ttfamily,
+ commentstyle=\color[rgb]{0.33,0.33,0.33},
+ stringstyle={\color[rgb]{0.75,0.49,0.07}},
+ upquote=true,
+ breaklines=true,
+ breakatwhitespace=true,
+ literate=*{`}{{`}}{1},
+ showstringspaces=false
+}
+
\begin{document}
\title{TODO
@@ -91,6 +120,13 @@ intermediate representation for Guile programming language, run benchmarks
using the scheduler and compare the performance of different implementations of
the same programme.
+To prevent ambiguity we use the term \emph{parallel} to describe computations
+that use several processor cores of single cluster node, the term
+\emph{distributed} to describe computations that use several cluster nodes and
+any number of cores on each node, and term \emph{cluster} to describe anything
+that refers to local cluster (as opposed to geographically distributed clusters
+which are not studied in this paper).
+
TODO \cite{lang-virt}
%\cite{fetterly2009dryadlinq}
%\cite{wilde2011swift}
@@ -521,6 +557,32 @@ distributed programmes with clear separation of concerns: the programmer takes
care of the application logic, and cluster scheduler takes care of the
parallelism, load balancing and fault tolerance.
+Our interpreter consists of standard \textit{read-eval-print} loop out of which
+only \textit{eval} step uses kernels for parallel and distributed computations.
+Inside \textit{eval} we use hybrid approach for parallelism: we use kernels to
+evaluate arguments of procedure calls and arguments of \texttt{cons} primitive
+asynchronously only if these arguments contain other procedure calls. This
+means that all simple arguments (variables, symbols, other primitives etc.) are
+computed sequentially without creating child kernels. Evaluating procedure
+calls and \texttt{cons} using kernels is enough to make \texttt{map} and
+\texttt{fold} forms parallel, and on these forms many other forms are
+based~\cite{hutton-fold}. Our implementations of these forms are shown in
+listing~\ref{lst-parallel-forms}.
+
+\begin{lstlisting}[language=Scheme,%
+caption={Parallel \texttt{map} and \texttt{fold} forms in Guile.},
+captionpos=b,
+label={lst-parallel-forms}]
+(define (map proc lst)
+ (if (null? lst) lst
+ (cons (proc (car lst)) (map proc (cdr lst)))))
+(define (fold proc init lst)
+ (if (null? lst) init
+ (fold proc (proc (car lst) init) (cdr lst))))
+\end{lstlisting}
+
+\section{Results}
+
In order to test performance of our interpreter we used a programme that
processes frequency-directional spectra of ocean waves from NDBC
dataset~\cite{ndbc-web-data-guide,ndbc-techreport}. Each spectrum consists of
@@ -532,8 +594,6 @@ groups of files and incomplete records are removed. After that we write the
resulting groups to disk. We wrote this programme in C++ with kernels,
in Guile with kernels and in Guile without kernels.
-\section{Results}
-
\section{Discussion}
\section{Conclusion}
