An associative array architecture intended for semantic network processing

ABSTRACT

This paper describes the organization and operation of a semantic network array processor (SNAP). The architecture consists of an array of identical cells each containing a content addressable memory, microprogram control and communication unit. Each cell is dedicated to one node of the semantic network and its associated relations. The array can perform global associative functions under the supervision of an outside controller. In addition, each cell is equipped with the necessary logic to perform individual functions. A set of primitive instructions were carefully chosen. Some of the applications discussed in this paper include pattern search operations, production systems and inferences. A LISP simulator was developed for this architecture, and some simulation results are presented in this paper.

References

1. 1.Ballard, and Brown: "Computer Vision" Prentice-Hall 1982.
2. 2.Brachman, R.J.: "On the Epistemological Status of Semantic Networks," in Findler, N.V. (Ed.): Associative Networks, Academic Press, Inc., 1979, pp.3-50.
3. 3.Davis, R. and King, J.: "An Overview of Production Systems", in Machine Intelligence 8, 1977, pp. 300-332.
4. 4.Fahlman, S.E. et al.: "Massively Parallel Architectures for AI: NETL, Thistle, and Boltzmann Machines," Proceedings of the National Conference on Artificial Intelligence, Washington, D.C., August 1983, pp. 109-113.
5. 5.Hillis, W.D.: "The Connection Machine," Massachusetts Institute of Technology Artificial Intelligence Laboratory, A.I. Memo No.646, September 1981.
6. 6.Quillian, M.R.: Semantic Memory, Ph.D. dissertation, Carnegie Institute of Technology (now Carnegie-Mellon University), October 1966, 222pp. Appeared as Report AFCRL-66-189.
7. 7.Schmalze, J.G. and Lipkis, T.A.: "Classification in the KL-ONE knowledge representation system," Proceedings of the Eight International Joint Conference on Artificial Intelligence, August 1983, Germany, pp. 330-332.
8. 8.Schuster, S.A. et al: "RAP 2—An Association Processor for Databases and its applications," IEEE Transactions on Computer, vol.C-28, no. 6, June 1979, pp.446-458.
9. 9.Shaw, D.E.: "A Hierarchical Associative Architecture for the Parallel Evaluation of Relational Algebraic Database Primitives," Artificial Intelligence Laboratory, Stanford University, October 1979.
10. 10.Stolfo, S.J. and Shaw, D.E.,: "DADO: A Tree-Structured Machine Architecture for Production Systems," 1982.
11. 11.Woods, W.A.: "What's in a link: foundation for semantic networks", in Representation and Understanding, Bobrow, D.G. and Collins, A.M. (Eds.), Academic Press, New York, 1975, pp.35-82.
12. 12.Woods, W.A.: "Parallel Algorithms for Real Time Knowledge based Systems", Technical Report 4181, Bolt Beranek and Newman Inc, December 1978.

Index Terms

• Computer systems organization

  • Architectures

    • Parallel architectures

      • Systolic arrays

• Computing methodologies

  • Modeling and simulation

    • Simulation evaluation