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

Multidimensional assignment problem (MAP);Linear assignment problem (LAP);Graphics processing unit (GPU);Lagrangian relaxation.

Natu, Shardul ; Nagi ; Rakesh

关键词: Multidimensional assignment problem (MAP);    Linear assignment problem (LAP);    Graphics processing unit (GPU);    Lagrangian relaxation.;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/101117/NATU-THESIS-2018.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

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.