Process-Based Aho-Corasick Failure Function Construction

摘要

This case study is embedded in a wider project aimed at investigating process-based software development to better utilise the multiple cores on contemporary hardware platforms. Three alternative process-based architectures for the classical Aho-Corasick failure function construction algorithm are proposed, described in CSP and implemented in Go. Empirical results show that these process-based implementations attain significant speedups over the conventional sequential implementation of the algorithm for significantly-sized data sets. Evidence is also presented to demonstrate that the process-based performances are comparable to the performance of a more conventional concurrent implementation in which the input data is simply partitioned over several concurrent processes.