  In this paper, we propose several optimizations for the SFA construction
algorithm, which greatly reduce the in-memory footprint and the processing
steps required to construct an SFA. We introduce fingerprints as a space- and
time-efficient way to represent SFA states. To compute fingerprints, we apply
the Barrett reduction algorithm and accelerate it using recent additions to the
x86 instruction set architecture. We exploit fingerprints to introduce hashing
for further optimizations. Our parallel SFA construction algorithm is
nonblocking and utilizes instruction-level, data-level, and task-level
parallelism of coarse-, medium- and fine-grained granularity. We adapt static
workload distributions and align the SFA data-structures with the constraints
of multicore memory hierarchies, to increase the locality of memory accesses
and facilitate HW prefetching. We conduct experiments on the PROSITE protein
database for FAs of up to 702 FA states to evaluate performance and
effectiveness of our proposed optimizations. Evaluations have been conducted on
a 4 CPU (64 cores) AMD Opteron 6378 system and a 2 CPU (28 cores, 2
hyperthreads per core) Intel Xeon E5-2697 v3 system. The observed speedups over
the sequential baseline algorithm are up to 118541x on the AMD system and
2113968x on the Intel system.
