Використання методів трансформації операторів циклів для оптимізації паралельних програмних додатків

О.А. Чемерис, д-р техн. наук, З.Х. Борукаєв, д-р техн. наук ,
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
Україна, 03164, Київ, вул. Генерала Наумова, 15
e-mail: Ця електронна адреса захищена від спам-ботів. Вам необхідно увімкнути JavaScript, щоб побачити її., Ця електронна адреса захищена від спам-ботів. Вам необхідно увімкнути JavaScript, щоб побачити її.
І.В. Блінов, д-р техн. наук,
Інститут електродинаміки НАН України
Україна, 03057, Київ, проспект Перемоги, 56
e-mail: Ця електронна адреса захищена від спам-ботів. Вам необхідно увімкнути JavaScript, щоб побачити її.

Èlektron. model. 2022, 44(1):53-69

https://doi.org/10.15407/emodel.44.01.053

АНОТАЦІЯ

Розглянуто можливість оптимізації працюючих програм, зокрема паралельних. Цільовою функцією оптимізації обрано мінімізацію часу виконання програми на па-ралельній обчислювальній системі. Для оптимізації використано алгоритми афінної трансформації ітераційного простору операторів циклів, кожний з яких подано у вигляді графа на основні залежностей між операторами, що створюють зв’язки у графі ітерацій оператора циклу. Розглянуто приклад процесу оптимізації програмного пакету MFDn, який використовують у ядерній фізиці для визначення багатотільного ядерного гамільтоніана. Наведено виграш в часі виконання оптимізованої програми.

КЛЮЧОВІ СЛОВА:

розпаралелювання, оптимізація програм, трансформація програм, афінні перетворення.

СПИСОК ЛІТЕРАТУРИ

  1. Sternberg P. Accelerating Configuration Interaction Calculations for Nuclear Structure. / P. Sternbergetal. // Proceedings of the 2008 ACM/IEEE Conference on Supercomputing. Austin, 2008, рр. 1-12, doi: 10.1109/SC.2008.5220090
  2. Collard J.F., Feautrier P., Risset T. Construction of do loops from systems of affine constraints // Parallel Processing Letters, 1995, Vol. 5, рр. 421—436.
  3. Chemeris A., Gorunova J., Lazorenko D. Loop Nests Parallelization for Digital System Synthesis // Proceedings of IEEE East-West Design & Test Symposium (EWDTS’2012). Kharkov, Ukraine, September 14–17, 2012, рр. 118—121.
  4. Bielecki W., Hyduke S. Kompilator jezyka VHDL do syntezy ukladow logicznych. // Reprogramowalne uklady cyfrowe (RUC’99). Szczecin, 1999, рр. 183—190.
  5. Lim A.W., Lam M.S. Communication-free parallelization via affine transformations // Languages and Compilers for Parallel Computing: 7th International Workshop Ithaca. Berlin: Springer Berlin Heidelberg, 1995, рр. 92—106.
  6. Vasilache N., Cohen A., Pouchet L.-N. Automatic Correction of Loop Transformations // Parallel Architectures and Compilation Techniques. Conference Proceedings, PACT. Brasov, Romania, 2007, рр. 292-304.
  7. Fraboulet A., Huard G., Mignotte A. Loop Alignment for Memory Accesses Optimization // Twelfth International  Symposiumon  System    Piscataway,  NewJersey,  1999, рр. 71–77.
  8. Aktulga H.M., Buluç A., Williamsand S., Yang C. Optimizing Sparse Matrix-Multiple Vectors Multiplication for Nuclear Configuration Interaction Calculations, 2014 IEEE 28th International Parallel and Distributed Processing Symposium, 2014, pp. 1213—1222, Doi: 10.1109/IPDPS.2014.125.
  9. Bielecki W. FindingSynchronization-FreeParallelismforNon-uniformLoops // Proceedings of the Computational Science (ICCS 2003), Lecture Notesin Computer Science, 2003, Vol. 2658, pp. 925—934.

ЧЕМЕРИС Олександр Анатолійович, д-р техн. наук, ст. наук. співробітник, заступник директора з наукової роботи Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України. В 1982 р. закінчив Київський політехнічний інститут. Область наукових досліджень — розподілені інформаційні та обчислювальні системи, високо­продуктивні обчислення та автоматичне розпаралелювання задач.

БОРУКАЄВ Зелімхан Харитонович, д-р техн. наук, ст. наук. співробітник, завідувач ла­бораторії математичного моделювання енергоринків відділу математичного та еконо­метричного моделювання Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України. У 1971 р. закінчив Ростовський держуніверситет. Область наукових досліджень — математичне моделювання фізичних полів та процесів, моделювання інформаційних процесів та систем.

БЛІНОВ Ігор Вікторович, д-р техн. наук, ст. наук. співробітник,заступник директора з наукової роботи Інституту електродинаміки НАН України, В 2005 р. закінчив Донець­кий національний технічний університет. Область наукових досліджень — моделюван­ня процесів ціноутворення на ринку електричної енергії з урахуванням мережевих та системних обмежень, методи пошуку місць пошкоджень в електричних мережах, прог­нозування електричного навантаження.

Повний текст: PDF