Premium
Performance of hardcoded finite automata
Author(s) -
Ketcha Ngassam E.,
Kourie Derrick G.,
Watson Bruce W.
Publication year - 2006
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.708
Subject(s) - computer science , cache , table (database) , finite state machine , automaton , cpu cache , parallel computing , theoretical computer science , deterministic finite automaton , cache algorithms , algorithm , data mining
We study the performance of a hardcoded algorithm for recognizing strings of a finite automaton's language and compare it with the use of the more conventional table‐driven algorithm. In both cases, performance depends on the finite automaton's dimensions such as alphabet size and the number of states. However, the respective processing mechanisms that influence the performance, in particular cache memory usage, depend on the details of the processor's underlying architecture. In the hardcoded case, the automaton's dimensions determine the size of the code which is, in turn, the primary determinant of the way in which cache memory is used. In the table‐driven case, cache memory usage is primarily determined by the way in which portions of the transition table are stored in it. Using statistical regression analysis, we provide multivariate equations to model the observed time efficiency of both methods. The equations obtained are cross‐compared and conclusions are drawn. Copyright © 2006 John Wiley & Sons, Ltd.