Adaptation of algorithms for efficient execution on GPUs

Vadim G. Bulavintsev*, Dmitry D. Zhdanov

*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

44 Downloads (Pure)

Abstract

We propose a generalized method for adapting and optimizing algorithms for efficient execution on modern graphics processing units (GPU). The method consists of several steps. First, build a control flow graph (CFG) of the algorithm. Next, transform the CFG into a tree of loops and merge non-parallelizable loops into parallelizable ones. Finally, map the resulting loops tree to the tree of GPU computational units, unrolling the algorithm's loops as necessary for the match. The method provides a convenient and robust mental framework and strategy for GPU code optimization. We demonstrate the method by adapting a backtracking search algorithm to the GPU platform and building an optimized implementation of the ResNeXt-50 neural network.

Original languageEnglish
Title of host publicationOptical Design and Testing XI
EditorsYongtian Wang, Tina E. Kidger, Osamu Matoba, Rengmao Wu
PublisherSPIE
ISBN (Electronic)9781510646391
DOIs
Publication statusPublished - 2021
EventOptical Design and Testing XI 2021 - Nantong, China
Duration: 10 Oct 202112 Oct 2021

Publication series

NameProceedings of SPIE - The International Society for Optical Engineering
Volume11895
ISSN (Print)0277-786X
ISSN (Electronic)1996-756X

Conference

ConferenceOptical Design and Testing XI 2021
Country/TerritoryChina
CityNantong
Period10/10/2112/10/21

Keywords

  • control ow graph
  • DPLL
  • GPU
  • loop optimization
  • resnet
  • SIMD

Fingerprint

Dive into the research topics of 'Adaptation of algorithms for efficient execution on GPUs'. Together they form a unique fingerprint.

Cite this