Image processing algorithms for template matching, two-dimensional (2-D) digital filtering, morphologic operations, and motion estimation share some common properties. They can all benefit from using reconfigurable computers that use coprocessor boards based on field-programmable gate array (FPGA) chips. This paper characterizes those applications as generalized template matching (GTM) operations and describes the mapping of the GTM operations onto reconfigurable computers. A three-step approach is described. The first two steps enumerate and prune the design space of basic GTM building blocks, which consist of FPGA buffers and GTM computation cores. The last step is to achieve a solution through an optimal combination of these building blocks where the cost function is the FPGA computation time and the constraints are FPGA coprocessor board resources. Various FPGA buffers are presented so as to introduce design options of basic GTM building blocks. Algorithms used for the mapping are described. Experimental results are summarized to reveal the relationship between the GTM mapping results and FPGA board resource parameters.

An infrared automatic target recognition (IR ATR) application is accelerated with an FPGA co-processor board. The board features and the application are first stated. The FPGA design is then described. The achieved performance is reported and analyzed at the end.

This paper describes the development of a dynamically reconfigurable system that can support multiple applications running concurrently. A dynamically reconfigurable system allows hardware reconfiguration while part of the reconfigurable hardware is busy computing. An FPGA resource manager (RM) is developed to allocate and de-allocate FPGA resources and to preload FPGA configuration files. For each individual application, different tasks that require FPGA resources are represented as a flow graph which is made available to the RM so as to enable efficient resource management and preloading. The performance of using the RM to support several applications is summarized. The impact of supporting concurrency and preloading in reducing application execution time is demonstrated.

Digital signal processing algorithms with multiple shift-invariant dependence graphs (DGs) can be mapped to field programmable gate array hardware in many different types of systolic processor arrays. Because of the finite amount of hardware resources, the problem is to use a "right" amount of hardware in a specific configuration so to maximize the processing speed. In this paper, the problem of finding the right processor array configuration is formulated as a constrained optimization problem where the cost function includes not only the cost of individual processor arrays but also the cost of interfacing circuits. Three heuristic algorithms are presented for the optimization problem. Among them, both the Lth axial neighbor algorithm and the simulated annealing algorithm produce good results on a test case. Simulation results on the test case also indicate that the initial configuration is important in getting a good configuration for both algorithms. The Lth axial neighbor algorithm has the extra advantage of requiring less amount of performance tuning.

The proposed dynamically reconfigurable system can support multiple applications running concurrently. An FPGA resource manager is developed to allocate and de-allocate FPGA resources and to pre-load FPGA configuration files. For each individual application, different tasks that require FPGA resources are represented as a flow graph which is made available to the resource manager so as to enable efficient resource management and pre-loading. The impact of supporting concurrency and pre-loading in reducing application execution time is demonstrated.

Parallel discrete event simulation (PDES) on general-purpose machines can reduce the logic simulation time for large circuits considerably. However, it generates more events than necessary for certain high activity circuits and produces inconsistent execution times over different circuits. This is because glitches contribute to a sizable portion of events during a simulation. The proposed Event-lookahead Time Warp (ETW) algorithm can look ahead, combine and execute multiple events at each gate optimistically, and recover from an error by using a rollback mechanism as used in the original time warp algorithm. As a result, it reduces unnecessary events and produces more consistent execution times and reasonable speedups.

Mapping DSP algorithms to FPGA/VLSI circuits is an important issue in Application-Specific Array Processor design. Since a DSP algorithm can be abstracted as a graph where each node is a shift-invariant DG (Dependence Graph) and the edges denote the data flow, it is possible to map a DSP algorithm to a set of processor arrays with some interface circuits. The interface design depends on the projection/scheduling vectors used on the two corresponding shift-invariant DGs and the interfacing cost is very significant when a lot of delays are necessary or when the processor operations are relatively inexpensive in terms of area. Therefore, when selecting these vectors in a design environment, the effect on the interface circuit must be accurately computed. In this paper, various interface circuit designs are presented and categorized based on the data conversion requirement. An algorithm to select a design from many design options to minimize the cost is also described.

A weight smoothing algorithm is proposed in this paper to improve a neural network's generalization capability. The algorithm can be used when the data patterns to be classified are presented on an n-dimensional grid (n>/=1) and there exists some correlations among neighboring data points within a pattern. For a fully-interconnected feedforward net, no such correlation information is embedded into the architecture. Consequently, the correlations can only be extracted through sufficient amount of network training. With the proposed algorithm, a smoothing constraint is incorporated into the objective function of backpropagation to reflect the neighborhood correlations and to seek those solutions that have smooth connection weights. Experiments were performed on problems of waveform classification, multifont alphanumeric character recognition, and handwritten numeral recognition. The results indicate that (1) networks trained with the algorithm do have smooth connection weights, and (2) they generalize better.

The author addresses the fault tolerance issue for rectangular arrays of a large number of processors. An array grid model based on n1/2-track switches is adopted. This model is a generalization of previous models using 1 1/2-track switches and 2 1/2-track switches. A reconfigurability theorem for n1/2 track arrays is established and a concept of pseudo processing elements (PEs) is introduced to decompose a routing problem into problems with smaller track numbers. Therefore, with the decomposition technique, only the routing algorithm developed for 1 1/2-track arrays is required. Simulation results for the 1 1/2-track array and 2 1/2-track array are given.>

A distance measure, called the generalized Euclidean distance, is developed for binary images to take into account perceptual distortions. Based on this distance measure, a type of transformation is devised to ensure that the generalized Euclidean distance of two images is the same as the Euclidean distance of two transformed images. A set of transformed images is then used to train and test a feed-forward neural network for handwritten numeral recognition. It is shown that the recognition rate is significantly improved by incorporating human perception into the neural network, and that the transformation step can be merged into the trained neural network so that no transformation is required during the recognition stage.>