Custom coprocessor based matrix algorithms for image and signal processing

Matrix algorithms are important in many types of applications including image and signal processing. A close examination of the algorithms used in these, and related, applications reveals that many of the fundamental actions involve matrix algorithms such as matrix multiplication. This paper presents an investigation into the design and implementation of different matrix algorithms such as matrix operations, matrix transforms and matrix decompositions using a novel custom coprocessor system for MATrix algorithms based on Reconfigurable Computing (RCMAT). The proposed RCMAT architectures are scalable, modular and require less area and time complexity with reduced latency when compared with existing structures.

RELATIONSHIP BETWEEN WORD AND BIT LEVEL SYSTOLIC ARRAYS AS APPLIED TO MATRIX multiplied by MATRIX MULTIPLICATIONS.

The mapping of matrix multiplied by matrix multiplication onto both word and bit level systolic arrays has been investigated. It has been found that well defined word and bit level data flow constraints must be satisfied within such circuits. An efficient and highly regular bit level array has been generated by exploiting the basic compatibilities in data flow symmetries at each level of the problem. A description of the circuit which emerges is given and some details relating to its practical implementation are discussed.

Valved Dataflow For FPGA Memory Hierarchy Synthesis

For modern FPGA, implementation of memory intensive processing applications such as high end image and video processing systems necessitates manual design of complex multilevel memory hierarchies incorporating off-chip DDR and onchip BRAM and LUT RAM. In fact, automated synthesis of multi-level memory hierarchies is an open problem facing high level synthesis technologies for FPGA devices. In this paper we describe the first automated solution to this problem.
By exploiting a novel dataflow application modelling dialect, known as Valved Dataflow, we show for the first time how, not only can such architectures be automatically derived, but also that the resulting implementations support real-time processing for current image processing application standards such as H.264. We demonstrate the viability of this approach by reporting the performance and cost of hierarchies automatically generated for Motion Estimation, Matrix Multiplication and Sobel Edge Detection applications on Virtex-5 FPGA.

Automatic FPGA Synthesis of Memory Intensive C-based Kernels

Realising high performance image and signal processing
applications on modern FPGA presents a challenging implementation problem due to the large data frames streaming through these systems. Specifically, to meet the high bandwidth and data storage demands of these applications, complex hierarchical memory architectures must be manually specified
at the Register Transfer Level (RTL). Automated approaches which convert high-level operation descriptions, for instance in the form of C programs, to an FPGA architecture, are unable to automatically realise such architectures. This paper
presents a solution to this problem. It presents a compiler to automatically derive such memory architectures from a C program. By transforming the input C program to a unique dataflow modelling dialect, known as Valved Dataflow (VDF), a mapping and synthesis approach developed for this dialect can
be exploited to automatically create high performance image and video processing architectures. Memory intensive C kernels for Motion Estimation (CIF Frames at 30 fps), Matrix Multiplication (128x128 @ 500 iter/sec) and Sobel Edge Detection (720p @ 30 fps), which are unrealisable by current state-of-the-art C-based synthesis tools, are automatically derived from a C description of the algorithm.

Streaming Elements for FPGA Signal and Image Processing Accelerators

Field programmable gate array devices boast abundant resources with which custom accelerator components for signal, image and data processing may be realised; however, realising high performance, low cost accelerators currently demands manual register transfer level design. Software-programmable ’soft’ processors have been proposed as a way to reduce this design burden but they are unable to support performance and cost comparable to custom circuits. This paper proposes a new soft processing approach for FPGA which promises to overcome this barrier. A high performance, fine-grained streaming processor, known as a Streaming Accelerator Element, is proposed which realises accelerators as large scale custom multicore networks. By adopting a streaming execution approach with advanced program control and memory addressing capabilities, typical program inefficiencies can be almost completely eliminated to enable performance and cost which are unprecedented amongst software-programmable solutions. When used to realise accelerators for fast fourier transform, motion estimation, matrix multiplication and sobel edge detection it is shown how the proposed architecture enables real-time performance and with performance and cost comparable with hand-crafted custom circuit accelerators and up to two orders of magnitude beyond existing soft processors.

Memory-centric VDF Graph Transformations for Practical FPGA Implementation

Realising memory intensive applications such as image and video processing on FPGA requires creation of complex, multi-level memory hierarchies to achieve real-time performance; however commerical High Level Synthesis tools are unable to automatically derive such structures and hence are unable to meet the demanding bandwidth and capacity constraints of these applications. Current approaches to solving this problem can only derive either single-level memory structures or very deep, highly inefficient hierarchies, leading in either case to one or more of high implementation cost and low performance. This paper presents an enhancement to an existing MC-HLS synthesis approach which solves this problem; it exploits and eliminates data duplication at multiple levels levels of the generated hierarchy, leading to a reduction in the number of levels and ultimately higher performance, lower cost implementations. When applied to synthesis of C-based Motion Estimation, Matrix Multiplication and Sobel Edge Detection applications, this enables reductions in Block RAM and Look Up Table (LUT) cost of up to 25%, whilst simultaneously increasing throughput.

