1% BEGIN LICENSE BLOCK 2% Version: CMPL 1.1 3% 4% The contents of this file are subject to the Cisco-style Mozilla Public 5% License Version 1.1 (the "License"); you may not use this file except 6% in compliance with the License. You may obtain a copy of the License 7% at www.eclipse-clp.org/license. 8% 9% Software distributed under the License is distributed on an "AS IS" 10% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See 11% the License for the specific language governing rights and limitations 12% under the License. 13% 14% The Original Code is The ECLiPSe Constraint Logic Programming System. 15% The Initial Developer of the Original Code is Cisco Systems, Inc. 16% Portions created by the Initial Developer are 17% Copyright (C) 1995 - 2006 Cisco Systems, Inc. All Rights Reserved. 18% 19% Contributor(s): 20% 21% END LICENSE BLOCK 22% 23% @(#)umsparallel.tex 1.6 95/07/26 24% 25 26\chapter{Parallel Execution} 27\label{chapparallel} 28 29{\eclipse} implements {\bf Or-Parallelism}. 30\index{parallelism} 31\index{Or-parallelism} 32This means that (on parallel hardware) the alternatives of 33non-deterministic choices can be explored in parallel rather 34than through sequential backtracking. 35 36{\bf Note that this feature is currently not actively supported!} 37 38\section{Using the Parallel System} 39A parallel {\eclipse} session consists of a number of processes that jointly 40execute your program in parallel. They are called {\bf workers}. 41\index{worker} 42On a multi-processor machine, the number of workers should match the 43number of physical processors available on the machine. 44When there are more workers than processors, then several workers 45must share a processor which is slower than having just one worker 46per processor. When there are more processors than workers the 47power of the machine cannot be fully exploited since some processors 48may be left idle. 49Note that {\eclipse} allows you to add and remove workers during program execution. 50 51A parallel session is started as follows: 52\begin{quote}\begin{verbatim} 53% peclipse 54ECRC Common Logic Programming System [sepia opium megalog parallel] 55Version 3.5.0, Copyright ECRC GmbH, Wed Nov 31 10:13 1994 56[eclipse 1]: 57\end{verbatim}\end{quote} 58Parallel {\eclipse} takes the following additional command line options: 59\begin{description} 60\item[--w $<$number of workers$>$] The initial number of workers. 61The default is 1. The space between w and the number is optional. 62%\item[--wh $<$hostname$>$] Start the initial workers on the specified host. 63%By default they are started on the host where peclipse runs. 64\item[--wmi] 65This option pops up an interactive worker manager window which allows 66\index{worker manager} 67you to dynamically control worker configuration during the session. 68\item[--wv] Be verbose while starting up the workers. 69\item[--wx $<$worker executable$>$] 70Use the specified sequential eclipse for the workers rather 71than the default one. 72\end{description} 73Apart from that, parallel {\eclipse} behaves much like the sequential 74version, in particular, all sequential command line options apply. 75 76\section{Parallel Programming Constructs} 77\subsection{Parallel Annotation} 78\index{parallel annotation} 79The basic language construct for parallelising a program is 80the \bipref{parallel/1}{../bips/kernel/compiler/parallel-1.html} annotation, for example 81\begin{quote}\begin{verbatim} 82:- parallel colour/1. 83colour(red). 84colour(green). 85colour(blue). 86\end{verbatim}\end{quote} 87Without the annotation, the system would backtrack sequentially through the 88alternative solutions of colour(X), and X would successively take the values 89red, green and blue. 90When using the parallel annotation, all three solutions are (potentially) 91explored in parallel by different workers, so one worker continues with X=blue, 92another with X=red and a third one with X=green. 93Note that for a parallel predicate 94\begin{itemize} 95\item the order of the clauses is not relevant 96\item there is no programmer control over which worker takes which 97alternative\footnote{this is controlled by an automatic scheduler.}. 98\end{itemize} 99Note that not only is colour/1 executed in parallel, but also the 100resulting alternative continuations, e.g.\ if a program contains 101the sequence 102\begin{quote}\begin{verbatim} 103..., colour(X), work(X), ... 104\end{verbatim}\end{quote} 105then the goals work(red), work(blue) and work(green) will also be executed 106in parallel, as a consequence of the nondeterminism in colour/1. 107 108For many applications, it is enough to add parallel annotations 109to a small number 110of central points in a program in order to achieve parallel speedup. 111 112\subsection{Built-In} 113A parallel primitive that is useful to build upon is \bipref{fork/2}{../bips/kernel/control/fork-2.html}. 114It behaves as if defined by 115\begin{quote}\begin{verbatim} 116:- parallel fork/2. 117fork(N, N). 118... 119fork(N, 2). 120fork(N, 1). 121\end{verbatim}\end{quote} 122i.e.\ a call of {\tt fork(100, X)} generates the numbers between 1 and 100 123in parallel, where the limit does not have to be fixed at compile time. 124 125\subsection{Utility Libraries} 126The library {\tt par_util} (see appendix \ref{chapparutil}) 127\index{parallel utilities} 128contains some predicates that are frequently 129used and are built on top of the above mentioned primitives. 130\bipref{par_member/2}{../bips/lib/par_util/par_member-2.html}, \bipref{par_delete/3}{../bips/lib/par_util/par_delete-3.html}, \bipref{par_between/3}{../bips/lib/par_util/par_between-3.html}, 131\bipref{par_maplist/3}{../bips/lib/par_util/par_maplist-3.html} etc.\ are parallel versions of the corresponding 132sequential predicates. 133It also contains \bip{\&/2} which implements a restricted form of 134AND-parallelism. 135The finite domain solver library library(fd) provides \bipref{par_indomain/1}{../bips/lib/fd/par_indomain-1.html}, 136a parallel version of \bipref{indomain/1}{../bips/lib/fd/indomain-1.html}. 137The finite set solver library(conjunto) provides \bip{par_refine/1}, 138a parallel version of \bipref{refine/1}{../bips/lib/conjunto_fd_sets/refine-1.html}. 139 140The library {\tt elipsys} provides compatibility with the ElipSys system and 141uses the {\tt par_util} library. 142 143\section{Controlling and Analysing the Execution} 144\subsection{Which worker executes this code?} 145Although the parallelism is controlled automatically, 146during program development it is useful to find out how the system 147actually behaves. In the following example we use \bipref{get_flag/2}{../bips/kernel/env/get_flag-2.html} 148to find out which worker finds which solution: 149\begin{quote}\begin{verbatim} 150[eclipse 1]: fork(10,X), get_flag(worker,W). 151 152X = 6 153W = 4 More? (;) 154 155X = 7 156W = 2 More? (;) 157\end{verbatim}\end{quote} 158The solution X=6 has been found on worker 4 and X=7 on worker 2. 159In a parallel session, the number identifying the worker is greater 160or equal to 1, in a sequential session it is 0. 161 162\subsection{Measuring Runtimes} 163Measuring runtimes of parallel executions is especially tricky, 164since the processes involved have their own local timers, e.g.\ for 165measuring cputime. 166The simplest way is to measure true elapsed time instead of cputimes, 167and use an otherwise unloaded machine. 168The primitive that should be used to read the clock is 169\begin{quote}\begin{verbatim} 170statistics(session_time, T) 171\end{verbatim}\end{quote} 172where {\tt T} is the number of seconds elapsed since the start of the parallel 173session. 174 175\subsection{Amount of Parallelism} 176On hardware that provides a high-precision low-overhead timer, 177the predicate \bip{par_statistics/0} from the {\tt par_util} 178library can be used. 179It prints a compact summary information about where the different workers 180spent their time, together with some other data about the parallel execution. 181For example: 182\begin{verbatim} 183[eclipse 7]: par_statistics_reset, queens(10), par_statistics. 184 Wrkr Jobs Prun Published Copy Copied Idling Working Copying Scheduling 185 ID # # cpts alts # bytes ms ms ms ms 186 187 1 24 0 34 34 11 30208 50 7591 10 157 188 2 24 0 16 16 15 29088 147 7638 8 18 189 3 35 0 38 38 18 39656 134 7604 38 35 190 4 30 0 25 25 13 36668 192 7519 34 24 191\end{verbatim} 192 193\subsection{Adding and Removing Workers} 194Workers in a parallel {\eclipse} session can be in one of two states: 195active (awake) or asleep. As one would expect, only active workers 196take part in any computation. A newly created worker's default state 197is active. New workers can be added and the number of active workers 198\index{worker} 199can be altered using the worker manager interface. 200These actions are performed asynchronously, thus the configuration 201can be altered even during parallel execution: a newly added 202worker will join the computation and when a worker is sent to sleep, it 203will stop working at an appropriate point of the execution. 204\index{worker manager} 205Note that the worker manager interface 206be started either using the {\tt -wmi} command-line option or via the 207\bipref{wm_set/2}{../bips/lib/sepia/index.html} builtin. 208 209Worker management is also possible under program control. Use the 210builtins \bipref{wm_get/2}{../bips/lib/sepia/index.html} to inquire about, and \bipref{wm_set/2}{../bips/lib/sepia/index.html} to affect 211the worker configuration. For example, to enquire about the number of 212workers currently active: 213\begin{quote}\begin{verbatim} 214[eclipse 1]: wm_get(workers(Host), Awake+Asleep). 215 216Host = "turing" 217Awake = 2 218Asleep = 1 219yes. 220\end{verbatim}\end{quote} 221 222This means that the there are a total of 3 workers on the machine 223``turing'', out of which 2 are active. In the above example, if one 224wanted to have only one worker active: 225 226\begin{quote}\begin{verbatim} 227[eclipse 2]: wm_set(workers(turing),1), wm_get(workers(turing),Status). 228 229Status = 1 + 2 230yes. 231\end{verbatim}\end{quote} 232 233\section{Parallelism and Side Effects} 234In the current version, all side effect builtins like assert, record, 235setval and the I/O predicates work on resources that are shared 236between the workers and are accessed in a mutually exclusive way. For 237example, when two workers write onto a stream at the same time, the 238access will be sequentialised such that one of them writes first, and 239then the other. The order is unspecified. It is however, expected 240that the internal database builtins (such as assert and retract) will 241not be fully supported in the next major release (which will allow the 242system to execute on distributed memory platforms). 243 244The current version also provides an explicit mutual exclusion primitive 245\bipref{mutex/2}{../bips/kernel/control/mutex-2.html}. It can be used to make a sequence of several goals atomic, 246ie.\ to make sure that the execution of a piece of code is not interleaved 247with the execution of similarly protected code on other workers. 248For example, the following code will make sure that every list is 249printed in one chunk, even when several workers execute different instances 250of atomic_write_list/1 in parallel: 251\begin{quote}\begin{verbatim} 252:- mutex_init(my_lock). 253atomic_write_list(List) :- 254 mutex(my_lock, write_list(List)). 255write_list([]) :- nl. 256write_list([X|Xs]) :- writeln(X), write_list(Xs). 257\end{verbatim}\end{quote} 258 259\section{Parallel Cuts} 260\index{cut!parallel} 261The semantics of cut follows the philosophy that the order of clauses in 262a parallel predicate is not relevant. E.g.\ a predicate like 263\begin{quote}\begin{verbatim} 264:- parallel p/0. 265p :- writeln(a). 266p :- !, writeln(b). 267p :- !, writeln(c). 268\end{verbatim}\end{quote} 269may print 'a' and 'b', 'a' and 'c', only 'b' or only 'c'. 270It depends on which cut is executed first, 271and whether it is executed before or after 'a' has been printed. 272 273\section{Restrictions} 274 275Some features of sequential {\eclipse} are not fully 276supported or make no sense in the parallel version. These include: 277\begin{itemize} 278 279\item The Debugger: The prolog debugger cannot be used to trace parallel 280sessions i.e. programs in which more than one worker is active. 281\index{debugger!parallel} 282 283\item File queries: When a compiled file contains queries (i.e.\ lines of 284the form \verb/:- <goal>./ or \verb/?- <goal>./, then these goals will not 285be executed in parallel. To start a parallel computation, either start 286it from the toplevel, or use the -e command line option. 287 288\item Dynamic predicates can currently not be declared parallel. 289 290\item Dynamic loading: This feature is not currently available in 291the parallel version, but should be available in subsequent releases. 292 293\item Unix process related primitives: Currently most primitives such as 294socket, accept, listen, exec, wait which depend on private data 295structures created by the operating system are not fully 296supported. For example, it is currently up to the user to guarantee 297that some operations on a socket (such as \bipref{accept/3}{../bips/kernel/iostream/accept-3.html}) are only performed 298on the worker on which the socket in question was created. In future 299releases most of these restrictions will be removed, however, it is 300likely that some complex builtins (e.g. \bipref{select/3}{../bips/kernel/obsolete/select-3.html}) will not be completely 301supported. 302 303%\item Execution saved states: This feature will not be supported for the 304%\index{saved states} 305%parallel version since it is difficult to guarantee that identical 306%resources will be available on restarting the system. Program saved states, 307%however, can be created. 308 309\item Timing statistics: The values returned by the \bip{statistics(times,_)} 310builtin do not make sense in a parallel session, since they only refer 311to timers local to the worker on which the call is executed. As noted 312earlier, elapsed time for a parallel session should be measured using 313the {\tt statistics(session_time,Time)} builtin. It is envisaged that the the 314\bipref{wm_get/2}{../bips/lib/sepia/index.html} builtin will be expanded in the future in order to allow 315the user to query total cpu usage of all active workers. 316 317\end{itemize} 318%\begin{itemize} 319%\item Execution saved states 320%\item Dynamic loading on some machines 321%\item Process communication primitives (sockets) 322%\item Unix process related primitives (exec/3, select/3) 323%\item Signal handling 324%\item CPU times 325%\end{itemize} 326 327\section{Troubleshooting} 328\subsection{No Space} 329When the system complains about lack of swap space, then it is likely 330that there is no space in your /tmp filesystem. In this case set 331the environment variable ECLIPSETMP to a directory that has enough space 332\index{ECLIPSETMP} 333to hold the temporary files that the system uses at runtime. 334It is recommended to use a different directory for different hosts, 335e.g. 336\begin{quote}\begin{verbatim} 337setenv ECLIPSETMP ~/tmp/`hostname` 338\end{verbatim}\end{quote} 339 340\subsection{Process structure} 341A parallel {\eclipse} session consists of 342\begin{itemize} 343\item The worker manager process {\tt peclipse}. 344\index{worker manager} 345This is usually the parent process of the whole parallel session. 346Its process id is used to identify a parallel session. 347All temporary files belonging to a parallel session contain this 348process id in their name. 349\item A number of worker processes {\tt eclipse.exec}. 350\index{worker} 351They are normal sequential {\eclipse} processes that do the actual 352work in parallel. 353\item A {\bf name server} process {\tt nsrv}. 354\index{nsrv} 355\index{name server} 356The name server is a support process and is not really part of a 357parallel {\eclipse} session. 358A name server process is launched when 359a parallel session is started on a machine for the first time. 360It stays in existence even after the session is finished and is reused 361by concurrent or future parallel sessions on the same machine. 362The name server puts some data files into the \$ECLIPSETMP (or /tmp) 363directory. Their names start with {\tt nsrv}. 364\end{itemize} 365 366\subsection{Crash recovery} 367After a machine crash or after an abnormal termination of a parallel 368session, it may be necessary to kill some processes and to remove files 369in the temporary directory 370(if ECLIPSETMP is not set, this defaults to /tmp): 371\begin{enumerate} 372\item When you still have a worker manager window, try exiting using 373the {\bf EXIT} button. If that does not help: 374\item Kill the peclipse process and then any remaining workers 375(eclipse.exec). This will most likely require a hard kill (-9). 376\item Remove temporary 377files \$ECLIPSETMP/session_id.*.map where session_id 378is the process number of the peclipse process. 379\end{enumerate} 380If it is not possible to restart a parallel session after this cleanup, 381then the name server may be corrupted as well. In this case: 382\begin{enumerate} 383\item Kill the nsrv process. Use kill -9 only if the process does not go away 384after a soft kill. 385\item Remove \$ECLIPSETMP/nsrv* if these files still exist. 386\end{enumerate} 387