GPU-accelerated Lagrangian heuristic for multidimensional assignment problems with decomposable costs

Shardul Natu; Ketan Date; Rakesh Nagi

doi:10.1016/j.parco.2020.102666

GPU-accelerated Lagrangian heuristic for multidimensional assignment problems with decomposable costs

Shardul Natu, Ketan Date, Rakesh Nagi

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

Abstract

In this paper, we describe a GPU-accelerated parallel algorithm for the axial Multidimensional Assignment Problem with Decomposable Costs (MDADC), which is one of the most fundamental formulations for data association. MDADC is known to be NP-hard and is large-dimensioned in most realistic cases; hence, heuristic solutions with qualified optimality gaps is the best one can hope for, given the state-of-knowledge. The main contribution of this paper is an efficient parallelization of the Lagrangian subgradient search algorithm specifically targeted towards the Graphics Processing Units (GPUs) based on the NVIDIA Compute Unified Device Architecture (CUDA). A GPU-accelerated Linear Assignment Problem (LAP) solver is leveraged in concert with the Lagrangian scheme for further speed-up. We also implemented a multi-GPU variant of this algorithm which maintains a good speedup profile, when tested on problems with 31 billion variables, on up to 128 GPUs.

Original language	English (US)
Article number	102666
Journal	Parallel Computing
Volume	97
DOIs	https://doi.org/10.1016/j.parco.2020.102666
State	Published - Sep 2020

Keywords

CUDA
Graphics processing unit
Lagrangian heuristic
Multi-dimensional assignment problem
Parallel algorithm

ASJC Scopus subject areas

Software
Theoretical Computer Science
Hardware and Architecture
Computer Networks and Communications
Computer Graphics and Computer-Aided Design
Artificial Intelligence

Online availability

10.1016/j.parco.2020.102666

Library availability

Discover UIUC Full Text

Cite this

