Top

The Journal of Supercomputing

Published in:

14-06-2016

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

Authors: Andrey Borisenko, Michael Haidl, Sergei Gorlatch

Published in: The Journal of Supercomputing | Issue 2/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

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.

previous article Highly scalable implementation of an implicit matrix-free solver for gas dynamics on GPU-accelerated clusters

next article Optimal dynamic data layouts for 2D FFT on 3D memory integrated FPGA

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Borisenko A, Karpushkin S (2014) Hierarchy of processing equipment configuration design problems for multiproduct chemical plants. J Comput Syst Sci Int 53(3):410–419. doi:10.1134/S1064230714030046 CrossRefMATH

Borisenko A, Kegel P, Gorlatch S (2011) Optimal design of multi-product batch plants using a parallel branch-and-bound method. In: Parallel computing technologies. Lecture notes in computer science, vol 6873. Springer, Berlin, pp 417–430. doi:10.1007/978-3-642-23178-0_36

Boukedjar A, Lalami ME, El Baz D (2012) Parallel branch and bound on a CPU-GPU system. In: PDP, pp 392–398. Citeseer. doi:10.1109/PDP.2012.23

Boyer V, El Baz D, Elkihel M (2012) Solving knapsack problems on GPU. Comput Oper Res 39(1):42–47. doi:10.1016/j.cor.2011.03.014 MathSciNetCrossRefMATH

Chakroun I, Mezmaz M, Melab N, Bendjoudi A (2013) Reducing thread divergence in a gpu-accelerated branch-and-bound algorithm. Concurr Comput Pract Exper 25(8):1121–1136. doi:10.1002/cpe.2931 CrossRef

Fumero Y, Corsano G, Montagna JM (2013) A mixed integer linear programming model for simultaneous design and scheduling of flowshop plants. Appl Math Model 37(4):1652–1664. doi:10.1016/j.apm.2012.04.043 MathSciNetCrossRefMATH

Han TD, Abdelrahman TS (2011) Reducing branch divergence in GPU programs. In: Proceedings of the fourth workshop on general purpose processing on graphics processing units. ACM, New York, p 3. doi:10.1145/1964179.1964184

Hoffman K, Padberg M (2001) Combinatorial and integer optimization. In: Encyclopedia of operations research and management science. Springer, US, pp 94–102. doi:10.1007/1-4020-0611-X_129

Melab N, Chakroun I, Mezmaz M, Tuyttens D (2012) A GPU-accelerated branch-and-bound algorithm for the flow-shop scheduling problem. In: 2012 IEEE international conference on cluster computing (CLUSTER), pp 10–17. IEEE, New York. doi:10.1109/CLUSTER.2012.18

10.

Meyer X, Chopard B, Albuquerque P (2013) A branch-and-bound algorithm using multiple GPU-based LP solvers. In: 2013 20th international conference on high performance computing (HiPC). IEEE, New York, pp 129–138. doi:10.1109/HiPC.2013.6799105

11.

Mokeddem D, Khellaf A (2009) Optimal solutions of multiproduct batch chemical process using multiobjective genetic algorithm with expert decision system. J Anal Meth Chem (2009). doi:10.1155/2009/927426

12.

NVIDIA Corporation (2012) NVIDIA’s next generation CUDA compute architecture: Kepler GK110. http://www.nvidia.com/content/PDF/kepler/NVIDIA-Kepler-GK110-Architecture-Whitepaper.pdf

13.

NVIDIA Corporation (2014) CUDA C programming guide 6.5. http://docs.nvidia.com/cuda/pdf/CUDA_C_Programming_Guide.pdf

14.

Terrazas-Moreno S, Grossmann IE, Wassick JM (2012) A mixed-integer linear programming model for optimizing the scheduling and assignment of tank farm operations. Ind Eng Chem Res 51(18):6441–6454. doi:10.1021/ie202217v CrossRef

15.

Vu TT, Derbel B (2014) Parallel branch-and-bound in multi-core multi-cpu multi-gpu heterogeneous environments. https://hal.inria.fr/hal-01067662

Title: A GPU parallelization of branch-and-bound for multiproduct batch plants optimization
Authors: Andrey Borisenko
Michael Haidl
Sergei Gorlatch
Publication date: 14-06-2016
Publisher: Springer US
Published in: The Journal of Supercomputing / Issue 2/2017
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-016-1784-x

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 2/2017

Multilevel parallelism scheme in a genetic algorithm applied to cardiac models with mass–spring systems

Parallelization efficiency versus stochasticity in simulation reaction–diffusion by cellular automata

P-SEP: a prolong stable election routing algorithm for energy-limited heterogeneous fog-supported wireless sensor networks

CCA: a deadline-constrained workflow scheduling algorithm for multicore resources on the cloud

Optimal dynamic data layouts for 2D FFT on 3D memory integrated FPGA

Gillespie’s Stochastic Simulation Algorithm on MIC coprocessors

Premium Partner