Publication Type:

Conference Paper


IMECS 2011 - International MultiConference of Engineers and Computer Scientists 2011, Volume 1, Hong Kong, p.555-562 (2011)





2-D filtering, Algorithms, Computer science, Conformal mapping, Data reuse, Dependence vectors, Engineers, FSBM, Imaging systems, Iteration spaces, Linear transformations, Mapping matrix, Matrix algebra, Motion estimation, Nested Loops, Search engines, Systolic mapping, Vector spaces, Vectors


2-D convolution in image processing and Full Search Block Motion (FSBM) estimation used in a H.264 video encoder, are highly data intensive and computationally intensive algorithms. Such algorithms require high memory access bandwidth due to repeated memory access. They are represented as nested do loop algorithms to enable systolic mapping. Mapping is used to facilitate the extraction of parallelism along with efficient data reuse. To enable the above, the dependence vector formulation and extraction of dependencies between iterations have been used. To implement the former the searching of scheduling vector t and Processor Matrix P is performed to form the mapping transformation matrix M. The focus of our work is the extraction of the dependence vectors from the application algorithm, followed by the search of the mapping matrix M, where a novel method of finding t vector has been used. This saves the search time as compared to the widely used exhaustive search methods. The resultant M matrix is used to arrive at the various design trade - offs. The method is applied to 2-D filtering algorithm and (FSBM) which act as good test cases for nested loop algorithms. The architecture is simulated and synthesized using Mentor Graphics tools and targeted to Virtex FPGA.


cited By 0; Conference of International MultiConference of Engineers and Computer Scientists 2011, IMECS 2011 ; Conference Date: 16 March 2011 Through 18 March 2011; Conference Code:85583

Cite this Research Publication

B. Bala Tripura Sundari, “Dependence vectors and fast search of systolic mapping for computationally intensive image processing algorithms”, in IMECS 2011 - International MultiConference of Engineers and Computer Scientists 2011, Hong Kong, 2011, vol. 1, pp. 555-562.