|
Article information
2015 , Volume 20, ¹ 4, p.17-28
Borisenko A.B., Karpushkin S.V.
Using of OpenMP for optimal choice of process equipment for multiproduct batch plants
In this work, we parallelize the Branch-and-Bound (B&B) algorithm and illustrate it with a practical application - the optimal selection of equipment for multi-product batch plants. We develop and evaluate an implementation of the parallel B&B method on a multicore system with shared memory using C++ programming language and OpenMP version 3.0 (Open Multi-Processing) for the task-based approach. To limit the degree of parallelism to a certain level of the tree we introduce a granularity parameter G: subtrees below the granularity level are not split into tasks but rather processed sequentially. We conducted our runtime experiments on a computer consisting of 4 CPUs with the total of 32 cores. We analyzed the impact of the degree of parallelism controlled by the granularity parameter on the runtime and show the analysis for speedup and efficiency of the processors’ usage. Selecting a suitable granularity value is crucial for optimal performance, but with a large number of tasks we may not have enough memory. It happends when G > 10 in our case. Implementation of our algorithm has near-linear speedup and provide high parallel scalability. Efficiency of processors’ usage is shown to be 0.9 - 0.95.
[full text]
Keywords: Discrete optimization, parallel branch-and-bound method, OpenMP, multiproduct batch plants, choice of process equipment
Author(s):
Borisenko Andrey Borisovich
PhD. , Associate Professor
Office: Tambov State Technical University
Address: 392000, Russia, Tambov, Sovetskaya Str. 106
Phone Office: (4752) 630706
E-mail: borisenko@mail.gaps.tstu.ru
Karpushkin Sergey Viktorovich
Dr. , Professor
Position: Professor
Office: Tambov State Technical University
Address: 392000, Russia, Tambov, Sovetskaya Str. 106
Phone Office: (4752) 630706
E-mail: karp@mail.gaps.tstu.ru
References:
[1] Borisenko, A.B., Karpushkin, S.V. Hierarchy of processing equipment configuration design problems for multiproduct chemical plantsž. Journal of Computer and Systems Sciences International. 2014; 53(3):410–419.
[2] Karpushkin, S.V., Krasnyansky, M.N., Borisenko, A.B. Method for choosing of engineering systems’ main apparatuses when designing of multi-product chemical plants. Pt I. Statements of tasks and scheme of their joint decision. Information Technologies in Design and Production. 2012; (3):52–58. (In Russ.)
[3] Karpushkin, S.V., Krasnyansky, M.N., Borisenko, A.B. Modernization of operating multi-product plant’s chemical-technological systems in case of products turnout plan’s variation. KHIMICHESKAYA PROMYSHLENNOST’ segodnya. 2012; (1):26–32. (In Russ.)
[4] Karpushkin, S.V., Krasnyansky, M.N., Borisenko, A.B. Technique of the estimation of efficiency of hardware registration of himiko-technological systems of poliassoprtiment manufactures. Information Systems and Technologies. 2011; 5(67):96–105. (In Russ.)
[5] Ponsich, A., Azzaro-Pantel, C., Domenech, S., Pibouleau, L. Mixed-integer nonlinear programming optimization strategies for batch plant design problems. Industrial & Engineering Chemistry Research. 2007; 46(3):854–863.
[6] Hamzaoui, Y.E., Hernandez, J.A., Cruz-Chavez, M.A., Bassam, A. Search for optimal design of multiproduct batch plants under uncertain demand using gaussian process modeling solved by heuristics methods. Chemical Product and Process Modeling. 2010; 5(1):1934–2659.
[7] Malygin, E.N., Karpushkin, S.V., Borisenko, A.B. Procedure for determination of multiproduct chemical-engineering systems equipment. Himicheskaya Promyshlennost’ segodnya. 2003; (5):43–50. (In Russ.)
[8] Leyffer, S., Linderoth, J., Luedtke, J., Miller, A., Munson, T. Applications and algorithms for mixed integer nonlinear programming. Journal of Physics: Conference Series. 2009; 180(1):12–14.
[9] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms, 3rd Edition. MIT Press; 2009: 1312.
[10] Sparrow, R.E., Forder, G.J., Rippin, D.W.T. The choice of equipment sizes for multiproduct batch plants. Heuristics vs. branch and bound. Industrial & Engineering Chemistry Process Design and Development. 1975; 14(3):197–203.
[11] Borisenko, A.B., Karpushkin, S.V. Application of branch-and-bound method for optimal selection of process equipment of chemical-engineering systems. Computational Technologies. 2012; 17(1):35–43. (In Russ.)
[12] Borisenko, A.B., Kutuzov, D.V., Osovskiy, A.V. Application of parallel computing for the calculation of hardware design of chemical-technological systems. Transactions of the TSTU. 2011; 17(2):493–496. (In Russ.)
[13] Borisenko, A.B., Karpushkin, S.V. Parallel algorithm for optimal process equipment selection of multiproduct batch plants. Applied Informatics. 2013; 45(3):56–68. (In Russ.)
[14] Message Passing Interface Forum. Official MPI (Message Passing Interface) standards documents, errata. Available at: http://www.mpi-forum.org/
[15] Timoshevskaya, N.E. Parallel methods for tree traverse. Matematicheskoe Modelirovanie. 2004; 16(1):105–114. (In Russ.)
[16] OpenMP Architecture Review Board. The OpenMP API Specification for Parallel Programming. Available at: http://www.openmp.org/
[17] Malygin, E.N., Karpushkin, S.V., Borisenko, A.B. A Mathematical model of the functioning of multiproduct chemical engineering systems. Theoretical Foundations of Chemical Engineering. 2005; 39(4):429–439.
[18] Knuth, D.E. The Art of Computer Programming. Volume 1: Fundamental Algorithms, 3rd Edition. Massachusetts: Addison Wesley; 1997: 650.
[19] Intel Developer Zone. Using Tasks Instead of Threads. Available at:https://software.intel.com/ sites/default/files/m/d/4/1/d/8/1-6-AppThr_Using_Tasks_Instead_of_Threads.pdf
Bibliography link:
Borisenko A.B., Karpushkin S.V. Using of OpenMP for optimal choice of process equipment for multiproduct batch plants // Computational technologies. 2015. V. 20. ¹ 4. P. 17-28
|
