Publication Type:

Conference Proceedings


International Conference on Embedded Systems (ICES), 2014 , Coimbatore; India, p.49-54 (2014)


2D spatial filtering algorithm, 3D matrix-matrix multiplication, 4D nested loop algorithm, 6D full search block motion estimation, Algorithm design and analysis, array architecture, Arrays, Computational subspace, computational subspace mapping methodology, computational task mapping, Design space exploration, Filtering, Full search block motion estimation, Graph merging, graph merging approach, graph merging technique, Graph theory, hardware description languages, higher dimensional problem, Linear programming, matrix multiplication, Merging, Motion estimation, multiobjective functions, multiplexers, Multiplexing, n-D nested loop problems, nested loop algorithms, optimal reconfigurable array allocation, program control structures, Reconfigurable architectures, reconfigurable array scheduling, RTL behavioral representation, Spatial filtering, spatial filters, systolic array, Systolic arrays, Verilog HDL, Xilinx ISE Design Suite 12.1


Inherent parallelism in the nested loop algorithms can be exploited by proposing an array architecture called systolic array and mapping the computational tasks of the algorithm using a suitable mapping methodology on to the array architecture. The computational subspace mapping methodology that identifies a lower dimension subspace of a higher dimensional problem is implemented using the technique of allocation. i.e., the lower dimensional sub-space is chosen to lie along the computational equation. The best computational direction for higher dimensional problem in terms of data reuse, number of ports, number of PEs, memory read is selected by multi-objective functions. A reconfigurable array for n-D nested loop problems is designed by graph merging approach which reduces the area and power compared with reconfigurable array using multiplexers. The algorithms under consideration here are the 3-D matrix-matrix multiplication, 2-D spatial filtering algorithm which is a 4-D nested loop algorithm and 6-D full search block motion estimation. Allocation and scheduling of reconfigurable array is implemented in Verilog HDL and synthesized by RTL behavioral representation using Xilinx ISE Design Suite 12.1. The graph merging approach is validated by the results which show that the area allocated is less for graph merging technique than the reconfigurable array using multiplexers.
Article number 6953049, Pages 49-54, 3 July 2014 through 5 July 2014, Category numberCFP1440Y-ART, Code 109145

Cite this Research Publication

R. Resmi and Dr. Bala Tripura Sundari B., “Allocation of Optimal Reconfigurable Array using Graph Merging Technique”, International Conference on Embedded Systems (ICES), 2014 . Coimbatore; India, pp. 49-54, 2014.