kale@m.cs.uiuc.edu (05/07/89)
Regarding "Linda in Context" article in CACM's April '89 issue:
I find the classification as used by Carrierro and Gelernter
somewhat incomplete:
If (1) Concurrent objects, (2) Concurrent Logic Programming (CLP)
and (3) Functional Programming
are meant to include all approaches to parallel programming,
then where does parallel execution of Logic Programs fit?
I hope readers of this group agree that CLP is not the same.
CLP is an (explicitly) parallel programming language,
with specific relationships with
Logic Programming languages (such as pure Prolog).
The Logic programming languages are different than (flat) CLP
because of don't know non-determinism, for one thing.
CLP is different in scope. It is characterized by tail recursive
predicates (processes) communicating via partially instantiated
logical variables (streams).
There are many research groups working on OR parallelism
(SICS, D.H.D. Warren, Argonne, Tinker-Lindstrom, ...),
on AND parallelism (DeGroot, Hermenegildo, Kumar, ...)
and on combining AND and OR parallelism (Conery, ECRC-Pepsys, Kale, Prism, ..)
for pure Logic Programs. So, it is not just a hypothetical class.
Let us see which arguments they gave will apply against this approach.
The Logic programming approach subsumes (or at least overlaps with)
the Functional programming approach they discuss.
One may argue about whether Functional/Logic programming approach
is applicable in specific domains.
However, in their "conclusions" section, they state that even for those
problems that do have elegant functional [or Logic language] solution,
they would not want to use such languages,
because such systems rely on a static analysis / runtime system ("auto-pilot")
which does not perform very efficiently, and it will be difficult to design
a "high performance auto-pilot".
This argument assumes that `blind' static analysis is the only way to
influence performance in such systems.
One can use simple annotations to surmount the problems.
In particular, we use granularity annotations (to specify when to
switch to sequential execution), and data dependence annotations
to achieve a fairly efficient parallel execution of Logic programs
on shared as well as non-shared memory machines
(AND and OR parallel, with interactions between them handled effectively).
Others have also used similar/different mechanisms to achieve efficient
parallel execution on parallel machines.
Such annotations are quite non invasive.
One can write a regular logic program, and then decide
(1) what partial order to impose on the literals of a clause.
(2) what grainsizes are appropriate and
Both the steps may eventually be carried out by a static analysis system;
but irrespective of that, it is clear that a method exists for
efficient parallel execution of Logic/Functional programs.
- L.V. Kale (kale@cs.uiuc.edu)
Dept. of Computer Science,
University of Illinois at Urbana Champaign
1304 W. Springfield Ave. Urbana, IL-61801
(217) 244-0094shankar@pompeii.SRC.Honeywell.COM (Son of Knuth) (05/16/89)
In article <5500014@m.cs.uiuc.edu> kale@m.cs.uiuc.edu writes:
#There are many research groups working on OR parallelism
#(SICS, D.H.D. Warren, Argonne, Tinker-Lindstrom, ...),
#on AND parallelism (DeGroot, Hermenegildo, Kumar, ...)
#and on combining AND and OR parallelism (Conery, ECRC-Pepsys, Kale, Prism, ..)
#for pure Logic Programs.
I was just wondering what the major problems and issues are as far
as combining AND and OR parallelism are?
---
Subash Shankar Honeywell Systems & Research Center
voice: (612) 782 7558 US Snail: 3660 Technology Dr., Minneapolis, MN 55418
shankar@src.honeywell.com srcsip!shankar