Accelerated Automata Processing Using Hybrid Spatial/von Neumann Architectures
Abstract:
With Moore’s Law slowing, and chip power density increasing due to the breakdown in Dennard scaling, building better general-purpose processors has become extremely difficult. To increase performance of computers, architects are increasingly focusing on the design of unconventional, domain-specific accelerators. One application domain that has garnered increased focus over the last decade has been automata processing. Automata processing is widely used to compute regular expression patterns in a wide variety of applications such as network packet inspection and virus detection. More recently, automata processing has been found to accelerate important kernels in bio-informatics, natural language processing, and data mining. However, a lack of standard, open-source tools for automata processing application and architecture research has slowed the pace of innovation.
This thesis first presents a new suite of open-source simulation, benchmarking, and design tools to enable new research in automata processing application and architecture development. This thesis then presents two architecture studies enabled by these tools. The first study characterizes and mitigates the overheads of automata output in spatial architectures, an essential design consideration previously ignored in the literature. The second study shows that automata graphs can usually be partitioned into highly active “hot”, and rarely active “cold” regions.
We show that “cold” regions can be large, and waste valuable compute resources when accelerated by spatial architectures. To more efficiently execute automata, we offload these “cold” regions to a von Neumann co-processor in a hybrid system, greatly reducing spatial processor resource requirements, with low added performance overheads.
Committee Members:
Kevin Skadron (Advisor), Samira Khan (Chair), Andrew Grimshaw, Gabriel Robins, Mircea Stan