Unification Algorithms for Massively Parallel Computers

Hiroaki Kitano


Abstract
This paper describes unification algorithms for fine-grained massively parallel computers. The algorithms are based on a parallel marker-passing scheme. The marker-passing scheme in our algorithms carry only bit-vectors, address pointers and values. Because of their simplicity, our algorithms can be implemented on various architectures of massively parallel machines without loosing the inherent benefits of parallel computation. Also, we describe two augmentations of unification algorithms such as multiple unification and fuzzy unification. Experimental results indicate that our algorithm attaines more than 500 unification per seconds (for DAGs of average depth of 4) and has a linear time-complexity. This leads to possible implementations of massively parallel natural language parsing with full linguistic analysis.
Anthology ID:
1991.iwpt-1.20
Volume:
Proceedings of the Second International Workshop on Parsing Technologies
Month:
February 13-25
Year:
1991
Address:
Cancun, Mexico
Editors:
Masaru Tomita, Martin Kay, Robert Berwick, Eva Hajicova, Aravind Joshi, Ronald Kaplan, Makoto Nagao, Yorick Wilks
Venue:
IWPT
SIG:
SIGPARSE
Publisher:
Association for Computational Linguistics
Note:
Pages:
172–181
Language:
URL:
https://aclanthology.org/1991.iwpt-1.20
DOI:
Bibkey:
Cite (ACL):
Hiroaki Kitano. 1991. Unification Algorithms for Massively Parallel Computers. In Proceedings of the Second International Workshop on Parsing Technologies, pages 172–181, Cancun, Mexico. Association for Computational Linguistics.
Cite (Informal):
Unification Algorithms for Massively Parallel Computers (Kitano, IWPT 1991)
Copy Citation:
PDF:
https://aclanthology.org/1991.iwpt-1.20.pdf