\documentclass{report} \usepackage{a4} \usepackage{graphicx} \usepackage{alltt} \usepackage{makeidx} \long\def\ignore#1{\relax} \input{env} \graphicspath{{img/}} \renewcommand{\baselinestretch}{1.2} \makeindex \begin{document} \newcommand{\ocamlpiiil}{{\sf OcamlP3l}} \newcommand{\alert}{\marginpar{!!!}} \newcommand{\ocaml}{{\sf Ocaml}} \newcommand{\pppl}{{\sf p3l}} \newcommand{\piiilversion}{\texttt{2.0}} \newcommand{\ocamlpiiilweb}{\texttt{http://www.dicosmo.org/ocamlp3l/}} \long\def\sp#1{% draft comment for Susanna \strut\nobreak \marginpar[\hfil\textbf{SP}$\Longrightarrow$]{$\Longleftarrow$\textbf{SP}}% \nobreak{\bfseries SP:[#1]}} \title{\ocamlpiiil\ \piiilversion: User Manual} %\author{Danelutto Di Cosmo Leroy Li Pelagatti Weis} \author{Roberto Di Cosmo, Zheng Li% \thanks{University of Paris 7 - France} \and Marco Danelutto, Susanna Pelagatti% \thanks{Dipartimento di Informatica - University of Pisa - Italy} \and Xavier Leroy, Pierre Weis% \thanks{INRIA Rocquencourt - France}} \maketitle % \begin{verse} % Still to be done: % \begin{itemize} % \item say that we used Sockets and why. Perspective MPI % implementation. % \item give an example of the command line call syntax (prog % -p3lroot etc.) and say how it works (NFS=rsh, not limited to % this in the future) % \item comment on security implications % \end{itemize} % \end{verse} \tableofcontents \begin{abstract} Writing parallel programs is not easy, and debugging them is usually a nightmare. To cope with these difficulties, a structured approach to parallel programs using skeletons and template based compiler techniques has been developed over the past years by several researchers, including the \pppl\ group in Pisa. This approach is based on the use of a set of predefined patterns for parallel computation which are really just functionals implemented via templates exploiting the underlying parallelism, so it is natural to ask whether marrying a real functional language like \ocaml\ with the \pppl\ skeletons can be the basis of a powerful parallel programming environment. The \ocamlpiiil\ prototype described in this document shows that this is the case. The prototype, written entirely in \ocaml\ using a limited form of closure passing, allows a very simple and clean programming style, shows real speed-up over a network of workstations and as an added fundamental bonus allows logical debugging of a user parallel program in a sequential framework without changing the user code. \end{abstract} %\chapter{Introduction and Overview} \chapter{Skeleton based programming and \ocamlpiiil} In a skeleton based parallel programming model \cite{cole-th,ic-parle-93-1,fgcs-firenze} a set of \textit{skeletons}, i.e. of second order functionals modeling common parallelism exploitation patterns are provided to the user/programmer. The programmer uses skeletons to give parallel structure to an application and uses a plain sequential language to express the sequential portions of the parallel application. He/she has no other way to express parallel activities but skeletons: no explicit process creation, scheduling, termination, no communication primitives, no shared memory, no notion of being executing a program onto a parallel architecture at all. \ocamlpiiil\ is a programming environment that allows to write parallel programs in \ocaml\footnote{See \texttt{http://pauillac.inria.fr/ocaml/}} according to a skeleton model derived by the one of \pppl\footnote{See \texttt{http://www.di.unipi.it/.susanna/p3l.html}}, provides seamless integration of parallel programming and functional programming and advanced features like sequential logical debugging (i.e. functional debugging of a parallel program via execution of the architecture at all parallel code onto a sequential machine) of parallel programs and strong typing, useful both in teaching parallel programming and in building of full-scale applications\footnote{See \ocamlpiiilweb\ for relevant information, up to date references, documentation, examples, distribution code and dynamic web pages showcasing the \ocamlpiiil\ features.}. In this chapter, we will first discuss the goals of our system design, then recall the basic notions of the skeleton model for structured parallel programming and describe the skeleton model provided by \ocamlpiiil, providing an informal sequential (functional) and parallel semantics. It will be then time to describe how an \ocamlpiiil\ program can be compiled and run on your system (Chapter~\ref{cap:run}). Then, we discuss more \ocamlpiiil\ examples (Chapter~\ref{cap:exe}) and detail \ocamlpiiil\ implementation (Chapter~\ref{cap:implementation}) describing how we achieved our goals using to our advantage the flexibility of the \ocaml\ system. \section{The system design goals} We started the developmentof the \ocamlpiiil\ in 1998. At that time, the main goal of the project was to test the possibility to integrate parallel programming in a functional language using the skeleton model: after all, as we will see later, skeletons are just functions, so a functional language should provide the natural setting for them. We also wanted to preserve the elegance and flexibility of the functional model, and the strong type system that comes with \ocaml. These goals were acheved in the first version of \ocamlpiiil . But during the implementation of the system, it turned out that we could get more than that: in our implementation, the sequential semantics that is traditionally used to describe the functional behaviour of the skeletons could actually be used to provide an elementary library allowing to execute the user code in a sequential mode, without modifying the user code. This is a major advantage of the approach: in our system, the user can easily debug the logic of his program running it with the sequential semantics on a sequential machine using all the traditional techniques (including tracing and step by step execution which are of no practical use on parallel systems), and when the program is logically correct he/she is guaranteed (assuming the runtime we provide is correct) to obtain a correct parallel execution. Although a similar approach has been taken in other skeleton based programming models, by using the \ocaml\ programming environment this result happens to be particularly easy to achieve. This is definitely not the case of programs written using a sequential language and directly calling communication libraries/primitives such as the Unix socket interface or the MPI or PVM libraries, as the logic of the program is inextricably intermingled with low level information on data exchange and process handling.\\ Following this same idea (no changes to the user code, only different semantics for the very same skeletons), we also provided a ``graphical semantics'' that produces a picture of the process network used during the parallel execution of the user program.\\ Finally, we wanted a simple way to generate (from the user source code) the various executables to be run on the different nodes of a parallel machine: here the high level of abstraction provided by functional programming, coupled with the ability to send closures over a channel among copies of the same program provided the key to an elementary and robust runtime system that consists of a very limited number of lines of code.\\ But let's first of all introduce the skeleton model of \ocamlpiiil\ \piiilversion . \section{The skeleton model of \ocamlpiiil\ \piiilversion} A skeleton parallel programming model supports so-called `structured parallel programming' \cite{cole-th,ic-parle-93-1,fgcs-firenze}. Using such a model, the parallel structure/behaviour of any application has to be expressed by using {\em skeletons} picked up out of a collection of predefined ones, possibly in a nested way. Each skeleton models a typical \textit{pattern} of parallel computation (or \textit{form} of parallelism) and it is parametric in the computation performed in parallel. As an example, pipeline and farm have been often included in skeleton collections. A \textit{pipeline}\index{pipeline} just models the execution of a number of computations (stages) in cascade over a stream of input data items. Therefore, the pipeline skeleton models all those computations where a function $f_n(f_{n-1}(\ldots (f_2(f_1(x))) \ldots))$ has to be computed (the $f_i$ being the functions computed in cascade). A \textit{farm}\index{farm} models the execution of a given function in parallel over a stream of input data items. Therefore, farms model all those computations where a function $f(x)$ has to be computed independently over $n$ input data items in parallel. In a skeleton model, a programmer must select the proper skeletons to program his/her application leaving all the implementation/optimization to the compiler/support. This means, for instance, that the programmer has no responsibility in deriving code for creating parallel processes, mapping and scheduling processes on target hardware, establishing communication frameworks (channels, shared memory locations, etc) or performing actual interprocess communications. All these activities, needed in order to implement the skeleton application code onto the target hardware are completely in charge to the compile/run time support of the skeleton programming environment. In some cases, the support also computes some parameters such as the parallelism degree or the communication grain needed to optimize the execution of the skeleton program onto the target hardware \cite{tesi-susanna,orlando-grosso,libro-susi}. In the years, the skeleton model supplied by \ocamlpiiil\ has evolved. Current \ocamlpiiil\ version (\piiilversion ) supplies three kinds of skeletons: \begin{itemize} \item \textit{task parallel} skeletons\index{task parallel skeletons}, modeling parallelism exploited between \textit{independent} processing activities relative to different input data. In this set we have: pipe (cf.~\ref{sec:pipe}) and farm (cf.~\ref{sec:farm}), whose semantics has already been informally described above. Such skeletons correspond to the usual task parallel skeletons appearing both in \pppl\ and in other skeleton models \cite{cole-th,ic-parle-93-1, darli-to-1}. \item \textit{data parallel} skeletons\index{data parallel skeletons}, modeling parallelism exploited computing different parts of the same input data. In this set, we provide \verb|mapvector| (cf.~\ref{sec:map}) and \verb|reducevector| (cf.~\ref{sec:red}). Such skeletons are not as powerful as the \verb|map| and \verb|reduce| skeletons of \pppl. Instead, they closely resemble the map~($*$) and reduce~($/$) functionals of the Bird-Meertens formalism discussed in \cite{bird1} and the \textsf{map} and \textsf{fold} skeletons in SCL \cite{darli-to-1}. The \texttt{mapvector} skeleton models the parallel application of a generic function $f$ to all the items of a vector data structure, whereas the \verb|reducevector| skeleton models a parallel computation folding all the elements of a vector with a commutative and associative binary operator $\oplus$). \item \textit{service} or \textit{control} skeletons\index{control skeletons}\index{service skeletons}, which are not parallel \textit{per se}. Service skeletons are used to encapsulate \ocaml\ non-parallel code to be used within other skeletons (seq skeleton (cf.~\ref{sec:seq})), to iterate the execution of skeletons (loop skeleton (cf.~\ref{sec:loop})), to transform a process network defined using skeletons in a valid \ocaml\ function (parfun skeleton (cf.~\ref{sec:parfun})) and to define global application structure (pardo skeleton (cf.~\ref{sec:pardo})). \end{itemize} % end addition As an example, consider an application whose initial and final phase cannot be parallelized, while the behavior in the central part is clearly divided in two consecutive phases (stages) working on a stream of data. This can be modeled by the combination of \ocamlpiiil\ skeletons in Fig.~\ref{fig:struct1}. \begin{figure}[h] \begin{center} \includegraphics[width=0.80\textwidth]{struct1} \end{center} \caption{Structure of an example \ocamlpiiil\ application: (a) the skeleton nesting, (b) processes participating to the implementation: \texttt{pardo}, \texttt{stage1} and \texttt{stage2}.\label{fig:struct1}} \end{figure} All the structure is encapsulated in a \texttt{pardo} skeleton. \texttt{initsec} and \texttt{finsec} are two sequential \ocaml\ functions describing the initial and final parts of application. The central part describes a parallel computation structured as a pipeline built out of two stages. If both stages are implemented via a sequential function (\texttt{seq}) data will flow as shown in Fig.~\ref{fig:struct1}.$(a)$. In particular, the implementation spawns three processes: a `pardo' process (executing the sequential parts) and a network of two processes implementing the pipeline (Fig.~\ref{fig:struct1}.$(b)$). \begin{figure}[h] \begin{center} \includegraphics[width=0.90\textwidth]{struct2} \end{center} \caption{Further parallelizing the example \ocamlpiiil\ application: (a) the skeleton nesting, (b) the processes participating to the implementation.\label{fig:struct2}} \end{figure} Now, suppose the programmer recognizes that the \texttt{initsec} is computationally intensive and can be decomposed in a sequential part (\texttt{initsec}) and a parallel part which applies a function \texttt{work} independently on each element on a stream of input data. In this case, we can use a farm skeleton to have a pool of replicas of \texttt{work}. Moreover, suppose the function \texttt{stage1} boils down to applying a function \texttt{f} to all the elements of a vector and function \texttt{stage2} ``sums'' up all the elements of the resulting vector by using an associative and commutative operator \texttt{g}. In this case, the programmer can refine the skeleton structure by using the combination in Fig.~\ref{fig:struct2}. Here, the four replicas of \texttt{work} act on different independent elements in the input stream, producing four stream of results (vectors) which are merged before entering the pipeline. Each stage is in turn implemented in parallel using four processes. In the first stage, each input vector is partitioned into four blocks. Each process takes care of applying \texttt{f} on one of the four blocks. Then in the second stage, each process sums up the elements in a block of the vector and then all the partial results are added before providing the final result back to the pardo (and to the \verb|finsec| function). The first ``application outline'' (Fig.~\ref{fig:struct1}) corresponds to the following (incomplete) \ocamlpiiil\ code: \begin{quote} \begin{verbatim} let initsec _ = ...;; (* generates stream *) let finsec x = ...;; (* consumes stream *) let stage1 _ x = ... ;; let stage2 _ x = ... ;; (* defines pipe network *) let pipe = parfun (fun () -> seq(stage1) ||| seq(stage2)) ;; pardo (fun () -> let y = pipe (initsec ()) in finsec y );; \end{verbatim} % corresponding to primo-esmpioUM.ml \end{quote} notice the use of \texttt{seq} skeleton to encapsulate ordinary \ocaml\ functions and the use of \texttt{parfun} to define the pipe network. Here is the sketch of \ocamlpiiil\ code for the second application outline (Fig.~\ref{fig:struct2}): \begin{quote} \begin{verbatim} let degree = ref 4; (* parallel degree *) let work _ x = ..;; (* to be farmed out *) let f _ x = ...;; (* to be mapped *) let g _ (x,y) = ...;; (* to be reduced *) let pstage1 = mapvector(seq(f),!degree);; let pstage2 = reducevector(seq(g),!degree);; let pipe = parfun (fun () -> pstage1 ||| pstage2);; let afarm = parfun (fun () -> farm (seq(farm_worker),!degree));; pardo (fun () -> let y = pipe (afarm (initsec ())) in finsec y );; \end{verbatim} \end{quote} here \verb|!degree| refers to the number of parallel processes to be used in the skeleton implementation of mapvector, reducevector and farm. This value can vary in each execution of the application without recompiling (eg., using a configuration file). Details on how to write and run proper \ocamlpiiil\ programs are given later in Chapter~\ref{cap:run}. In the current release, the user is supposed to explicitly give the number of processors to be used in each farm, mapvector and reduce skeleton. In other words the choice of the parallelism degree actually exploited in such skeletons is up to the programmer. It is foreseeable in a future release to ask the system to guess optimal values depending on available resources (following the approach of \pppl\ \cite{orlando-grosso,tesi-susanna}), as it is discussed in more detail below. Applications with a parallel structure given by skeletons (such as the ones outlined above) can be implemented by using \textit{implementation templates} \cite{cole-th,tesi-susanna}. An implementation template is a known, parametric way of exploiting the kind of parallelism modeled by a skeleton onto a particular target architecture. As an example, a template corresponding to the mapvector skeleton will take some input vector data, it will split the data into chunks holding one or more data items of the vector, schedule them to a set of ``worker'' processes computing the map function $f$ and finally collect the results and rebuild the output vector data structure. All these operations will be performed by some processes, using either communications or shared memory locations for data communication. Such a template must, as its primary goal, implement in an efficient way the mapvector skeleton and therefore: \begin{itemize} \item it must implement any kind of mapvector function $f$, and therefore must be parametric with respect to the input and output data types \item it must support any reasonable parallelism degree, therefore it must work (and provide effective parallelism exploitation) when executed on an arbitrary number of processors. \end{itemize} In \ocamlpiiil\ \piiilversion, the parallelism degree of each skeleton is chosen by the programmer. In following releases, we will explore the possibility of using \textit{analytic performance models} associated with the implementation template process networks to derive the parallelism degree automatically\cite{skbook02}. An analytic performance model is a set of functions computing different measures of the performance achieved by a template on the basis of a small set of machine dependent and user code parameters. Examples of machine dependent parameters are the cost of communication startup and the per-byte transmission cost. Examples of user code parameters are the mean and variance of execution time for user-defined sequential parts of the program and the size of data flowing between skeletons. The models describe the template behavior as a function of the resources used (e.g.\ the physical number of executors in a farm) and can be used by the skeleton support to predict such behavior and to tune resource allocation. A more detailed description of the whole automatic optimization process executed by a compiler using performance models for skeleton tuning is given in \cite{tesi-susanna,libro-susi,skbook02}. \label{f0} % html: End of file: `overview.html' %qua e' cambiato tutto!!!! you can find teh old stuff in %\input{old-manual.tex} \subsection{Parallel execution model} A parallel computation in \ocamlpiiil\ is defined by three components: \begin{itemize} \item a set of plain sequential \ocaml\ functions (CF, common functions in Figure~\ref{fig:pardo}), \item some clusters of parallel processes, each one defined by a suitable composition of skeleton combinators enclosed in a \verb|parfun| (SF, skeleton functions in Figure~\ref{fig:pardo}) and \item a \verb|pardo| application. \end{itemize} Each time a \verb|parfun(h)| functon definition is evaluated, a corresponding network of processes is created according to the skeleton composition in \verb|h|. Each network transforms a stream of independent input data $\ldots x_1, x_0$ in a stream of output data $\ldots h(x_1), h(x_0)$ according to \verb|h|. When a \verb|pardo| is evaluated, applications of common functions boil down to normal sequential evaluation, while applications of skeletal functions feed arguments data to the corresponding skeletal process network and are evaluated in parallel. In practice, each \verb|pardo| defines a network built out of all the processes in skeletal networks (\verb|parfun| defined functions) plus a \emph{root} process orchestrating all the computation. Both the root node and the generic nodes run in SPMD model. Initially, the root specializes all the generic nodes sending information on the actual process to be executed (eg., a farm dispatcher, a farm worker, a mapvector worker etc). Then, the root process starts executing the \verb|pardo|. If code is sequential, it is executed locally on the root node. Otherwise, if the evaluation of a \verb|parfun| function is encountered, the root activates evaluation passing the relevant parameters to the correponding network. The same network can be activated many times, each time an evaluation of the corresponding \verb|parfun| function is encountered.\\ Notice that the execution model assumes an unlimited number of homogenous processors. In practical situations, processors will be less than processes and have heterogeneus capacity. The \ocamlpiiil\ upport, possibly with some help from the programmer (using colors, see Sec.~\ref{ss:colors}), is in charge of implementing this in a transparent way. \begin{figure}[ht] \centering \includegraphics[width=0.80\textwidth]{pardo} \caption{Parallel execution model: the role of parfun and pardo}\label{fig:pardo} \end{figure} \subsection{Discussion: a comparision with \pppl } Even if \ocamlpiiil\ skeletons are close to original \pppl\ ones, the parallel evaluation model is completely different. Thus, for these familiar with \pppl , it is interesting to highlight the main differences between two models and to give a brief account on the reasons that have lead to such a design change. In the original {\pppl} system (and, actually in initial versions of \ocamlpiiil \cite{Ocamlp3lMlw98}), a program is clearly stratified into two levels: there is a skeleton \emph{cap}, that can be composed of an arbitrary number of skeleton combinators, but as soon as one goes outside this cap, passing into the sequential code through the \texttt{seq} combinator, there is no way for the sequential code to call a skeleton. To say it briefly, the entry point of a {\pppl} program \emph{must} be a skeleton expression, and no skeleton expression is allowed anywhere else in the sequential code. Using current \ocamlpiiil\ terminology, \pppl\ restricts the pardo to contain one single call to a network defind with \texttt{parfun}, and \emph{without} calls to sequential functions. \\ This restriction is quite reasonable when the goal is to build \emph{a single} stream processing network described by the skeleton cap. However, it has several drawbacks in the general case: \begin{itemize} \item it breaks uniformity, since even if the skeletons \emph{look like} ordinary functionals, they \emph{cannot} be used as ordinary functions, in particular inside sequential code, \item many applications (such as the numerical algorithms described in \cite{clement04}) boil down to simple nested loops, some of which can be easily parallelised, and some cannot; forcing the programmer to push all the parallelism in the skeleton cap could lead to rewriting the algorithm in a very unnatural way, \item indeed, a `parallelizable' operation can be used at several stages in the algorithm: the {\pppl} skeleton cap does not allow the user to specify that parts of the stream processing network can be shared among different phases of the computation, which is an essential requirement to avoid wasting computational resources. \end{itemize} To overcome all these difficulties and limitations, the {\piiilversion} version of {\ocamlpiiil} introduces the new \texttt{parfun} skeleton (not present in \pppl ), the very \emph{dual} of the \texttt{seq} skeleton. In simple words, one can wrap a full skeleton expression inside a \texttt{parfun}, and obtain a regular \ocaml\ stream processing function, usable with no limitations in any sequential piece of code: a \texttt{parfun} encapsulated skeleton behaves exactly as a normal function that receives a stream as input, and returns a stream as output. However, in the parallel semantics, the \texttt{parfun} combinator gets a parallel interpretation, so that the encapsulated function is actually implemented as a parallel network (the network to which the \texttt{parfun} combinator provides an interface).\\ % Since many {\texttt parfun} expressions may occur in an {\ocamlpiiil} program, there may be several disjoint parallel processing networks at runtime. This implies that, to contrast with {\pppl}, the {\ocamlpiiil} model of computation requiers a {\em main} sequential program (the \verb|pardo|): this main program is responsible for information interchange with the various \texttt{parfun} encapsulated networks. \subsection{A simple example: farming square computation}\label{ss:example} %FFT-Hist is a kernel which has been used as atestbed in the literature of task %and data parallel progeamming models \cite{cmusuite,subholkyoung}. Although %simple the kernel represents the structure of a large class of signal and %image processing applications. .... It is now time to discuss a simple but complete \ocamlpiiil\ program. The program in Figure~\ref{fig:squarecode} uses a farm to compute a very simple function over a stream of floats. \begin{figure} \begin{verbatim} (* computes x square *) let farm_worker _ = fun x -> x *. x;; (* prints a result *) let print_result x = print_float x; print_newline();; let compute = parfun (fun () -> (farm (seq(farm_worker),4)));; pardo(fun () -> let is = P3lstream.of_list [1.0;2.0;3.0;4.0;5.0;6.0;7.0;8.0] in let s' = compute is in P3lstream.iter print_result s'; );; \end{verbatim} \caption{\ocamlpiiil\ code using a farm to square a stream of float.\label{fig:squarecode}} \end{figure} First we have two standard \ocaml\ functions: \verb|farm_worker| which simply computes the square of a float argument and \verb|print_result| which dumps results on the stardard output. Notice that \verb|farm_worker| takes two parameters instead of one as it would seem reasonable. The extra parameter (\verb|_|) is required by the \verb|seq| skeleton type and is used in general to provide local initialization data (for instance, an initialization matrix, some initial seed or the like)\index{local initialization}\index{initialization!local}. In this simple case, initialization data are not needed and the parameter is just ignored by \verb|farm_worker|. This optional initialization is provided for all \ocamlpiiil\ skeletons (see Section~\ref{sss:unit}). Function \verb|compute| uses \verb|parfun| to define a parallel network built by a single farm, in particular: \begin{verbatim} seq(farm_worker) \end{verbatim} turns the sequential \verb|farm_worker| function into a `stream processor' applying it to a stream of input values. Then, an instance of the farm skeleton is defined with \begin{verbatim} farm (seq(farm_worker),4) \end{verbatim} which spawns four workers. Finally, \begin{verbatim} parfun (fun () -> (farm (seq(farm_worker),4)));; \end{verbatim} encapsulates the skeleton network into a standard \ocaml\ function. The last \verb|pardo| defines how sequential functions and parallel modules are interconnected. In this case, we have a single parallel module (\verb|compute|) and two sequential parts. The first sequential part builds up the data stream (using the standard \ocamlpiiil\ library function \begin{verbatim} P3lstream.of_list [1.0;2.0;3.0;4.0;5.0;6.0;7.0;8.0] \end{verbatim} which turns lists in streams) and the second part applies \verb|print_results| to all the elements in the stream (using standard stream iterator \verb|P3lstream.iter|). The global network is shown in Figure~\ref{fig:simplefarm}, where arrows point out the data flow among processes. \begin{figure}[ht] \centering \includegraphics[width=0.70\textwidth]{farme} \caption{Overall process network of the simple farm squaring a stream of double.}\label{fig:simplefarm} \end{figure} \section{Skeleton syntax, semantics, and types} \label{sec:skeletons} Here we describe the syntax, the informal semantics, and the types assigned to each skeleton combinator. Each skeleton is a stream processor, transforming an input stream into an output stream and is equipped with three semantics: \begin{description} \item[sequential semantics] a suitable sequential \ocaml\ function transforming all the elements of the input stream; \item[parallel semantics] a process network implementing the stream transformation in parallel; \item[graphical semantics] a graphical representation of the process network corresponding to the parallel semantics. \end{description} \subsection{On the type of skeleton combinators} \label{sss:unit} First of all, let's explain why the actual {\ocaml} types of our skeleton combinators are a bit more complex than those used by other skeleton systems (eg., \cite{darli-to-1}). In effect, our types seem somewhat polluted by spurious additional \verb|unit| types, compared to the types one would expect. For istance, consider the \verb|seq| combinator. As informally discussed above, \verb|seq| encapsulates any {\ocaml} function $f$ into a sequential process which applies $f$ to all the inputs received in the input stream. This means that, writing \verb|seq f|, any {\ocaml} function with type \verb|f : 'a -> 'b| is wrapped into a sequential process (this is reminiscent to the \verb"lift" combinator used in many stream processing libraries of functional programming languages). Hence, a strightforward type for \verb|seq| would be \verb|('a -> 'b) -> 'a stream -> 'b stream|.\\ However, in {\ocamlpiiil}, \verb|seq| is declared as % \begin{center} \verb|seq : (unit -> 'a -> 'b) -> unit -> 'a stream -> 'b stream| \end{center} \noindent meaning that the lifted function argument \verb|f| gets an extra \verb|unit| argument. In effect, in real-world application, the user functions may need to hold a sizeable amount of local data (e.g. some huge matrices that have to be initialised in a numerical application), and we decided to have a type general enough to allow the user to finely describe where and when those data have to be initialized and/or copied. %Of course, this additional complexity is not purely %incidental: it has been forced by strong practical considerations to %implement new functionalities that where mandatory to effectively run %the numerical applications described below. Reminiscent to partial evaluation and $\lambda$-lifting, we reuse the classical techniques of functional programming to initialize or allocate data globally and/or locally to a function closure. This is just a bit complicated here, due to the higher-order nature of the skeleton algebra, that in turn reflects the inherent complexity of parallel computing: \begin{itemize} \item \emph{global initialization}: the data is initialised once and for all, and is then replicated in every copy of the stream processor that a \verb|farm|, a \verb|mapvector| or a \verb|reducevector| may launch; this was already available in the previous versions of {\ocamlpiiil}, since we could write \begin{alltt} let f = let localdata = do_huge_initialisation_step () in fun x -> compute (localdata, x);; \ldots{} farm (seq f, 10) \end{alltt} \item \emph{local initialization}: the data is initialised by each stream processor, \emph{after} the copy has been performed by a \verb|farm| or a \verb|mapvector| skeleton; this was just impossible in the previous versions of {\ocamlpiiil}; with unit types, it is now easy to achieve: % \begin{alltt} let f () = let localdata = do_huge_initialisation_step () in fun x -> compute (localdata, x);; \ldots{} farm (seq f, 10) \end{alltt} % when the \verb|farm| skeleton creates $10$ copies of \verb|seq f|, each copy is created by passing $()$ to the \verb|seq| combinator, which in turn passes $()$ to $f$, producing the allocation of a different copy of $localdata$ for each instance\footnote{% In practice, the initialization step may do weird, non referentially transparent things, like opening file descriptors or negociating a network connection to other services: it is then crucial to allow the different instances of the user's function to have their own local descriptors or local connections to simply avoid the chaos.}. Note also that the old behaviour, namely \ocamlpiiil\ version 1.0, where a unique initialization was shared by all copies, is still easy (and can be freely combined to further local initializations if needed): % \begin{alltt} let f = let localdata = do_huge_initialisation_step () in fun () -> fun x -> compute (localdata, x);; \ldots{} farm (seq f, 10) \end{alltt} \end{itemize} % To sum up, the extra \verb|unit| parameters give the programmer the hability to decide whether local initialisation data in his functions are shared among all copies or not. In other words, we can regard the skeleton combinators in the current version of {\ocamlpiiil} as ``delayed skeletons'', or ``skeleton factories'', that produce \emph{an instance} of a skeleton every time they are passed an $()$ argument. In the following sections we detail the types and semantics of all the skeletons and provide some usage examples. \subsection{The seq skeleton} \label{sec:seq} The seq skeleton encapsulates an \ocaml\ function $f$ into a stream process which applies $f$ to all the inputs received on the \emph{input stream} and sends off the reselts on the \emph{output stream}. Any \ocaml\ function with type \begin{verbatim} f: unit -> 'a -> 'b \end{verbatim} can be encapsulated in the seq skeletons as follows: \begin{verbatim} seq f \end{verbatim} The central point is that the function must be \emph{unary}, i.e. functions working on more that one argument must collect them in a single tuple before being used in a seq. For instance, the fragment \begin{verbatim} let g _ (x,y) = x *. y;; let redmul = parfun (fun () -> reducevector(seq(g),6));; \end{verbatim} shows how to encapsulate a float binary operator (\texttt{*.}) to use it within a reducevector with 6 working processes. \subsection{The farm skeleton} \label{sec:farm} The farm skeleton computes in parallel a function $f$ over different data items appearing in its input stream.\\ % From a functional viewpoint, given a stream of data items $x_1, \ldots, x_n$, and a function $f$, the expression $\texttt{farm} (f, k)$ computes $f(x_1), \ldots, f(x_n)$. Parallelism is gained by having $k$ independent processes that compute $f$ on different items of the input stream.\\ % If $f$ has type \texttt{(unit -> 'b stream -> 'c stream)}, and $k$ has type $\texttt{int}$, then $farm (f, k)$ has type \texttt{unit -> 'b stream -> 'c stream}. In terms of (parallel) processes, a sequence of data appearing onto the input stream of a farm is submitted to a set of worker processes. Each worker applies the same function ($f$, which can be in turn difined using parallel skeletons) to the data items received and delivers the result onto the output stream. The resulting process network looks like the following: \begin{center} \includegraphics[scale=.50]{sfarm} \end{center} where the emitter process takes care of task-to-worker scheduling (possibly taking into account some load balancing strategy). The \texttt{farm} function takes two parameters: \begin{itemize} \item the first denoting the skeleton expression representing the farm worker computation, \item the second denoting the parallelism degree the user decided for the farm, i.e. the number of worker processes that have to be set up in the farm implementation. \end{itemize} Figure~\ref{fig:magiclocal} shows an \ocamlpiiil\ program which chooses randomly a number from a list and writes it to the file \texttt{magic\_number}. Notice the local initialization of the random number generator (which takes a different seed in each worker) and the local open of the file to be written. In Figure~\ref{fig:magicglobal} you can see how the worker code can be simply transformed to have all the workers share the same filed descripto if needed (global initialization)\index{global initialization!example: magic number}\index{local initialization!example: magic number}. \begin{figure} \begin{verbatim} let write_int = function () -> let fd = Unix.openfile "magic_number" [Unix.O_WRONLY; Unix.O_CREAT; Unix.O_TRUNC] 0o644 in let () = Random.self_init () in ( function x -> let time_to_wait = 1 + (Random.int 3) in Unix.sleep(time_to_wait); let sx = string_of_int x in ignore(Unix.write fd sx 0 (String.length sx));; let parwrite = parfun(fun () -> farm(seq(write_int), 5));; pardo( fun () -> let the_stream = P3lstream.of_list [0;1;2;3;4] in parwrite the_stream );; \end{verbatim} \caption{A simple farm example (with local initialization) \label{fig:magiclocal}} \end{figure} \begin{figure} \begin{verbatim} let write_int = let fd = Unix.openfile "magic_number" [Unix.O_WRONLY; Unix.O_CREAT; Unix.O_TRUNC] 0o644 in ( function () -> let () = Random.self_init () in function x -> let time_to_wait = 1 + (Random.int 3) in Unix.sleep(time_to_wait); let sx = string_of_int x in ignore(Unix.write fd sx 0 (String.length sx));; \end{verbatim} \caption{Worker code using global initialization to share file descriptor \label{fig:magicglobal}} \end{figure} \subsection{The pipeline skeleton}\label{sec:pipe} The pipeline skeleton is denoted by the infix operator \verb1|||1; it performs in parallel the computations relative to different stages of a function composition over different data items of the input stream.\\ % Functionally, $f_1 \verb"|||" f_2 \ldots \verb"|||" f_n$ computes $f_n (\ldots f_2 (f_1 (x_i))\ldots)$ over all the data items $x_i$ in the input stream. Parallelism is now gained by having $n$ independent parallel processes. Each process computes a function $f_i$ over the data items produced by the process computing $f_{i-1}$ and delivers its results to the process computing $f_{i+1}$.\\ % If $f_1$ has type \texttt{(unit -> 'a stream -> 'b stream)},\\ % and $f_2$ has type \texttt{(unit -> 'b stream -> 'c stream)},\\ % then $f_1 ||| f_2$ has type \texttt{unit -> 'a stream -> 'c stream}. In terms of (parallel) processes, a sequence of data appearing onto the input stream of a pipe is submitted to the first pipeline stage. This stage computes the function $f_1$ onto every data item appearing onto the input stream. Each output data item computed by the stage is submitted to the second stage, computing the function $f_2$ and so on and so on until the output of the $n-1$ stage is submitted to the last stage. Eventually, the last stage delivers its own output onto the pipeline output channel. The resulting process network looks like the following: \begin{center}\includegraphics[scale=.50]{pipe} \end{center} For instance, a pipeline made out of three stages, the first one squaring integers, the second one multiplying integers by 2 and the third one incrementing integers can be written as follows: \small{ \begin{verbatim} let square _ x = x * x;; let double _ x = 2 * x;; let inc _ x = x + 1;; let apipe = parfun (fun () -> seq(square) ||| seq(double) ||| seq(inc));; \end{verbatim} } A pipeline models (parallel) function composition, thus input and output types of stages should match. This means that if stage $(i-1)$ has type \verb1unit -> 'c -> 'a1 stage $(i+1)$ has type \verb1unit -> 'b -> 'd1 stage $i$-th must have type \verb1unit -> 'a -> 'b1. %\marginpar{Pierre: tu veux mettre ça sous forme de règles d'inférence?} \subsection{The loop skeleton} \label{sec:loop} The loop skeleton named \texttt{loop}; it computes a function $f$ over all the elements of its input stream until a boolean condition $g$ is verified. A {\em loop } has type \begin{verbatim} ('a -> bool) * (unit -> 'a stream -> 'a stream) \end{verbatim} provided that $f$ has type \verb|unit -> 'a stream -> 'a stream| and $g$ has type \verb|'a -> bool|. Function $f$ is computed before testing termination, thus it is applied at least one time to each input stream element. In terms of (parallel) processes, a sequence of data appearing onto the input stream of a loop is submitted to a {\em loop in} stage. This stage just merges data coming from the input channel and from the feedback channel and delivers them to the {\em loop body} stage. The loop body stage computes $f$ and delivers results to the {\em loop end} stage. This latter stage computes $g$ and either delivers (\texttt{f x}) onto the output channel (in case (\texttt{g (f x)}) turns out to be \texttt{true}) or it delivers the value to the loop in process along the feedback channel (\texttt{(g (f x)) = false}). The resulting process network looks like the following: \begin{center} \includegraphics[scale=.50]{loop} \end{center} For instance, the following loop increments all the integer data items in the input stream until they become divisible by 5: \begin{verbatim} let notdivbyfive x = (x mod 5 <> 0);; let inc _ x = x + 1;; let aloop = parfun (fun () -> loop(notdivbyfive,seq(inc)));; \end{verbatim} The output of this function on the sequence \begin{verbatim} 3,7,10,14 \end{verbatim} is \texttt{5,10,15,15}. In particular, the call \texttt{theloop 10} returns \texttt{15} as the body \texttt{seq(inc)} is evaluated on input data \textit{before} the condition, and therefore the first time the condition is evaluated on 11 and not on 10. \subsection{The map skeleton}\label{sec:map} The map skeleton is named \texttt{mapvector}; it computes in parallel a function over all the data items of a vector, generating the (new) vector of the results.\\ % Therefore, for each vector $X$ in the input data stream, $\texttt{mapvector} (f, n)$ computes the function $f$ over all the items of $X=[x_1,\ldots , x_n]$, using $n$ distinct parallel processes that compute $f$ over distinct vector items ($[f(x_1),\ldots , f(x_n)]$).\\ % If $f$ has type \texttt{(unit -> 'a stream -> 'b stream)}, and $n$ has type $\texttt{int}$, then $mapvector (f, n)$ has type \texttt{unit -> 'a array stream -> 'b array stream}. In terms of (parallel) processes, a vector appearing onto the input stream of a mapvector is split $n$ elements and each element is computed by one of the $n$ workers. Workers apply $f$ to the elements they receive. A collector process is in charge of gluing together all the results in a single result vector. \begin{center} \includegraphics[scale=.50]{map} \end{center} Different strategies can be used to distribute a vector \verb#[|x1;...;xm|]# appearing in the input data stream to the workers. As an example the emitter: \begin{itemize} \item may round robin each \verb|xi| to the workers (\verb|{w1,...wn}|). The workers in this case simply compute the function $f : 'a \rightarrow 'b$ over all the elements appearing onto their input stream (channel). \item may split the input data vector in exactly \texttt{n} sub-vectors to be delivered one to each one of the worker processes. The workers in this case compute an $\texttt{Array.map} f$ over all the elements appearing onto their input stream (channel). \end{itemize} Summarizing, the emitter process takes care of (sub)task-to-worker scheduling (possibly implementing some kind of load balancing policy), while the collector process takes care of rebuilding the vector with the output data items and of delivering the new vector onto the output data stream. \texttt{mapvector} takes two arguments: \begin{itemize} \item the skeleton expression denoting the function to be applied to all the vector elements, and \item the parallelism degree of the skeleton, i.e.\ the number of processes to be used in the implementation. \end{itemize} For instance, the following code works on a stream of integer vectors and squares each vector element. The skeleton has a parallelism degree of 10, that is ten parallel processes are used to compute each vector in the stream. \begin{verbatim} let square _ x = x * x;; let amap = parfun (fun () -> mapvector(seq(square),10));; \end{verbatim} the result on a single array is as follows \begin{verbatim} # amap [|1;2;3;4;5|];; - : int array = [|1; 4; 9; 16; 25|] \end{verbatim} \subsection{The reduce skeleton}\label{sec:red} The reduce skeleton is named \texttt{reducevector}; it folds a function over all the data items of a vector.\\ % Therefore, $\texttt{reducevector} (\oplus, n)$ computes $ x_1 \oplus x_2 \oplus \ldots \oplus x_n$ out of the vector $x_1, \ldots, x_n$, for each vector in the input data stream. The computation is performed using $n$ different parallel processes that compute $f$.\\ % If $\oplus$ has type \texttt{(unit -> 'a * 'a stream -> 'a stream)}, and $n$ has type $\texttt{int}$, then\\ % $reducevector(\oplus, n)$ has type \texttt{unit -> 'a array stream -> 'a stream}. In terms of (parallel) processes, a vector appearing onto the input stream of a reducevector is processed by a logical tree of processes. Each process is able to compute the binary operator $g$. The resulting process network looks like the following tree: \begin{center} \includegraphics[scale=.50]{reduce} \end{center} In this case, the emitter process is the one delivering either couples of input vector data items or couples of sub-vectors of the input vector to the processes belonging to the tree base. In the former case, $\log (n)$ levels of processes are needed in the tree, in the latter one, any number of process levels can be used, and the number of sub-vectors to be produced by the emitter can be devised consequently. \\ The \texttt{reducevector} function takes two parameters as usual: \begin{itemize} \item the first parameter is the skeleton expression denoting the binary, associative and commutative operation (these properties must be ensured by the programmer to have a correct execution) \item the second is the parallelism degree, i.e. the number of parallel processes that have to be set up to execute the \texttt{reducevector} computation. \end{itemize} For instance, the following skeleton instance accepts in input a stream of vectors and, for each vector, computes the sum of all elements using the arithmetic + operator. \begin{verbatim} let areduce = parfun (fun () -> reducevector(seq(fun _ (x,y) -> x + y),10));; \end{verbatim} \noindent the result on a single array is as follows \begin{verbatim} # areduce [|1;2;3;4|];; - : int = 10 \end{verbatim} \subsection{The parfun skeleton} \label{sec:parfun} One would expect \texttt{parfun} to have type \texttt{(unit -> 'a stream -> 'b stream) -> 'a stream -> 'b stream}: given a skeleton expression with type \texttt{(unit -> 'a stream -> 'b stream)}, \texttt{parfun} returns a stream processing function of type \texttt{'a stream -> 'b stream}. \texttt{parfun}'s actual type introduces an extra level of functionality: the argument is no more a skeleton expression but a functional that returns a skeleton: \begin{alltt} val parfun : (unit -> unit -> 'a stream -> 'b stream) -> 'a stream -> 'b stream \end{alltt} This is necessary to guarantee that the skeleton wrapped in a \texttt{parfun} expression will only be launched and instanciated by the main program (\verb|pardo|), not by any of the multiple running copies of the SPMD binary, even though thoses copies may evaluate the \texttt{parfun} skeletons; the main program will actually create the needed skeletons by applying its functional argument, while the generic copies will just throw the functional away, carefully avoiding to instanciate the skeletons. \subsection{The pardo skeleton: a parallel scope delimiter} \label{sec:pardo} \subsubsection{Typing} Finally, the \texttt{pardo} combinator defines the scope of the expressions that may use the \texttt{parfun} encapsulated expressions. \begin{alltt} val pardo : (unit -> 'a) -> 'a \end{alltt} {\tt pardo} takes a thunk as argument, and gives back the result of its evaluation. As for the \texttt{parfun} combinator, this extra delay is necessary to ensure that the initialization of the code will take place exclusively in the main program and not in the generic SPMD copies that participate to the parallel computation. \subsubsection{Parallel scoping rule} In order to have the \verb|parfun| and \verb|pardo| work correctly together the following scoping rule has to be sollowed: \begin{itemize} \item functions defined via the \texttt{parfun} combinator must be \emph{defined} \emph{before} the occurrence of the \texttt{pardo} combinator, \item those \texttt{parfun} defined functions can only be \emph{executed} \emph{within} the body of the functional parameter of the \texttt{pardo} combinator, \item no \texttt{parfun} can be used directly inside a \texttt{pardo} combinator. \end{itemize} \subsubsection{Structure of an {\ocamlpiiil} program }\label{f11} Due to the scoping rule in the pardo, the general structure of an {\ocamlpiiil} program looks like the following: \begin{small} \begin{alltt} (* (1) Functions defined using parfun *) let f = parfun(\emph{skeleton expression}) let g = parfun(\emph{skeleton expression}) (* (2) code referencing these functions under abstractions *) let h x = \ldots{} (f \ldots{}) \ldots{} (g \ldots{}) \ldots{} \ldots\\ (* NO evaluation of code containing a parfun is allowed outside pardo *) \ldots\\ (* (3) The pardo occurrence where parfun encapsulated functions can be called. *) pardo (fun () -> (* NO parfun combinators allowed here *) (* code evaluating parfun defined functions *) \ldots{} let a = f \ldots{} let b = h \ldots{} \ldots{} ) (* \emph{finalization of sequential code here} *) \end{alltt} \end{small} At run time, in the sequential model, each generic copy just waits for instructions from the main node; the main node first evaluates the arguments of the \texttt{parfun} combinators to build a representation of the needed skeletons; then, upon encountering the \texttt{pardo} combinator, the main node initializes all the parallel computation networks, specialising the generic copies (as described in details in {\cite{Ocamlp3lMlw98}}), connects these networks to the sequential interfaces defined in the \texttt{parfun}'s, and then runs the sequential code in its scope by applying its function parameter to \texttt{():unit}. The whole picture is illustrated in Figure \ref{fig:pardo}. The skeleton networks are initiated only once but could be invoked many times during the execution of \texttt{pardo}. \section{Load balancing: the colors} \label{ss:colors} In the {\ocamlpiiil} system, the combinators expressions govern the shape of the process network and the execution model assumes a `virtual' processor, for each process. The mapping of virtual to physical processors is delegated to the {\ocamlpiiil} system. The mapping is currently not optimized in the system. However, programs and machines can be annotated by the programmer using \emph{colors}, which can pilote the virtual-to-physical mapping process. The idea is to have the programmer to rank the relative `weight' of skeleton instances and the machine power in a range of integer values (the colors). Then, weights are used to generate a mapping in which load is evenly balanced on the partecipating machine according to their relative power. Pushing the difficult part of the generaion of weights to the programmer's knowledge and ability, this simple and practical idea gives surprisingly good results in practice. Let's consider as an example, the skeletal expression we discussed in the example (Sec~\ref{ss:example}): \[ \texttt{farm} \ (\texttt{seq}\ (fun\ x \rightarrow x\ *\ x), 16) \] that corresponds to a network of one emitter node, one collector node, and 16 worker nodes which compute the square function. There are numerous ways of mapping a set of virtual nodes to a set of physical nodes. %Which is the best mapping and how to obtain it from the %compiler is still unclear at this stage: for the time being, the %process is completely automatic and the programmer has no control over %the strategy used by the system to found a good mapping. If no information is provided, the support uses a simple round robin, which maps virtual to physical nodes in a cyclic way: first all phisical processors get one process then we start again from the beginning until virtual processors are all allocated. Unfortunately, such a solution doesn't take into account the load balancing constraints: all the physical (resp. virtual) nodes are considered equivalent in computing power and are used evenly. If the programmer knows more about machines and processes he/she can tell the system using colors. A \emph{color} is an optional integer parameter that is added to {\ocamlpiiil} expressions in the source program and to the execution command line of the compiled program. We use the regular {\ocaml}'s optional parameters syntax, with keyword \emph{col}, to specify the colors of a network of virtual nodes. For example, writing \verb|farm ~col:k (f, n)| means that all virtual nodes inside this farm structure should be mapped to some physical nodes with a capability ranking $k$. The scope of a color specification covers all the inner nodes of the structure it qualifies: unless explicitely specified, the color of an inside expression is simply inherited from the outer layer (the outermost layer has a default color value of 0 which means no special request). For combinators \texttt{farm}, \texttt{mapvector} and \texttt{reducevector}, in addition to the color of the combinator itself, their is an additional optional color parameter $colv$. A $colv[\ ]$ specification is a {\tt color list} (i.e. an {\tt int list}) that specifies the colors of the parallel worker structures that are arguments of the combinator. As an example, the {\ocamlpiiil} expression \begin{alltt} map ~col:2 ~colv:[ 3; 4; 5; 6 ] (seq f, 4) \end{alltt} \noindent is a {\texttt{mapvector}} skeleton expression, with emitter and collector nodes of rank 2, and four worker nodes (four copies of \verb|seq f|) whith respective ranks 3, 4, 5, and 6. To carefully map virtual nodes to physical nodes, we also need a way to define the colors of physical nodes. This information is specified on the command line when launching the program (see Section~\ref{cap:run}). One can write: \begin{alltt} prog.par -p3lroot ip1:port1\#color1 ip2:port2\#color2 ... \(\backslash\) ip\_i:port\_i\#color\_i ... \end{alltt} \noindent where \texttt{ip\_i:port\_i\#color\_i} indicates the ip address (or name), the port, and the color of the physical node {\tt i} participating to the computation. The port and color here are both optional. With no specified port, a default p3lport is used; with no color specification, the default color 0 is assumed. If the colors of all the virtual processors and all the physical processors have a one-to-one correspondance, the mapping is easy. But such a perfect mapping does not exist in general: first of all, there is not always equality between the amount of physical processors we have and the amount of virtual processors we need; second, in some very complex {\ocamlpiiil} expressions, it is complex and boring for the programmer to calculate manually how many virtual nodes are needed for each color class. So, we decided to use a simple but flexible mapping algorithm, based on the idea that \emph{what a color means is not the \textbf{exact} capability required but the \textbf{lowest} capability acceptable}. For example, a virtual node with color value 5 means a physical node of color 5 is needed, but if there is no physical node with value 5, and there exists a physical node of color 6 free and available, why don't we take it instead? In practice, we sort the virtual nodes in decreasing order of their color values, to reflect their priority in choosing a physical node: virtual nodes with bigger colors should have more privilege and choose their physical node before the nodes with smaller colors. Then, for each virtual node, we lists all the physical nodes with a color greater than or equal to the virtual node color. Among all those qualified ones, the algorithm finally associates the virtual node with the qualified node which has the smallest work load (the one that has the least number of virtual nodes that have been assigned to it). This algorithm provides a mapping process with some degree of automatization and some degree of manual tuning, but one has to keep in mind that the \emph{color} designs a computational class, qualitatively, and is not an exact quantitative estimation of the computational power of the machine, as the current version of {\ocamlpiiil} does not provide yet the necessary infrastructure to perform an optimal mapping based on precise quantitative estimations of the cost of each sequential function and the capabilities of the physical nodes, so that we cannot guarantee our color-based mapping algorithm to be highly accurate or highly effective. Still, the ``color'' approach is accurate and simple enough to be quite significant to the programmer: according to the experiments we have conducted, it indeed achieved some satisfactory results in our test bed case (see \cite{clement04}). Figure {\ref{t:full}} summarizes the types of the combinators, exactly as they are currently available to the programmer in the {\piiilversion} version of {\ocamlpiiil}, including the optional color parameters. \begin{figure}[htbf] \begin{alltt} type color = int val seq : ?col:color -> (unit -> 'a -> 'b) -> unit -> 'a stream -> 'b stream val ( ||| ) : (unit -> 'a stream -> 'b stream) -> (unit -> 'b stream -> 'c stream) -> unit -> 'a stream -> 'c stream val loop : ?col:color -> ('a -> bool) * (unit -> 'a stream -> 'a stream) -> unit -> 'a stream -> 'a stream val farm : ?col:color -> ?colv:color list -> (unit -> 'b stream -> 'c stream) * int -> unit -> 'b stream -> 'c stream val mapvector : ?col: color -> ?colv:color list -> (unit -> 'b stream -> 'c stream) * int -> unit -> 'b array stream -> 'c array stream val reducevector : ?col:color -> ?colv:color list -> (unit -> ('b * 'b) stream -> 'b stream) * int -> unit -> 'b array stream -> 'b stream val parfun : (unit -> unit -> 'a stream -> 'b stream) -> 'a stream -> 'b stream val pardo : (unit -> 'a) -> 'a \end{alltt} \caption{The (complete) types of the {\ocamlpiiil} skeleton combinators \label{t:full}} \end{figure} \input{Running} \chapter{More programming examples}\label{cap:exe} \section{Generating and consuming streams} Streams to be feed to the parallel networks can be created and consumed using functions in \texttt{P3lstream}. Main functions are as follows: \begin{table}[h] \begin{tabular}{||l|l|l||} \hline Function & Description & Secs\\ \hline \texttt{P3lstream.of\_list} & transforms a list in a valid stream & \ref{sec:inputuno}, \ref{sec:inputoutputdafile},\\ & & \ref{sec:mixingUnix} \\ \texttt{P3lstream.iter} & iterates on all elements of a stream & \ref{sec:inputuno}, \ref{sec:inputoutputdafile},\\ & &\ref{sec:of_fun}\\ \texttt{P3lstream.of\_fun} & allows stream generation & \\ & iterating a sequential function &\\ & which explicitely raises \verb|End_Of_File| & \ref{sec:of_fun}\\ \texttt{P3lstream.to\_list} & transforms streams into lists & \ref{sec:to_list}\\ \hline \end{tabular} \end{table} \subsection{Generating streams from lists} \label{sec:inputuno} % dal file terzo-esempioUM.ml \begin{small} \begin{verbatim} let rec generate_list_of_float n s = if ( n <= 0 ) then [] else s :: (generate_list_of_float (n-1) (s +. 1.0)) ;; let initseq n s = P3lstream.of_list (generate_list_of_float n s);; let finseq y = P3lstream.iter (fun x -> print_float x; print_newline()) y;; (* Define stage1 and stage 2, can be anything......*) let stage1 _ x = x +. x;; let stage2 _ x = x *. x;; (* definizione network del pipe *) let pipe = parfun (fun () -> seq(stage1) ||| seq(stage2));; (* pardo activation *) pardo (fun () -> let s = initseq 10 1.0 in let y = pipe s in finseq y );; \end{verbatim} \end{small} \subsection{Generating streams from files} \label{sec:inputoutputdafile}%from sesto_esempioUM.ml \begin{small} \begin{verbatim} let read_input_float fd = Scanf.fscanf fd "%f" (fun n -> n);; let rec fgenerate_list_of_float cin n= if ( n <= 0 ) then [] else (try (let s = (read_input_float cin) in Printf.printf "Ecco %f\n" s; s:: (fgenerate_list_of_float cin (n-1))) with End_of_file -> []; ) ;; (* stream generation *) let initseq cin n = P3lstream.of_list (fgenerate_list_of_float cin n);; (* prints out stream *) let finseq cout y = P3lstream.iter (fun x -> Printf.fprintf cout "%f" x; output_string cout "\n") y;; (* Defines stage1 and stage 2 *) let stage1 _ x = x +. x;; let stage2 _ x = x *. x;; (* defining a two stage pipe network *) let pipe = parfun (fun () -> seq(stage1) ||| seq(stage2));; (* pardo activation *) pardo (fun () -> let cin = open_in "pippo" and cout = open_out "pluto" in let s = initseq cin 10 in let y = pipe s in finseq cout y ) ;; \end{verbatim} \end{small} \subsection{Generating streams repeatedly calling a function}\label{sec:of_fun} Here, the stream is generated by repeatedly calling function \texttt{generate\_input\_stream} via \verb|P3lstream.of_fun|. \begin{small} \begin{verbatim} %quinto-esempioUM.ml (* generating the input stream calling repetedly a function *) let generate_input_stream = let x = ref 0.0 in (function () -> begin x := !x +. 1.0; if(!x < 10.0) then !x else raise End_of_file end);; (* prints out an integer stream *) let finseq y = P3lstream.iter (fun x -> print_float x; print_newline()) y;; (* Defines stage1 and stage 2 as identity*) let stage1 _ x = x;; let stage2 _ x = x;; let pipe = parfun (fun () -> seq(stage1) ||| seq(stage2));; (* pardo activation *) pardo (fun () -> let s = P3lstream.of_fun generate_input_stream in let y = pipe s in finseq y ) ;; \end{verbatim} \end{small} \subsection{Transforming streams into lists}\label{sec:to_list} %settimo-esempioUM.ml \begin{small} \begin{verbatim} (* generating the input stream calling repeatedly a function *) let generate_input_stream = let x = ref 0.0 in (function () -> begin x := !x +. 1.0; if(!x < 10.0) then !x else raise End_of_file end);; (* Defines stage1 and stage 2*) let stage1 _ x = x +. 1.;; let stage2 _ x = x +. 7.;; let print_result x = print_float x; print_newline();; let pipe = parfun (fun () -> seq(stage1) ||| seq(stage2));; (* pardo activation *) pardo (fun () -> let is = P3lstream.of_fun generate_input_stream in (* transforms a stream into a list *) let l = P3lstream.to_list (pipe is) in List.iter print_result (List.map (fun n -> n*. 4.) l) ) ;; \end{verbatim} \end{small} \section{Global and local definitions} As discussed in Section\ref{sec:commonerrors}, global variables \emph{must} not be used in an \ocamlpiiil\ pragram, as their value on different processing nodes will be different and updates will have effect only on the node which executes them. On the other hand, we can have both local and global definitions which are evaluated before or after specializing a procesing node. For instance we can share the same file descriptor between all the processing nodes partecipating to a skeleton. See examples in Section~\ref{sec:farm}. \section{Managing command line: \texttt{option}} To be done \section{Directing allocation: colors} To be done \section{Mixing Unix processes with \ocamlpiiil}\label{sec:mixingUnix} The following code defines a farm in which each worker computes the square over a stream of float. However, the function is computed by an external command which is spawned and connected via stdin / stdout to the farm worker in the seq skeleton. In the following code, care is taken to activate the external process only once. \texttt{spawned} is \texttt{true} only if the Unix process and connecting pipes descriptor are maintained in variables \texttt{cin} and \texttt{cout}. Notice that pattern matching in \texttt{(* * *)} is not exhaustive, because if process has been already spawned \texttt{cin} and \texttt{cout} must contain a valid descriptor. \begin{verbatim} let farm_worker _ = let conto = ref 0 and spawned = ref false and cin = ref None and cout = ref None in (fun x -> conto := !conto + 1; if not !spawned then begin let (ic,oc) = Unix.open_process "./square" in cin := Some ic; cout := Some oc; spawned:=true end; let Some ic, Some oc = (!cin , !cout) in (* * *) Printf.fprintf oc "%d\n" x; Pervasives.flush oc; let i = Scanf.fscanf ic "%d" (fun x -> x) in ) ;; let compute = parfun (fun () -> farm(seq(farm_worker),4));; let print_result x = print_int x; print_newline();; pardo(fun () -> let is = P3lstream.of_list [1;2;3;4;5;6;7;8;9] in let s' = compute is in P3lstream.iter print_result s'; );; \end{verbatim} The important thing is remember to fflush data output in the external commend source otherwise we block. The following is an example of valid C definition for the square program. \begin{verbatim} #include #define TRUE 1 int main(void) { int i; while (TRUE) { /* reading from standard input */ scanf("%d",&i); /* writing on strandard output */ printf("%d\n",i*i); /* fflushing buffers otherwise you block the output stream */ fflush(NULL); } exit(0); } \end{verbatim} \chapter{Implementing \ocamlpiiil} \label{cap:implementation} Now, let us point out the peculiar features relative to the implementation of \ocamlpiiil. First, we will discuss the mechanism used to implement different processes onto different nodes, by exploiting a particular form of ``closure communication''. Then, we will point out some details relative to the interprocess communication layer and we will motivate the choice of the Unix sockets as the \ocamlpiiil\ communication layer. Finally, we will discuss some details of the templates we used to implement the skeletons provided by \ocamlpiiil. \section{Closure passing as distributed higher order parameterization} A sequential implementation of an \ocamlpiiil\ program is quite easy to provide: just use a library \verb|seqp3l.ml| which implements each skelton with a valid \ocaml\ sequential function. % not sure it is still like this %containing % \emph{precisely} the definitions given in % section~\ref{f5}\footnote{Indeed, that is the \emph{actual} code % in the system.}. The type safety is a direct consequence of the fact that we are not using here anything from outside the safe core of Ocaml. \noindent Similarly, providing the graphical semantics poses no real challenge. But what about the parallel semantics? What is the right way to implement such a thing? We must guarantee the type safety and ensure that the runtime is reasonably small as to allow the verification of its properties, which will become an important point in industrial applications. Both points posed problems which we overcame during the development of the system. First of all, to ensure that the system is manageable and safe, we immediately discarded the approach based on parsing the source file to extract the code corresponding to each node of the network: this would impose to use external tools to perform an analysis of the user code which is difficult, error prone, and whose semantics would have a very unclear status. Instead, we choose to use an SPMD approach: all the nodes of the network will run the \emph{same} program (in a sense this is the ``template process interpreter code'', as we will see in while) , which will be the result of the compilation of the full user code, and a control node\footnote{The control node runs the same program as the others, but it is invoked by the user with a special designating option \mbox{\tt -p3lroot}.} will dispatch to the rest of the nodes in the network the parameterization information needed to specialize it to the particular function it is really supposed to perform (emitter, collector, sequential node running a given function $f$, etc.). In order to achieve this behavior, the control node performs the following tasks: \begin{itemize} \item executes the \texttt{parfun} skeleton expression definitions, which has as a consequence to build a data structure describing all the parallel process networks. From this data structure, we compute behind the scenes the configuration information for each node in the process network. \item executes the \texttt{pardo} expression: this has the following effect \begin{itemize} \item maps virtual nodes to the processor pool given on the command line, \item initializes a socket connection with all the participating nodes, \item gets the port addresses from each of them (a fixed port number ---\texttt{p3lport}--- or some dynamically generated number if more than one copy run on the same machine), \item sends out to each node the addresses of its connected neighbors (this step together with the previous two provides an implementation of a centralized deadlock free algorithm to interconnect the other nodes into the process network specified by the skeleton expression), \item sends out to each node the specialization information that consists of the \emph{function} it must perform. \end{itemize} \end{itemize} This very last task requires a sophisticated operation: sending a \emph{function} (or a closure) over a communication channel. This is usually not possible in traditional functional programming languages, since sending an arbitrary function supposes that we are able to find on the receiving side the code corresponding to the function name received \emph{or} that we can transfer executable code (a feature known as \emph{mobility} today). Now, mobility is necessary to send closures between arbitrary programs (since two different programs have no reason to know each other's function code), but \emph{not} between two copies of the \emph{same} program: in the latter case, it suffices to send what essentially amounts to a code pointer. Starting from version 1.06, \ocaml\ contains a modified marshaling library, originary designed for the \ocamlpiiil\ system, that performs closure sending between copies of the same program (this is checked by means of an MD5 signature of the program code). The \texttt{ocaml} run time system takes care of dealing with differences in endianness and word size between communicating machines, as well as flattening tree-shaped data structures. On the other side, all the other nodes simply wait for a connection to come in from the root node, then send out the address of the port they allocate to do further communication, wait for the list of neighbors and for the specialization function, then simply perform it until termination. To summarize, in the implementation the possibility of sending closures allowed us to obtain a kind of higher order distributed parameterization that kept the runtime code to a minimum size (the source codes of the full system is less than twenty kilobytes). \section{Communication and process support} % communications As far as the general mechanism of closure passing is concerned, no particular requirement/restrictions have been posed onto the physical communication implementation. Even considering the fact that we need to move data between the different processes making up the parallel implementation of an \ocamlpiiil\ program, we derived no particular constraint onto the communication layer. Thus, at the very beginning of the \ocamlpiiil\ project, we faced the problem of choosing a suitable communication system. We had as a goal to come out with the maximum ``portability'' of \ocamlpiiil. Furthermore, we wanted to fully demonstrate the feasibility of integrating the parallel skeleton world within a functional framework. These two goals had priority over the classical ``efficiency and performance'' goal one usually has to achieve when dealing with parallelism. The result is that we have adopted the plain Unix socket world as the communication layer. This has some (very) positive consequences on the overall \ocamlpiiil\ design: \begin{itemize} \item the socket communication support is generally available on Unix/Linux and Windows system % and it turns out to be available even in the % Windows world, even if in this case reliability is often a % problem, \item no particular customization of the support is needed to match the \ocamlpiiil\ features, \item the point-to-point, connection oriented, stream model provided by Unix sockets is perfect to model data streams flowing around between the processes belonging to the process network derived by \ocamlpiiil\ to implement the user skeleton code, \item last but not least, there was an existing and suitable \texttt{ocaml} interface to Unix system calls, including those relative to sockets. \end{itemize} On the down side, the adoption of Unix sockets presents an evident disadvantage which is the low performance achieved in communications (a raw synchronization (i.e.\ zero length data communication) takes several milliseconds to be performed, even in those cases when the data transmission media turns out to be free, i.e.\ no collisions are detected). At the moment, we are considering to use in the next version of \ocamlpiiil\ a communication layer based on an optimized communication library such as MPI \cite{mpi}, as an efficient alternative to the socket communication layer, which will be nevertheless retained for its ease of deployment, that makes it attractive for programming courses. Porting to MPI will require some modifications in the template code used within \ocamlpiiil, and will not necessarily completely solve the performance problems of the socket communication layer when run on a network of computers, where most MPI libraries are still implemented using sockets, but will allow to target real multiprocessor machines where MPI is efficiently implemented, without touching the user code. Also, we will be able to delegate to the MPI system the administrative tasks involved in copying and launching the programs on the different machines. As far as the process model is concerned, we felt happy with the Unix one. All we need is a mechanism allowing an instance of the template interpreter (the one specialized by using the closure passing mechanism) to be run onto different workstations belonging to a local area network. The Unix \texttt{rsh} mechanism matches this requirement. Note that, as processes are generated and run on different machines just at the beginning of the \ocamlpiiil\ program execution, any considerations about performance in \texttt{rsh}-ing is irrelevant. \section{Template implementation} % template implementation \ocamlpiiil\ implements each skeleton appearing in the application code by generating a proper instantiation of the corresponding implementation template. In \ocamlpiiil, a single implementation template is provided for each one of the skeletons supported. The implementation templates provided within the current prototype closely resemble the ones discussed in the informal parallel semantics section (Section~\ref{sec:skeletons}). Actually, only the \textit{reduce} template is slightly different, in that the tree discussed in Section \ref{sec:red} is actually implemented by a process network similar to the one discussed for the farm, where partially evaluated data is iteratively passed back from the collector to the emitter process. We are currently studying a more efficient mechanism based on a formal calculus for data distribution and computation over dense arrays \cite{Zheng03,hlpp03,clss05}. Each template appearing in \ocamlpiiil: \begin{itemize} \item \emph{is parametric in the parallelism degree exploited} As an example the farm template may accommodate any positive numbers of worker processes. Currently, the programmer must specify this parameter, which is the second parameter of a \texttt{farm(f,n)} skeleton call. \item \emph{is parametric in the function computed as the body of the skeleton} For instance, the farm skeleton accepts as a parameter the function that has to be computed by the worker processes. This function must be a skeleton itself. Therefore, either it is a \texttt{seq} skeleton call, or it is a skeleton call modeling a parallel computation. In the former case, the skeleton is implemented by a process network whose workers just perform the sequential computation \texttt{f} denoted by some \texttt{seq(f)}. In the latter case, each worker process is itself a process network known by the emitter and collector processes implementing the farm just as channels where data has to be delivered/fetched. \item \emph{provides a set of process templates} i.e.\ parametric process specifications that can be instantiated to get the real process codes building out the implementation template process network. As an example, consider again the farm template. The emitter process behavior can be fully specified by the data type of items that have to be processed, by the channel from which those data items have to be read and by the set of channels onto which the data items have to be scheduled (written) to the worker processes, possibly with some ``clever'' (e.g.\ achieving load balancing) scheduling strategy. Such a process can be completely specified by providing a function \begin{center} \texttt{farmetempl (OutChanSel f) ic ocl} \end{center} %\sp{this final part should be aligned to code or dropped} \noindent whose first parameter provides the worker scheduling function, the second one provides the input channel where data has to be fetched and the third one provides the set of channels used to deliver tasks to be computed to the farm workers. The type of such a function turns out to be {\small \begin{verbatim} val farmetempl : ('a, 'b) Parp3l.action -> in_channel -> out_channel list -> unit \end{verbatim}} \noindent The process template definition in the \ocamlpiiil\ code looks like the following: % {\small \begin{verbatim} let farmetempl (OutChanSel f) ic ocl = while true do try let theoc = f ocl in match (Marshal.from_channel ic) with UserPacket(p,seqn,tl) -> Marshal.to_channel theoc (UserPacket (p,seqn,Farmtag::tl)) [Marshal.Closures]; flush theoc; | EndStream -> List.iter (fun x -> Marshal.to_channel x EndStream [Marshal.Closures]; flush x) ocl; List.iter close_out ocl; close_in ic; exit 0 with End_of_file -> List.iter close_out ocl; close_in ic done;; \end{verbatim} } \end{itemize} % Therefore the whole compilation process transforming an \ocamlpiiil\ skeleton program into the parallel process network implementing the program can be summarized in the following steps: \begin{enumerate} \item the skeleton code is parsed and transformed into a skeleton tree data structure, recording all the significant details of the skeleton nesting supplied by the user code, \item the skeleton tree is traversed and processes are assigned to each skeleton according to the implementation templates. During this phase, processes are denoted by their input/output channels, identified via a unique number. \item once the number and the kind of parallel processes building out the skeleton code implementation is known, code is generated that either delivers the proper closures, derived by using the process templates, to the ``template interpreter'' instances running on distinct workstations (this happens just on one node, the ``root'' one), or waits for a closure and repeatedly computes this closure on the proper input and output channels until an \texttt{EndOfFile} mark is received. \end{enumerate} %\input{esempi} \chapter{Multivariant semantics and logical debugging} By providing modules that implement the three \ocamlpiiil\ skeleton semantics (the sequential one, the parallel one and the graphical one), we allow the \ocamlpiiil\ user to perform the following parallel application development process: \begin{itemize} \item develop skeleton code modeling the application at hand. This just requires a full understanding of the skeleton sequential semantics and usually allows the user to reuse consistent portions of existing applications written in plain \texttt{ocaml} or legacy in C, C++ etc. \item test the functionality of the new application by supplying relevant input data items and looking at the results computed using the sequential skeleton semantics. In case of problems, the user may run the sequential debugging tools to overcome problems. \item link the parallel skeleton semantics module and run the application onto the workstation network. Provided that the application was sequentially correct, no new errors should be found at this step (we assume that the run time is guaranteed correct!). In practice, a few errors can occur ussually related to wrong assumption on global variables. If your code uses global variables updating them durin gexecution, this will work OK in the sequential semantics as memory is actually shared but not in the parallel version as update will be only seen locally on the processing node. \item look at the performance results of running the application on the number of processors available and possibly adjust the significant performance parameters, such as the number of workers of the \texttt{farm}, \texttt{map} and \texttt{reduce} and the color of each of them. This is actually the real problem in the development of an \textit{efficient} parallel application. Forthcoming versions of \ocamlpiiil\ will include analytical performance models for the templates and these models will be used to automatically guess colors and giude the complier in the compiler. During performance tuning, the programmer may link the graphic semantic skeleton module and look at the results of the program execution, i.e.\ at the resulting process graph, in order to understand where bottlenecks are or which parts of the program must be further decomposed using skeletons in order to get better performant application code. \end{itemize} \ignore{As an example, let us show what happens with a real example. Let us suppose we want to plot the Mandelbrot set. This is a classical example of parallel application with unbalanced load. First of all, the user comes out with a code (such as the one shown in Appendix \ref{mandelbrot}). This code allows to plot a particular fractal picture directly in the \texttt{ocaml} graphical output window. The code is debugged by linking the sequential skeleton semantics just including in the code the line \texttt{open Seqp3l;;}. Once the code has been debugged, the programmer just deletes the \texttt{open Seqp3l;;} statement and supplies the three statements linking the parallel skeleton semantics \texttt{open Parp3l;;}, \texttt{open Nodecode;;} and \texttt{open Template;;} and he/she can immediately compile the code and launch it on his/her workstation network by means of a command such as \begin{center} \begin{verbatim} ocamlp3lrun \end{verbatim} \end{center} He will then look at the performance, i.e.\ he/she will consider the number of workstations used and the time spent in the computation, and consider if it is the case to vary either the number of worker appearing in the farm skeleton within the code or the number of workstations used for executing the parallel code. In so doing, the user may look at the application process network by linking the graphical skeleton semantics via a \texttt{open GrafP3l;;} statement. The output of the program will be in this case the following: \begin{center} \includegraphics[scale=.20]{mandelgra} \end{center} \noindent (The user in this case indicated that the farm has 10 workers.) Eventually, the overall application will show a linear speedup on a small number of workstations (i.e.\ on a small number of worker processes in the farm), due to the fact that each row of the plot takes a long time to be computed. By launching the sequential Mandelbrot code (that exploiting the sequential skeleton semantics) on a machine and the parallel one (that exploiting the parallel skeleton semantics) on a cluster of workstation the result will look like the following: \begin{center} \includegraphics[scale=.30]{mandelparseq} \end{center} The left graphic display is the one coming out from the parallel execution, while the right one is the one coming from the sequential code. Sequential and parallel code only differ for the semantic file include and have been started at the same time. We can notice that the left display gets filled much faster than the right one. By performing precise time profile activity, we found a linear speedup of the parallel code with respect to the sequential one when using up to 4 workstations. } Let us spend now some words concerning logical, sequential debugging of \ocamlpiiil\ applications. A user developing an \ocamlpiiil\ application may link the sequential skeleton semantics module to his/her code and debug the application by using the plain sequential debugging tools of \texttt{ocaml}. This debugging activity can be performed on a single machine, provided the machine supplies \texttt{ocaml}. Also, performance tuning can be directed using standard sequential profiling tools such as \texttt{gprof}. Once the application has been debugged, i.e.\ the user perceives it computes the expected results, he/she can compile the parallel version of the application by linking the parallel skeleton semantics. As we guarantee that the implementation templates for the different skeletons of \ocamlpiiil\ are correct (deadlock free, load-balanced, etc.) and as we guarantee that the process transforming the skeleton code in the process code is correct, the user does not need to perform explicit activities in order to check that the results computed by the parallel code are correct. In particular, the user does not need to check that all the processes have been correctly scheduled for execution, or that the communication channels have been set up properly between these processes, or that data of type \texttt{'a} has been never delivered on channels transmitting data of type \texttt{'b}. This is a very short list of bad things that may affect the correct behavior of an explicitly parallel program, indeed. The fact that the user is not required at all to take them into account is one of the biggest pro's of the functional skeleton approach. \chapter{Related work, conclusions and perspectives} \section{Related work} %\sp{to be updated} Many researchers are currently working on skeletons and most of them are building some kind of parallel implementation, but our work, as far as we know, is unique in its combination of a fully functional strongly typed language with the skeleton approach. In particular, Darlington's group at Imperial College in London is actively working on skeletons. They have explored the problems relative to implementing a skeleton programming system, but the approach taken uses an imperative language as the implementation language. Currently there is a ``local'' prototype implementation but no public domain implementation of their skeleton approach and they seem deeply involved in the study of the data-parallel and coordination aspects of skeletons. \cite{darli-to-1,darli-to-2,Darlington1996} A different approach relative to skeleton parallel programming within a functional framework has been discussed by Bratvold \cite{bratvold-thesis}. Bratvold takes into account plain ML programs and looks for skeletons within them, compiling these skeletons by using process networks that look like implementation templates. However, both the final target language and the implementation language are imperative. %%%###%%% Finally, S\'erot \cite{serot97,parco02}, presents an embedding of skeletons within \texttt{ocaml} that seems to be close to our work, although independently developed. The message passing is performed by interfacing the MPI library with \texttt{ocaml}. The skeletons taken into account are different. She considers data-parallel \texttt{farm}, roughly corresponding to our \texttt{mapvector} skeleton, and two further skeletons, \texttt{scm} and \texttt{filt}. \texttt{filt} is a plain filter skeleton, canceling data items from a list, while \texttt{scm} (Split, Compute and Merge) looks like a map skeleton working on lists with explicit, user defined, decomposition/recomposition functions. S\'erot's implementation of the skeletons within \texttt{ocaml} is quite different from ours and only allows one skeleton at a time to be realized on the processor networks, thus preventing skeleton composition (you cannot nest two \texttt{scm} skeletons for example), and only allowing for a limited form of staging of the parallel computation: you can perform an \texttt{scm}, then when this is finished, you can reorganize your network and perform another \texttt{scm}. This way, the mapping of virtual processors to real processors on the network is a trivial task, and is done inside each skeleton at run-time instead of beforehand in a specific pass like in \ocamlpiiil. S\'erot implements the skeletons included in his model by providing second order functions that directly call MPI and realize an SPMD execution model. %@inproceedinpgs{serot, % author = "Jocelyn S\'erot", % title = "{Embodying parallel functional skeletons: an experimental % implementation on top of MPI}, % booktitle = "Proceedings of the EuroPar'97", % note = "Passau, Germany", % year = 1997, % publisher = "Springer Verlag, LNCS No.", % monht = "August" %} %%%###%%% As for the relevant effort done in the field of languages for mobile agents, like for example~\cite{KnabePhD,FournetMaranget_Join_calculus_language}, it should be noted that they address quite a different kind of problems, but once stable, these languages could form the basis of a next generation fully fault-tolerant and dynamically load-balanced version of our system. \section{Conclusions and perspectives} % conclusions Here we showed how a skeleton parallel programming modelcan be successfully married with the functional programming environments such as the one provided by \ocaml. In particular, we discussed a powerful skeletal model, how skeletons can be embedded within \ocaml\ as second order functions and how modules implementing both the sequential and the parallel skeleton and discuss the typical application development cycle in \ocamlpiiil. The whole process preserves the strong typing properties of \texttt{ocaml}. At the moment, the prototype \ocamlpiiil\ implementation is being tested as described in this paper and is available from the \ocamlpiiil\ project home Web page \ocamlpiiilweb. In the near future we want first of all to include a more powerful MAP skeleton working on dense arrays with an arbitrary number of dimensions\cite{Zheng03,hlpp03,clss05}. This will call for a more efficient communication layer, by using colective MPI communications \cite{mpi} instead of the plainUnix socket library. At the same time, we investigate the feasibility of porting the system on the ubiquitous Windows boxes, for didactical purposes. Finally, we already developed a parallel numerical code \cite{clement04} and plan to write some more significant parallel applications in order to fully test the prototype. \ignore{ \appendix \section{Mandelbrot code} \label{mandelbrot} {\small \begin{verbatim} open Graphics;; type task = Task of (int*(float*float*float*float)*int*int);; type result = Result of (int*(int array));; let color_pixel (x0,y0,x1,y1) n res i j = let dx = (x1-.x0)/.(float n) in let dy = (y1-.y0)/.(float n) in let zr = ref (y0 +. (dy *. (float i))) in let zi = ref (x0 +. (dx *. (float j))) in let cr = ref (!zr) in let ci = ref (!zi) in let col= ref 0 in begin for k=0 to (res-1) do if(!zr *. !zr +. !zi *. !zi <= 4.0) then begin zi := 2.0 *. !zr *. !zi *. !ci; zr := !zr *. !zr -. !zi *. !zi +. !cr; col:= k end done; !col end;; let colorof c res = Pervasives.truncate (((float c)/.(float res))*.(float (255*255*255+255*255+255)));; let plot_mandel_row (x0,y0,x1,y1) n res j = let line = Array.create n black in for k = 0 to n - 1 do line.(k) <- colorof (color_pixel (x0,y0,x1,y1) n res k j) res done; (Result (j, line));; let gen_tasks (x0,y0,x1,y1) n res = let rec gen_tasks0 (x0,y0,x1,y1) n res k = if(k=(n-1)) then [] else (Task (k,(x0,y0,x1,y1),n,res))::(gen_tasks0 (x0,y0,x1,y1) n res (k+1)) in gen_tasks0 (x0,y0,x1,y1) n res 0;; let worker t = match t with Task (row,interval,n,res) -> (plot_mandel_row interval n res row);; let show_a_result r = match r with Result(j,col) -> draw_image (make_image [| col |]) 0 j;; type packet = Tpack of task | Rpack of result;; let start = let tasks = ref (gen_tasks (0.704,0.704,0.709,0.709) 500 500) in function () -> match !tasks with (t0::rest) -> (tasks := rest;(Tpack t0)) | [] -> print_string "Finished tasking: hit return to finish";print_newline(); let _ = read_line() in raise End_of_file;; let stop = function r -> match r with Rpack rr -> show_a_result rr | Tpack _ -> raise (Failure "task to collector");; let farmworker = function Tpack t -> (Rpack (worker t)) | _ -> raise (Failure "untask packet to worker");; let stopinitf() = print_string "opening...";print_newline();open_graph " 500x500";; let stopfinalize() = Unix.sleep 30; print_string "finishing... type ENTER to close down"; print_newline(); let _ = read_line() in ();; let mandelexpr () = startstop (start,fun()->()) (stop,stopinitf,stopfinalize) (farm(seq(farmworker),10)) in pardo mandelexpr;; \end{verbatim} } } \nocite{FournetGonthier96_rcham-join-calculus} \bibliographystyle{plain} \bibliography{ocamlbib} \printindex \end{document}