English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper we modify a fast heuristic solver for the Linear Sum AssignmentProblem (LSAP) for use on Graphical Processing Units (GPUs). The motivatingscenario is an industrial application for P2P live streaming that is moderatedby a central node which is periodically solving LSAP instances for assigningpeers to one another. The central node needs to handle LSAP instances involvingthousands of peers in as near to real-time as possible. Our findings aregeneric enough to be applied in other contexts. Our main result is a parallelversion of a heuristic algorithm called Deep Greedy Switching (DGS) on GPUsusing the CUDA programming language. DGS sacrifices absolute optimality infavor of low computation time and was designed as an alternative to classicalLSAP solvers such as the Hungarian and auctioning methods. The contribution ofthe paper is threefold: First, we present the process of trial and error wewent through, in the hope that our experience will be beneficial to adopters ofGPU programming for similar problems. Second, we show the modifications neededto parallelize the DGS algorithm. Third, we show the performance gains of ourapproach compared to both a sequential CPU-based implementation of DGS and aparallel GPU-based implementation of the auctioning algorithm.

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