Parallel Unification Scheduling in Prolog
Abstract
Unification, the fundamental operation in the Prolog logic programming language can take up to 50% of the execution time of a typical Prolog system. One approach to speeding up the unification operation is to perform it on parallel hardware. Although it has been shown that, in general, there is no parallel algorithm for unification that is better than the best sequential algorithm, there is a substantial subset of unification which may be done in parallel. Identifying these subsets involves gathering data using an extension of Chang's static data-dependency analysis (SDDA), then using that data to schedule the components of a unification for parallel unification. Improvements to the information gathered by SDDA may be achieved through procedures splitting, a source-level transformation of the program. This thesis describes and evaluates the above-mentioned techniques and their implementation. Results are compared to other techniques for speeding up unification. Ways in which these techniques may be applied to the Berkeley PLM machine are also described.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 18, 1986
- Accession Number
- ADA173122
Entities
People
- Wayne Citrin
Organizations
- University of California, Berkeley