Independent and-parallel execution

Author(s): Manuel Carro, Manuel Hermenegildo.

Version: 1.11#222 (2004/5/24, 13:8:7 CEST)

Version of last change: 1.7#160 (2001/11/27, 12:35:53 CET)

Note: This is just a partial first shot. The real library still needs to be written. Not difficult, just no time...

This library will eventually allow and-parallel execution of goals in (Herbrand-)independent fashion. It resembles the execution rules of &-Prolog [HG90]. Basically, goals are run in and-parallel provided that their arguments do not share bindings, i.e., are not bound to terms which contain a common variable.

• Usage and interface (andprolog)
• Documentation on internals (andprolog)
• Known bugs and planned improvements (andprolog)

Usage and interface (andprolog)

Documentation on internals (andprolog)

PREDICATE: @&/2:

@&(GoalA, GoalB)

GoalA and GoalB are run in independent and-parallel fashion. This is just a first sketch, and valid only for deterministic independent goals. The use is as

q:- a & b.

which would start a and b in separate threads (possibly in parallalel, if the machine architecture and operating system allows that), and continue when both have finished. This type of execution is safe only when a and b are independent in the sense of variable sharing. This condition can be tested with the indep/2 predicate.

PREDICATE: active_agents/1:

active_agents(NumberOfAgents)

Tests/sets the NumberOfAgents which are active looking for goals to execute. As for now, those agents are resource-consuming, even when they are just looking for work, and not executing any user goals.

PREDICATE: indep/2:

indep(X, Y)

X and Y are independent, i.e., they are bound to terms which have no variables in common. For example, indep(X,Y) holds for X=f(Z),Y=g(K) and also for X=f(a),Y=X (since both X and Y are bound to ground terms). It does not hold for X=f(Z),Y=g(Z) and for X=Y.

PREDICATE: indep/1:

indep(X)

X is a list of lists of length two, i.e., a list of the form [[T1, T2], [T3, T4], ...]. The variables in each pair of the list X are tested for independence using indep/2. This list-of-pairs format is the output of several independdnce analyzers for pair sharing.

Known bugs and planned improvements (andprolog)

• Beware: the current code is just a partial first shot. It is provided for the sole purpose of experimentation and development.
• The fact that only the first solution is returned for the conjunction is due to performance issues (and lack of time), and we expect to remove it in a near future.
• CGEs (i.e., =>) are not supported.
• The indep/1, indep/2, and ground/1 tests are not very efficient; they will be replaced by native versions (taken from the &-Prolog code) in the future.

Go to the first, previous, next, last section, table of contents.