Exploiting parallelism in a Relational Associative Processor

ABSTRACT

The Relational Associative Processor (RAP) is a special purpose non-numeric back-end processor used in supporting general Data Base Management Systems. In particular, it is ideally suited for supporting a relational data base. The architecture and instruction set of RAP are discussed in this context. It is the purpose of this paper to show that RAP performance can be enhanced considerably by more fully exploiting its parallel nature. It is shown that a greater degree of concurrent activity will result in better overall performance. An operating system executive to support this high level of concurrency is proposed and modelled using simulation techniques. Both the analytic and simulation results support the value of the proposals.

REFERENCES

• 1: M. M. Astrahan , D. D. Chamberlin, Implementation of a structured English query language, Communications of the ACM, v.18 n.10, p.580-588, Oct. 1975 [doi>10.1145/361020.361215]
• 2: Anderson, G. A., Kain, R. Y., A Content-Addressed Memory Designed for Data Base Applications, Proceedings of the 1976 International Conference on Parallel Processing, 1976, pp. 191-195.
• 3: Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
• 4: Philip Y. Chang, Parallel processing and data driven implementation of a relational data base system, Proceedings of the annual conference, p.314-318, October 20-22, 1976, Houston, Texas, United States [doi>10.1145/800191.805606]
• 5: George P. Copeland, Jr. , G. J. Lipovski , Stanley Y.W. Su, The architecture of CASSM: A cellular system for non-numeric processing, Proceedings of the 1st annual symposium on Computer architecture, p.121-128, December 09-11, 1973
• 6: Conway, R. W., Maxwell, W. L., Miller, L. W., Theory of Scheduling, Addison-Wesley, 1967.
• 7: 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]
• 8: Coffman, E. G. (editor), Computer and Job Shop Scheduling Theory, John Wiley and Sons, Inc., 1976.
• 9: Digital Equipment Corporation, PDP11 04/05/10/35/40/45 Processor Handbook, 1975.
• 10: Duff, T. S., The Slogo Reference Manual Third Edition, Dynamic Graphics Project Technical Memo DGP 3, Computer Systems Research Group, University of Toronto, 1977.
• 11: Freen, R., A Partitioned Data Base for use with a Relational Associative Processor, M.S. Thesis, University of Toronto, 1977.
• 12: 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]
• 13: McGill, M. J. (editor), SIGIR-SIGARCH-SIGMOD Third Workshop on Computer Architecture for Non-Numeric Processing, May, 1977.
• 14: Nakano, R., A Simulator for a RAP Virtual Memory System, M.S. Thesis, University of Toronto, 1976.
• 15: E. A. Ozkarahan , K. C. Sevcik, Analysis of aarchitectural features for enhancing the performance of a database machine, ACM Transactions on Database Systems (TODS), v.2 n.4, p.297-316, Dec. 1977 [doi>10.1145/320576.320577]
• 16: E. A. Ozkarahan , S. A. Schuster , K. C. Sevcik, Performance evaluation of a relational associative processor, ACM Transactions on Database Systems (TODS), v.2 n.2, p.175-195, June 1977 [doi>10.1145/320544.320553]
• 17: Ozkarahan, E. A., Schuster, S. A., Smith, K. C., RAP - An Associative Processor for Data Base Management, AFIPS Conference Proceedings, Vol. 44, May 1975, pp. 379-387.
• 18: John Miles Smith , Philip Yen-Tang Chang, Optimizing the performance of a relational algebra database interface, Communications of the ACM, v.18 n.10, p.568-579, Oct. 1975 [doi>10.1145/361020.361025]
• 19: Sibley, E. H. (editor), Special Issue: Data-Base Management Systems, ACM Computing Surveys, Vol. 8, 1, June, 1976.
• 20: S. A. Schuster , H. B. Nguyen , E. A. Ozkarahan , K. C. Smith, RAP. 2 - an Associative Processor for data bases, Proceedings of the 5th annual symposium on Computer architecture, p.52-59, April 03-05, 1978 [doi>10.1145/800094.803027]
• 21: Schuster, S. A., Ozkarahan, E. A., Smith, K. C., A Virtual Memory System for a Relational Associative Processor, AFIPS Conference Proceedings, Vol. 45, June 1976, pp. 855-862.
• 22: Stone, H. S., Multiprocessor Scheduling with the Aid of Network Flow Algorithms, IEEE Transactions on Software Engineering, Vol. SE-3, 1, 1977, pp. 85-93.
• 23: Zaw-Sing Su, Dynamic scheduling with preemption: a deterministic approach., 1975
• 24: Tjaden, G. S., Hierarchical Properties of Concurrency, Proceedings of the 1976 International Conference on Parallel Processing, 1976, pp. 55-64.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.6 Database Machines

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Associative processors

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Management, Performance