A GPU parallelization of branch-and-bound for multiproduct batch plants optimization

详细信息    查看全文

• 作者：Andrey Borisenko ; Michael Haidl ; Sergei Gorlatch
• 关键词：GPU computing ; CUDA ; Parallel branch ; and ; bound ; Combinatorial optimization ; Multi ; product batch plant design
• 刊名：The Journal of Supercomputing
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：73
• 期：2
• 页码：639-651
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Programming Languages, Compilers, Interpreters; Processor Architectures; Computer Science, general;
• 出版者：Springer US
• ISSN：1573-0484
• 卷排序：73

文摘

Branch-and-bound (B&B) is a popular approach to accelerate the solution of the optimization problems, but its parallelization on graphics processing units (GPUs) is challenging because of B&B’s irregular data structures and poor computation/communication ratio. The contributions of this paper are as follows: (1) we develop two CUDA-based implementations (iterative and recursive) of B&B on systems with GPUs for a practical application scenario—optimal design of multi-product batch plants, with a particular example of a chemical-engineering system (CES); (2) we propose and implement several optimizations of our CUDA code by reducing branch divergence and by exploiting the properties of the GPU memory hierarchy; and(3) we evaluate our implementations and their optimizations on a modern GPU-based system and we report our experimental results.