Unification parallelism for prolog processing

Autor: Ken Ishikawa, Katsuhiro Yamazaki, Takanobu Baba, Kenzo Okuda, Masayuki Inagawa
Rok vydání: 1988
Předmět:
Zdroj: Systems and Computers in Japan. 19:37-46
ISSN: 1520-684X
0882-1666
DOI: 10.1002/scj.4690190104
Popis: The unification is a basic component of Prolog processing. However, its parallel processing has not been well studied because the number of arguments, which corresponds to the degree of the unification parallelism, is small, and a consistency check operation is necessary after a parallel unification operation. On these issues, we have implemented the following ideas: (1) enhancing the degree of parallelism by decomposing a compound term into a functor and the arguments at compile-time; (2) allocating decomposed unification processing to multiple processor units (PUs) at run-time; (3) decreasing the number of consistency checks by the compile-time clustering and reducing the overhead by embedding the consistency check operations into the unification processing; and (4) stopping the operations of the other processors if the unification fails. To clarify the effect, we have developed and evaluated a Prolog processor on a multiprocessor system. The results show that statistically: (1) the decomposition of compound terms makes the number of arguments 3.2 on the average even after clustering, and that dynamically, (1) the unification parallelism performs 41 percent speed up, and the effect is evident at a small number of processors; (2) the compile-time clustering makes the consistency check unnecessary; (3) the stop operation of processors, running in parallel, attains 0.5 – 6 percent (and 10 percent for some problems) performance improvement; and (4) the processing of clause head occupies 60 – 70 percent of dynamic microsteps and is an important object of parallel processing.
Databáze: OpenAIRE
Externí odkaz: