A unified model of pattern-matching circuits for field-programmable gate arrays

The objective of this dissertation is to develop a methodology for describing the functionality, analyzing the complexity, and evaluating the performance of a large class of pattern-matching circuit design approaches for field-programmable gate arrays (FPGAs). The developed methodology consists of three elements. The first is a functional model and associated nomenclature that unifies a significant portion of published circuit design approaches while also illuminating many novel approaches. The second is a set of analytical expressions that model the area and time complexity of each circuit design approach based on attributes of a given pattern set. Third, software tools are developed that facilitate architectural design space exploration and circuit implementation. This methodology is used to conduct an extensive evaluation and comparison of design approaches under a wide range of conditions using pattern sets from multiple application domains as well as synthetic pattern sets. The results indicate strong dependences between pattern set properties and circuit performance and provide new insights on the fundamental nature of various design approaches. Pattern-matching, or the process of comparing two sequences of data, is a common task that is used in many different applications. Pattern-matching is often performed with software, but hardware implementations can be used to increase pattern-matching performance. In recent years, a number of techniques have been proposed for designing pattern-matching hardware circuits with reconfigurable FPGA chips. The use of FPGAs enables high performance because the circuits can be customized for a particular application and pattern set. A relatively unstudied consequence of tailoring circuits for specific patterns is that circuit area and performance are affected by various properties of the patterns used. Most previous work in this field only considers a single design approach and a small number of pattern sets. Therefore, it is not clear how each design is affected by pattern set properties. For a given set of patterns, it is difficult to determine which approach would be the most efficient or provide the highest performance. Previous attempts to compare approaches using results from different publications are conflicting and inconclusive due to variations in the FPGA devices, patterns, and circuit optimizations used. There has been no attempt to evaluate a wide range of designs under a common set of conditions. The methodology presented in this dissertation provides a framework for studying multiple aspects of FPGA pattern-matching circuits in a controlled and consistent manner. This dissertation is organized as follows. Chapter 1 introduces the pattern-matching problem, some common pattern-matching applications, and various solution techniques. FPGA pattern-matching methods are reviewed in Chapter 2. A unified model for describing FPGA pattern-matching circuits is presented in Chapter 3. Chapter 4 discusses a number of pattern-matching circuit architectures and provides an analytical model of the area and time complexity of each architecture. A set of software tools based on these models is described in Chapter 5. In Chapter 6, results are presented from a design space exploration and several application case studies conducted using the software tools. Finally, Chapter 7 provides concluding remarks and future research directions.