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

Content Provider	ACM Digital Library
Author	Akin, Abdulkadir Atienza, David Beretta, Ivan Nacci, Alessandro Antonio Sciuto, Donatella Rana, Vincenzo
Copyright Year	2016
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 (GPPs). One of the main advantages of these accelerators over their sequential counterparts (GPPs) is their ability to perform massive parallel computation. However, to exploit this competitive edge, it is necessary to extract the parallelism from the target algorithm to be executed, which generally is 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 article, 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.
Starting Page	1
Ending Page	27
Page Count	27
File Format	PDF
ISSN	15399087
e-ISSN	15583465
DOI	10.1145/2851497
Volume Number	15
Issue Number	3
Journal	ACM Transactions on Embedded Computing Systems (TECS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-03-07
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Chambolle $TV-L^{1}$ Custom hardware Field programmable gate arrays Optical flow Parallel architectures
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A high-performance parallel implementation of the Chambolle algorithm

HLS approach in designing FPGA-based custom coprocessor for image preprocessing

Parallel Architecture for Hierarchical Optical Flow Estimation Based on FPGA

High Performance Phylogenetic Analysis With Maximum Parsimony on Reconfigurable Hardware

Dual core architecture on FPGA as an integrated solution in the development of Telemedicine-capable devices

FPGA implementations of the massively parallel GCA model

New conception and algorithm of allocation mapping for processor arrays implemented into multi-context FPGA devices

Are Field-Programmable Gate Arrays Ready for the Mainstream?

RAMP: Research Accelerator for Multiple Processors

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

Similar Documents

A high-performance parallel implementation of the Chambolle algorithm

HLS approach in designing FPGA-based custom coprocessor for image preprocessing

Parallel Architecture for Hierarchical Optical Flow Estimation Based on FPGA

High Performance Phylogenetic Analysis With Maximum Parsimony on Reconfigurable Hardware

Dual core architecture on FPGA as an integrated solution in the development of Telemedicine-capable devices

FPGA implementations of the massively parallel GCA model

New conception and algorithm of allocation mapping for processor arrays implemented into multi-context FPGA devices

Are Field-Programmable Gate Arrays Ready for the Mainstream?

RAMP: Research Accelerator for Multiple Processors

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