Allocation of optimal reconfigurable array using graph merging technique

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.