pushing parallel and constraint programming
Alan Baljeu
in practical programming. What happens if we eliminate those (var, !,
setarg, etc.), but include
* constraint programming (eg. CLP(FD)), add whatever else you need,
* constraints to enforce typing (O'Keefe style type constraints),
and
* or-parallel processing. Given A ; B, run both simultaneously for
true non-determinism, but suspend any disjunct when the other
succeeds.
How expressive is the language? What of current Prolog would become
hard? What would become inefficient?
To what extent can we achieve modeless programs? Meaning f(A, B)
works equally well with (+,-) as (-, +)
Jan Burse
> * or-parallel processing. Given A ; B, run both simultaneously for
> true non-determinism, but suspend any disjunct when the other
> succeeds.
Oho, I believe this ain't working. What if you ask ((A ; B), C),
that A succeeds does not allow you to cancel B, since (A, C) might
fail, so that finally (B, C) will only succeed.
>
> How expressive is the language? What of current Prolog would become
> hard? What would become inefficient?
See below, breadth first is more memory intensive.
>
> To what extent can we achieve modeless programs? Meaning f(A, B)
> works equally well with (+,-) as (-, +)
Modes, well, there is problem that current depth first search
of Prolog is incomplete. So using breadth first broadens
the solution space.
But only if you don't use negation, with negation things
get a little bit more complicated, at least classically, since
there might be floundering.
Bye
Alan Baljeu
On Dec 17, 3:05 pm, Jan Burse <janbu...@fastmail.fm> wrote:
> Oho, I believe this ain't working. What if you ask ((A ; B), C),
> that A succeeds does not allow you to cancel B, since (A, C) might
> fail, so that finally (B, C) will only succeed.
Okay we need to be more careful about this. Is there any
known reasonable approach?
> But only if you don't use negation, with negation things
> get a little bit more complicated, at least classically, since
> there might be floundering.
>
Constraint-based negation perhaps?
Paulo Moura
> ...
> * or-parallel processing. Given A ; B, run both simultaneously for
> true non-determinism, but suspend any disjunct when the other
> succeeds.
Not exactly what you describe but you may want to take a look at
Logtalk support for competitive or-parallelism:
http://logtalk.org/manuals/refman/builtins/threaded1.html
http://logtalk.org/manuals/userman/threads.html#threads_threaded
Cheers,
Paulo
Jan Burse
> Thanks for the response, Jan.
> On Dec 17, 3:05 pm, Jan Burse <janbu...@fastmail.fm> wrote:
>> Oho, I believe this ain't working. What if you ask ((A ; B), C),
>> that A succeeds does not allow you to cancel B, since (A, C) might
>> fail, so that finally (B, C) will only succeed.
>
> Okay we need to be more careful about this. Is there any
> known reasonable approach?
Well if A generates solutions A1, A2. You can feed them
in parallel to B, and thus generating the solutions for
(A, B). But when you are interested in \+ \+ (A, B) (i.e.
not in alls solutions, only whether it succeeds at least
once), then proceeding as just described, you might use
more machine load with multiple processors than
with a single processor.
>> But only if you don't use negation, with negation things
>> get a little bit more complicated, at least classically, since
>> there might be floundering.
>>
> Constraint-based negation perhaps?
Yes and no. Constraints based on a domain and some relations
such as equality or order do not help much, since dealing
with negation in the presence of predicates is most useful
when there is also some handling of quantifiers. BTW,
\+ \+ can be also viewed as a quantifier.
Bye
Alan Baljeu
Of course, \+ Goal should have a dedicated implementation that kills
all "threads" as soon as one solution is found. Seems to me it's not
a problem then.
bart demoen
I am fine with the community returning to parallellism (although I think
that certain approaches are doomed to fail), but instead of reinventing
most of what was done 10 and 20 years ago - and is still active in
systems like Ciao - about and- and or-parallellism ... maybe people should
have a look at this old literature ?
Cheers
Bart Demoen
Paulo Moura
That's how the Logtalk implementation of and-parallelism works (see
the links in my previous post). You can find some examples here:
http://svn.logtalk.org/viewvc.cgi/trunk/examples/threads/
Cheers,
Paulo
Alan Baljeu
I think the world is finally ready for commonplace parallel computing,
for two reasons: internet-based computational servers, and multicore
computers (because Intel gave up trying to grow single cores any
faster). That's why I'm trying to understand what Prolog can do with
it.
When I started this thread, I was hoping someone would direct me to
some practical literature. I had a feeling things like parlog were
obsolete, and better stuff was out there, but I don't know where to
look.
bart demoen
> I think the world is finally ready for commonplace parallel computing,
> for two reasons: internet-based computational servers, and multicore
> computers (because Intel gave up trying to grow single cores any
> faster).
Basically the same argument was heard in the 80s and lots of
people/groups/systems have given it a shot. Very little of that survived.
> When I started this thread, I was hoping someone would direct me to some
> practical literature. I had a feeling things like parlog were obsolete,
> and better stuff was out there, but I don't know where to look.
Parlog might be obsolete in the sense that there is no full fledged system
(anymore - or perhaps there never was), but it is still worth looking into.
Also Concurrent Prolog (Shapiro), Aurora, Andorra, KL1, KLIC, &-Prolog ...
Have a look at (in)dependent and-// (Ciao) and what Yap offers parallel-wise.
Recently, also Mercury goes up the //-path.
<my 2cents>
Prolog was always advertised as a language with "natural"
parallelism. But this is actually not true: Horn-clause logic has natural
parallelism, but if one wants to respect the depth-first, left-to-right
procedural semantics (that is Prolog) and things like order of side-effects
and pruning operators, it becomes damn difficult to parallelize. The number of
papers (and the difficulty implementing them) on the cut issue alone might
give an idea that making Prolog parallel has little chance to succeed.
Not to say that all attempts to introduce into Prolog explicit parallel
constructs (for multi-threading) are doomed. The essence of those attempts is
that they change the semantics - by introducing new built-ins or by tampering
with the old ones (especially the control constructs). And that's fine. It
follows a different philosophy from trying to automatically parallelize Prolog.
Have a look at Oz/Mozart as well (I know it is full of good ideas, but I don't
know it enough to tell you why you need to look at it - just recommending
it :-).
</my 2cents>
Cheers
Bart Demoen
fodor
> practical literature. I had a feeling things like parlog were obsolete,
> and better stuff was out there, but I don't know where to look.
Hi, I know that there are many people more qualified than me to give
you some advices, but I can still provide some links for you.
First off all there is a huge amount of work about parallelism in
logic programming. As Bart said in his previous post there are
multiple ways to pursue parallelism in logic programming: and or-
parallelism, modified WAMs, multi-threading, etc. I think there
something about everything published, a lot of code is available,
research and industrial systems, and still much more to do.
Considering your previous posts, I guess you might want to start with
reading the paper:
G. Gupta, K. A. M. Ali, M. Carlsson, and M. V. Hermenegildo. Parallel
execution of prolog programs: A survey. In ACM Transactions on
Programming Languages and Systems, 1995.
It’s also a nice history and gives you a start to parallel Prolog
implementations and how the Warren State Machine was modified to
support parallelism (copying of environments or binding arrays).
I think that from the old systems the most representative were: Muse
and Aurora and there are still a lot of papers available online about
them. I can enumerate a few if you want to read them or search for
other papers by the same authors (the ones bellow are still available
online and I can send you the links if you cannot find them):
K. A. M. Ali and R. Karlsson. The muse aproach to or-paralel prolog.
In International Journal of Parallel Programming, 1994.
E. Lusk, R. Butler, T. Disz, R. Olson, R. Overbeek, R. Stevens,
D.H.Warren, A. Calderwood, P. Szeredi, S. Haridi, P. Brand,
M.Carlsson, A. Ciepielewski, and B. Hausman. The aurora or-parallel
prolog system. In New Generation Computing, 7(2-3), 243 - 271, 1990.
Solving optimization problems in the Aurora Or-parallel Prolog system,
Peter Szeredi
Interfacing Engines and Schedulers in Or-Paralel Prolog Systems, Peter
Szeredi,Rong Yang, Mats Carlsson
The sources for the Aurora system are still available online:
http://www.sics.se/isl/aurora.html
Most of its features were implemented in YapOr and might be still
working (still present in the sources of Yap Prolog):
R. Rocha, F. Silva, V. S. Costa, and R. R. Fern. Yapor: an or-parallel
prolog system based on environment copying. In Progress in Artificial
Intelligence, 1999.
There is the other direction that Jan, Paulo, and Bart mentioned in
their posts: multi-threading. A lot of Prolog systems have
implementations of multi-threading: Swi, Yap, XSB, Mercury, and you
can just read their manuals.
If you are interested to preserve the model theory, you should be
looking at parallelism of various logic programming paradigms: well
founded and answer-sets semantics.
J. Freire, R. Hu, T. Swift, and D. S. Warren. Parallelizing tabled
evaluation. 7th International PLILP Symposium, pages 115–132. Springer-
Verlag, 1995.
Rui Marques, Terrance Swift, Concurrent and Local Evaluation of Normal
Programs, Theoretical Computer Science, 2008.
R. Rocha, F. Silva, and V. S. Costa. On applying or-parallelism and
tabling to logic programs. Theory and Practice of Logic Programming, 4
(6), 2004.
The bottom-up industrial system OntoBroker (using the well-founded
semantics) computes the well-founded model on multi-core processors
(and, from my experience, it’s quite good).
If you are interested in parallelism in the answer set semantics, look
for the papers by Enrico Pontelli, Gupta, etc.
There are papers about parallelism every year in ICLP and there is
also a workshop every year called DAMP (Declarative Aspects of Multi-
Core Programming).
I hope you can find something helpful above.
Paul.
Alan Baljeu
On Dec 19, 8:04 am, bart demoen <b...@cs.kuleuven.be> wrote:
> On Fri, 18 Dec 2009 15:04:18 -0800, Alan Baljeu wrote:
> > I think the world is finally ready for commonplace parallel computing,
>
> Basically the same argument was heard in the 80s and lots of
> people/groups/systems have given it a shot. Very little of that survived.
In the 80s I didn't have a parallel computer. Nor the 90s, nor the
0s.
But I do now.
> <my 2cents>
> Prolog was always advertised as a language with "natural"
> parallelism. But this is actually not true: Horn-clause logic has natural
> parallelism, but if one wants to respect the depth-first, left-to-right
> procedural semantics (that is Prolog) and things like order of side-effects
> and pruning operators, it becomes damn difficult to parallelize. The number of
> papers (and the difficulty implementing them) on the cut issue alone might
> give an idea that making Prolog parallel has little chance to succeed.
Right. Thus this thread started by asking to parallelize pure prolog
with constraints. Maybe that means call_parallel(Goal) where Goal is
expected
to satisfy don't-care non-determinism. So where do I look for ideas
about this?
I'm off to see the references already given, thanks.
fodor
> Thus this thread started by asking to parallelize pure prolog
> with constraints. Maybe that means call_parallel(Goal) where Goal is
> expected to satisfy don't-care non-determinism.
> So where do I look for ideas about this?
Maybe you should look into deductive databases (Datalog) where the
program execution is independent of the order or rules and facts, but
you don't have special predicates (such as the cut) to influence the
procedural evaluation of the program. You can read more about
deductive databases, definite programs, non-monotonic logics, logic
programming model theories (well-founded and answer-set semantics),
negations, etc. There are also a set of systems available (dlv,
OntoBroker, smodels, etc.) and there are also Prolog systems that are
hybrids between Prolog and deductive databases Prolog (XSB, Yap) which
use tabling (memoization) to compute the well-founded model of the
program in a top-down fashion. In my previous post, I mentioned that
there are a few works for parallelism for these deductive database
systems. For instance, there are a lot of papers by the XSB developers
on computing the well-founded model when multi-threading is employed
in XSB prolog. The OntoBroker also allows computation on a multi-core
processor (and it's quite good at it because we tested this parallel
version in our OpenRuleBench benchmark suite and it does speed up the
execution about 15% per CPU (not much, but it's a fine)).
I find your idea interesting (parallelism+constraints), but I must
admit that I don't think the technology is there yet. I don't know
anything about constraints in deductive databases and I think that
they don't really make sense in bottom-up computations because the
answers should also carry some constraint information). However, I am
aware only of a single set of work that employed tabling and
constraints done by Tom Schrijvers, Bart Demoen (who replied to your
posts) and David S. Warren, TCHR: a framework for tabled CLP. If I
would work on parallelism+constraints, I think that I would start with
parallelism of tabled computations (XSB and Yap) and then exploit the
idea of tabling in TCHR. I hope this helps to put your thoughts in
order.
Paul.
A.L.
<alanb...@gmail.com> wrote:
>First, thanks to everyone for the leads. They will keep me busy.
>
>On Dec 19, 8:04�am, bart demoen <b...@cs.kuleuven.be> wrote:
>> On Fri, 18 Dec 2009 15:04:18 -0800, Alan Baljeu wrote:
>> > I think the world is finally ready for commonplace parallel computing,
>>
>> Basically the same argument was heard in the 80s and lots of
>> people/groups/systems have given it a shot. Very little of that survived.
>
>In the 80s I didn't have a parallel computer. Nor the 90s, nor the
>0s.
>But I do now.
You think that multicore processor is "parallel computer"?... No, it
is not
A.L.
fodor
Hi A.L.,
Alan means "thread level parallelism" (task parallelism with shared
memory) on multicore processors. This is already exploited by threads
for explicit parallelism (as everyone said in their posts (Paulo)).
However, from Alan's posts I know he means some kind of "implicit
parallelism". I think that in some posts he means or-parallelism,
while in other posts he means and-parallelism.
I must also agree with you that in many cases multi-core processors
are definitely not good enough for very large problems. Any possible
gains are limited by the number of cores (usually, a very small number
- I have a dual-core, but I don't think I can afford anything with
more cores) and the main memory of the system.
For instance, for the Billion Triple Challenge at the International
Semantic Web Conference, no multi-core system and Prolog system can
compute queries or even load the data. In these cases one needs to
find some kind of data parallelism and distribute the computation in a
network or a cluster. I've seen two papers doing this (btw, these are
not logic programming, but description logics; however, I think many
people would agree that these very close to logic programming with
some differences (close vs. open world, etc.); you can see that both
papers are computing a transitive closure on their data):
Jacopo Urbani, Spyros Kotoulas, Eyal Oren, Frank van Harmelen,
Scalable Distributed Reasoning using MapReduce, ISWC 2009.
Jesse Weaver, James Hendler, Parallel Materialization of the Finite
RDFS Closure for Hundreds of Millions of Triples, ISWC 2009.
However, I also worked on a Prolog project where multi-core processors
were really required for an acceptable speed. The Watson question
answering system that IBM is working on to challenge a Jeopardy
champion is using Prolog modules for some of its question analysis NLP
tasks. They have to have response times comparable with the human
competitor, so the speed is very important in their case. Their entire
UIMA architecture is using multi-threading (it's like a workflow where
multiple tasks are computed in parallel). I've also seen it working as
a pipeline where different processors were executing different steps
in the analysis and annotation.
I also think that pipelining for data-streams is also a very good
application for multi-threading.
Finally, the point is that there are many kinds of parallelism and I'm
sure they are all great for some tasks.
Sometimes it also looks to me (as it does for Bart in his posts) that
implicit parallelism in logic programming is not a quite fruitful
research area or industry direction, but I think that it's quite
necessary for some tasks where one has either a very complex and time
consuming program or a huge amount of data.
There are plenty of directions of research, so there is a place for
everyone.
Paul.
Jan Burse
> On Dec 21, 1:22 pm, Alan Baljeu <alanbal...@gmail.com> wrote:
>> Thus this thread started by asking to parallelize pure prolog
>> with constraints. Maybe that means call_parallel(Goal) where Goal is
>> expected to satisfy don't-care non-determinism.
>> So where do I look for ideas about this?
>
> Maybe you should look into deductive databases (Datalog) where the
> program execution is independent of the order or rules and facts, but
> you don't have special predicates (such as the cut) to influence the
> procedural evaluation of the program. You can read more about
> deductive databases, definite programs, non-monotonic logics, logic
> programming model theories (well-founded and answer-set semantics),
> negations, etc.
In the end, it often delivers less than any SQL query optimizer
can do. Well you might have tabling for a predicate. But what
happens in between the predicates? Normal backtracking? Then you
would need at least indexing on one of the tabled predicates.
But the core speed up in database queries happens by reordering
joins. And most of the databases can do this now quite cleverly
in that you don't have to give them hints via explicitly defining
indexes, they just collect statistics over your past queries.
Interestingly the join re-odering is computationally intensive.
Its an optimization problem in itself, when I remember well.
But from the view point of expressive adequateness for some
problems, I don't like datalog. What you call well-funded and
answer-set semantics, usually also poses severe restrictions on
the rule bodies and heads. The program has to be stratified, the
rules have to be range restricted. So I would rather prefer a
marriage of constraints and DB technology than just datalog.
Bye
fodor
> can do.
> Well you might have tabling for a predicate. But what
> happens in between the predicates? Normal backtracking? Then you
> would need at least indexing on one of the tabled predicates.
> But the core speed up in database queries happens by reordering
> joins. And most of the databases can do this now quite cleverly
> in that you don't have to give them hints via explicitly defining
> indexes, they just collect statistics over your past queries.
Yes, I agree with you that join re-ordering using histograms and other
statistics is very important and that relational database query
optimizers excel doing it. Some Datalog systems are also doing it
(OntoBroker, dlv), but not to the extent of relational DBs. Automatic
indexes are simpler tasks, so some Prolog systems also have algorithms
or data structures for making some kind of automatic indexing or
complex indexing (Yap has dynamic indexing, XSB has tries (internal
and for tabled predicates), etc.) Bottom-up datalog systems also have
their own query optimization techniques: magic sets, static and
dynamic filtering, etc.
> But from the view point of expressive adequateness for some
> problems, I don't like datalog. What you call well-funded and
> answer-set semantics, usually also poses severe restrictions on
> the rule bodies and heads. The program has to be stratified, the
> rules have to be range restricted. So I would rather prefer a
> marriage of constraints and DB technology than just datalog.
Personally, I like very much both traditional databases (relational
algebra, SQL) and logic programming. I just think that various
problems have different requirements which might fit one theory better
than another, and that relational algebra and logic programming are
just different theories with various affinities for different people.
I guess that some people interested in practical problems like
relational algebra more than LP because of its set based operands and
query optimizations, while other people like having rules better. In
fact, relational algebra is actually a subset of Datalog without
recursion and negation, so it's just a matter of what one feels it's
better suited for his or her problems.
Jan Wielemaker
> On Dec 22, 8:49�am, A.L. <alewa...@aol.com> wrote:
>> On Mon, 21 Dec 2009 10:22:12 -0800 (PST), Alan Baljeu
>> <alanbal...@gmail.com> wrote:
>> >In the 80s I didn't have a parallel computer. �Nor the 90s, nor the
>> >0s. But I do now.
>>
>> You think that multicore processor is "parallel computer"?... No, it
>> is not
>> A.L.
>
> Hi A.L.,
> Alan means "thread level parallelism" (task parallelism with shared
> memory) on multicore processors. This is already exploited by threads
> for explicit parallelism (as everyone said in their posts (Paulo)).
> However, from Alan's posts I know he means some kind of "implicit
> parallelism". I think that in some posts he means or-parallelism,
> while in other posts he means and-parallelism.
>
> I must also agree with you that in many cases multi-core processors
> are definitely not good enough for very large problems. Any possible
> gains are limited by the number of cores (usually, a very small number
> - I have a dual-core, but I don't think I can afford anything with
> more cores) and the main memory of the system.
>
> For instance, for the Billion Triple Challenge at the International
> Semantic Web Conference, no multi-core system and Prolog system can
> compute queries or even load the data. In these cases one needs to
For the exact 1 billion, that is actually not the case. SWI-Prolog's libs can
load approx 300 million on a 64Gb machine (that is really cheap now; 128Mb is
getting affortable, so that means 600 million). SWI-Prolog's RDF DB however
is read/write. As we have seen in the same ISWC, there was a Swiss student
that managed to put a few 100 million triples on an iPhone. That was using
a dedicated read-only representation, but her ideas make it easy to load
a few billion triples in memory (read-only).
Of course, I won't deny that web-scale asks for distribution ... Just stating
that you can do a bit more in-core than some popular in-core stores suggest :-)
Cheers --- Jan
Jan Burse
> Yes, I agree with you that join re-ordering using histograms and other
> statistics is very important and that relational database query
> optimizers excel doing it. Some Datalog systems are also doing it
> (OntoBroker, dlv), but not to the extent of relational DBs. Automatic
> indexes are simpler tasks, so some Prolog systems also have algorithms
> or data structures for making some kind of automatic indexing or
> complex indexing (Yap has dynamic indexing, XSB has tries (internal
> and for tabled predicates), etc.) Bottom-up datalog systems also have
> their own query optimization techniques: magic sets, static and
> dynamic filtering, etc.
Thank you for the informative summary about some
advanced features of existing systems. Hopefully I
have soon some time on my hands to have a look
at these. ;-)
Bye