Reconfigurable computing is emerging as the new paradigm for satisfying the simultaneous demand for application performance and flexibility. The ability to customize the architecture to match the computation and the data flow of the application has demonstrated significant performance benefits compared to general purpose architectures. Computer vision applications are one class of applications that have significant heterogeneity in their computation and communication structures. At the low level, vision algorithms have regular repetitive computations operating on large sets of image data with predictable data dependencies. At the higher level, the computations have irregular dependencies. Computer vision application characteristics have significant overlap with the advantages of reconfigurable architectures. The main focus of the paper is on outlining the methodologies required to realize the potential of reconfigurable architectures for vision applications. After giving a broad introduction to reconfigurable computing, the advantages of utilizing reconfigurable architectures for vision applications are outlined and illustrated using example computations. The paper discusses the development of fundamental configurable computing models that abstract the underlying hardware for high-level application mapping. The Hybrid System Architecture Model and algorithms utilizing the model are illustrated to demonstrate a formal framework. The paper also outlines ongoing research and provides a comprehensive list of references for further reading.

Reconfigurable architectures promise significant performance and flexibility advantages over conventional architectures. Automatic mapping techniques that exploit the features of the hardware are needed to leverage the power of these architectures. In this paper, we develop techniques for parallelizing nested loop computations from digital signal processing (DSP) applications onto high performance pipelined configurations. We propose a novel data context switching technique that exploits the embedded distributed memory available in reconfigurable architectures to parallelize such loops. Our technique is demonstrated on two diverse state-of-the-art reconfigurable architectures, namely, Virtex and the Chameleon Systems Reconfigurable Communications Processor. Our techniques show significant performance improvements on both architectures and also perform better than state-of-the-art DSP and microprocessor architectures.

Effective utilization of cache memories is a key factor in achieving high performance in computing the Discrete Fourier Transform (DFT). Most optimization techniques for computing the DFT rely on either modifying the computation and data access order or exploiting low level platform specific details, while keeping the data layout in memory static. In this paper we propose a high level optimization technique, dynamic data layout (DDL). In DDL, data reorganization is performed between computations to effectively utilize the cache. This cache-conscious factorization of the DFT including the data reorganization steps is automatically computed by using efficient techniques in our approach. An analytical model of the cache miss pattern is utilized to predict the performance and explore the search space of factorizations. Our technique results in up to a factor of 4 improvement over standard FFT implementations and up to 33% improvement over other optimization techniques such as copying on SUN UltraSPARC-II, DEC Alpha and Intel Pentium III.

Reconfigurable architectures promise significant performance benefits by customizing the configurations to suit the computations. Variable precision for computations is one important method of customization for which reconfigurable architectures are well suited. The precision of the operations can be modified dynamically at run-time to match the precision of the operands. Though the advantages of reconfigurable architectures for dynamic precision have been discussed before, we are not aware of any work which analyzes the qualitative and quantitative benefits which can be achieved This paper develops a formal methodology for dynamic precision management. We show how the precision requirements can be analyzed for typical computations in loops by computing the precision variation curve. We develop algorithms to generate optimal schedules of configurations using the precision variation curves. Using our approach, we demonstrate 25%-37% improvement in the total execution time of an example loop computation on the XC6200 device.

This paper presents efficient multicasting with reduced contention on irregular networks with switch-based wormhole interconnection and unicast message passing. First, it is proved that for an arbitrary irregular network with a typical deadlock-free, adaptive routing, it may not be possible to create an ordered list of nodes to implement an arbitrary multicast in a contention-free manner with minimal number of communication steps. Next, three different multicast algorithms are proposed with their respective node orderings to reduce contention: switch-based ordering (SO), switch-based hierarchical ordering (SHO), and chain concatenation ordering (CCO). A variation of a binomial tree-based communication pattern with unicast message passing is used on the above ordered lists to implement multicast. The proposed multicast algorithms are compared with each other as well as with the naive random ordering (RO) algorithm for a range of system sizes, switch sizes, message lengths, degrees of connectivity, destination set sizes, and communication start-up times. The CCO algorithm is shown to be the best to implement multicast with reduced contention and minimum latency. Such results related to multicast on irregular networks are the first of their kind in the wormhole literature. Thus, these demonstrate significant potential to be applied to current and future generation NOW systems with irregular interconnection.