Special Issue: Prague Stringology Conference 2005No Access

DYNAMIC ALLOCATION OF FINITE AUTOMATA STATES FOR FAST STRING RECOGNITION

ERNEST KETCHA NGASSAM

School of Computing, University of South Africa, Pretoria, 0003, South Africa

School of Computing, University of South Africa P.O. Box 392 UNISA 0003, Pretoria, South Africa.

Search for more papers by this author

BRUCE W. WATSON

FASTAR Research Group, Department of Computer Science, University of Pretoria, Pretoria, 0002, South Africa

Search for more papers by this author

, and

DERRICK G. KOURIE

FASTAR Research Group, Department of Computer Science, University of Pretoria, Pretoria, 0002, South Africa

Search for more papers by this author

https://doi.org/10.1142/S0129054106004431Cited by:1 (Source: Crossref)

Abstract

The spatial and temporal locality of reference on which cache memory relies to minimize cache swaps, is exploited to design a new algorithm for finite automaton string recognition. It is shown that the algorithm, referred to as the Dynamic State Allocation algorithm outperforms the traditional table-driven algorithm for strings that tend to repeatedly access the same set of states, provided that the string is long enough to amortize the allocation cost. Further improvements on the algorithm result in even better performance.

Keywords:

AMSC: 22E46, 53C35, 57S20

References

Ketcha Ngassam, E. Hardcoding Finite Automata. MSC Dissertation. University of Pretoria, 2003 . Google Scholar
Ketcha Ngassam, E., Watson, B. W. and Kourie, D. G. Preliminary Experiments in Hardcoding Finite Automata. Poster paper, CIAA, Santa Barbara, 299–300, September 2003 . Google Scholar
E. Ketcha Ngassam, B. W. Watson and D. G. Kourie, Hardcoding Finite State Automata Processing, SAICSIT (2003) pp. 111–121. Google Scholar
E. Ketcha Ngassam , B. W. Watson and D. G. Kourie , A Framework for the Dynamic Implementation of Finite Automata for Performance Enhancement , Prague Stringology Conference ( 2004 ) . Google Scholar
E. Ketcha Ngassam , B. W. Watson and D. G. Kourie , Reordering finite Automatata States for Fast String Recognition , Prague Stringology Conference ( 2005 ) . Google Scholar
J. L. Hannessy and D. A. Patterson , Computer Architecture: A Quantitative Approach , 3rd edn. ( Morgan Kaufmann Publishers , 2003 ) . Google Scholar
Intel Corporation. The Intel Opimization Reference Manual. http://www.intel.com/design/pentiumiii/manuals/, 2002 . Google Scholar
K. Thompson, Communications of the ACM 11(6), 323 (1968). Web of Science, Google Scholar
D. E. Knuth, J. H. Morris Jr. and V. R. Pratt, SIAM J. Comput. 6(1), 323 (1977). Crossref, Google Scholar
A. C. Yao, SIAM J. Comput. 8(3), 368 (1979). Crossref, Web of Science, Google Scholar
R. Gerber , The Software Optimization Cookbook: High-Performance Recipes for the Intel Architecture ( Intel Corporation , 2002 ) . Google Scholar