Effective Parallelization of a High-Order Graph Matching Algorithm for GPU Execution

Chulhee Lee; Hyuk Jae Lee

doi:10.1109/TCSVT.2018.2797992

Effective Parallelization of a High-Order Graph Matching Algorithm for GPU Execution

Chulhee Lee, Hyuk Jae Lee

Department of Electrical and Electronic Engineering

Research output: Contribution to journal › Article › peer-review

5 Citations (Scopus)

Abstract

High-order graph matching is a feature-matching algorithm that uses geometric information among features. This algorithm is more robust to repetitive patterns or unclear areas than first-order matching that uses only feature descriptors. However, the processing speed of high-order matching is very slow because of its high computational complexity. To accelerate its speed, this paper proposes a new parallelization algorithm of high-order matching for GPU execution. The obstacle for parallelization is the write collision caused by multiple threads that must simultaneously update the data at the same memory location. In high-order matching, multiple formulations of the objective function can generate the same solution. By taking advantage of this property, the proposed algorithm replaces the operation causing write collision with another operation eliminating the collision while generating the same solution. The proposed algorithm is tested with GTX 960 and takes 31.3 ms, which is 68 times faster than the execution time with a CPU and approximately three times faster than that with a straightforward parallelization for the same GPU.

Original language	English
Article number	8269387
Pages (from-to)	560-571
Number of pages	12
Journal	IEEE Transactions on Circuits and Systems for Video Technology
Volume	29
Issue number	2
DOIs	https://doi.org/10.1109/TCSVT.2018.2797992
Publication status	Published - 2019 Feb

Bibliographical note

Funding Information:
This work was supported in part by MOTIE (Ministry of Trade, Industry, and Energy) under Grant 10080568

Funding Information:
Manuscript received May 22, 2017; revised September 28, 2017 and December 5, 2017; accepted January 20, 2018. Date of publication January 25, 2018; date of current version February 5, 2019. This work was supported in part by MOTIE (Ministry of Trade, Industry, and Energy) under Grant 10080568, in part by KSRC (Korea Semiconductor Research Consortium) support program for the development of the future semiconductor device, and in part by the Institute for Information and Communications Technology Promotion grant through the Korea government, Development of intelligent semiconductor technology for vision recognition signal processing for vehicle based on multi-sensor fusion, under Grant 2017-0-00721. This paper was recommended by Associate Editor S. Shirani. (Corresponding author: Hyuk-Jae Lee.) The authors are with the Inter-university Semiconductor Research Center, Department of Electrical and Computer, Seoul National University, Seoul 08826, South Korea (e-mail: chlee@capp.snu.ac.kr; hyuk_jae_lee@ capp.snu.ac.kr).

Publisher Copyright:
© 1991-2012 IEEE.

All Science Journal Classification (ASJC) codes

Media Technology
Electrical and Electronic Engineering

Access to Document

10.1109/TCSVT.2018.2797992

Cite this

@article{ebe4b85b51b04658bd25dac5fff32216,

title = "Effective Parallelization of a High-Order Graph Matching Algorithm for GPU Execution",

abstract = "High-order graph matching is a feature-matching algorithm that uses geometric information among features. This algorithm is more robust to repetitive patterns or unclear areas than first-order matching that uses only feature descriptors. However, the processing speed of high-order matching is very slow because of its high computational complexity. To accelerate its speed, this paper proposes a new parallelization algorithm of high-order matching for GPU execution. The obstacle for parallelization is the write collision caused by multiple threads that must simultaneously update the data at the same memory location. In high-order matching, multiple formulations of the objective function can generate the same solution. By taking advantage of this property, the proposed algorithm replaces the operation causing write collision with another operation eliminating the collision while generating the same solution. The proposed algorithm is tested with GTX 960 and takes 31.3 ms, which is 68 times faster than the execution time with a CPU and approximately three times faster than that with a straightforward parallelization for the same GPU.",

author = "Chulhee Lee and Lee, {Hyuk Jae}",

note = "Funding Information: This work was supported in part by MOTIE (Ministry of Trade, Industry, and Energy) under Grant 10080568 Funding Information: Manuscript received May 22, 2017; revised September 28, 2017 and December 5, 2017; accepted January 20, 2018. Date of publication January 25, 2018; date of current version February 5, 2019. This work was supported in part by MOTIE (Ministry of Trade, Industry, and Energy) under Grant 10080568, in part by KSRC (Korea Semiconductor Research Consortium) support program for the development of the future semiconductor device, and in part by the Institute for Information and Communications Technology Promotion grant through the Korea government, Development of intelligent semiconductor technology for vision recognition signal processing for vehicle based on multi-sensor fusion, under Grant 2017-0-00721. This paper was recommended by Associate Editor S. Shirani. (Corresponding author: Hyuk-Jae Lee.) The authors are with the Inter-university Semiconductor Research Center, Department of Electrical and Computer, Seoul National University, Seoul 08826, South Korea (e-mail: chlee@capp.snu.ac.kr; hyuk_jae_lee@ capp.snu.ac.kr). Publisher Copyright: {\textcopyright} 1991-2012 IEEE.",

year = "2019",

month = feb,

doi = "10.1109/TCSVT.2018.2797992",

language = "English",

volume = "29",

pages = "560--571",

journal = "IEEE Transactions on Circuits and Systems for Video Technology",

issn = "1051-8215",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "2",

}

