GPU-based Lagrangian heuristic for multidimensional assignment problems with decomposable costs
Natu, Shardul
Loading…
Permalink
https://hdl.handle.net/2142/101117
Description
Title
GPU-based Lagrangian heuristic for multidimensional assignment problems with decomposable costs
Author(s)
Natu, Shardul
Issue Date
2018-02-23
Director of Research (if dissertation) or Advisor (if thesis)
Nagi, Rakesh
Department of Study
Industrial&Enterprise Sys Eng
Discipline
Industrial Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Keyword(s)
Multidimensional assignment problem (MAP)
Linear assignment problem (LAP)
Graphics processing unit (GPU)
Lagrangian relaxation.
Abstract
Multidimensional assignment problem (MAP) is one of the many formulations of data association problem which categorizes data based on various data sources. A higher number of data sources ensures an accurate categorization of data. But it also leads to a significant increase in the amount of data, consequently increasing the computation time where quick results are sought. In this work, we used Lagrangian relaxation technique to solve the MAPs with decomposable costs. But the major contribution was an efficient parallelization of this algorithm on a graphics processing unit (GPU) based programming architecture. Bigger problems with larger data sets were solved by using multiple processors with each having a GPU of its own. This not only handled the data by distributing it among the processors, but also increased the amount of parallelization to give us good iteration times. Problems with 796 million cost variables were solved on varying number of processors between 1 and 64, with significantly fast iteration times. Owing to the good scalability of the developed parallel solver, we successfully solved problems with 31 billion cost variables on processors ranging from 64 to 128 in good amount of time.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
