Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!usc!ucsd!ucsdhub!hp-sdd!ncr-sd!ncrcae!hubcap!tillamook!mohamed
From: tillamook!mohamed@uunet.UU.NET (Moataz Mohamed)
Newsgroups: comp.parallel
Subject: Re: Thesis for sale
Keywords: Prolog, AND-parallel, Transputer
Message-ID: <7285@hubcap.clemson.edu>
Date: 1 Dec 89 21:13:50 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 78
Approved: parallel@hubcap.clemson.edu

hansteb@cs.vu.nl (Tebra Hans) writes:

>At November 21, I defended my thesis, titled

>	"Optimistic AND-parallelism in Prolog"

>(and I did succeed :-))

Congratulations, hope I join the club (before the end of next decade ;-> )

[stuff about obtaininig copies deleted]

>SUMMARY OF THE THESIS

[lot's of stuff deleted]

>In this thesis, a new method for parallel execution of the logic
>programming language Prolog is presented.  In addition to a detailed
>discussion of algorithms, a realistic implementation of the method is
>given.  The thesis concludes with an observation of the strong and weak
>points of the method.

>Chapter 3 covers the methods of obtaining faster execution by means of
>parallel methods.  The main categories are AND and OR parallelism.
>They are orthogonal, i.e. each of the methods can be implemented
>without concern of the details of the other method.

True, but this does not mean that having both categories can't be faster
than either one alone!

>The optimistic method is specified in terms of "solver" processes,
>operating in an abstract machine.  New versions of the resolution and
>unification algorithms illustrate the differences with respect of the
>sequential implementation of chapter 2.  Large programs cause a large
>number of solvers to be generated.  To control the resources of the
>abstract machine, the method must be fitted with a utility to perform
>reorganisations at intervals.

My guess is that the comlexity of doing this reorganization
is incredibly costly. You seem to be assuming that there is a central
process responsible for monitoring the system state and deciding
when to reorganize. The usual arguments about reliability and the
cost of collecting dynamic system state information apply here.

>Chapter 7 presents a realistic implementation of the abstract machine
>of chapter 5.  The architecture of the system must be scalable, to
>obtain a further improvement of the processing capability if components
>are added.  The Transputer has been selected as the key component of a
>grid structure. 

Do you have toroidal edges or is it a flat mesh!?

> The properties of this MIMD-system have been used to
>build a simulator program to investigate performance in terms of
>elapsed time, allocation of processes, overloading of processors and
>uncontrolled growth of the process load in parts of the system.

How are you dealing with the process allocation problem? The consesus 
is that random placement works as well as sophisiticated algorithms that 
collect a lot of system state inofrmataion. According to my knowledge, there
hasn't been much work on addressing the problem in logic programming systems.
Many systems use off the shelf allocation algorithms such as the
pressure gradient method. However, I'm working on an algorithm that 
while employing randomness still utilizes communication characteristics of the
processes in the AND/OR [Conery's] model. 


..Moataz Mohamed

mohamed@cs.uoregon.edu

CIS Dept.,
Univ. of Oregon
Eugen, OR 97403

===========================================================================
I don't have time to construct a fancy signature! :-((
===========================================================================


Brought to you by Super Global Mega Corp .com