Parallelizing Branch-and-Bound on GPUs for Optimization of Multiproduct Batch Plants

Borisenko A, Haidl M, Gorlatch S

Research article in edited proceedings (conference) | Peer reviewed

Abstract

Parallel implementation of the Branch-and-Bound (B&B)technique for optimization problems is a promising approach to accel-erating their solution, but it remains challenging on Graphics ProcessingUnits (GPUs) due to B&B's irregular data structures and poor computa-tion/communication ratio. The contributions of this paper are as follows:1) we develop two basic implementations (iterative and recursive) of B&Bon systems with GPUs for a practical application scenario - optimal de-sign of multi-product batch plants; 2) we propose and implement severaloptimizations of our CUDA code using both algorithmic techniques ofreducing branch divergence and GPU-specific properties of the memoryhierarchy; and 3) we evaluate our implementations and optimizations ona modern GPU-based system and we report our experimental results.

Details about the publication

PublisherSpringer
Book titleParallel Computing Technologies
Page range324-337
Publishing companySpringer
Place of publicationCham
Title of seriesLecture Notes in Computer Science (ISSN: 978-3-319-21909-7)
Volume of series9251
StatusPublished
Release year2015
Language in which the publication is writtenEnglish
Conference13th International Conference on Parallel Computing Technologies, Petrozavodsk, Russia
ISBN978-3-319-21908-0
DOI10.1007/978-3-319-21909-7_33
KeywordsGPU computing; CUDA; branch-and-bound; combinatorial optimization; multi-product batch plant design

Authors from the University of Münster

Gorlatch, Sergei
Professur für Praktische Informatik (Prof. Gorlatch)
Haidl, Michael
Professur für Praktische Informatik (Prof. Gorlatch)