Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!usc!ucsd!pacbell.com!att!emory!hubcap!schmolze%cs.tufts.edu From: schmolze%cs.tufts.edu@RELAY.CS.NET Newsgroups: comp.parallel Subject: Re: Research for RETE-based systems on Intel hypercube Message-ID: <12554@hubcap.clemson.edu> Date: 9 Jan 91 21:15:19 GMT Sender: fpst@hubcap.clemson.edu Lines: 96 Approved: parallel@hubcap.clemson.edu I am not on the parallel bulletin board, but learned of several messages concerning the above subject, in which I have some research results. Would you please post the message below? I think it will be of interest to those involved in the ongoing discussion. I'm not ready to join this bulletin board just yet, so I've included a note to respond directly to me. Thanks -- Jim ----- I am not a member of this bulletin board, but have seen some messages from it and wanted to respond to requests for information. There is much research on parallelizing OPS5-like languages for distributed-memory machines that is ongoing, and the messages I've seen regarding this topic did not mention all of it. So, here is some more of it, which includes work of mine. 1. My own work has focused on the PARS system, which runs OPS5 on a hypercube (by NCUBE) where: - the WM and PM is distributed over the processors, - each processor runs its own basic loop (MATCH-SELECT-ACT), - the processors run asynchronously for the most part, - actions that affect the WM or PM stored in other processors are forwarded as needed, - certain communications are performed during the basic loop so as to guarantee: * serializability -- the resulting overall WM is one that could have been produced on a serial machine running OPS5 from the original WM and PM. This is my correctness criterion. Note that PARS does not guarantee any particular conflict resolution strategy. * no errors due to temporary WM inconsistencies -- while actions are being communicated between processors, temporary WM inconsistencies can occur which can lead to non-serializable results. These problems are prevented. * no deadlocks -- in order to guarantee serializability, certain rules must be prevented from co-executing at the same time. I perform this in a way that prevents deadlocks. The theoretical foundation of PARS is described in: "A Parallel Asynchronous Distributed Production System", by Schmolze and Goel, Proceedings of the Eighth National Conference on Artificial Intelligence (AAAI-90), Boston, MA, July 1990. Not all of the proofs are not included in that paper, but the missing ones are nearly identical to the proofs appearing in the following paper that builds upon earlier work of Ishida and Stolfo and runs multiple rules in parallel in a synchronous fashion for shared-memory machines. "Guaranteeing Serializable Results in Synchronous Parallel Production Systems", Technical Report 89-5, Dept. of Computer Science, Tufts University, October 1989. (For those interested in shared memory approaches with multiple rule firings, I am in the midst of collecting benchmark measurements for a variety of algorithms. This work should be completed by February 1.) The loss of a conflict resolution strategy in PARS (and pretty much all similar works) is unfortunate but necessary. To make up for some if its impact, in PARS I have extended OPS5 slightly to include a special provision for forming rule groups. Basically, only the rules in the "current" group can be executed. This addresses the main problem that the loss of a conflict strategy causes. The PARS system is itself in the midst of being completed. It will run on the NCUBE hypercube and is based on the C version of serial OPS5 written by Miranker et al at U. Texas, which is called OPS5C. The only dependence on NCUBE (versus, say, Intel) is the manner of starting it up and of sending messages, thus it could be ported fairly easily. 2. Work that is similar to my PARS work but done independently is that of Ishida and Yokoo (of NTT Labs in Japan) and Gasser (of USC). Their system also addresses the problem of running OPS5 on a distributed memory machine in an asynchronous fashion. The resulting system is very similar to PARS except that: - it does not prevent deadlocks nor problems arising from temporary WM inconsistencies, - it offers a dynamic distribution algorithm, whereas PARS offers a static distibution algorithm. The best parts of PARS and this system can easily be combined, something that Ishida and I have discussed. As far as I know, Ishida et al are not currently constructing an implementation. Contact: shochi.ishida@ntt-20.ntt.jp 3. Work on distributed memory machines is also being pursued at U Texas by Miranker et al. At my last reading of their work, they were still in the midst of designing their system. Most of their results at that time were with regard to re-writing rule sets so as to take advantage of parallel hardware. (Of course, this group has a host of other results from TREAT to lazy serial matching algorithms to etc.) Contact: miranker@cs.utexas.edu That's all for now. If you wish to contact me, please do so directly as Iam not a regular member of this bulletin board. Jim Schmolze Dept. of Computer Science Phone: 617/381-3681 Tufts University Internet: schmolze@cs.tufts.edu Medford, MA 02155 USA