Vectorization techniques for prolog

ABSTRACT

Several techniques for running Prolog programs on pipelined vector processors, such as the Hitachi S-820 or the Cray-2, are developed. This paper presents an automatic program transformation (vectorization) method of Prolog, which enables a type of or-parallel execution of Prolog programs using vector operations. Performance is evaluated on the Hitachi S-810 using the Eight-Queens problem. Its vector execution speed is 4.5 MLIPS (18 ms). This is eight or nine times faster than scalar execution. This result confirms the effectiveness of vectorization techniques and applicability of vector processors to Prolog execution and to symbol processing applications.

REFERENCES

• Clo 81: W F. Clocksin , Christopher S. Mellish, Programming in Prolog (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1984
• Con 81: John S. Conery , Dennis F. Kibler, Parallel interpretation of logic programs, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.163-170, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806775]
• Ito 86: N. Ito , M. Sato , E. Kuno , K. Rokusawa, The architecture and preliminary evaluation results of the experimental parallel inference machine PIM-D, Proceedings of the 13th annual international symposium on Computer architecture, p.149-156, June 02-05, 1986, Tokyo, Japan
• Kam 83: Kamiya, S., Isobe, F., Takashima, H., and Takiuchi, M., "Practical Vectorization Techniques for the "FACOM VP ...., information Processing 83, pp.389-394, Elsevier Science Publishers B. V., 1983.
• Kan 84: Kanada, Y., "A Schema for Solving N-Queens Problem by a Vector Processor: Parallel Backtracking Schema", 29th National Conference of Japan Society of Information Processing, pp.1251-1252, 1984 (in Japanese).
• Kan 85: Kanada, Y., "Improving Prolog Performance using Supercomputer", Proceedings of 26th Programming Symposium, pp.47-56, 1985 (in Japanese}.
• Kan 87: Kanada, Y., "Or-parallel Vector Processing Methods for N-Queens: Towards High-Speed Execution of Logic Programs on Vector Processors", Technical Group on Programming Language, Japan Society of Information Processing, 87-PL-12, 1987 (in Japanese).
• Kum 86: Kumon, K., et. al., "KABU-WAKE: A New Parallel Inference Method and Its Evaluation", COMPCON Spring 86, pp.168-172, 1986.
• Nag 84: Nagashima, S., et. al., "Design Consideration for High- Speed Vector Processor: S-810", Proceedings of IEEE International Conference on Computer Design, pp.238- 242, 1984.
• Nil 86: Martin Nilsson , Hidehiko Tanaka, -FLENG Prolog- the language which turns supercomputers into parallel Prolog machines, The 5th Conference on Logic programming '86, p.170-179, July 1987, Tokyo, Japan
• Ona 86: Rikio Onai , Hajime Shimizu , Kanae Masuda , Akira Matsumoto , Moritoshi Aso, Architecture and evaluation of a reduction-based parallel inference machine: PIM-R, Proceedings of the 4th conference on Logic programming '85, p.1-12, August 1986, Tokyo, Japan
• Tam 87: Tamaki, H., "Stream-Based Compilation of Ground I/O Prolog into Committed-choice Languages", 4th International Conference on Logic Programming, pp.376-393, Melborne, 1987.
• Tat87: Tatsuguchi, K., and Muraoka, Y., "Parallel Logic Programming Language Interpreters on Supercomputers", Technical Group on Programming Language, Japan Society of Information Processing, 87- PL-14,1987 (in Japanese).
• Ueda 85: Ueda, K., "Guarded Holm Clauses", ICOT Technical Report, TR-103, Institute for New Generation Computer Technology, 1985.
• Ueda87: Kazunori Ueda, Making exhaustive search programs deterministic, Proceedings on Third international conference on logic programming, p.270-282, September 1986, London, United Kingdom

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.5 Programming Languages and Software

          Nouns: Prolog

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Array and vector processors; Pipeline processors**
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Prolog

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation

General Terms:
Design, Languages, Performance