PARULEL: Parallel rule processing using meta-rules for redaction
Salvatore J. Stolfo, Ouri Wolfson, Philip K. Chan, Hasanat M. Dewan, Leland Woodbury, Jason S. Glazier, D. Ohsie · Journal of Parallel and Distributed Computing · 1991
Although the problem of increasing the speed of rule-based programs has been studied for a long while, so far the level of parallelism achieved under various parallel processing schemes fails to meet expectations of high performance gains. Most of the work has focused on manipulating existing rule programs to accommodate parallel architectures. However, without changing the inherently sequential algorithms encoded in rule form and without using intrinsic parallel rule languages to exploit parallelism, speedup is severely limited. In this paper we demonstrate that to maximize parallelism, manipulations must take place at the algorithmic level in addition to the program level. However, traditional rule languages are not equipped to easily express parallel algorithms. Thus, an inherently parallel rule language must be devised to enable maximum parallelism. We present our initial specification of such a language, named PARULEL. Preliminary performance results are detailed for one test case program. PARULEL is one part of a larger research effort that considers four key approaches to parallel rule processing: inherently parallel execution semantics; the use of redaction meta-rules to allow programmer control of the set of parallel instantiations; an incremental evaluation algorithm that incorporates, in an efficient manner, updates to the initial set of assumptions; and an algorithm that maps a program to a parallel architecture.