ПРИМЕНЕНИЕ МЕТОДА ПРОЕКТИРОВАНИЯ Q-ЭФФЕКТИВНЫХ ПРОГРАММ ДЛЯ АЛГОРИТМА ДЕЙКСТРЫ (2023)
Проблема повышения эффективности параллельных вычислений чрезвычайно актуальна. В статье впервые продемонстрировано применение концепции Q-детерминанта для эффективной реализации алгоритма на графах. Концепция Q-детерминанта основана на унифицированном представлении численных алгоритмов в форме Q-детерминанта. Q-детерминант позволяет выразить и оценить внутренний параллелизм алгоритма, а также показать способ его параллельного исполнения. В работе приведены основные понятия концепции Q-детерминанта, необходимые для понимания приведенного исследования. Также описан основанный на концепции Q-детерминанта метод проектирования эффективных программ для численных алгоритмов. Результатом применения метода является программа, полностью использующая ресурс параллелизма алгоритма. Такая программа называется Q-эффективной. В качестве первого применения метода проектирования Q-эффективных программ для алгоритмов на графах описано проектирование программ для реализации алгоритма Дейкстры на параллельных вычислительных системах с общей и распределенной памятью. Приведены также результаты экспериментального исследования разработанных программ, проведенного с помощью суперкомпьютера «Торнадо ЮУрГУ». На основе анализа результатов экспериментального исследования определяются динамические характеристики разработанных программ и выявляются особенности их выполнения. Проведенные в статье исследования дают возможность сделать вывод, что применение концепции Q-детерминанта с целью разработки эффективных программ возможно не только для численных алгоритмов, но и для алгоритмов на графах.
Идентификаторы и классификаторы
- eLIBRARY ID
- 53847227
В настоящее время широко распространены параллельные вычислительные системы (далее — ПВС), к которым относятся, в том числе, персональные компьютеры с многоядерными процессорами. Архитектура ПВС позволяет сократить общее время решения задач с помощью последовательных программ за счет их одновременного выполнения. Однако, подобная организация работы программ во многих случаях не использует все доступные ресурсы вычислительной системы на всем промежутке времени выполнения данных программ. Для дальнейшего ускорения работы необходима разработка параллельных программ, то есть программ, производящих одновременные вычисления на нескольких ядрах или вычислительных узлах, причем эффективных программ, которые имеют наибольшую эффективность по сравнению с программами, выполняющими другие реализации данного алгоритма.
Список литературы
- Dijkstra E.W. A note on two problems in connexion with graphs // Numerische Mathematik. 1959. Vol. 1, no. 1. P. 269-271. DOI: 10.1007/BF01386390
- Алеева В.Н., Алеев Р.Ж. Применение Q-детерминанта численных алгоритмов для параллельных вычислений // Параллельные вычислительные технологии (ПаВТ’2019): Труды международной научной конференции, Калининград, 2-4 апреля 2019. Короткие статьи и описания плакатов. Челябинск: Издательский центр ЮУрГУ, 2019. С. 133-145. EDN: HJNKUZ
- Алеева В.Н. Основные положения технологии Q-эффективного программирования // Наука ЮУрГУ. Секции технических наук: материалы 71-й научной конференции, Челябинск, апрель 2019. Челябинск: Издательский центр ЮУрГУ, 2019. С. 334-342. EDN: YFOCUP
- Алеева В.Н., Шатов М.Б. Применение концепции Q-детерминанта для эффективной реализации численных алгоритмов на примере метода сопряженных градиентов для решения систем линейных уравнений // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. 2021. Т. 10, № 3. С. 56-71. DOI: 10.14529/cmse210304 EDN: PNJEVG
- Aleeva V.N. Improving Parallel Computing Efficiency // Proceedings - 2020 Global SmartIndustry Conference, GloSIC 2020, Chelyabinsk, Russia, November 17-19, 2020. IEEE, 2020. P. 113-120. Article number 9267828. DOI: 10.1109/GloSIC50886.2020.9267828 EDN: WANUZG
- Voevodin V.V., Voevodin Vl.V. The V-Ray technology of optimizing programs to parallel computers // Numerical Analysis and Its Applications. WNAA 1996. Vol. 1196 / ed. by L.G. Vulkov, P. Yalamov, J. Wasniewski. Springer, 1997. P. 546-556. LNCS. DOI: 10.1007/3-540-62598-4_136
- Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 608 с. EDN: SYTPKD
- Voevodin Vl., Antonov A., Dongarra J. AlgoWiki: an Open Encyclopedia of Parallel Algorithmic Features // Supercomputing Frontiers and Innovations. 2015. Vol. 2, no. 1. P. 4-18. DOI: 10.14529/jsfi150101 EDN: UCUUWZ
- Voevodin Vl., Antonov A., Dongarra J. AlgoWiki Project as an Extension of the Top500 Methodology // Supercomputing Frontiers and Innovations. 2018. Vol. 5, no. 1. P. 4-10. DOI: 10.1529/jsfi180101 EDN: XNQPEL
-
Абрамов С.М., Адамович А.И., Коваленко М. Р. Т-система - среда программирования с поддержкой автоматического динамического распараллеливания программ. Пример реализации алгоритма построения изображений методом трассировки лучей // Программирование. 1999. Т. 25, № 2. С. 100-107. EDN: LFIGXL
-
Абрамов С.М., Васенин В.А., Мамчиц Е.Е. и др. Динамическое распараллеливание программ на базе параллельной редукции графов. Архитектура программного обеспечения новой версии Т-системы // Научная сессия МИФИ-2001, 22-26 января 2001: Сборник научных трудов. Т. 2. 2001. С. 234.
-
Malyshkin V.E., Perepelkin V.A., Schukin G.F. Distributed Algorithm of Data Allocation in the Fragmented Programming // Parallel Computing Technologies (PaCT'2015): Proceedings of the 13th International Scientific Conference, Petrozavodsk, Russia, August 31 - September 4, 2015. Proceedings. Vol. 9251 / ed. by V. Malyshkin. Springer, 2015. P. 80-85. LNCS. DOI: 10.1007/978-3-31-21909-7_8
-
Malyshkin V.E., Perepelkin V.A., Tkacheva A.A. Control Flow Usage to Improse Performanse of Fragmented // Parallel Computing Technologies (PaCT'2015): Proceedings of the 13th International Conference, Petrozavodsk, Russia, August 31 - September 4, 2015. Proceedings. Vol. 9251 / ed. by V. Malyshkin. Springer, 2015. P. 86-90. LNCS. DOI: 10.1007/978-3-319-21909-7_9
-
Легалов А.И. Функциональный язык для создания архитектурно-независимых параллельных программ // Вычислительные технологии. 2005. Т. 1, № 10. С. 71-89.
-
Gurieva Y.L., Il'in V.P. On Parallel Computational Technologies of Augmented Domain Decomposition Methods // Parallel Computing Technologies (PaCT'2015): Proceedings of the 13th International Conference, Petrozavodsk, Russia, August 31 - September 4, 2015. Proceedings. Vol. 9251. / ed. by V. Malyshkin. Springer, 2015. P. 35-46. LNCS. DOI: 10.1007/978-3-319-21909-7_4
-
Schlueter M., Munetomo M. Parallelization strategies for evolutionary algorithms for MINLP // IEEE Congress on Evolutionary Computation, Cancun, Mexico, June 23-25, 2013. P. 635-641. DOI: 10.1109/CEC.2013.6557628
-
Wang Q., Liu J., Tang X., et al. Accelerating embarrassingly parallel algorithm on Intel MIC // IEEE International Conference on Progress in Informatics and Computing, Shanghai, China, May 16-18, 2014. P. 213-218. DOI: 10.1109/PIC.2014.6972327 EDN: UQMLSH
-
Li Y., Dou W., Yang K., et al. Optimized Data I/O Strategy of the Algorithm of Parallel Digital Terrain Analysis // 13th International Symposium on Distributed Computing and Applications to Business, Engineering and Science, Xi'an, China, November 24-27, 2014. P. 34-37. DOI: 10.1109/DCABES.2014.10
-
Prifti V., Bala R., Tafa I., et al. The time profit obtained by parallelization of quicksort algorithm used for numerical sorting // Science and Information Conference (SAI), London, UK, July 28-30, 2015. P. 897-901. DOI: 10.1109/SAI.2015.7237248
-
Rajashri A. Parallelization of shortest path algorithm using OpenMP and MPI // International Conference on I-SMAC (IoT in Social, Mobile, Analytics and Cloud) (I-SMAC), Palladam, India, February 10-11, 2017. P. 304-309. DOI: 10.1109/I-SMAC.2017.8058360
-
Fazio M., Buzachis A., Galletta A., et al. A Map-Reduce Approach for the Dijkstra Algorithm in SDN Over Osmotic Computing Systems // International Journal of Parallel Programming. 2021. Vol. 49, no. 3. P. 347-375. DOI: 10.1007/s10766-021-00693-3
-
Zhang W., Zhang L., Chen Y. Asynchronous Parallel Dijkstra's Algorithm on Intel Xeon Phi Processor // International Conference on Algorithms and Architectures for Parallel Processing. 2018. P. 337-357. DOI: 10.1007/978-3-030-05051-1_24
-
Jasika N., Alispahic N., Elma A.,et al. Dijkstra's shortest path algorithm serial and parallel execution performance analysis // 2012 Proceedings of the 35th International Convention MIPRO, Opatija, Croatia, May 21-25, 2012. P. 1811-1815. URL: https://ieeexplore.ieee.org/document/6240942/ (дата обращения: 14.03.2023).
-
Биленко Р.В., Долганина Н.Ю., Иванова Е.В., Рекачинский А.И. Высокопроизводительные вычислительные ресурсы Южно-Уральского государственного университета // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2022. Т. 11, № 1. С. 15-30. DOI: 10.14529/cmse220102 EDN: OLCPUG
-
Алеева В.Н., Зотова П.С., Склезнев Д.С. Расширение возможностей исследования ресурса параллелизма численных алгоритмов с помощью программной Q-системы // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2021. Т. 10, № 2. С. 66-81. DOI: 10.14529/cmse210205 EDN: UJHTDK
-
Aleeva V., Bogatyreva E., Skleznev A., et al. Software Q-system for the Research of the Resource of Numerical Algorithms Parallelism // Supercomputing. Vol. 1129 / ed. by V. Voevodin, S. Sobolev. Springer, 2019. P. 641-652. Communications in Computer and Information Science. DOI: 10.1007/978-3-030-36592-9_52 EDN: HGOKLW
Выпуск
Другие статьи выпуска
Статья является продолжением собственных предыдущих исследований автора в рамках многолетней работы по созданию учебного языка программирования СИНХРО, предназначенного для ознакомления с параллелизмом. Основное направление работ - уточнение понятий, способствующих подготовке небольших многопоточных программ при обучении параллельному программированию. Главный результат последнего года заключается в развитии механизма взаимодействия локальной и общей памяти. Дан приоритет парадигме функционального программирования, популярной при подготовке прототипов многопоточных программ. Это помогло преодолеть зависимость порядка вычислений от последовательности вхождения выражений в текст программы и размещения данных в памяти. Описаны отличия от привычных понятий программирования, сдерживающих решение задач организации параллельных вычислений и предельно распределенных систем из ряда потоков, взаимодействующих в терминах доступа к значениям переменных, возможно расположенных в общей памяти. Повышен базовый уровень воздействий на память. Часть из них укрупнены для предотвращения неожиданностей из-за асинхронности и ослабления императивности элементов распределенных систем. Добавлено понятие команд-двойников для управления императивной синхронизацией взаимодействующих устройств, полезное при решении вопросов освобождения памяти.
В статье описана параллельно-конвейерная реализация решения сеточных уравнений модифицированным попеременно-треугольным итерационным методом (МПТМ), получаемых при численном решенииуравнений математической физики. Наибольшие вычислительные затраты при использовании указанного метода приходятся на этапы решения системы линейных алгебраических уравнений (СЛАУ) с нижнетреугольной и верхнетреугольной матрицами. Представлен алгоритм решения СЛАУ с нижнетреугольной матрицей на графическом ускорителе с использованием технологии NVIDIA CUDA. Для реализациипараллельно-конвейерного метода использовалась трехмерная декомпозиция расчетной области. Она делится по координате y на блоки, количество которых соответствует количеству потоковых мультипроцессоровGPU, задействованных в вычислениях. В свою очередь, блоки разделяются на фрагменты по двум пространственным координатам - x и z. Представленная графовая модель описывает взаимосвязь между соседнимифрагментами расчетной сетки и процессом конвейерного расчета. По результатам проведенных вычислительных экспериментов получена регрессионная модель, описывающая зависимость времени расчета одногошага МПТМ на GPU, вычислены ускорение и эффективность расчетов СЛАУ с нижнетреугольной матрицей параллельно-конвейерным методом на GPU при задействовании различного количества потоковыхмультипроцессоров.
В статье представлены результаты исследований по поиску аномалий в сенсорных данных из различных приложений цифровой индустрии. Рассматриваются временные ряды, полученные при эксплуатации деталей машин, показания датчиков, установленных на металлургическом оборудовании, и показания температурных датчиков в системе умного управления отоплением зданий. Аномалии, найденные в таких данных, свидетельствуют о нештатной ситуации, отказах, сбоях и износе технологического оборудования. Аномалия формализуется как диапазонный диссонанс - подпоследовательность временного ряда, расстояние от которой до ее ближайшего соседа не менее наперед заданного аналитиком порога. Ближайшим соседом данной подпоследовательности является такая подпоследовательность ряда, которая не пересекается с данной и имеет минимальное расстояние до нее. Поиск диссонансов выполняется с помощью параллельного алгоритма для графического процессора, ранее разработанного автором данной статьи. Для визуализации найденных аномалий предложены метод построения тепловой карты диссонансов, имеющих различные длины, и алгоритм нахождения в построенной тепловой карте наиболее значимых диссонансов независимо от их длин.
В статье представлена новая версия масштабируемого итерационного метода линейного программирования, получившего название «апекс-метод». Ключевой особенностью этого метода является построение пути, близкого к оптимальному, на поверхности допустимой области от определенной начальной точки до точного решения задачи линейного программирования. Оптимальный путь - это путь движения по поверхности многогранника в направлении максимального увеличения или уменьшения значения целевой функции в зависимости от того, ee максимум или минимум необходимо найти. Апекс-метод основан на схеме предиктор-корректор и состоит из двух стадий: Quest (предиктор) и Target (корректор). На стадии Quest вычисляется грубое начальное приближение задачи линейного программирования. Основываясь на этом начальном приближении, на стадии Target вычисляется решение задачи линейного программирования с заданной точностью. Основная операция, используемая в апекс-методе, - это операция, которая вычисляет псевдопроекцию, являющуюся обобщением метрической проекции на выпуклое замкнутое множество. Псевдопроекция используется как на стадии Quest, так и на стадии Target. Представлен параллельный алгоритм, использующий фейеровское отображение для вычисления псевдопроекции. Получена аналитическая оценка ресурса параллелизма для этого алгоритма. Также приведен алгоритм, реализующий стадию Target, и доказана его сходимость. Описаны вычислительные эксперименты на кластерной вычислительной системе по применению апекс-метода для решения различных задач линейного программирования.
Издательство
- Издательство
- ЮУрГУ
- Регион
- Россия, Челябинск
- Почтовый адрес
- 454080, Уральский федеральный округ, Челябинская область, г. Челябинск, просп. В.И. Ленина, д. 76
- Юр. адрес
- 454080, Уральский федеральный округ, Челябинская область, г. Челябинск, просп. В.И. Ленина, д. 76
- ФИО
- Александр Рудольфович Вагнер (Ректор)
- E-mail адрес
- admin@susu.ru
- Контактный телефон
- +7 (351) 2635882
- Сайт
- https://www.susu.ru