The design of a hardware recognizer for utilization in scanning operations

ABSTRACT

This paper addresses the design issues and the performance evaluation of a special purpose hardware recognizer device capable of performing pattern matching and text retrieval operations. In addition, the VLSI design and the time and space complexities of the proposed organization are discussed. The structure of the system is based on the concept of the non-deterministic finite state model with a high degree of parallelism incorporated into the design. The system simulates a parallel finite state automaton by utilizing a number of identical units called “CELLs” which have associative processing capabilities. The proposed system improves the performance of pattern matching operations by matching several patterns in parallel. Because of the similarities between the scanning process during compilation and the pattern matching operations, the proposed module can be used as a hardware scanner. The hardware scanner can be used as an interface between the user and the compiler in the conventional general purpose systems as well as the language oriented or high-level language computers.

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: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 3: Zvi Kohavi , Richard W. Hamming , Edward A. Feigenbaum, Switching and Finite Automata Theory: Computer Science Series, McGraw-Hill Higher Education, 1990
• 4: Knuth, D.E. , Morris, J.H. and Pratt, V.R. "Fast Pattern Matching in Strings," SIAM Jo~irnal of Computing, Vol. 6(2) , June 1977, pp. 240-267.
• 5: Lewis If, P.M. , Rosenkrantz, D.J. and Stearnes, R.E., Compiler Design Tneor_~, Addison-Wesley, Massachusetts, 1978
• 6: Muknopadnyay, A. and Hurson, A., "An Associative Search Language - ASL for Data Management, AFIPS, 1979, Vol. 48, pp. 727-752.
• 7: McKeeman, W.M. , "Language Directed Computer Design, Fall Joint Computer Conference, 1967 , pp. 413-417.
• 8: Glenford J. Myers, Advances in Computer Architecture, John Wiley & Sons, Inc., New York, NY, 1982
• 9: Myers, G.J. , "The Advantages of Higner-Level Computer Architecture," IBM Systemj Research Institut, e, New York, pp. 678-682.
• 10: Cnu , Y. "High Level Compute r Architecture, IEEE Com~uter, July 1981 , Vol. 14, pp. 2-8.
• 11: Cnu , Y . and Abranams , N. , "Programming Lang,aages and Direct Execution Computer Arcnitecture, IEEE Com~puter, July 1981 , Vol. 14, pp. 22-23.
• 12: 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
• 13: Roger L. Haskin , Lee A. Hollaar, Operational characteristics of a harware-based pattern matcher, ACM Transactions on Database Systems (TODS), v.8 n.1, p.15-40, March 1983 [doi>10.1145/319830.319832]
• 14: George P. Copeland, String storage and searching for data base applications: Implementation on the INDY backend kernel, Proceedings of the fourth workshop on Computer architecture for non-numeric processing, p.8-17, August 01-04, 1978, Blue Mountain Lake, New York, United States [doi>10.1145/800128.804162]
• 15: Mukhopadyay, A., "H'..,rd',, ~zJ Algorithms for Non-Numeric Computation, IEEE Transactions on Comp.~ters, Vol. C-28, June 1979, pp. 384-394.
• 16: Hollaar , L. A . , "Text Retrieval Computers, IEEE Computer, March 1979, Vol. 12, pp. 40-50.
• 17: David C. Roberts, A specialized computer architecture for text retrieval, Proceedings of the fourth workshop on Computer architecture for non-numeric processing, p.51-59, August 01-04, 1978, Blue Mountain Lake, New York, United States [doi>10.1145/800128.804167]
• 18: Stellnorn, W.H. , "A Processor for Direct Scanning of Text," Worksnop on Computer Arcnitecture for Non-numeric Processing, 1974.
• 19: Bullen, Jr. R.H. and Millen, J.K. " Microtext- tne De s ign of a Microprogrammed Finite State Searcn Machine for Full Text Retrieval," AFIPS, 1972, Vol. 41, pp. 479-488.
• 20: S. S. Yau , H. S. Fung, Associative Processor Architecture—a Survey, ACM Computing Surveys (CSUR), v.9 n.1, p.3-27, March 1977 [doi>10.1145/356683.356685]
• 21: Hurson, A. and Snirazi, B. , "A Hardware Implementation of tne Parallel Finite State Model," Micro-Delcon 1984, Delaware, pp. 97-104.
• 22: Hurson, A. and Snirazi, B., "A VLBi Design for the Parallel Finite State Automaton," IEEE international Conference on Computer Design~VLSf in Computers (ICCh), 0jr'. 1984.
• 23: Anderson, G.A. , "Multiple Match Resolvers: A New Design Method, IEEE Transactions on Computers, December 1974, Vol. C-23, pp. 3~7-1320.
• 24: Lesk, M.E. and Schmidt, E. , "LEX-A Lexical Analyzer Generator, Bell Laboratories, Murray Hill, New Jersey.
• 25: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

General Terms:
Design, Performance, Theory

Keywords:
VLSI design, associative processing, finite state automation, hardware architecture, parallel finite state automation, pattern matching, performance evaluation, text retrieval