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

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

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

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

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

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

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

Еще

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

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

IDR: 147233188   |   DOI: 10.14529/cmse190102

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

  • 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