TY - JOUR

T1 - Effective Parallelization of a High-Order Graph Matching Algorithm for GPU Execution

AU - Lee, Chulhee

AU - Lee, Hyuk Jae

N1 - Funding Information: This work was supported in part by MOTIE (Ministry of Trade, Industry, and Energy) under Grant 10080568 Funding Information: Manuscript received May 22, 2017; revised September 28, 2017 and December 5, 2017; accepted January 20, 2018. Date of publication January 25, 2018; date of current version February 5, 2019. This work was supported in part by MOTIE (Ministry of Trade, Industry, and Energy) under Grant 10080568, in part by KSRC (Korea Semiconductor Research Consortium) support program for the development of the future semiconductor device, and in part by the Institute for Information and Communications Technology Promotion grant through the Korea government, Development of intelligent semiconductor technology for vision recognition signal processing for vehicle based on multi-sensor fusion, under Grant 2017-0-00721. This paper was recommended by Associate Editor S. Shirani. (Corresponding author: Hyuk-Jae Lee.) The authors are with the Inter-university Semiconductor Research Center, Department of Electrical and Computer, Seoul National University, Seoul 08826, South Korea (e-mail: chlee@capp.snu.ac.kr; hyuk_jae_lee@ capp.snu.ac.kr). Publisher Copyright: © 1991-2012 IEEE.

PY - 2019/2

Y1 - 2019/2

N2 - High-order graph matching is a feature-matching algorithm that uses geometric information among features. This algorithm is more robust to repetitive patterns or unclear areas than first-order matching that uses only feature descriptors. However, the processing speed of high-order matching is very slow because of its high computational complexity. To accelerate its speed, this paper proposes a new parallelization algorithm of high-order matching for GPU execution. The obstacle for parallelization is the write collision caused by multiple threads that must simultaneously update the data at the same memory location. In high-order matching, multiple formulations of the objective function can generate the same solution. By taking advantage of this property, the proposed algorithm replaces the operation causing write collision with another operation eliminating the collision while generating the same solution. The proposed algorithm is tested with GTX 960 and takes 31.3 ms, which is 68 times faster than the execution time with a CPU and approximately three times faster than that with a straightforward parallelization for the same GPU.

AB - High-order graph matching is a feature-matching algorithm that uses geometric information among features. This algorithm is more robust to repetitive patterns or unclear areas than first-order matching that uses only feature descriptors. However, the processing speed of high-order matching is very slow because of its high computational complexity. To accelerate its speed, this paper proposes a new parallelization algorithm of high-order matching for GPU execution. The obstacle for parallelization is the write collision caused by multiple threads that must simultaneously update the data at the same memory location. In high-order matching, multiple formulations of the objective function can generate the same solution. By taking advantage of this property, the proposed algorithm replaces the operation causing write collision with another operation eliminating the collision while generating the same solution. The proposed algorithm is tested with GTX 960 and takes 31.3 ms, which is 68 times faster than the execution time with a CPU and approximately three times faster than that with a straightforward parallelization for the same GPU.

UR - http://www.scopus.com/inward/record.url?scp=85041009266&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85041009266&partnerID=8YFLogxK

U2 - 10.1109/TCSVT.2018.2797992

DO - 10.1109/TCSVT.2018.2797992

M3 - Article

AN - SCOPUS:85041009266

SN - 1051-8215

VL - 29

SP - 560

EP - 571

JO - IEEE Transactions on Circuits and Systems for Video Technology

JF - IEEE Transactions on Circuits and Systems for Video Technology

IS - 2

M1 - 8269387

ER -

Effective Parallelization of a High-Order Graph Matching Algorithm for GPU Execution

Abstract

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this