Aho-Corasick failure function construction

Get Complete Project Material File(s) Now! »

Scope

Naturally, in a limited-resource project such as this, one cannot provide comprehensive answers to these many questions. Instead, practical boundaries have to be determined to match the time and resources available for the project, in the hope that future research may more deeply explore some of the issues suggested by the conclusions reached here. This section outlines those boundaries.
The main focus here is on gathering evidence to support the hypothesis that process-based decomposition enables one to better utilise modern hardware, yielding improved software run-time performance. For pragmatic reasons, such evidence is gathered subject to the following limitations:
• Only a limited number of problems commonly solved by sequential algorithms are considered. Section 1.3 provides more details regarding the specific domain.
• No formal attempt is made to develop a software development methodology. Nor is an existing software development process (such as Agile, RUP, etc) followed. Rather, concurrent software is developed in an intuitive, ad hoc manner as described in Section 1.3. Nevertheless, the experiences in doing this are recorded and could inform future research to develop an appropriate software methodology for this kind of software development.
• A single machine will be used for performance experiments. It is for future research to verify the results to various other hardware platforms.
• After a preliminary investigation of concurrency formalisms it was decided, as mentioned in Section 1.2, to use Communicating Sequential Processes (CSP). No attempt is made, therefore, to cross-compare the advantages or disadvantages of such formalisms against one another.

Concurrent programming

Concurrency and parallelism are two related, but different ideas (Buhr and Harji 2005; Gerrand 2013; Harper 2011; Pike 2012a). This text follows Turon (2013) and defines concurrency as the arbitrarily overlapped execution of processes whereas parallelism is seen as the simultaneous execution of computations. Overlapped execution does not entail simultaneous execution.
Consider, for example, the multiprogramming that takes place on a uniprocessor computer. Here, execution is overlapped in the sense that each of several programs is allocated a slice of time to execute on the single processor, then swapped out for the next program to execute for its allocated
time-slice, typically in a round-robin fashion.
These definitions (of concurrency versus parallelism) are congruent with the idea of Buhr and Harji (2005) that concurrency is the logical concept of actions happening at the same time and parallelism is the physical concept of actions happening at the same time. Concurrency is a system structuring mechanism and parallelism is a resource. A given machine has a certain capacity for parallelism and the goal is to maximise the throughput by intelligently utilising this resource.

READ STRUCTURE AND CHEMICAL COMPOSITION OF COWPEA SEEDS

Guarded Command Language

Abstract algorithms are presented in this thesis in Dijkstra’s GCL (Dijkstra 1975, 1976; Gries 1980; Kourie and B. W. Watson 2012). In this section, the aim is to provide sufficient detail to enable someone familiar with programming to comprehend the notation. It is therefore not considered necessary to provide a formal specification of the semantics of the various language constructs. The syntax is described and some semantic matters are addressed informally. Formal semantics—based one pre- and postconditions— may be found in the references above.
GCL relies on the following basic constructs. Although program constructs are commonly called statements, Dijkstra preferred the term command. The empty command (skip), assignment (≔), composition (;), selection (if ), and repetition (do). A discussion of each of these commands now follow.

1 Introduction
1.1 Scope
1.2 Concurrent programming
1.3 Methodology
1.4 Structure of thesis
2 Background
2.1 General definitions
2.2 Strings and languages
2.3 Automata
2.4 Guarded Command Language
2.5 Communicating Sequential Processes
2.6 Go overview
2.7 Parallel computing
3 Aho-Corasick failure function construction
3.1 Sequential AC algorithm
3.2 Process-based decomposition
3.3 Concurrency through data partitioning
3.4 Implementation
3.4.1 Variant 1
3.5 Performance analysis
3.6 Conclusion and Future Work
4 Brzozowski’s DFA construction
4.1 Sequential algorithm
4.2 Concurrent DFA construction
4.2.1 Configuration A
4.2.2 Configuration B
4.3 Implementation
4.4 Performance comparison
4.5 Conclusion
5 Incremental DFA minimisation
5.1 Preliminaries
5.2 Sequential algorithm
5.3 Process-based decomposition
5.4 Performance comparison
5.5 Conclusion
6 Single keyword pattern matching
6.1 Sequential algorithm
6.2 Process-based decompositions .
6.3 Performance comparison
6.4 Conclusion
7 Conclusion
7.1 Reflection
7.2 Future work
Bibliography
Acronyms and Abbreviations
Colophon