Change search
ReferencesLink to record
Permanent link

Direct link
A GPU-enabled solver for time-constrained linear sum assignment problems
RISE, Swedish ICT, SICS. RISE, Swedish ICT, SICS, Computer Systems Laboratory.
Show others and affiliations
Number of Authors: 5
2010 (English)Conference paper (Refereed)
Abstract [en]

This paper deals with solving large instances of the Linear Sum Assignment Problems (LSAPs) under realtime constraints, using Graphical Processing Units (GPUs). The motivating scenario is an industrial application for P2P live streaming that is moderated by a central tracker that is periodically solving LSAP instances to optimize the connectivity of thousands of peers. However, our findings are generic enough to be applied in other contexts. Our main contribution is a parallel version of a heuristic algorithm called Deep Greedy Switching (DGS) on GPUs using the CUDA programming language. DGS sacrifices absolute optimality in favor of a substantial speedup in comparison to classical LSAP solvers like the Hungarian and auctioning methods. We show the modifications needed to parallelize the DGS algorithm and the performance gains of our approach compared to a sequential CPU-based implementation of DGS and a mixed CPU/GPU-based implementation of it.

Place, publisher, year, edition, pages
2010, 16. 1-6 p.
National Category
Computer and Information Science
URN: urn:nbn:se:ri:diva-23806OAI: diva2:1042883
Informatics and Systems (INFOS), 2010 The 7th International Conference.
Available from: 2016-10-31 Created: 2016-10-31

Open Access in DiVA

fulltext(180 kB)8 downloads
File information
File name FULLTEXT01.pdfFile size 180 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links


Search in DiVA

By author/editor
Haridi, Seif
By organisation
SICSComputer Systems Laboratory
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 8 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 4 hits
ReferencesLink to record
Permanent link

Direct link