language: en

Predictive Dynamic Load Balancing of Parallel and Distributed Rule and Query Processing

Hasanat M. Dewan Salvatore J. Stolfo Mauricio Hernandez Jae-Jun Hwang
Department of Computer Science Columbia University,
New York, NY 10027
CUCS-025-94

(This paper appeared in the Proceedings of the 1994 ACM SIGMOD Conference.)

Abstract Expert Databases are environments that support the processing of rule programs against a disk resident database. They occupy a position intermediate between active and deductive databases, with respect to the level of abstraction of the underlying rule language. The operational semantics of the rule language influences the problem solving strategy, while the architecture of the processing environment determines efficiency and scalability. In this paper, we present elements of the PARADISER architecture and its kernel rule language, PARULEL. The PARADISER environment provides support for parallel and distributed evaluation of rule programs, as well as static and dynamic load balancing protocols that predictively balance a computation at runtime. This combination of features results in a scalable database rule and complex query processing architecture. We validate our claims by analyzing the performance of the system for two realistic test cases. In particular, we show how the performance of a parallel implementation of transitive closure is significantly improved by predictive dynamic load balancing.

1 Introduction