Аннотация: Использование указателей и косвенной адресации в программе, а также сложная структура графа потока управления являются одними из основных препятствий при выполнении статического анализа программ. Обнаруженные в результате такого анализа свойства программы слишком консервативно описывают ее поведение и часто оказываются недостаточными для принятия решений о возможности ее параллельного выполнения. Использование динамического анализа программ позволяет расширить возможности средств автоматизации распараллеливания. В системе SAPFOR (System FOR Automated Parallelization) реализован инструмент динамического анализа, опирающийся на инструментацию программ в представлении LLVM, что позволяет исследовать программы на языках C и Fortran. Чтобы снизить накладные расходы на время выполнения инструментированной программы, сохранив при этом полноту проводимого анализа, используются возможности статического анализа, реализованного в SAPFOR. В процессе динамического анализа часть обращений к памяти, информация о которых была получена в процессе статического анализа, может быть проигнорирована. Разработанный инструмент был протестирован на тестах производительности из пакета NAS Parallel Benchmarks для языков C и Fortran. В процессе динамического анализа кроме традиционных видов зависимостей (flow, anit, output) также определяются переменные, зависимость по которым может быть устранена за счет приватизации или конвейерного выполнения циклов. Совместно с возможностями DVM и OpenMP это существенно облегчает, в том числе, и ручное распараллеливание, облегчая задание соответствующих директив компилятора.

Аннотация:

Представлены результаты исследований параллельных приложений для гетерогенных архитектур с использованием стандарта SYCL и его реализации DPC++, а также технологии OpenMP, разработанные студентами кафедры прикладной математики и искусственного интеллекта (ПМИИ) ФГБОУ ВО «НИУ «МЭИ» в ходе выполнения научно-исследовательских работ. В качестве прикладной задачи рассмотрен поиск кратчайших путей в графах различной размерности с использованием алгоритмов Беллмана-Форда и дельта-шага.

Алгоритм Беллмана – Форда легко поддается распараллеливанию и продемонстрировал отличную масштабируемость. Для алгоритма дельта-шага, напротив, использование GPU не дало заметного ускорения из-за сложности согласования памяти и необходимости многократного копирования данных между устройствами.

Тестирование проводилось с использованием следующих аппаратных средств: центральный процессор Intel Core i5-12400F (6 ядер, 12 потоков), графический процессор NVIDIA GeForce GTX1660 (1408 CUDA-ядер). Результаты тестирования показывают, что даже в рамках одной вычислительной задачи различные реализации могут демонстрировать разное поведение при изменении параметров задачи. Это подтверждает важность предварительного анализа и тестирования при выборе аппаратно-программной архитектуры для задач, требующих высокой производительности.

Разработанный комплекс программ визуализирует зависимость ускорения параллельных реализаций алгоритма от числа вершин в графе при различных параметрах метода и успешно используется в учебно-научном процессе кафедры ПМИИ ФГБОУ ВО «НИУ «МЭИ».