Зменшення обʼєму памʼяті, що використовується програмою, внаслідок трансформації програмного коду

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

Èlektron. model. 2022, 44(2):51-67

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

АНОТАЦІЯ

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

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

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

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

  1. Marwedel P. Embedded System Design: Embedded Systems Foundations of Cyber-Phy­sical Systems, and the Internet of Things. Springer, Cham, 2021, 433 р. ISSN 2193-0155, DOI: https://doi.org/10.1007/978-3-030-60910-8
  2. Ахо А., Лам М., Сети Р., Ульман Д. Компиляторы: принципы, технологии и инстру­мен­тарий (Compilers: Principles, Techniques, and Tools.). Изд. 2. М.: «Вильямс», 2008, 1184 с. ISBN 978-5-8459-1349-4.
  3. Cooper K., Torczon L. Engineering a Compiler. Second Edition — Morgan Kaufmann, 2011, 824р. ISBN 978-0-12-088478-0.
  4. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. Петербург: БХВ-Петербург, 2002, 603 с. ISBN: 5-94157-160-7 .
  5. Darte A., Robert Y., Vivien F. Loop parallelization algorithms. Compiler Optimizations for Scalable Parallel Systems // LNCS, 2001, Vol. 1808, pp. 141—171. Springer, Heidelberg. https://doi.org/10.1007/3-540-45403-9_5
  6. Wolf M.E., Lam M.S. A loop transformation theory and an algorithm to maximize parallelism // IEEE Transactions on Parallel and Distributed Systems, 1991, Vol. 2, N 4, pp. 452—471. Режим доступу: https://suif.stanford.edu/papers/wolf91b.pdf
  7. Pingali K. Locality of Reference and Parallel Processing. // Encyclopedia of Parallel Computing. Springer, Boston, MA, 2011. https://doi.org/10.1007/978-0-387-09766-4_206
  8. Lam M.S., Wolf M.E. A data locality optimizing algorithm. ACM SIGPLAN Notices, 2004, Vol. 39, Issue 4, pp. 442—459. https://doi.org/10.1145/989393.989437
  9. Lefebvre V., Feautrier P. Optimizing Storage Size for Static Control Programs in Automatic Parallelizers // Proc. EuroPar Conf., 1997, 1300 of Lecture notes in computer science (Passau, Germany), pp. 356—363. Режим доступу: https://doi.org/10.1007/ BFb0002757
  10. De Greef E., Catthoor F., De Man H. Memory size reduction through storage order optimization for embedded parallel multimedia applications // Proceedings of the Workshop on Parallel Processing and Multimedia of the International Parallel Processing Symposium, 1997, 84—98. Режим доступу: https://citeseerx.ist.psu.edu/viewdoc/download?doi =10.1.1.47.3832&rep=rep1&type=pdf
  11. Ranjan Panda P. et al., Data memory organization and optimizations in application-specific systems // IEEE Design & Test of Computers, 2001, Vol. 18, No. 3, pp. 56—68. DOI: 10.1109/54.922803.
  12. Tronçon R., Bruynooghe M., Janssens G., Catthoor F. Storage Size Reduction by In-place Mapping of Arrays. Verification, Model Checking, and Abstract Interpretation. Lecture Notes in Computer Science // VMCAI 2002, Vol. 2294, рр. 167—181. Режим доступу: https:// doi.org/10.1007/3-540-47813-2_12

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

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