Accession Number:

ADA289345

Title:

Scalability in Production System Programs

Descriptive Note:

Doctoral thesis

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Acharya, Anurag

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.

Descriptors:

• *RULE BASED SYSTEMS
• *DATA MANAGEMENT
• COMPUTERIZED SIMULATION
• PRODUCTION
• SIZES(DIMENSIONS)
• PROGRAMMING LANGUAGES
• PARALLEL PROCESSING
• PROBLEM SOLVING
• LIMITATIONS
• DATA DISPLAYS
• COMBINATORIAL ANALYSIS
• HANDLING
• ADAPTERS
• DATA BASES
• ALGORITHMS

Subject Categories:

• Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE