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

Обложка

Цитировать

Полный текст

Аннотация

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

Об авторах

Елена Анатольевна Метелица

Южный Федеральный Университет

Автор, ответственный за переписку.
Email: metelica@sfedu.ru
ORCID iD: 0000-0001-6253-150X
м.н.с. Института математики механики и компьютерных наук им. Воровича, Южный федеральный университет. Научные интересы в областях компиляторных преобразований, оптимизации и распараллеливания программ

Список литературы

  1. Wolf M. E., Lam M. S.. “A loop transformation theory and an algorithm to maximize parallelism”, IEEE Transactions on Parallel and Distributed Systems, 2:4 (1991), pp. 452–471.
  2. Wolf M., Banerjee U.. “Data dependence and its application to parallel processing”, International Journal of Parallel Programming, 16:2 (1987), pp. 137–178.
  3. Bondhugula U., Baskaran M., Krishnamoorthy S., Ramanujam J., Rountev A., Sadayappan P.. “Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model”, CC 2008: Compiler Construction, Lecture Notes in Computer Science, vol. 4959, Springer, Berlin–Heidelberg, 2008, ISBN 978-3-540-78791-4, pp. 132–146.
  4. Lamport L.. “The parallel execution of DO loops”, Commun. ACM, 17:2 (1974), pp. 83–93.
  5. Mullapudi R. T., Vasista V., Bondhugula U.. “PolyMage: automatic optimization for image processing pipelines”, ACM SIGPLAN Notices, 50:4 (2015), pp. 429—443.
  6. Maydan D. E., Hennessy J. L., Lam M. S.. “Efficient and exact data dependence analysis”, ACM SIGPLAN Notices, 26:6 (1991), pp. 1–14.
  7. Wolfe M.. “Loop skewing: the wavefront method revisited”, Int. J. Parallel. Program., 15:4 (1986), pp. 279–293.
  8. Irigoin F., Triolet R.. “Supernode partitioning”, POPL '88: Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages (San Diego, California, USA, January 10–13, 1988), ACM, New York, 1988, ISBN 978-0-89791-252-5, pp. 319–329.
  9. Allen R., Kennedy K.. “Automatic translation of FORTRAN programs to vector form”, ACM Transactions on Programming Languages and Systems, 9:4 (1987), pp. 491–542.
  10. Vasilenko A., Veselovskiy V., Metelitsa E., Zhivykh N., Steinberg B., Steinberg O.. “Precompiler for the ACELAN-COMPOS package solvers”, PaCT 2021: Parallel Computing Technologies, Lecture Notes in Computer Science, vol. 12942, Springer, Cham, 2021, ISBN 978-3-030-86359-3, pp. 103–116.
  11. Штейнберг Б. Я.. «О взаимосвязи между решетчатым графом программы и графом информационных связей», Известия высших учебных заведений. Северо-Кавказский регион. Серия: Естественные науки, 2011, №5(165), с. 28–30.
  12. Савельев В. А., Штейнберг Б. Я.. Распараллеливание программ, Изд-во Южного федерального университета, Ростов-на-Дону, 2008, ISBN 978-5-9275-0547-0, 192 с.
  13. Christen M., Schenk O., Burkhart H.. “PATUS: a code generation and autotuning framework for parallel iterative stencil computations on modern microarchitectures”, 2011 IEEE International Parallel & Distributed Processing Symposium (Anchorage, AK, USA, 16–20 May 2011), 2011, pp. 676–687.
  14. Bagliy A. P., Metelitsa E. A., Steinberg B. Ya.. “Automatic parallelization of iterative loops nests on distributed memory computing systems”, PaCT 2023: Parallel Computing Technologies, Lecture Notes in Computer Science, vol. 14098, Springer, Cham, 2023, ISBN 978-3-031-41673-6, pp. 18–29.
  15. Воеводин В. В., Воеводин Вл. В.. Параллельные вычисления, БХВ-Петербург, СПб., 2002, ISBN 5-94157-160-7, 608 с.
  16. Баглий А. П., Дубров Д. В., Штейнберг Б. Я., Штейнберг Р. Б.. «43–47», Научный сервис в сети Интернет: труды XIX Всероссийской научной конференции (18–23 сентября 2017 г., г. Новороссийск), ИПМ им. М.В.Келдыша, М., 2017, ISBN 978-5-98354-037-8 URL http://keldysh.ru/abrau/2017/53.pdf.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать


Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution 4.0 International License.

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».