Исследование масштабируемости алгоритма Чиммино для решения систем линейных неравенств на кластерных вычислительных системах

Ирина Михайловна Соколинская, Леонид Борисович Соколинский

Аннотация


Работа посвящена исследованию масштабируемости алгоритма Чиммино для решения систем неравенств. Данный алгоритм является типичным представителем класса итерационных проекционных алгоритмов для решения систем линейных уравнений и неравенств. Для аналитического анализа масштабируемости используется модель параллельных вычислений BSF (Bulk Synchronous Farm). Дается представление алгоритма Чиммино в виде операций над списками с использованием функций высшего порядка Map и Reduce. Выводятся аналитические оценки верхней границы масштабируемости алгоритма для многопроцессорных вычислительных систем с распределенной памятью. Приводятся данные о реализация алгоритма Чиммино над списками на языке С++ с использованием программного шаблона BSF и библиотеки параллельного программирования MPI. Демонстрируются результаты масштабных вычислительных экспериментов, выполненных на кластерной вычислительной системе. На основе экспериментальных результатов дается анализ адекватности оценок, полученных аналитическим путем с помощью стоимостных метрик модели BSF.

Ключевые слова


алгоритм Чиммино, система линейных неравенств, итерационный алгоритм, проекционный алгоритм, релаксация, модель параллельных вычислений BSF, оценка масштабируемости, эффективность распараллеливания, кластерные вычислительные системы

Полный текст:

PDF

Литература


Cottle R.W., Pang J.-S., Stone R.E. The Linear Complementarity Problem. Society for Industrial and Applied Mathematics, 2009. xxiv + 757 p. DOI: 10.1137/1.9780898719000

Sokolinskaya I., Sokolinsky L.B. On the Solution of Linear Programming Problems in the Age of Big Data. Parallel Computational Technologies. PCT 2017. Communications in Computer and Information Science. Springer, 2017. vol. 753. pp. 86–100. DOI: 10.1007/978-3-319-67035-5_7

Censor Y. et al. On Diagonally Relaxed Orthogonal Projection Methods. SIAM Journal on Scientific Computing. Society for Industrial and Applied Mathematics, 2008. vol. 30, no. 1. pp. 473–504. DOI: 10.1137/050639399

Zhu J., Li X. The Block Diagonally-Relaxed Orthogonal Projection Algorithm for Compressed Sensing Based Tomography. 2011 Symposium on Photonics and Optoelectronics (SOPO). IEEE, 2011. pp. 1–4. DOI: 10.1109/SOPO.2011.5780660

Censor Y. Mathematical optimization for the inverse problem of intensity-modulated radiation therapy. Intensity-Modulated Radiation Therapy: The State of the Art. WI: Medical Physics Publishing, 2003. pp. 25–49. DOI: 10.1118/1.1628279

Agmon S. The relaxation method for linear inequalities. Canadian Journal of Mathematics. 1954. vol. 6. pp. 382–392. DOI: 10.4153/CJM-1954-037-2

Motzkin T.S., Schoenberg I.J. The relaxation method for linear inequalities. Canadian Journal of Mathematics. 1954. vol. 6. pp. 393–404. DOI: 10.4153/CJM-1954-038-x

Cimmino G. Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari. La Ricerca Scientifica, XVI, Series II, Anno IX, 1. 1938. pp. 326–333.

Benzi M. Gianfranco Cimmino’s Contributions to Numerical Mathematics. Atti del Semi-Seminario di Analisi Matematica, Dipartimento di Matematica dell’Universit`a di Bologna (Ciclo di Conferenze in Ricordo di Gianfranco Cimmino, 2004). Bologna, Italy: Tecnoprint, 2005. pp. 87–109.

Censor Y., Zenios S.A. Parallel Optimization: Theory, Algorithms, and Applications. New York: Oxford University Press, 1997.

Censor Y., Elfving T. New methods for linear inequalities. Linear Algebra and its Applications. North-Holland, 1982. vol. 42. pp. 199–211. DOI: 10.1016/0024-3795(82)90149-5

Censor Y. Sequential and parallel projection algorithms for feasibility and optimization. Proc. SPIE 4553, Visualization and Optimization Techniques, (25 September 2001). Society for Optics and Photonics, 2001. pp. 1–9. DOI: 10.1117/12.441550

Kelley C.T. Iterative Methods for Linear and Nonlinear Equations. Philadelphia: Society for Industrial and Applied Mathematics, 1995. xiii + 156 p. DOI: 10.1137/1.9781611970944

Bilardi G., Pietracaprina A. Models of Computation, Theoretical. Encyclopedia of Parallel Computing. Boston, MA: Springer US, 2011. pp. 1150–1158. DOI: 10.1007/978-0-387-09766-4_218

JaJa J.F. PRAM (Parallel Random Access Machines). Encyclopedia of Parallel Computing. Boston, MA: Springer US, 2011. pp. 1608–1615. DOI: 10.1007/978-0-387-09766-4_23

Valiant L.G. A bridging model for parallel computation. Communications of the ACM. 1990. vol. 33, no. 8. pp. 103–111. DOI: 10.1145/79173.79181

Culler D. et al. LogP: towards a realistic model of parallel computation. Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, PPOPP ’93. New York, New York, USA: ACM Press, 1993. pp. 1–12. DOI: 10.1145/155332.155333

Forsell M., Leppänen V. An extended PRAM-NUMA model of computation for TCF programming. Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2012. Washington, DC, USA: IEEE Computer Society, 2012. pp. 786–793. DOI: 10.1109/IPDPSW.2012.97

Gerbessiotis A. V. Extending the BSP model for multi-core and out-of-core computing: MBSP. Parallel Computing. Elsevier B.V., 2015. vol. 41. pp. 90–102. DOI: 10.1016/j.parco.2014.12.002

Lu F., Song J., Pang Y. HLognGP: A parallel computation model for GPU clusters. Concurrency and Computation: Practice and Experience. 2015. vol. 27, no. 17. pp. 4880–4896. DOI: 10.1002/cpe.3475

Sokolinsky L.B. Analytical Estimation of the Scalability of Iterative Numerical Algorithms on Distributed Memory Multiprocessors. Lobachevskii Journal of Mathematics. 2018. vol. 39, no. 4. pp. 571–575. DOI: 10.1134/S1995080218040121

Sokolinskaya I., Sokolinsky L.B. Scalability Evaluation of NSLP Algorithm for Solving Non-Stationary Linear Programming Problems on Cluster Computing Systems. Supercomputing. RuSCDays 2017. Communications in Computer and Information Science. Cham: Springer, 2017. vol. 793. pp. 40–53. DOI: 10.1007/978-3-319-71255-0_4

Cole M.I. Parallel programming with list homomorphisms. Parallel Processing Letters. 1995. vol. 5, no. 2. pp. 191–203. DOI: 10.1142/S0129626495000175

Sokolinskaya I., Sokolinsky L. Revised Pursuit Algorithm for Solving Non-stationary Linear Programming Problems on Modern Computing Clusters with Manycore Accelerators. Supercomputing. RuSCDays 2016. Communications in Computer and Information Science. Cham: Springer, 2016. vol. 687. pp. 212–223. DOI: 10.1007/978-3-319-55669-7_17

Kostenetskiy P.S., Safonov A.Y. SUSU Supercomputer Resources. Proceedings of the 10th Annual International Scientific Conference on Parallel Computing Technologies (PCT 2016). CEUR Workshop Proceedings. 2016. vol. 1576. pp. 561–573.




DOI: http://dx.doi.org/10.14529/cmse190102