A virtual memory system for a relational associative processor

ABSTRACT

The Relational Associative Processor (RAP) is an experimental "backend" cellular processor for implementing data base management systems. RAP is particularly well suited to supporting Codd's relational model of data. The capacity of a RAP device implemented with current IC and memory technology can be estimated to contain 10⁸ to 10⁹ bits of associatively processable data. Because many data bases are larger, a virtual memory environment for RAP has been proposed and its performance simulated. The environment incorporates conventional memories for bulk storage and a single RAP processor---both controlled by a general purpose front-end computer. The system requires that the entire relational data base be divided into pages of size equal to one RAP cell memory. A buffer memory is added to RAP to permit the overlap of paging with processing. It has been found that user environments containing small relations or queries exhibiting either long processing times relative to paging requirements or some "locality" (defined as the degree to which sequences of queries reference some relations more than others) can efficiently page data between large data bases and data base machines without significant losses in performance.

REFERENCES

• 1: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 2: Ozkarahan, E. A., S. A. Schuster and K. C. Smith, A Data Base Processor, CSRG-43, Computer Systems Research Group, University of Toronto, September 1974.
• 3: E. A. Ozkarahan , S. A. Schuster , K. C. Smith, RAP: an associative processor for data base management, Proceedings of the May 19-22, 1975, national computer conference and exposition, May 19-22, 1975, Anaheim, California [doi>10.1145/1499949.1500024]
• 4: Esen A. Ozkarahan, An associative processor for relational data bases--rap. (volumes 1 and 2), University of Toronto, Toronto, Ont., Canada, 1976
• 5: Nakano, R., A Simulator for a RAP Data Management System, M.Sc. Thesis, Department of Computer Science, University of Toronto, 1976.
• 6: Ozkarahan, E. A., S. A. Schuster and K. C. Sevcik, Performance Evaluation of a Relational Associative Processor, CSRG-65, Computer Systems Research Group, University of Toronto, January 1976.
• 7: Casper R. DeFiore , P. Bruce Berra, A data management system utilizing an associative memory, Proceedings of the June 4-8, 1973, national computer conference and exposition, June 04-08, 1973, New York, New York [doi>10.1145/1499586.1499641]
• 8: Richard Moulder, An implementation of a data management system on an associative processor, Proceedings of the June 4-8, 1973, national computer conference and exposition, June 04-08, 1973, New York, New York [doi>10.1145/1499586.1499639]
• 9: Stanley Y. W. Su , G. Jack Lipovski, CASSM: a cellular system for very large data bases, Proceedings of the 1st International Conference on Very Large Data Bases, September 22-24, 1975, Framingham, Massachusetts [doi>10.1145/1282480.1282518]
• 10: Chyuan Shiun Lin , Diane C. P. Smith , John Miles Smith, The design of a rotating associative memory for relational database applications, ACM Transactions on Database Systems (TODS), v.1 n.1, p.53-65, March 1976 [doi>10.1145/320434.320447]