Soft-core Stream Processor for Sliding Window Applications

Software-programmable `soft' processors have shown tremendous potential for efficient realisation of high performance signal processing operations on Field Programmable Gate Array (FPGA), whilst lowering the design burden by avoiding the need to design fine-grained custom circuit archi-tectures. However, the complex data access patterns, high memory bandwidth and computational requirements of sliding window applications, such as Motion Estimation (ME) and Matrix Multiplication (MM), lead to low performance, inefficient soft processor realisations. This paper resolves this issue, showing how by adding support for block data addressing and accelerators for high performance loop execution, performance and resource efficiency over four times better than current best-in-class metrics can be achieved. In addition, it demonstrates the first recorded real-time soft ME estimation realisation for H.263 systems.

Constructive Synthesis of Memory-Intensive Accelerators for FPGA From Nested Loop Kernels

Field-programmable gate arrays are ideal hosts to custom accelerators for signal, image, and data processing but de- mand manual register transfer level design if high performance and low cost are desired. High-level synthesis reduces this design burden but requires manual design of complex on-chip and off-chip memory architectures, a major limitation in applications such as video processing. This paper presents an approach to resolve this shortcoming. A constructive process is described that can derive such accelerators, including on- and off-chip memory storage from a C description such that a user-defined throughput constraint is met. By employing a novel statement-oriented approach, dataflow intermediate models are derived and used to support simple ap- proaches for on-/off-chip buffer partitioning, derivation of custom on-chip memory hierarchies and architecture transformation to ensure user-defined throughput constraints are met with minimum cost. When applied to accelerators for full search motion estima- tion, matrix multiplication, Sobel edge detection, and fast Fourier transform, it is shown how real-time performance up to an order of magnitude in advance of existing commercial HLS tools is enabled whilst including all requisite memory infrastructure. Further, op- timizations are presented that reduce the on-chip buffer capacity and physical resource cost by up to 96% and 75%, respectively, whilst maintaining real-time performance.

2-D R-matrix propagation: A large scale electron scattering simulation dominated by the multiplication of dynamically changing matrices

We examine the computational aspects of propagating a global R-matrix, R, across sub-regions in a 2-D plane. This problem originates in the large scale simulation of electron collisions with atoms and ions at intermediate energies. The propagation is dominated by matrix multiplications which are complicated because of the dynamic nature of R, which changes the designations of its rows and columns and grows in size as the propagation proceeds. The use of PBLAS to solve this problem on distributed memory HPC machines is the main focus of the paper.

BIT-LEVEL SYSTOLIC ARRAY CIRCUIT FOR MATRIX VECTOR MULTIPLICATION.

A bit-level systolic array for computing matrix x vector products is described. The operation is carried out on bit parallel input data words and the basic circuit takes the form of a 1-bit slice. Several bit-slice components must be connected together to form the final result, and authors outline two different ways in which this can be done. The basic array also has considerable potential as a stand-alone device, and its use in computing the Walsh-Hadamard transform and discrete Fourier transform operations is briefly discussed.

Reduction of sample matrix effects - The analysis of benzimidazole residues in serum by immunobiosensor

Regulatory authorities, the food industry and the consumer demand reliable determination of chemical contaminants present in foods. A relatively new analytical technique that addresses this need is an immunobiosensor based on surface plasmon resonance (SPR) measurements. Although a range of tests have been developed to measure residues in milk, meat, animal bile and honey, a considerable problem has been encountered with both serum and plasma samples. The high degree of non-specific binding of some sample components can lead to loss of assay robustness, increased rates of false positives and general loss of assay sensitivity. In this paper we describe a straightforward precipitation technique to remove interfering substances from serum samples to be analysed for veterinary anthelmintics by SPR. This technique enabled development of an assay to detect a wide range of benzimidazole residues in serum samples by immunobiosensor. The limit of quantification was below 5 ng/ml and coefficients of variation were about 2%.

B-spline methods in R-matrix theory for scattering in two-electron systems

The use of B-spline basis sets in R-matrix theory for scattering processes has been investigated. In the present approach a B-spline basis is used for the description of the inner region, which is matched to the physical outgoing wavefunctions by the R-matrix. Using B-splines, continuum basis functions can be determined easily, while pseudostates can be included naturally. The accuracy for low-energy scattering processes is demonstrated by calculating inelastic scattering cross sections for e colliding on H. Very good agreement with other calculations has been obtained. Further extensions of the codes to quasi two-electron systems and general atoms are discussed as well as the application to (multi) photoionization.