Научные статьи \ Математика. Естественные науки \ Математика \ Вычислительная математика. Численный анализ

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

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

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

Журнал: Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика @vestnik-susu-cmi

Статья в выпуске: 1 т.8, 2019 года.

Бесплатный доступ

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

Еще

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

Короткий адрес: https://sciup.org/147233188

IDR: 147233188   |   УДК: 519.688,   |   DOI: 10.14529/cmse190102

Scalability evaluation of Cimmino algorithm for solving systems of linear inequalities on cluster computing systems

The paper is devoted to a scalability study of Cimmino algorithm for linear inequality systems. This algorithm belongs to the class of iterative projection algorithms. For the analytical analysis of the scalability, the BSF (Bulk Synchronous Farm) parallel computation model is used. An implementation of the Cimmino algorithm in the form of operations on lists using higher-order functions Map and Reduce is presented. An analytical estimation of the upper scalability bound of the algorithm for cluster computing systems is derived. Information about the implementation of Cimmino algorithm on lists in C++ language using the BSF program skeleton and MPI parallel programming library is given. The results of large-scale computational experiments performed on a cluster computing system are demonstrated. A conclusion about the adequacy of the analytical estimations by comparing them with the results of computational experiments is made.

Еще

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

  • 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
  • Соколинская И.М., Соколинский Л.Б. О решении задачи линейного программирования в эпоху больших данных//Параллельные вычислительные технологии -XI международная конференция (ПаВТ'2017): Короткие статьи и описания плакатов (Казань, 3-7 апреля 2017 г.). Челябинск: Издательский центр ЮУрГУ, 2017. С. 471-484. URL: http://omega.sp.susu.ru/pavt2017/short/014.pdf.
  • 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. P. 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. P. 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/ed. Palta J.R., Mackie T.R. Madison, WI: Medical Physics Publishing, 2003. P. 25-49. DOI: 10.1118/1.1628279
  • Agmon S. The relaxation method for linear inequalities//Canadian Journal of Mathematics. 1954. Vol. 6. P. 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. P. 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. P. 326-333.
  • Benzi M. Gianfranco Cimmino's Contributions to Numerical Mathematics//Atti del SemiSeminario di Analisi Matematica, Dipartimento di Matematica dell'Universit`a di Bologna (Ciclo di Conferenze in Ricordo di Gianfranco Cimmino, 2004). Bologna, Italy: Tecnoprint, 2005. P. 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. P. 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)/ed. Censor Y., Ding M. International Society for Optics and Photonics, 2001. P. 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. P. 1150-1158.
  • DOI: 10.1007/978-0-38709766-4_218
  • JaJa J.F. PRAM (Parallel Random Access Machines)//Encyclopedia of Parallel Computing. Boston, MA: Springer US, 2011. P. 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. P. 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. P. 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. P. 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. P. 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. P. 4880-4896.
  • DOI: 10.1002/cpe.3475
  • Ежова Н.А., Соколинский Л.Б. BSF: модель параллельных вычислений для многопроцессорных систем с распределенной памятью//Параллельные вычислительные технологии -XII международная конференция (ПаВТ'2018): Короткие статьи и описания плакатов (Ростов-на-Дону, 2-6 апреля 2018 г.). Челябинск: Издательский центр ЮУрГУ, 2018. С. 253-265. URL: http://omega.sp.susu.ru/pavt2018/short/001.pdf.
  • Sokolinskaya I., Sokolinsky L.B. Scalability evaluation of the NSLP algorithm for solving non-stationary linear programming problems on cluster computing systems//Суперкомпьютерные дни в России: Труды международной конференции (Москва, 25-26 сентября 2017 г.). М.: Изд-во МГУ, 2017. С. 319-332. URL: http://russianscdays.org/files/pdf17/319.pdf.
  • Cole M.I. Parallel programming with list homomorphisms//Parallel Processing Letters. 1995. Vol. 5, No. 2. P. 191-203.
  • DOI: 10.1142/S0129626495000175
  • Соколинская И.М., Соколинский Л.Б. Модифицированный следящий алгоритм для решения нестационарных задач линейного программирования на кластерных вычислительных системах с многоядерными ускорителями//Суперкомпьютерные дни в России: труды международной конференции (Москва, 26-27 сентября 2016 г.). М.: Изд-во МГУ, 2016. C. 294-306. URL: http://2016.russianscdays.org/files/pdf16/294.pdf.
  • 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. P. 561-573.
Еще
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp