Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!samsung!emory!hubcap!Anurag.Acharya From: Anurag.Acharya@dravido.soar.cs.cmu.edu Newsgroups: comp.parallel Subject: Re: Research for RETE-based systems on Intel hypercube Message-ID: Date: 10 Jan 91 14:31:25 GMT Sender: fpst@hubcap.clemson.edu Organization: Carnegie Mellon University Lines: 101 Approved: parallel@hubcap.clemson.edu Distributed memory machines have not been popular platforms for implementing Rete and other production system match algorithms. There have been several efforts to place production systems on distributed memory machines but most of them were either not pursued to the point of actual implementation or did not yield encouraging results. Here is a list of some of the projects that I know about with a reference to each one of them. 1. The Dado project at Columbia : Salvatore Stolfo, Dan Miranker [1] 2. The Non-Von project at columbia : Bruce Hillyer and David Shaw [2] 3. The Pesa-1 project at university of kaiserslautern, germany : Franz Schreiner and Gerhard Zimmermann [3] 4. The Rubic Project at University of Southern Calif : Dan Moldovan [4] 5. The Cupid project at university of waterloo : Michael Kelly and Rudolph Seviora [5] 6. Mapping Rete onto a dynamically reconfigurable tree-structured architecture : BT Smith and D Middleton [6] 7. Mapping Rete onto the Connection machine using Oflazer's algorithm : Rex Flynn [7] 8. Compiling constant productions into Activity Flow Networks and mapping them onto the Connection machine : Guy Blelloch [8] 9. Mapping Rete onto the MIT tagged token dataflow architecture : Jean-Luc Gaudiot, Sukhan Lee and Andrew Sohn [9] In addition, there was some work done by a couple of Japanese researchers which was published in a large-scale database/knowledgebase conference -- the names and details of the work escape at the moment but I have a hazy recollection that the approach taken resembled that taken by the CUPID project. Most of these efforts were based on custom hardware. Milind Tambe and Anoop Gupta published a paper in AAAI that described a mapping for fine-grained stock hardware, i.e. with no special support for production systems. [10] Milind Tambe and myself followed up on this. We modified the original mapping which was intended for fine-grained machines for medium-grained machines (that is machines with 2-25 processors). We performed simulations to evaluate the mapping and study the effect of varying the computation/communication ratio on the speedups. The simulations assumed a crossbar interconection network and Sparc-based processing elements. Results indicated that it was possible to achieve reasonable speedups (where reasonable means between 4 and 10 fold) on such machines. This work has been reported at ICPP'89 [11]. A more detailed version of the report is soon going to be published in the IEEE transaction on parallel and distributed systems. I had some communication with Bill Harding, who was a grad student at the Air Force Institute of Technology (at the Wright-Patterson Air Force Base) about placing production systems on hypercubes. He was working with Gary Lamont who is on the faculty of the institute. However, I have not been able to get in touch with him since Feb last or thereabouts. Attractive as they might seem for parallelization, production systems have not been effectively parallelized. To the best of my knowledge, only two parallel implementations have been made available : ParaOPS5 and CParaOPS5. Both of these are on shared memory machines and are available from the School of Computer Schience, Carnegie Mellon University. [1] Salvatore Stolfo and Dan Miranker, "The Dado Production System Machine", Journal of Parallel and Distributed Computing (JPDC), volume 3, 1986, pp 269-296 [2] Bruce Hillyer and David Shaw, "Execution of OPS5 Production systems on a Massively Parallel Machine", JPDC, vol 3, 1986 pp 236-268 [3] Franz Schreiner and Gerhard Zimmermann, "Pesa-1 - A Parallel Architecture for Production Systems", ICPP'87, pp 167-169 [4] Dan Moldovan, "RUBIC: A Multiprocessor for Rule-based Systems", IEEE Transactions on Systems, Man and Cybernetics, vol 19 (4),Jul/aug 89 [5] Michael Kelly and Rudolph Seviora, "Performance of OPS5 Matching on CUPID", Microprocessing and Microprogramming, vol 27, 1989, pp 397-404 [6] BT Smith and D Middleton, "Exploiting Fine-grained Parallelism in Production Systems", National Conf of the Canadian Society for the Computational Studies of Intelligence, 1987, pp 262-270 [7] Rex Flynn, "Placing Soar on the Connection Machine", AAAI workshop on "How Slow Elements can Think so Fast". [8] Guy Blelloch, "CIS : A Massivley Concurrent Rule-based System", Probably in AAAI -- I have the paper but don't have the reference [9] Jean-Luc Gaudiot, Suckhan Lee and Andrew Sohn, "Data-driven Multiprocessor Implementation of the Rete Match Algorithm", ICPP'88 [10] Anoop Gupta and Milind Tambe, "Suitability of Message Passing Computers for Implementing Production Systems", NCAI'88, pp 687-692 [11] Anurag Acharya and Milind Tambe, "Production Systems on Message Passing Computers: Simulation Results and Analysis", ICPP'89. anurag ps: Steve, I tried to get this message to you but my mail either hung in the mail queue or bounced right back at me after a couple of days.