Files in this item



application/pdfNATU-THESIS-2018.pdf (2MB)
(no description provided)PDF


Title:GPU-based Lagrangian heuristic for multidimensional assignment problems with decomposable costs
Author(s):Natu, Shardul
Advisor(s):Nagi, Rakesh
Department / Program:Industrial&Enterprise Sys Eng
Discipline:Industrial Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(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.
Issue Date:2018-02-23
Rights Information:Copyright 2018 Shardul Natu
Date Available in IDEALS:2018-09-04
Date Deposited:2018-05

This item appears in the following Collection(s)

Item Statistics