Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Towards cache optimization in finite automata implementations
Thesis (PhD (Computer Science))--University of Pretoria, 2007.
Saved in:
| Other Authors: | |
|---|---|
| Format: | Thesis |
| Published: |
University of Pretoria
2013
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613534266851328 |
|---|---|
| access_status_str | Open Access |
| author2 | Watson, Bruce William |
| author_browse | Watson, Bruce William |
| author_facet | Watson, Bruce William |
| collection | Thesis |
| dc_rights_str_mv | © University of Pretor |
| description | Thesis (PhD (Computer Science))--University of Pretoria, 2007. |
| format | Thesis |
| id | oai:repository.up.ac.za:2263/26467 |
| institution | University of Pretoria (South Africa) |
| last_indexed | 2026-06-10T12:37:40.523Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from UPSpace — University of Pretoria Institutional Repository |
| publishDate | 2013 |
| publishDateRange | 2013 |
| publishDateSort | 2013 |
| publisher | University of Pretoria |
| publisherStr | University of Pretoria |
| record_format | dspace |
| source_str | UPSpace — University of Pretoria Institutional Repository |
| spelling | oai:repository.up.ac.za:2263/26467 Towards cache optimization in finite automata implementations Watson, Bruce William Kourie, Derrick G. ngassek@unisa.ac.za Ketcha Ngassam, Ernest Software construction Toolkit Taxonomy Algorithmic Finite automata UCTD Thesis (PhD (Computer Science))--University of Pretoria, 2007. To the best of our knowledge, the only available implementations of FA-based string recognizers are the so-called conventional table-driven algorithm and, of course, its hardcoded counterpart suggested by Thompson, Penello, and DeRemer in 1967, 1986, and 2004 respectively. However, our early experiments have shown that the performance of both implementations is hampered by the random access nature of the automaton’s transition table in the case of table-driven, and also the random access nature of the directly executable instructions that make up each hardcoded state. Moreover, the problem of memory load and instruction load are also performance bottlenecks of these algorithms, since, as the automaton size grows, more space in memory is required to hold data/instructions relevant to the states. This thesis exploits the notion of cache optimization (that requires good data or instructions organization) in investigating various enhancements of both table-driven and hardcoding. Functions have been used to formally define the denotational semantics of string recognizers. These functions rely on various so-called strategy variables that are integrated into the formal definition of each recognizer. By appropriately selecting these variables, the conventional algorithms may be described, without loss of generality. By specializing these strategy variables, the new and enhanced recognizers can be denotationally described, and resulting algorithms can then be implemented. We first introduce the so-called Dynamic State Allocation (DSA) strategy regarded as a sort of Just-In-time (JIT) implementation of FA-based string recognizers whereby a predefined portion of the memory is reserved for acceptance testing. Then follows the State pre-Ordering (SpO) strategy that assumes some prior knowledge on the order in which states would be visited. In this case, acceptance testing takes place once each state have been allocated to its new position in memory. The last strategy referred to as the Allocated Virtual Caching (AVC) strategy is based on the premise that a portion of the memory originally occupied by the automaton’s states is virtually used as a sort of cache memory in which acceptance testing takes place, enabling therefore, the exploitation of the various performance enhancement notions on which hardware cache memory relies. It is shown that the algorithms can be classified in a taxonomy tree which is further mapped into a class-diagram that represents the design of a toolkit for FA-based string recognition. Also given in the thesis are empirical results that indicate that the algorithms suggested can, in general, outperform their conventional counterparts when recognizing large and appropriately chosen input strings. Computer Science PhD unrestricted 2013-09-07T05:51:31Z 2007-08-01 2013-09-07T05:51:31Z 2007-04-25 2007-08-01 2007-07-21 Thesis Ketcha Ngassam, E 2007, Towards cache optimization in finite automata implementations, PhD Thesis, University of Pretoria, Pretoria, viewed yymmdd <http://hdl.handle.net/2263/26467> Pretoria http://hdl.handle.net/2263/26467 http://upetd.up.ac.za/thesis/available/etd-07212007-120525/ © University of Pretor application/pdf application/pdf application/pdf application/pdf application/pdf application/pdf University of Pretoria |
| spellingShingle | Software construction Toolkit Taxonomy Algorithmic Finite automata UCTD Towards cache optimization in finite automata implementations |
| title | Towards cache optimization in finite automata implementations |
| title_full | Towards cache optimization in finite automata implementations |
| title_fullStr | Towards cache optimization in finite automata implementations |
| title_full_unstemmed | Towards cache optimization in finite automata implementations |
| title_short | Towards cache optimization in finite automata implementations |
| title_sort | towards cache optimization in finite automata implementations |
| topic | Software construction Toolkit Taxonomy Algorithmic Finite automata UCTD |
| url | http://hdl.handle.net/2263/26467 http://upetd.up.ac.za/thesis/available/etd-07212007-120525/ |