University of Houston
Department of Computer Science
In partial fulfillment of the Requirements for the Degree of
Doctor of Philosophy
Ling-Hua Chang
will defend her dissertation
Efficient Compiler Techniques for Data Driven Languages
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.
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 working memory and
what instantiations might be chosen.
This dissertation investigates two approaches for
handling large data sets in production system programs -- scalable
parallelism and scalable match algorithms.
The Rete match algorithm was parallelized for the match phase,
and three different approaches were studied for the select phase:
sequential firings,
partial parallelized firings, and fully parallelized firings.
Our experiments on an IBM SP2
demonstrate that the approach fully parallelized firings improves
significantly the performance over partial parallelized firings, which
in turn was better than sequential firings.
We obtained super-linear scalability on several benchmark programs (when
executing them on between 1 and 32 nodes).
We also ported this compiler to an HP Itanium2 cluster to demonstrate
the platform independence of our MPI-based approach. Both versions
show similar speed-ups.
Date: Monday, March 8, 2004
Time: 10:00 AM
Place: 550-PGH
Faculty, students, and the general public are invited.
Thesis Advisor: Dr. Ernst L. Leiss