АВТОМАТИЗИРОВАННОЕ ПРОЕКТИРОВАНИЕ И ИСПОЛНЕНИЕ ЭФФЕКТИВНЫХ ПРОГРАММ ДЛЯ ЧИСЛЕННЫХ АЛГОРИТМОВ (2023)
Проектировать эффективные параллельные программы для многопроцессорных архитектур сложно, так как нет четких формальных правил, которых необходимо придерживаться. Для решения этой проблемы при реализации численных алгоритмов может применяться концепция Q-детерминанта. Данная теория позволяет проводить автоматизированный анализ ресурса параллелизма алгоритма, автоматизированное сравнение ресурсов параллелизма алгоритмов, решающих одну и ту же алгоритмическую проблему, проектировать эффективные программы для реализации алгоритмов с помощью специально разработанного метода проектирования, повысить эффективность реализации численных методов и алгоритмических проблем. Результаты, полученные на основе концепции Q-детерминанта, представляют собой один из вариантов решения проблемы эффективной реализации численных алгоритмов, методов и алгоритмических проблем на параллельных вычислительных системах. Однако пока остается не решенной фундаментальная проблема автоматизированного проектирования и исполнения для любого численного алгоритма программы, реализующей алгоритм эффективно. В статье описана разработка единой для численных алгоритмов программной системы проектирования и исполнения Q-эффективных программ - эффективных программ, спроектированных с помощью концепции Q-детерминанта. Система предназначена для использования на параллельных вычислительных системах с общей памятью. Она состоит из компилятора и виртуальной машины. Компилятор преобразует представление алгоритма в форме Q-детерминанта в исполняемую программу, использующую ресурс параллелизма алгоритма полностью. Виртуальная машина исполняет программу, полученную с помощью компилятора. В статье также приведено экспериментальное исследование созданной программной системы с применением суперкомпьютера «Торнадо ЮУрГУ».
Идентификаторы и классификаторы
В сфере высокопроизводительных вычислений одним из ведущих ученых мира является Джек Донгарра (Jack Dongarra). На протяжении десятков лет производительность вычислительной техники росла в соответствии с законом Мура [25]. И если большинство программных средств не поспевало за аппаратными достижениями, то программное обеспечение высокопроизводительных вычислений справлялось с этим успешно. Во многом это объясняется использованием алгоритмов Дж. Донгарры. В университете Теннесси для поддержки библиотеки матрично-векторных операций DPLASMA [22] научным коллективом с участием Дж. Донгарры развивается подход к конструированию и исполнению параллельных программ на основе машинно-независимого представления прикладного алгоритма в виде бесконтурного ориентированного графа. Это позволяет обеспечивать высокопроизводительную реализацию прикладных алгоритмов благодаря планированию вычислений и динамической поддержке исполнительной системы PaRSEC [23]. Дж. Донгарра занимается также вопросами автоматического распараллеливания алгоритмов [20]. Ассоциация вычислительной техники (ACM) присудила Джеку Донгарре премию Тьюринга за 2021 год.
В Российской Федерации одним из наиболее развитых направлений исследований в области параллельных вычислений является направление, созданное В.В. Воеводиным. Именно оно наиболее близко к направлению, использующему концепцию Q-детерминанта. Из работ, связанных с направлением исследований В.В. Воеводина, отметим монографию [4], где проводится очень важное и развитое исследование параллельной структуры алгоритмов и программ для их реализации на ПВС. Исследование параллельной структуры алгоритмов основано на описании и изучении информационных графов алгоритмов. Оно применяется в открытой энциклопедии AlgoWiki [9, 19]. Этот проект сформировался под руководством Вл. В. Воеводина и Дж. Донгарры. В энциклопедии описываются и изучаются графы конкретных алгоритмов. Это позволяет реализовывать алгоритмы эффективно. Однако в работах данного направления исследований программное обеспечение для автоматизированного исследования и использования ресурса параллелизма алгоритмов не рассматривается.
Список литературы
- Алеева В.Н. Анализ параллельных численных алгоритмов. Препринт № 590. Новосибирск: ВЦ СО АН СССР, 1985. 23 с.
- Алеева В.Н., Зотова П.С., Склезнев Д.С. Расширение возможностей исследования ресурса параллелизма численных алгоритмов с помощью программной Q-системы // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2021. Т. 10, № 2. С. 66-81. DOI: 10.14529/cmse210205 EDN: UJHTDK
- Алеева В.Н., Шатов М.Б. Применение концепции Q-детерминанта для эффективной реализации численных алгоритмов на примере метода сопряженных градиентов для решения систем линейных уравнений // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2021. Т. 10, № 3. С. 56-71. DOI: 10.14529/cmse210304 EDN: PNJEVG
- Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 608 с. EDN: SYTPKD
- Ершов Ю.Л., Палютин Е.А. Математическая логика. М.: Наука, 1987. 336 с.
- Репозиторий компилятора программной системы. URL: https://github.com/yuferovalex/qc (дата обращения: 29.06.2023).
- Репозиторий виртуальной машины программной системы. URL: https://github.com/yuferovalex/qvm (дата обращения: 29.06.2023).
- Недожогин Н.С., Копысов С.П., Новиков А.К. Параллельное решение систем линейных уравнений на гибридной архитектуре CPU+GPU // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2020. Т. 9, № 2. С. 40-54. DOI: 10.14529/cmse200203 EDN: HBTWIF
- Открытая энциклопедия свойств алгоритмов. URL: https://algowiki-project.org/ru (дата обращения: 30.05.2023).
-
Суперкомпьютер.Торнадо ЮУрГУ.. URL: http://supercomputer.susu.ru/computers/tornado/ (дата обращения: 30.05.2023).
-
Afanasyev I.V., Voevodin V.V., Komatsu K., et al. Distributed Graph Algorithms for Multiple Vector Engines of NEC SX-Aurora TSUBASA Systems // Supercomputing Frontiers and Innovations. 2021. Vol. 8, no. 2. P. 95-113. DOI: 10.14529/jsfi210206 EDN: ALILAJ
-
Akmed-Zaki D., Lebedev D., Malyshkin V., et al. Automated Construction of High Performance Distributed Programs in LuNA System // Parallel Computing Technologies (PaCT 2019). Vol. 11657. Springer, 2019. P. 3-9. Lecture Notes in Computer Science. DOI: 10.1007/978-3-030-25636-4_1
-
Aleeva V. Designing a Parallel Programs on the Base of the Conception of Q-Determinant // Supercomputing. RuSCDays 2018. Vol. 965. Springer, 2019. P. 565-577. Communications in Computer and Information Science. DOI: 10.1007/978-3-030-05807-4_48
-
Aleeva V.N. Improving Parallel Computing Efficiency // Proceedings - 2020 Global Smart Industry Conference, GloSIC 2020. IEEE, 2020. P. 113-120. Article number 9267828. DOI: 10.1109/GloSIC50886.2020.9267828 EDN: WANUZG
-
Aleeva V., Aleev R. Investigation and Implementation of Parallelism Resources of Numerical Algorithms // ACM Transactions on Parallel Computing. 2023. Vol. 10. no. 2. Article number 8. P. 1-64. DOI: 10.1145/3583755
-
Aleeva V.N., Aleev R.Zh. High-Performance Computing Using Application of Q-determinant of Numerical Algorithms // Proceedings - 2018 Global Smart Industry Conference, GloSIC 2018. IEEE, 2018. 8 p. Article number 8570160. DOI: 10.1109/GloSIC.2018.8570160 EDN: IYOKYU
-
Aleeva V., Bogatyreva E., Skleznev A., et al. Software Q-system for the Research of the Resource of Numerical Algorithms Parallelism // Supercomputing. RuSCDays 2019. Vol. 1129. Springer, 2019. P. 641-652. Communications in Computer and Information Science. DOI: 10.1007/978-3-030-36592-9_52 EDN: HGOKLW
-
Aleeva V.N., Sharabura I.S., Suleymanov D.E. Software System for Maximal Parallelization of Algorithms on the Base of the Conception of Q-determinant // Parallel Computing Technologies (PaCT 2015). Vol. 9251. Springer, 2015. P. 3-9. Lecture Notes in Computer Science. DOI: 10.1007/978-3-319-21909-7_1 EDN: VAFYEF
- Antonov A.S., Dongarra J., Voevodin V.V. AlgoWiki Project as an Extension of the Top500 Methodology // Supercomputing Frontiers and Innovations. 2018. Vol. 5, no. 1. P. 4-10. DOI: 10.1452/jsfi180101 EDN: XNQPEL
-
Balaprakash P., Dongarra J., Gamblin T., et al. Autotuning in High-Performance Computing Applications // Proceedings of the IEEE. 2018. Vol. 106, no. 11. P. 2068-2083. DOI: 10.1109/JPROC.2018.2841200
-
Bauer M., Treichler S., Slaughter E., Aiken A. Legion: Expressing locality and independence with logical regions // SC '12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis. 2012. P. 1-11. DOI: 10.1109/SC.2012.71
-
Bosilca G., Bouteiller A., Danalis A., et al. Flexible Development of Dense Linear Algebra Algorithms on Massively Parallel Architectures with DPLASMA // 2011 IEEE International Symposium on Parallel and Distributed ProcessingWorkshops and Phd Forum. 2011. P. 1432-1441. DO: 10.1109/IPDPS.2011.299
-
Bosilca G., Bouteiller A., Danalis A., et al. PaRSEC: Exploiting Heterogeneity to Enhance Scalability // Computing in Science & Engineering. 2013. Vol. 15, no. 6. P. 36-45. DOI: 10.1109/MCSE.2013.98
-
Legalov A.I., Vasilyev V.S., Matkovskii I.V., et al. A Toolkit for the Development of DataDriven Functional Parallel Programmes // Parallel Computational Technologies (PCT'2018). Vol. 910. Springer, 2018. P. 16-30. Communications in Computer and Information Science. DOI: 10.1007/978-3-319-99673-8_2
-
Moore G. Cramming More Components onto Integrated Circuits // Electronics Magazine. 1965. Vol. 38, no. 8. P. 114-117.
-
Moskovsky A., Roganov V., Abramov S. Parallelism Granules Aggregation with the TSystem // Parallel Computing Technologies (PaCT 2007). Vol. 4671. Springer, 2007. P. 293-302. Lecture Notes in Computer Science. DOI: 10.1007/978-3-540-73940-1_30
Выпуск
Другие статьи выпуска
Основной предмет статьи - рассмотрение задач, возникающих при исследовании необходимых условий равенства бесконечных итераций конечных языков. В предыдущих публикациях автором рассматривались примеры применения соответствующего этому равенству специального бинарного отношения эквивалентности на множестве конечных языков, причем рассматривались как примеры, описывающие необходимые условия его выполнения, так и примеры его использования. К одному из таких необходимых условий применены два варианта сведeния рассматриваемой задачи: к конечным автоматам и к бесконечным итерационным деревьям. Также в статье приведены несколько вариантов важной гипотезы, формулируемой для множества конечных языков; ее исследование дает и иные варианты сведeния рассматриваемой задачи к специальным задачам для недетерминированных конечных автоматов. При этом в случае выполнения сформулированной гипотезы некоторые из таких задач решаются за полиномиальное время, а некоторые не решаются; при продолжении работ по данной тематике последний факт может дать возможность переформулировки проблемы P = NP в виде специальной задачи теории формальных языков.
В статье рассмотрена задача поиска аномальных подпоследовательностей временного ряда, решение которой в настоящее время востребовано в широком спектре предметных областей. Предложен новый метод обнаружения аномальных подпоследовательностей временного ряда с частичным привлечением учителя. Метод базируется на концепциях диссонанса и сниппета, которые формализуют соответственно понятия аномальных и типичных подпоследовательностей временного ряда. Предложенный метод включает в себя нейросетевую модель, которая определяет степень аномальности входной подпоследовательности ряда, и алгоритм автоматизированного построения обучающей выборки для этой модели. Нейросетевая модель представляет собой сиамскую нейронную сеть, где в качестве подсети предложено использовать модификацию модели ResNet. Для обучения модели предложена модифицированная функция контрастных потерь. Формирование обучающей выборки выполняется на основе репрезентативного фрагмента ряда, из которого удаляются диссонансы, маломощные сниппеты со своими ближайшими соседями и выбросы в рамках каждого сниппета, трактуемые соответственно как аномальная, нетипичная деятельность субъекта и шумы. Вычислительные эксперименты на временных рядах из различных предметных областей показывают, что предложенная модель по сравнению с аналогами показывает в среднем наиболее высокую точность обнаружения аномалий по стандартной метрике VUS-PR. Обратной стороной высокой точности метода является большее по сравнению с аналогами время, которое затрачивается на обучение модели и распознавание аномалии. Тем не менее, в приложениях интеллектуального управления отоплением зданий метод обеспечивает быстродействие, достаточное для обнаружения аномальных подпоследовательностей в режиме реального времени.
В медицинской практике первичную диагностику заболеваний следует проводить быстро и по возможности автоматически. Обработка многомодальных данных в медицине стала повсеместно распространеннымметодом классификации, прогнозирования и обнаружения заболеваний. Пневмония - одно из наиболее распространенных заболеваний легких. В нашем исследовании для выявления пневмонии мы использовалирентгенограммы органов грудной клетки в качестве первой модальности и результаты лабораторных исследований пациента в качестве второй модальности. Архитектура многомодальной модели глубокого обучениябыла основана на промежуточном слиянии. Модель обучалась на сбалансированных и несбалансированныхданных, когда наличие пневмонии определялось в 50% и 9% от общего числа случаев соответственно. Дляболее объективной оценки результатов мы сравнили производительность нашей модели с несколькими другими моделями с открытым исходным кодом на наших данных. Эксперименты демонстрируют высокуюэффективность предложенной модели выявления пневмонии по двум модальностям даже в случаях несбалансированных классов (до 96.6%) по сравнению с результатами одномодальных моделей (до 93.5%). Мысделали несколько интегральных оценок производительности предлагаемой модели, чтобы охватить и исследовать все аспекты многомодальных данных и особенностей архитектуры. Были показатели точности,ROC AUC, PR AUC, показателя F1 и коэффициента корреляции Мэтьюса. Используя различные метрики, мы доказали возможность и целесообразность использования предложенной модели с целью правильнойклассификации заболевания. Эксперименты показали, что производительность модели, обученной на несбалансированных данных, даже немного выше, чем у других рассмотренных моделей.
В работе рассматривается решение многомерных задач многоэкстремальной оптимизации с использованием деревьев решений для выявления областей притяжения локальных минимумов. Целевая функцияпредставлена как «черный ящик», она может быть недифференцируемой, многоэкстремальной и вычислительно трудоемкой. Для функции предполагается, что она удовлетворяет условию Липшица с априоринеизвестной константой. Для решения поставленной задачи многоэкстремальной оптимизации применятсяалгоритм глобального поиска. Хорошо известно, что сложность решения существенно зависит от наличия нескольких локальных экстремумов. В данной работе предложена модификация алгоритма, в которойопределяются окрестности локальных минимумов целевой функции на основе анализа накопленной поисковой информации. Проведение такого анализа с использованием методов машинного обучения позволяетпринять решение о запуске локального метода, что может ускорить сходимость алгоритма. Данный подход был подтвержден результатами численных экспериментов, демонстрирующих ускорение при решениинабора тестовых задач.
Издательство
- Издательство
- ЮУрГУ
- Регион
- Россия, Челябинск
- Почтовый адрес
- 454080, Уральский федеральный округ, Челябинская область, г. Челябинск, просп. В.И. Ленина, д. 76
- Юр. адрес
- 454080, Уральский федеральный округ, Челябинская область, г. Челябинск, просп. В.И. Ленина, д. 76
- ФИО
- Александр Рудольфович Вагнер (Ректор)
- E-mail адрес
- admin@susu.ru
- Контактный телефон
- +7 (351) 2635882
- Сайт
- https://www.susu.ru