Often we are faced with the situation that the behavior of a circuit changes in an unpredictable way when a chassis cover is attached or the system is not easily accessible. For instance, in a deployed environment, such as space, hardware can malfunction in unpredictable ways. What can a designer do to ascertain the cause of the problem? Register interrogations only go so far, and sometimes the problem being debugged is register transactions themselves, or the problem lies in the FPGA programming. This work provides a solution; namely, the ability to drive a JTAG chain via an on-board microcontroller and support a read/write register interface running a logic analyzer core. This is achieved without the use of a JTAG cable or any external interface. We have demonstrated the functionality of the prototype system using a Xilinx Spartan 3E FPGA and a microchip PIC18f2550 microcontroller. This paper will discuss the implementation details as well as present case studies describing how the tools have aided satellite hardware development at Los Alamos National Laboratory.

Vector and data-flow processors are particularly strong at dense, regular computation. Sparse, irregular data layouts cause problems because their unpredictable data access patterns prevent computational pipelines from filling effectively. A number of algorithms in image processing have been proposed which are not dense, and instead apply local neighborhood operations to a sparse, irregular set of points. Sparse and irregular data transfer is difficult for modern processors because they have more processing power than memory bandwidth. However, if the computation can be expanded while not increasing the bandwidth, modern processors can be made more efficient. The application targeted in this paper is patch matching over large scenes. Given two sequential frames of video data, corresponding points between the two frames are found. Correspondences are determined by comparing small image patches around each point. By rotating and comparing patches of the image over a range of angles, it is possible to more accurately match them through the scene. Rotation and interpolation are required to produce an appropriate image to compare against. Results for CPU, FPGA, and GPU are presented, with FPGA far outperforming the GPU or CPU due to its potential for high levels of hardware parallelism as the total volume of computation increases.

Shortest path algorithms are key elements of many graph problems. They are used in such applications as online direction finding and navigation, and modeling of traffic for large scale simulations of major metropolitan areas. As shortest path algorithm are execution bottlenecks, it is beneficial to move their execution to parallel hardware such as field programmable gate arrays (FPGAs). One of the innovations of this approach is the use of a small bubble sort core to produce the extract-min function. While bubble sort is not usually considered an appropriate algorithm for any non-trivial usage, it is appropriate in this case as it can produce a single minimum out of the list in O(n) cycles, where n is the number of elements in the vertex list. The cost of this min operation does not impact the running time of the architecture, because the queue depth for fetching the next set of edges from memory is roughly equivalent to the number of cores in the system. Additionally, this work provides a collection of simulation results that model the behavior of the node queue in hardware. The results show that a hardware queue, implementing a small bubble-type minimum function, need only be on the order of 16 elements to provide both correct and optimal paths. With support for a large DRAM graph store with SRAM-based caching on a Cray XD-1 FPGA-accelerated system, the system provides a speedup of roughly 50x over the CPU-based implementation.

The matched filter is an important kernel in the processing of hyperspectral data. The filter enables researchers to sift useful data from instruments that span large frequency bands and can produce Gigabytes of data in seconds. In this work, we evaluate the performance of a matched filter algorithm implementation on an FPGA-accelerated co-processor (Cray XD-1), the IBM Cell microprocessor, and the NVIDIA GeForce 7900 GTX GPU graphics card. We provide extensive discussion of the challenges and opportunities afforded by each platform. In particular, we explore the problems of partitioning the filter most efficiently between the host CPU and the co-processor. Using our results, we derive several performance metrics that provide the optimal solution for a variety of application situations.

The Apriori algorithm is a fundamental correlation-based data mining kernel used in a variety of fields. The innovation in this paper is a highly parallel custom architecture implemented on a reconfigurable computing system. Using this "bitmapped CAM," the time and area required for executing the subset operations fundamental to data mining can be significantly reduced. The bitmapped CAM architecture implementation on an FPGA-accelerated high performance workstation provides a performance acceleration of orders of magnitude over software-based systems. The bitmapped CAM utilizes redundancy within the candidate data to efficiently store and process many subset operations simultaneously. The efficiency of this operation allows 140 units to process about 2,240 subset operations simultaneously. Using industry-standard benchmarking databases, we have tested the bitmapped CAM architecture and shown the platform provides a minimum of 24times (and often much higher) time performance advantage over the fastest software Apriori implementations

The use of reconfigurable hardware for network security applications has recently made great strides as FPGA devices have provided larger and faster resources. Regular expressions have become a necessary and basic capability of intrusion detection systems, but their implementation tends to be expensive in terms of memory cost and time performance. This work provides an architecture that reduces the exponential NFA to DFA conversion cost to a linear growth for many expressions. By handling the timing and integration of the regular expression-based rules in a custom microcontroller, the memory costs are reduced and the capabilities are increased over a DFA-only solution. Both the microcontroller and its associated DFA are implemented on the FPGA. The patterns and software are stored using run-time programmable memory tables. This allows on-the-fly modification to the regular expressions. This paper presents the design details of the regular expression microcontroller and its integration to the DFA state machines. The types of expressions that the system can handle efficiently are discussed as well as the outstanding problems that continue to challenge the community.

