Prof. Salvatore J. Stolfo

Department of Computer Science, Columbia University, New York, NY 10027
sal@cs.columbia.edu

Member of the Polytechnic University Center for Advanced Technology

Parallel Rule-based Systems

Many of the ideas in PARULEL were derived from my early work on parallel rule based systems. The DADO massively parallel hardware was designed to accelerate rule-based (and structural pattern recognition) systems, but this required several new parallel algorithms and strategies to accomplish the task efficiently and in a scalable manner. (Although in those days, scalability was not the prime desideratum, but rather speed was the entire game!)

For example, we studied various parallel processing strategies to speed up deductive and active database applications. To parallelize any task one requires a mechanism to distribute workload among separate processing sites. The mechanism we use here is precisely the same technique I invented for the DADO machine years earlier, and it is called copy-and-constrain. To distribute the work attributed to say one rule of a rule program, copy that rule some number of times, but constrain each replicate to manipulate only a (disjoint) subset of data processed by the originating rule. These familiar notions are put to use in many parallel database systems today. We developed this technique for Production System programs years ago for centralized parallel processors and DADO in particular.

The earliest work I did on parallel rule based systems can be found in the 1984 AAAI proceedings where a number of parallel algorithms that one may find "common" today (especially in the parallel database arena) were detailed for the first time for parallel rule based expert systems.

By the way, during my early work on parallel rule processing, I was visited by Toru Ishida for a year who assumed the position of Visiting Research Scientist on my project. Toru and I worked together to develop a means of extracting inherent parallelism from a Production System program based upon an analysis of the dataflow and logical relationships between rules. This work extended my thesis work that used dataflow graphs and analysis algorithms to generalize control strategies for use as heurisitc guidance in problem solving. Our work on using these techniques to elicit parallelism can be found in the 1985 ICPP proceedings. (Its a popular paper, having been cited by researchers in this area for quite some time.)

Toru has since gone back to Japan, earned his PhD and is now a Professor at Kyoto University. You may be interested in visiting Toru Ishida's homepage in Japan to learn about his recent work on distributed AI, system reorganization and distributed intelligent agents.
BACK