The Cost of Data Dependence in Motion Vector
Estimation for Reconfigurable Platforms
Su-Shin Ang †1, George Constantinides †, Wayne Luk ∗, Peter Cheung †
†Department of Electrical and Electronics Engineering, Imperial College
South Kensington campus, London SW7 2AZ, United Kingdom
1su-shin.ang@imperial.ac.uk
∗Department of Computing, Imperial College
180 Queen’s Gate, South Kensington Campus, London SW7 2AZ, United Kingdom
Abstract— Motion vector estimation is frequently performed
as a prelude to the exploitation of temporal redundancies in
video applications. As a result, a large volume of work has been
done to develop techniques to avoid the heavy memory access
requirements of full search motion vector estimation. Often,
these approaches introduce data dependence to the algorithm,
leading to memory accesses which cannot be determined at design
time. Consequently, this complicates the exploitation of data re-
use in hardware. In this work, the cost of data dependence
is quantified. Experiments indicate that a data dependent fast
motion vector estimation approach is faster than full search by
up to 47% in the absence of data re-use optimisation. However,
full search is approximately 16 times faster than the ‘fast’ motion
vector estimation algorithm when a static line buffering scheme
and a parallel caching scheme are used respectively to exploit
data re-use. Therefore, it is established that data dependence in
motion vector estimation is very expensive in terms of hardware
performance.
I. INTRODUCTION
Future embedded systems are required to be transparent
to multiple processing and communication standards, while
preserving the quality of service. Since Field Programmable
Gate Arrays (FPGAs) allow the implementation of highly
parallel as well as reconfigurable systems, FPGAs afford the
target application considerable performance and flexibility. For
this reason, FPGAs are likely to play an increasingly important
role in future embedded systems.
To increase the performance of a given application, typical
features o