DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
ADA289345
Title:
Scalability in Production System Programs
Descriptive Note:
Doctoral thesis
Corporate Author:
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Report Date:
1994-01-01
Pagination or Media Count:
368.0
Abstract:
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.
Distribution Statement:
APPROVED FOR PUBLIC RELEASE