Processor allocation strategies for multiprocessor database machines

ABSTRACT

In this paper four alternative strategies for assigning processors to queries in multiprocessor database machines are described and evaluated. The results demonstrate that SIMD database machines are indeed a poor design when their performance is compared with that of the three MIMD strategies presented. Also introduced is the application of data-flow machine techniques to the processing of relational algebra queries. A strategy that employs data-flow techniques is shown to be superior to the other strategies described by several experiments. Furthermore, if the data-flow query processing strategy is employed, the results indicate that a two-level storage hierarchy (in which relations are paged between a shared data cache and mass storage) does not have a significant impact on performance.

REFERENCES

• 1: ARVlND, AND GOSTELOW, K.P. A computer capable of exchanging processors for time. Information Processing 77: Proc. IFIP Congr. 77, B. Gilchrist, Ed. North-Holland, New York, Aug. 1977, pp. 849-853.
• 2: E. Babb, Implementing a relational database by means of specialzed hardware, ACM Transactions on Database Systems (TODS), v.4 n.1, p.1-29, March 1979 [doi>10.1145/320064.320065]
• 3: BANEI~JEE, J., HSIAO, D.K., AND KANNAN, K. DBC--A database computer for very large databases. IEEE Trans. Comput. C-28, 6 (June 1979), 414-429.
• 4: BLASGEN, M.W., AND ESWARAN, K.P. Storage and access in relational data bases. IBM Syst. J. 16, 4 (1977), 363-378.
• 5: Haran Boral , David J. DeWitt, Design considerations for data-flow database machines, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California [doi>10.1145/582250.582266]
• 6: C~ESSON, G. Personal communication.
• 7: A. L. Davis, The architecture and system method of DDM1: A recursively structured Data Driven Machine, Proceedings of the 5th annual symposium on Computer architecture, p.210-215, April 03-05, 1978 [doi>10.1145/800094.803050]
• 8: Jack B. Dennis , David P. Misunas, A preliminary architecture for a basic data-flow processor, Proceedings of the 2nd annual symposium on Computer architecture, p.126-132, January 20-22, 1975
• 9: David J. DeWitt, DIRECT - a multiprocessor organization for supporting relational data base management systems, Proceedings of the 5th annual symposium on Computer architecture, p.182-189, April 03-05, 1978 [doi>10.1145/800094.803046]
• 10: DEWITT, D.J. DIRECT--A multiprocessor organization for supporting relational database management systems. IEEE Trans. Comput. C-28, 6 (June 1979), 395-406.
• 11: David J. DeWitt, Query execution in DIRECT, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582098]
• 12: DIGITAL EQUIPMENT CORPORATION, Maynard, Mass., Microcomputer Handbook, 1977.
• 13: HAWTHORN, P.B., AND DEWITT, D.J. Performance analysis of alternative database machine architectures. Comput. Sci. Tech. Rep. 383, Univ. Wisconsin, March 1980; submitted to IEEE Trans. Softw. Eng.
• 14: Paula Hawthorn , Michael Stonebraker, Performance analysis of a relational data base management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582097]
• 15: C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]
• 16: LORIE, R.A. Personal communication.
• 17: OZKA~aHAN, E.A., SCHISSTEa, S.A., AND SMITH, K.C. RAP--Associative processor for database management. AFIPS Conf. Proc., vol. 44, AFIPS Press, Arlington, Va., I975, pp. 379-388.
• 18: 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]
• 19: RUMBAUGH, J.E. A data flow multiprocessor. IEEE Trans. Cornput. C-26, 2 (Feb. 1977), 138-146.
• 20: SCHUSTER, S.A., OZKARAHAN, E.A., AND SMITH, K.C. A virtual memory system for a relational associative processor. In Proc. 1976 Nat. Computer Conf., AFIPS Press, Arlington, Va., pp. 855-862.
• 21: SLOTNIK, D.L. Logic per track devices. In Advances in Computers, vol. 10. F. Alt, Ed. Academic Press, New York, 1970, pp. 291-296.
• 22: 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]
• 23: STONEBRAKER, M. Personal communication.
• 24: Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
• 25: Su, S.Y.W., AND LIPOVSKI, G.J. CASSM: A cellular system for very large databases. In Proc. Conf. Very Large Databases, 1975, pp. 456-472.
• 26: S. Bing Yao, Optimization of query evaluation algorithms, ACM Transactions on Database Systems (TODS), v.4 n.2, p.133-155, June 1979 [doi>10.1145/320071.320072]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems

General Terms:
Design

Keywords:
associative processors, back-end computers, computer architective, data-flow computers, database machines, database management, parallel processors, processor scheduling