Титульная страница
English version
Программные системы:
 теория и приложения 
 ISSN 2079-3316
12+ 
Двуязычный электронный научный Электронный научный журнал Института программных систем имени А. К. Айламазяна ИПС им. А. К. Айламазяна ИПС Российской Академии Наук РАН
Том 15 (2024) .– Выпуск 1 (60) .– Статья № 4 (425)

Программное и аппаратное обеспечение распределенных и суперкомпьютерных систем

Научная статья
УДКУниверсальная десятичная классификация 004.424.22, 004.312.46УДК 004: Информационные технологии. Компьютерные технологии. Теория вычислительных машин и систем УДК 004.424: Методы программирования УДК 004.424.22: Повторения. Петли. Итерации. Циклы УДК 004.312: Логические схемы, блоки УДК 004.312.46: Цепи управления для математических операций
ББКБиблиотечно-библиографическая классификация 32.972.11ББК 32: Радиоэлектроника ББК 32.972: Программные средства (программное обеспечение) ББК 32.972.11: Системное программное обеспечение
ГРНТИГосударственный рубрикатор научно-технической информации 50.07.05ГРНТИ 50: АВТОМАТИКА. ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА ГРНТИ 50.07: Теоретические основы вычислительной техники ГРНТИ 50.07.05: Теория вычислительных систем высокой производительности
DOIЦифровой идентификатор интернет-объекта 10.25209/2079-3316-2024-15-1-63-94

Обоснование методов ускорения гнёзд циклов итерационного типа

Елена Анатольевна МетелицаПереписывавшийся автор

Южный Федеральный Университет, Ростов-на-Дону, Россия
Елена Анатольевна Метелица — Переписывавшийся автор metelica@sfedu.ru

Аннотация. Рассматривается ускорение итерационных алгоритмов, которые встречаются при решении задач математической физики, математического моделирования, обработки изображений и других. В программной реализации таких алгоритмов лежат гнёзда циклов (участки программы, состоящие из вложенных циклов). Такие гнёзда циклов ускоряются при помощи комбинации оптимизирующих преобразований, включающих тайлинг, метод гиперплоскостей и распараллеливание на общую память. Обосновывается эквивалентность комбинации используемых преобразований программ.

Предлагается и обосновывается метод изменения порядка обхода тайла. Метод даёт ускорение за счёт увеличения количества чтений данных из регистров, вместо чтений из более медленной памяти. С учётом этого метода получена формула вычисления оптимальных размеров тайлов.

Представленной в статье цепочкой преобразований достигается ускорение в 1.4 раза большее, чем в известном алгоритме оптимизации, реализованном в системе PLUTO. Приводятся численные эксперименты, которые в некоторых случаях на процессоре с 8 ядрами демонстрируют ускорение относительно исходных последовательных программ более чем на порядок. Результаты статьи могут использоваться для ручной и автоматизированной оптимизации программ.

Ключевые слова: тайлинг, метод гиперплоскостей, распараллеливание, общая память, гнёзда циклов итерационного типа

Благодарности: Автор благодарен д.т.н. Б.Я. Штейнбергу за руководство работой и Ар.В. Климову за внимание и интерес к работе.

Для цитирования: Метелица Е. А. Обоснование методов ускорения гнёзд циклов итерационного типа // Программные системы: теория и приложения. 2024. Т. 15. № 1. С. 63–94. https://psta.psiras.ru/2024/1_63-94.

Полный текст статьи (PDF): https://psta.psiras.ru/read/psta2024_1_63-94.pdf.

Статья поступила в редакцию 21.01.2024; одобрена после рецензирования 13.02.2024; принята к публикации 15.02.2023; опубликована онлайн 26.03.2024.

© Метелица Е. А.
2024
Адрес редакции: 152021, Ярославская обл., Переславский район, село Веськово, ул. Петра Первого, д. 4а, Институт программных систем имени А. К. Айламазяна РАН; Тел: +7(4852) 695-228 E-mail: ; Сетевой адрес издания:  http://psta.psiras.ru
© Федеральное государственное бюджетное учреждение науки Институт программных систем имени А. К. Айламазяна Российской академии наук (дизайн сайта) 2010–2024 The text of CC-BY-4.0 license