@article{3b240bbed4fd4f37b5d44ad8717009b9,

title = "GPU-accelerated Lagrangian heuristic for multidimensional assignment problems with decomposable costs",

abstract = "In this paper, we describe a GPU-accelerated parallel algorithm for the axial Multidimensional Assignment Problem with Decomposable Costs (MDADC), which is one of the most fundamental formulations for data association. MDADC is known to be NP-hard and is large-dimensioned in most realistic cases; hence, heuristic solutions with qualified optimality gaps is the best one can hope for, given the state-of-knowledge. The main contribution of this paper is an efficient parallelization of the Lagrangian subgradient search algorithm specifically targeted towards the Graphics Processing Units (GPUs) based on the NVIDIA Compute Unified Device Architecture (CUDA). A GPU-accelerated Linear Assignment Problem (LAP) solver is leveraged in concert with the Lagrangian scheme for further speed-up. We also implemented a multi-GPU variant of this algorithm which maintains a good speedup profile, when tested on problems with 31 billion variables, on up to 128 GPUs.",

keywords = "CUDA, Graphics processing unit, Lagrangian heuristic, Multi-dimensional assignment problem, Parallel algorithm",

author = "Shardul Natu and Ketan Date and Rakesh Nagi",

note = "Funding Information: Numerical testing of this work was done using the resources from the Blue Waters sustained-petascale computing project, which is supported by the National Science Foundation (awards OCI-0725070and ACI-1238993) and the state of Illinois. Blue Waters is a joint effort of the University of Illinois at Urbana-Champaign and its National Center for Supercomputing Applications. We gratefully appreciate this support. The authors would also like to thank the associate editor and the anonymous referees for providing thorough review comments which helped improve the exposition of this paper. Funding Information: Numerical testing of this work was done using the resources from the Blue Waters sustained-petascale computing project, which is supported by the National Science Foundation (awards OCI-0725070 and ACI-1238993 ) and the state of Illinois. Blue Waters is a joint effort of the University of Illinois at Urbana-Champaign and its National Center for Supercomputing Applications. We gratefully appreciate this support. The authors would also like to thank the associate editor and the anonymous referees for providing thorough review comments which helped improve the exposition of this paper. Publisher Copyright: {\textcopyright} 2020 Elsevier B.V.",

year = "2020",

month = sep,

doi = "10.1016/j.parco.2020.102666",

language = "English (US)",

volume = "97",

journal = "Parallel Computing",

issn = "0167-8191",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - GPU-accelerated Lagrangian heuristic for multidimensional assignment problems with decomposable costs

AU - Natu, Shardul

AU - Date, Ketan

AU - Nagi, Rakesh

N1 - Funding Information: Numerical testing of this work was done using the resources from the Blue Waters sustained-petascale computing project, which is supported by the National Science Foundation (awards OCI-0725070and ACI-1238993) and the state of Illinois. Blue Waters is a joint effort of the University of Illinois at Urbana-Champaign and its National Center for Supercomputing Applications. We gratefully appreciate this support. The authors would also like to thank the associate editor and the anonymous referees for providing thorough review comments which helped improve the exposition of this paper. Funding Information: Numerical testing of this work was done using the resources from the Blue Waters sustained-petascale computing project, which is supported by the National Science Foundation (awards OCI-0725070 and ACI-1238993 ) and the state of Illinois. Blue Waters is a joint effort of the University of Illinois at Urbana-Champaign and its National Center for Supercomputing Applications. We gratefully appreciate this support. The authors would also like to thank the associate editor and the anonymous referees for providing thorough review comments which helped improve the exposition of this paper. Publisher Copyright: © 2020 Elsevier B.V.

PY - 2020/9

Y1 - 2020/9

N2 - In this paper, we describe a GPU-accelerated parallel algorithm for the axial Multidimensional Assignment Problem with Decomposable Costs (MDADC), which is one of the most fundamental formulations for data association. MDADC is known to be NP-hard and is large-dimensioned in most realistic cases; hence, heuristic solutions with qualified optimality gaps is the best one can hope for, given the state-of-knowledge. The main contribution of this paper is an efficient parallelization of the Lagrangian subgradient search algorithm specifically targeted towards the Graphics Processing Units (GPUs) based on the NVIDIA Compute Unified Device Architecture (CUDA). A GPU-accelerated Linear Assignment Problem (LAP) solver is leveraged in concert with the Lagrangian scheme for further speed-up. We also implemented a multi-GPU variant of this algorithm which maintains a good speedup profile, when tested on problems with 31 billion variables, on up to 128 GPUs.

AB - In this paper, we describe a GPU-accelerated parallel algorithm for the axial Multidimensional Assignment Problem with Decomposable Costs (MDADC), which is one of the most fundamental formulations for data association. MDADC is known to be NP-hard and is large-dimensioned in most realistic cases; hence, heuristic solutions with qualified optimality gaps is the best one can hope for, given the state-of-knowledge. The main contribution of this paper is an efficient parallelization of the Lagrangian subgradient search algorithm specifically targeted towards the Graphics Processing Units (GPUs) based on the NVIDIA Compute Unified Device Architecture (CUDA). A GPU-accelerated Linear Assignment Problem (LAP) solver is leveraged in concert with the Lagrangian scheme for further speed-up. We also implemented a multi-GPU variant of this algorithm which maintains a good speedup profile, when tested on problems with 31 billion variables, on up to 128 GPUs.

KW - CUDA

KW - Graphics processing unit

KW - Lagrangian heuristic

KW - Multi-dimensional assignment problem

KW - Parallel algorithm

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

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

U2 - 10.1016/j.parco.2020.102666

DO - 10.1016/j.parco.2020.102666

M3 - Article

AN - SCOPUS:85087084470

SN - 0167-8191

VL - 97

JO - Parallel Computing

JF - Parallel Computing

M1 - 102666

ER -

GPU-accelerated Lagrangian heuristic for multidimensional assignment problems with decomposable costs

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this