The use of reconfigurable hardware for network security applications has recently made great strides as field-programmable gate array (FPGA) devices have provided larger and faster resources. The performance of an intrusion detection system is dependent on two metrics: throughput and the total number of patterns that can fit on a device. In this paper, we consider the FPGA implementation details of the bit-split string-matching architecture. The bit-split algorithm allows large hardware state machines to be converted into a form with much higher memory efficiency. We extend the architecture to satisfy the requirements of the IDS state-of-the-art. We show that the architecture can be effectively optimized for FPGA implementation. We have optimized the pattern memory system parameters and developed new interface hardware for communicating with an external controller. The overall performance (bandwidth * number of patterns) is competitive with other memory-based string matching architectures implemented in FPGA.

This paper presents a methodology and a tool for automatic synthesis of highly efficient intrusion detection systems using a high-level, graph-based partitioning methodology and tree-based lookahead architectures. Intrusion detection for network security is a compute-intensive application demanding high system performance. The tools implement and automate a customizable flow for the creation of efficient field programmable gate array (FPGA) architectures using system-level optimizations. Our methodology allows for customized performance through more efficient communication and extensive reuse of hardware components for dramatic increases in area-time performance

This paper presents a hardware architecture for highly efficient intrusion detection systems. In addition, a software tool for automatically generating the hardware is presented.Intrusion detection for network security is a compute-intensive application demanding high system performance. By moving both the string matching and the linking of multi-part rules to hardware, our architecture leaves the host system free for higher-level analysis. The tool automates the creation of efficient Field Programmable Gate Array architectures (FPGA). The generated hardware allows an FPGA-based system to perform deep-packet inspection of streams at up to 10 Gb/s line rates at a high level of area efficiency. Going beyond previous basic string-matching implementations that offer only single-string matching, the architecture provides support for rules requiring complex, linked (correlated-content) constructions. This allows most Snort content-linking extensions including `distance' and `within' bounding restrictions.

The Apriori algorithm is a popular correlation-based data mining kernel. However, it is a computationally expensive algorithm and the running times can stretch up to days for large databases, as database sizes can extend to Gigabytes. Through the use of a new extension to the systolic array architecture, time required for processing can be significantly reduced. Our array architecture implementation on a Xilinx Virtex-II Pro 100 provides a performance improvement that can be orders of magnitude faster than the state-of-the-art software implementations. The system is easily scalable and introduces an efficient "systolic injection" method for intelligently reporting unpredictably generated mid-array results to a controller without any chance of collision or excessive stalling.

Pattern matching for network security and intrusion detection demands exceptionally high performance. This paper describes a novel systolic array-based string matching architecture using a buffered, two-comparator variation of the Knuth-Morris-Pratt (KMP) algorithm. The architecture compares favorably with the state-of-the-art hardwired designs while providing on-the-fly reconfiguration, efficient hardware utilization, and high clock rates. KMP is a well-known computationally efficient string-matching technique that uses a single comparator and a precomputed transition table. Through the use of the transition table, the number of redundant comparisons performed is reduced. Through various algorithmic changes, we enable KMP to be used in hardware, providing the computational efficiency of the serial algorithm and the high throughput of a parallel hardware architecture. The efficiency of the system allows for a faster and denser implementation than any other RAM-based exact match system. We add a second comparator and an input buffer and then prove that the modified algorithm can function efficiently implemented as an element of a systolic array. The system can accept at least one character in each cycle while guaranteeing that the stream will never stall. In this paper, we prove the bound on the buffer size and running time of the systolic array, discuss the architectural considerations involved in the FPGA implementation, and provide performance comparisons against other approaches.

Intrusion detection for network security is a computation intensive application demanding high system performance. System level design, a relatively unexplored field in this area, allows more efficient communication and extensive reuse of hardware components for dramatic increases in area-time performance. By applying optimization strategies to the entire database, we reduce hardware requirements compared to architectures designed with single pattern matchers in mind. We present a methodology for system-wide integration of graph-based partitioning of large intrusion detection pattern databases. Integrating ruleset-based graph creation and min-cut partitioning, our methodology allows efficient multi-byte comparisons and partial matches for high performance FPGA-based network security. Through pre-processing, this methodology yields designs with competitive clock frequencies that are a minimum of 8x more area efficient than previous non-predecoded shift-and-compare architectures.

Pattern matching for network security and intrusion detection demands exceptionally high performance. Much work has been done in this field, and yet there is still significant room for improvement in efficiency, flexibility, and throughput. We develop a novel linear-array string matching architecture using a buffered, two-comparator variation on the Knuth-Morris-Pratt(KMP) algorithm. For small (16 or fewer characters) patterns, it competes favorably with the state-of-the-art while providing better scalability and reconfiguration, and more efficient hardware utilization. The area efficiency compared to other approaches improves further still as the pattern size increases because only the tables increase in size.KMP is a well-known, efficient string matching technique using a single comparator and a precomputed transition table. We add a second comparator and an input buffer, allowing the system to accept at least one character in each cycle and terminate after a number of clock cycles at maximum equal to the length of the input string plus the size of the buffer. The system also provides a clean, modular route to reconfiguring the patterns on-the-fly and scaling the system to support more units, using several rows of linear array elements. In this paper, we prove the bound on the buffer size and running time, and provide performance comparisons against other approaches.