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

Chulhee Lee, Hyuk Jae Lee

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


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 languageEnglish
Article number8269387
Pages (from-to)560-571
Number of pages12
JournalIEEE Transactions on Circuits and Systems for Video Technology
Issue number2
Publication statusPublished - 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


Dive into the research topics of 'Effective Parallelization of a High-Order Graph Matching Algorithm for GPU Execution'. Together they form a unique fingerprint.

Cite this