GPU-Based Heuristic Solver for Linear Sum Assignment Problems Under Real-time Constraints

Details GPU-Based Heuristic Solver for Linear Sum Assignment Problems Under Real-time Constraints GPU-Based Heuristic Solver for Linear Sum Assignment Problems Under Real-time Constraints

2011-06-28

arxiv.org/abs/1106.5694v2

Computer Science

Distributed, Parallel, and Cluster Computing

White Paper, Peerialism Inc. (www.peerialism.com)

Scientific paper

In this paper we modify a fast heuristic solver for the Linear Sum Assignment Problem (LSAP) for use on Graphical Processing Units (GPUs). The motivating scenario is an industrial application for P2P live streaming that is moderated by a central node which is periodically solving LSAP instances for assigning peers to one another. The central node needs to handle LSAP instances involving thousands of peers in as near to real-time as possible. Our findings are generic enough to be applied in other contexts. Our main result 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 low computation time and was designed as an alternative to classical LSAP solvers such as the Hungarian and auctioning methods. The contribution of the paper is threefold: First, we present the process of trial and error we went through, in the hope that our experience will be beneficial to adopters of GPU programming for similar problems. Second, we show the modifications needed to parallelize the DGS algorithm. Third, we show the performance gains of our approach compared to both a sequential CPU-based implementation of DGS and a parallel GPU-based implementation of the auctioning algorithm.

Affiliated with

Also associated with

No associations

Rating

GPU-Based Heuristic Solver for Linear Sum Assignment Problems Under Real-time Constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with GPU-Based Heuristic Solver for Linear Sum Assignment Problems Under Real-time Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and GPU-Based Heuristic Solver for Linear Sum Assignment Problems Under Real-time Constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-41697