A parallel machine for the unification algorithm : design, simulation, and performance evaluation

Abstract

Unification, which has applications in databases, expert and knowledge-based systems, and natural language and image processing, is known to be the most repeated operation in logic and PROLOG interpreters. Slow execution of logic and PROLOG programs has been related to unification's poor performance. Therefore, the execution time of logic programs can be reduced by improving the performance of unification. A parallel machine for speeding up the unification algorithm is presented. The machine's novel architecture exploits the low amounts of parallelism offered by unification. The machine is simulated at the register transfer level and the simulation results as well as performance comparisons with two serial unification coprocessors are given. Significant performance improvements over the serial coprocessors are recorded and related to the machine's efficient features. The parallel unification machine's speedup over the coprocessor UNIFIC for two functions with increasing arities and two functions with increasing level of nesting was recorded in the ranges 1.490-1.965 and 2.037-2.791, respectively The machine was also shown to perform unification at least 3 times faster than the AT&T Unification Unit and over 30 times faster than the software unify function of a UNSW interpreter.