Parallelizing the Chambolle Algorithm for Performance-Optimized Mapping on FPGA Devices

Beretta, I., Rana, V., Akin, A., Nacci, A. A., Sciuto, D. and Atienza, D. 2016. Parallelizing the Chambolle Algorithm for Performance-Optimized Mapping on FPGA Devices. ACM Transactions on Embedded Computing Systems (TECS) . 15 (3), p. Article No. 44. doi:10.1145/2851497

TitleParallelizing the Chambolle Algorithm for Performance-Optimized Mapping on FPGA Devices
AuthorsBeretta, I., Rana, V., Akin, A., Nacci, A. A., Sciuto, D. and Atienza, D.
Abstract

The performance and the efficiency of recent computing platforms have been deeply influenced by the widespread adoption of hardware accelerators, such as Graphics Processing Units (GPUs) or Field Programmable Gate Arrays (FPGAs), which are often employed to support the tasks of General Purpose Processors (GPP). One of the main advantages of these accelerators over their sequential counterparts (GPPs) is their ability of performing massive parallel computation. However, in order to exploit this competitive edge, it is necessary to extract the parallelism from the target algorithm to be executed, which is in general a very challenging task.

This concept is demonstrated, for instance, by the poor performance achieved on relevant multimedia algorithms, such as Chambolle, which is a well-known algorithm employed for the optical flow estimation. The implementations of this algorithm that can be found in the state of the art are generally based on GPUs, but barely improve the performance that can be obtained with a powerful GPP. In this paper, we propose a novel approach to extract the parallelism from computation-intensive multimedia algorithms, which includes an analysis of their dependency schema and an assessment of their data reuse. We then perform a thorough analysis of the Chambolle algorithm, providing a formal proof of its inner data dependencies and locality properties. Then, we exploit the considerations drawn from this analysis by proposing an architectural template that takes advantage of the fine-grained parallelism of FPGA devices. Moreover, since the proposed template can be instantiated with different parameters, we also propose a design metric, the expansion rate, to help the designer in the estimation of the efficiency and performance of the different instances, making it possible to select the right one before the implementation phase. We finally show, by means of experimental results, how the proposed analysis and parallelization approach leads to the design of efficient and high-performance FPGA-based implementations that are orders of magnitude faster than the state-of-the-art ones.

KeywordsOptical flow
TV-L1 Algorithm
FPGA
Parallel Architectures
Custom Hardware
Article number44
JournalACM Transactions on Embedded Computing Systems (TECS)
Journal citation15 (3), p. Article No. 44
ISSN1539-9087
1558-3465
Year2016
PublisherACM
Accepted author manuscript
Digital Object Identifier (DOI)doi:10.1145/2851497
Publication dates
Published21 Jul 2016

Related outputs

Efficient Hardware Design Of Iterative Stencil Loops
Rana, V., Beretta, I., Bruschi, F., Nacci, A. A., Atienza, D. and Sciuto, D. 2016. Efficient Hardware Design Of Iterative Stencil Loops. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 35 (12), pp. 2018-2031. doi:10.1109/TCAD.2016.2545408

Permalink - https://westminsterresearch.westminster.ac.uk/item/9yx08/parallelizing-the-chambolle-algorithm-for-performance-optimized-mapping-on-fpga-devices


Share this
Tweet
Email

Usage statistics

9 total views
34 total downloads
1 views this month
1 downloads this month
These values are for the period from September 2nd 2018, when this repository was created

Export as