Download SICStus Prolog User's Manual

Chapter 3: Running Prolog in Parallel
43
3.3 Main Issues of Parallel Execution
3.3.1 The Muse Model
The Muse model assumes a multiprocessor system with a number of processors or processes, called
workers, with identical local address spaces, and some global address space shared by all workers.
We use the term worker to represent a process or processor. The Muse model implements each
worker as a sequential Prolog engine with its own WAM stacks in private memory. The Prolog
program is stored in shared memory.
During execution, the actual work is to explore a search tree implicitly dened by the Prolog
program. The available work is represented as choicepoints containing outstanding execution alternatives on one of the WAM stacks.
The work is performed concurrently by the workers. A distributed scheduler is responsible for
dynamic load balancing of available work among available workers. Workers try to maximize the
time they spend working and minimize the time they spend scheduling. When a worker is working,
it adopts a depth-rst left-to-right search strategy.
In the Muse model each worker keeps its own WAM stacks to avoid conicting variable bindings
in common parts of the search tree. Whenever a worker runs Prolog it therefore can use (more
or less) the same machinery as the sequential SICStus Prolog implementation. The exceptions
are (1) bookkeeping of local work each time a choicepoint is created, (2) testing for signals at
predicate calls, and (3) synchronizing with other workers when taking work from a shared (public)
choicepoint. The overhead for doing this is some few percent making Muse (nearly) as ecient as
sequential SICStus Prolog.
When a worker (Q) runs out of work it must interrupt some busy worker (P) to get work. All of P's
private choicepoints are then made public and the dierence between P's and Q's state is copied
from P to Q. Q can then simply simulate failure to backtrack for work.
3.3.2 Scheduling
The two main functions of the scheduler are to maintain the sequential semantics of Prolog and to
match idle workers with the available work with minimal overhead. The sources of overhead in the
Muse model include (1) copying a part of worker state, (2) making local choicepoints sharable, and
(3) grabbing a piece of work (a task) from a shared choicepoint. Other important scheduling issues
are to maximize the grain size of computations, and to prefer \promising" work over less promising
work (see Section 3.3.3 [Muse Exe Cut], page 44).