Some thoughts on the future of associative memories/processors in the solution of data base management problems

ABSTRACT

Associative memories and processors have been discussed in the literature for the past 15 years and a small number of hardware devices have actually been built (21). A number of applications have been considered and include air traffic control (22), computer graphics (24, 25), information retrieval (9), numerical analysis (15), networks (18, 19) and among others, data base management (2, 4-8, 10, 11, 13, 17). A significant percentage of present computer resources are expended in the processing of large data bases. Of this, a great deal is wasted by processing largely non-sequential data by sequential means. With hardware costs going down; and software and personnel costs going up it is important to look at the impact of non-sequential computer hardware on data base management (DBM). Based upon previous research in the application of associative processing devices to DBM, it appears that the opportunity exists for increased efficiencies by utilizing these devices in conjunction with sequential computers. In this paper, some of the advantages and limitations of these devices are presented and some brief thoughts are given concerning this author's view of the future. It is assumed here that the reader has a working knowledge of associative processors and DBM.

REFERENCES

• 1: Berra, P. B., "Some References in Data Management," May, 1973, available from the author on request. (Approximately 200 references)
• 2: Berra, P. B., "A Synopsis of Research Results in the Applications of Associative/Parallel Processors to Operations Research, Data Management and Change Detection," 1972 Sagamore Computer Conference Proceedings, Syracuse University, August 23-25, 1972.
• 3: 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
• 4: Casper Richard Defiore, An associative approach to data management, 1972
• 5: DeFiore, C. R. and P. B. Berra, "A Data Management System Utilizing an Associative Memory," AFIPS Conference Proceedings, Vol. 42, June, 1973.
• 6: DeFiore, C. R. and P. B. Berra, "A Quantitative Analysis of the Utilizations of Associative Memories in Data Management," IEEE Transactions on Electronic Computers, Vol. C-23, No. 2, February, 1974.
• 7: Caspar R. DeFiore , Neil J. Stillman , P. Bruce Berra, Associative techniques in the solution of data management problems, Proceedings of the 1971 26th annual conference, p.28-36, January 1971 [doi>10.1145/800184.810470]
• 8: Downs, H. G., "Real-Time Algorithms and Data Management on Illiac IV," IEEE Transactions on Electronic Computers, Vol. C-22, No. 8, August, 1973.
• 9: Goodyear Aerospace Corporation, "The Application of an Associative Memory to Chemical Information Storage and Retrieval," GER 13224, April 14, 1967.
• 10: Juan Carlos Goti, Optimal n-rectangular partitioning of large data-bases for multiple-attribute retrieval., 1973
• 11: Green, R. S., J. Minker, and W. E. Shindle, "Analysis of Small Associative Memories for Data Storage and Retrieval Systems," Vols. 1 & 2, RADC-TR-65-397, July, 1966.
• 12: Healy, L. D., G. J. Lipovski and K. L. Doty, "The Architecture of a Context Addressed Segment-Sequential Storage," AFIPS Conference Proceedings, Vol. 41, December, 1972.
• 13: Linde, R. R., R. Gates, and T. Peng, "Associative Processor Applications to Real-Time Data Management," AFIPS Conference Proceedings, Vol. 42, June, 1973.
• 14: Minker, J., "Bibliography 25: An Overview of Associative or Content-Addressable Memory Systems and a KWIC Index to the Literature: 1958-1970," University of Maryland and Auerbach Corporation, Computing Reviews, October, 1971.
• 15: Miranker, W. L., "A Survey of Parallelism in Numerical Analysis," SIAM Review, Vol. 13, No. 4, October, 1971.
• 16: Minsky, N., "Rotating Storage Devices as Partially Associative Memories," AFIPS Conference Proceedings, Vol. 41, 1972
• 17: Moulder, R., "An Implementation of a Data Management System on an Associative Processor, AFIPS Conference Proceedings, Vol. 42, June, 1973.
• 18: Orlando, V. A., "Associative Processing in the Solution of Network Problems," unpublished doctoral dissertation, Syracuse University, February, 1972.
• 19: Orlando, V. A. and P. B. Berra, "The Solution of the Minimum Cost Flow and Maximum Cost Flow Network Problems Using Associative Processing," AFIPS Conference Proceedings, Vol. 41, 1972.
• 20: Parhami, B., "A Highly Parallel Computing System for Information Retrieval," AFIPS Conference Proceedings, Vol. 41, December, 1972.
• 21: Rudolph, J. A., "A Production Implementation of an Associative Array Processor-STARAN," AFIPS Conference Proceedings, Vol. 41, 1972.
• 22: Rudolph, J. A., L. C. Fulmer, and W. C. Meilander, "The Coming of Age of the Associative Processor," Electronics, February, 1971.
• 23: Shore, J. E., "Second Thoughts on Parallel Processing," NRL Report 7364, Naval Research Laboratory, Washington, D. C., December 30," 1971.
• 24: Neil Jack Stillman, A feasibility study of the applicability of a hardware associative memoryto computer graphics, 1972
• 25: Stillman, N. J., C. R. DeFiore, and P. B. Berra, "Associative Processing of Line Drawings," AFIPS Conference Proceedings, Vol. 38, 1971.
• 26: Berra, P. B., "Some Problems in Associative Processors and Data Base Management," AFIPS Conference Proceedings, Vol 43, 1974.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Associative memories

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

General Terms:
Design, Management