Scalability in Production System Programs
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
Production system programs have been notorious for their inability to handle large data sets. The primary cause of their poor scalability is the combinatorial explosion in the number of possible matches which arises from the need to match conjunctive conditions where each conjunct can match the whole data set. This dissertation investigates two approaches for handling large data sets in production system programs - scalable parallelism and scalable match algorithms. The primary limitation on parallelism in production system programs is the data-dependent nature of the computation combined with a lack of information about the run-time contents of the tuple-space. This dissertation argues that effective parallelization of production system programs requires information about the run-time contents of the tuple-space. Results from a simulation study show that simple extensions to existing production system languages can provide sufficient information to parallelize a wide variety of programs. These results also show that, in general, there is no program-independent bound on the speedup that can be achieved by parallel production system programs and that speedups in such programs can scale with data set size.
- Computer Programming and Software