Hardware algorithms for nonnumeric computation

ABSTRACT

This paper is concerned with the design of hardware algorithms for nonnumeric computation. The subset of nonnumeric operations considered is derived from string processing languages such as SNOBOL or high-level data base languages used in data base management architectures. It is shown that cellular hardware can be designed to perform these operations on-line while the data is accessed from a rotating secondary storage medium. Being uniformly structured, the hardware could be implemented using LSI technology yielding an estimated pattern matching rate of about 100 million characters/sec. The proposed nonnumeric processor will find applications in the environment of parallel (or associative) data base management architecture, processing of large unstructured textual files, as a stand-alone microprocessor in digital communications which need simple search and update operations, or as a nonnumeric CPU that can be used along with the conventional CPU to expedite string processing operations.

REFERENCES

• 1: Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: Amello, G.F., "Charge-coupled Devices for Memory Applications," AFIPS Conf. Proc. 44(1975), 515-522.
• 4: R. M. Bird , J. C. Tu , R. M. Worthy, Associative/parallel processors for searching very large textual data bases, Proceedings of the 3rd workshop on Computer architecture : Non-numeric processing, p.8-9, January 1977
• 5: Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
• 6: Buchholz, W. (Ed.), "Planning a Computer System," McGraw-Hill, 1962.
• 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: 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
• 9: Copi, I.R., Elgot, C.C. and Wright, J.B., "Realization of Events by Logical Nets," in "Sequential Machines," E.F. Moore (Ed.), Addison-Wesley (1964), 175.
• 10: Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science (Prentice Hall Series in Automatic Computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1974
• 11: M. J. Fischer , M. S. Paterson, STRING-MATCHING AND OTHER PRODUCTS, Massachusetts Institute of Technology, Cambridge, MA, 1974
• 12: Fleck, A.C., "Formal Models for String Patterns," in Current Trends in Programming Methodology, vol. 4 (R. Yeh, Ed.), Prentice-Hall (in Press), 1978.
• 13: Caxton C. Foster, Content Addressable Parallel Processors, John Wiley & Sons, Inc., New York, NY, 1976
• 14: Gaines, R.S. and Lee, C.Y., "An Improved Cell Memory," IEEE Trans. Electron. Comput. 14(1965), 72.
• 15: Gillis, A.K. et al., "Holographic Memories—Fantasy or Reality?" AFIPS Conf. Proc. 44(1975), 535-539.
• 16: James F Gimpel, Algorithms in SNOBOL4, Catspaw, Salida, CO, 1986
• 17: Ralph E Griswold, The SNOBOL4 programming language, Bell Telephone Laboratories, 1968
• 18: Healy, L.D., Lipovski, G.J. and Doty, K.L., "The Architecture of a Context Addressed Segment Sequential Storage," Proc. of FJCC, 1972, 691.
• 19: Hughes, W.C. et al., "BEAMOS, A New Electronic Digital Memory," AFIPS Conf. Proc. 44(May 1975), 541-548.
• 20: Hunt, J.W. and McIllroy, M.D., "An Algorithm for Differential File Comparison," Computing Science Technical Report #41, Bell Laboratories, Murray Hill, June, 1976.
• 21: Karlowsky, I., Leilich, H.O. and Steige, G., "A Search Processor Proposal for Data Base Applications," Elektronische Rechenanlagen, 17(June 1975), 108-118 (in German; abstract in Computer Abstracts, 19, 9(Sept. 1975), 194).
• 22: Kautz, W.H., "Programmable Cellular Logic," in Recent Developments in Switching Theory, A. Mukhopadhyay (Ed.), Academic Press, 1971.
• 23: Kleene, S.C., "Realization of Events in Nerve Nets and Finite Automata," in "Automata Studies," C.E. Shannon and J. McCarthy (Eds.), Princeton, N.J., 1956.
• 24: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 25: Knuth, D.E., Morris, J.H. and Pratt, V.R., "Fast Pattern Matching in Strings," SIAM J. Comput. 6, 2(June 1977), 323-350.
• 26: Kuck, D.J., Lawrie, D.H. and Sameh, A.H. (Eds.), "High Speed Computer and Algorithm Organization," Proc. Symp. High Speed Computer and Algorithm Organization, Univ. of Illinois, April 13-15, 1977, Academic Press.
• 27: Lee, C.Y. and Paul, M.C., "A Content Addressable Distributed Logic Memory with Applications to Information Retrieval," Proc. IEEE (June 1963), 924.
• 28: 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]
• 29: Lorin, H., "Sorting and Sort Systems," Addison-Wesley (1975).
• 30: Robert C. Minnick, A Survey of Microcellular Research, Journal of the ACM (JACM), v.14 n.2, p.203-241, April 1967 [doi>10.1145/321386.321387]
• 31: Minsky, N., "Rotating Storage Devices as Partially Associative Memories," Proc. ACM SIGFIDET Workshop on Data Description, Access, and Control, 1972.
• 32: Mukhopadhyay, A. and Stone, H.S., "Cellular Logic," in "Recent Developments in Switching Theory," Academic Press (1971), A. Mukhopadhyay (Ed.).
• 33: Ozkarahan, E.A., Schuster, S.A. and Smith, K.C., "RAP—An Associative Processor for Data Base Management," NCC, 1975.
• 34: Parhami, B., "A Highly Parallel Computer System for Information Retrieval," Proc. FJCC, 1972.
• 35: Parker, J.L., "A Logic Per Track Retrieval Systems," IFIP Congress, 1971.
• 36: Rivest, R.L., "On the Worst-Case Behavior of String-Searching Algorithms," SIAM J. Comput. (Dec. 1977), 669.
• 37: Edward M. Reingold , Jurg Nievergelt , Narsingh Deo, Combinatorial Algorithms: Theory and Practice, Prentice Hall College Div, 1977
• 38: Slade, A.E. and McMahon, "A Cryotron Catalog Memory System," Proc. FJCC, 1960, 120.
• 39: Slotnik, D.L., "Logic Per Track Devices," Advances in Computers, Academic Press (1970).
• 40: 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
• 41: Ken Thompson, Programming Techniques: Regular expression search algorithm, Communications of the ACM, v.11 n.6, p.419-422, June 1968 [doi>10.1145/363347.363387]
• 42: Thurber, K.J., "Large Scale Computer Architecture: Parallel and Associative Processors," Hayden Book Co. (1976).
• 43: Unger, S.H., "A Computer Oriented Toward Spatial Problems," Proc. IRE, 46(Oct. 1958), 1744.
• 44: Vranesic, Z.G. and Zaky, S.G., "Nonnumeric Applications of Microprocessors," Proc. IEEE, 64, 6 (June 1976).
• 45: Ypma, J.E., "Bubble Domain Memory Systems," AFIPS Conf. Proc. 44(May 1975), 523-528.
• 46: S. G. Zaky, Microprocessors for non-numeric processing, Proceedings of the 3rd workshop on Computer architecture : Non-numeric processing, p.23-30, January 1977

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.0 General

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware

General Terms:
Algorithms