Design and performance measurements of a parallel machine for the unification algorithm

ABSTRACT

Unification is known to be the most repeated operation in logic programming and PROLOG interpreters. To speed up the execution of logic programs, the performance of unification must be improved. We propose a parallel unification machine for speeding up the unification algorithm. The machine is simulated at the register transfer level and the simulation results as well as performance comparison with a serial unification coprocessor are presented.

REFERENCES

• 1: Richard Kendall Miller, Fifth Generation Computers, Prentice Hall PTR, Upper Saddle River, NJ, 1986
• 2: S. Abe , T. Bandoh , S. Yamaguchi , K. Kurosawa , K. Kiriyama, High performance integrated Prolog processor IPP, Proceedings of the 14th annual international symposium on Computer architecture, p.100-107, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30362]
• 3: Nam Sung Woo, A hardware unification unit: design and analysis, Proceedings of the 12th annual international symposium on Computer architecture, p.198-205, June 17-19, 1985, Boston, Massachusetts, United States
• 4: N. S. Woo, The architecture of the hardware unification unit and an implementation, Proceedings of the 18th annual workshop on Microprogramming, p.89-98, December 03-06, 1985, Pacific Grove, California, United States
• 5: J. A. Robinson, A Machine-Oriented Logic Based on the Resolution Principle, Journal of the ACM (JACM), v.12 n.1, p.23-41, Jan. 1965 [doi>10.1145/321250.321253]
• 6: Paterson, M. S., Wegman, M. N., "Linear Unification," Journal Of Computer And System Sciences, vol. 16(2), pp. 158-167, April 1978.
• 7: Alberto Martelli , Ugo Montanari, An Efficient Unification Algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.2, p.258-282, April 1982 [doi>10.1145/357162.357169]
• 8: Yssuura, H., ""On Parallel Computational Complexity Of Unification," in Proceedings Of The International Conference On Fifth Generation Computer Systems, pp. 235-248, Tokyo, Japan, November 1984.
• 9: Cynthia Dwork , Paris C. Kanellakis , John C. Mitchell, On the sequential nature of unification, Journal of Logic Programming, v.1 n.1, p.35-50, June 1984 [doi>10.1016/0743-1066(84)90022-0]
• 10: Chang, S., Towards A Theorem Proving Architecture, Department Of Computer Science, California Institute Of Technology, Pasadena, CA, 1981.
• 11: Robinson, P., "The SUM: An AI Coprocessor," Byte, vol. 10(6), pp. 169-180, June 1985.
• 12: Gollakota, R., Design And Analysis Of UNIFIC: A Coprocessor For The Unification Algorithm, M. S. Thesis, Department Of Electrical Engineering, Texas A&M University, College Station, Texas, August 1986.
• 13: Y. Shobatake , H. Aiso, A unification processor based on a uniformly structured cellular hardware, Proceedings of the 13th annual international symposium on Computer architecture, p.128-139, June 02-05, 1986, Tokyo, Japan
• 14: Chen, W., Hsieh, K., "An Overlapping Unification Algorithm And Its Hardware Implementation," in Proceedings Of The 1987 International Conference On Parallel Processing, pp. 803-805, University Park, Pennsylvania, 1987.
• 15: Shih, Y., Irani, K., "Large Scale Unification Using A Mesh-Connected Array Of Hardware Unifiers," in Proceedings Of The 1987 International Conference On Parallel Processing, pp. 787-794, University Park, Pennsylvania, 1987.
• 16: Inagawa, M. et al, "Unification Parallelism For Prolog Processing," Systems And Computers In Japan, vol. 19(l), pp. 37-46, January 1988.
• 17: Barbacci, M. et al, "ISPS Computer Description Language," Departments of Computer Science and Electrical Engineering, Carnegie-Mellon University, Pittsburg, Pennsylvania, 1981.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.2 Control Structure Performance Analysis and Design Aids
          Subjects: Simulation**
      B.1.4 Microprogram Design Aids
          Subjects: Languages and compilers
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Simulation

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Alternation and nondeterminism
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

General Terms:
Algorithms, Design, Languages, Measurement, Performance