Intellectual method of the iterative space partitioning for program loop operators

Authors

  • С. В. Сушко
  • О. А. Чемерис

DOI:

https://doi.org/10.18372/2073-4751.65.15375

Keywords:

parallel programs, program parallelization, loop parallelization, particle swarm optimization, tiling

Abstract

The article is devoted to the methods of automatic parallelization and software optimization. The authors focus on parallelizing the cyclic parts of algorithms, in particular, methods for splitting the iterative space of loop operators for C/C ++ programs. The problem of quickly choosing a partitioning method and determining its parameters is an urgent problem and its solution provides a reduction in the preparation time for software for computing systems with multiprocessor architecture. This is especially true for microprocessor control systems, IoT systems, mobile devices, Industry 4.0 systems, and so on. To build an automated system for parallelizing programs, the authors proposed to use the discrete particle swarm method as an optimization method that allows the one to find a local or global minimum of program execution time with a different nature of the relationship between block sizes and execution time. The article proposes an approach to optimizing the process of partitioning the iterative space of loop operators using the methods of Swarm Intellect. The developed method for optimizing the partitioning of the iterative space of program loop operators, which is tested in the 2-dimensional case, partitioning into rectangular parts, has no fundamental restrictions on its use for other types of partitioning (triangles, parallelograms, rhombuses, etc.).

References

Воеводин В.В., Воеводин Вл. В. Параллельные вычисления. – СПб.: БХВ-Петербург, 2002. – 608 с.: ил.

Дружиніна О. О. Підвищення ефективності функціонування веб-серверів з використанням технології прогнозування часових рядів на основі нейромереж / О. О. Дружиніна, Р. Н. Квєтний // Інформаційні технології та комп'ютерна інженерія. – 2013. – № 1. – С. 15-21.

Луцкий Г. М. Повышение эффективности кластеров на основе Infiniband / Г. М. Луцкий, И. С. Райзин // Вісник університету «Україна». Інформатика, обчислювальна техніка та кібернетика. – 2011. – № 8. – С. 133.

Havinga, P., Smit, G. Low power systems design techniques for mobile computers. Centre for Telematics and Information Technology University of Twente, Enschede (1997). ISSN 1381-3625

Клименко І. А. Методи та засоби підвищення ефективності обробки інформації в реконфігурованих комп’ютерних системах на базі ПЛІС: дис. Клименко Ірини Анатоліївни д-ра техн. наук: 05.13.05. Київ, 2017, 377 с.

Борисова Н.В. Ефективне управління ресурсами вбудованих систем для обчислювальної техніки реального часу / Н.В. Борисова, Л.В. Шабанова-Кушнаренко // Системи обробки інформації. – 2018. – № 1(152). – с. 87-93.

Душин В. К. Теоретические основы информационных процессов и систем/ В. К. Душин – Москва: Дашков и Ко, 2003. – 348 с.

Kennedy Ken Optimizing Compilers for Modern Architectures - A dependence based approach / Ken Kennedy, Allen Randy // San Francisco, San Diego, New York : Morgan Kaufmann Publishers. – 2001.

Huang T.-C. Data dependence analysis for array references / T.-C. Huang, C.-M. Yang // Journal of Systems and Software. – 2000. – Vol. 52. – P. 55–65.

Banerjee U. Time and Parallel Processor Bounds for Fortran-like Loops / U. Banerjee et al. // IEEE Trans. on Computers. – 1979. – № 9. – P. 660-670.

Uday Bondhugula, Albert Hartono, J. Ramanujam, Ponnuswamy Sadayappan A practical automatic polyhedral parallelizer and locality optimizer. // In Conference: PLDI '08: Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, May 2008. - ACM SIGPLAN Notices 43(6), DOI: 10.1145/1375581.1375595

Sushko S. Dependency between Tiles’ Sizes and Program Execution Time. / Sushko S., Chemerys A. // in Proceedings: Reconfigurable Ubiquitous Computing (RUC-2018), 12 жовтня 2018, Дзівнув, Польща.

M.A. El-Shorbagy, Aboul Ella Hassanien Particle Swarm Optimization from Theory to Applications. // International Journal of Rough Sets and Data AnalysisVolume 5 • Issue 2 • April-June 2018. – p. 1-22. DOI: 10.4018/IJRSDA.2018040101

Chemeris A. Usage of Discrete Particle Swarm Optimization Method for the Searching of Optimal Tile Size / A. Chemeris, S. Sushko // 2019 IEEE International Scientific-Practical Conference Problems of Infocommunications, Science and Technology (PIC S&T-2019), October 8-11, 2019, Kyiv, P. 202-206. ISBN: 978-1-7281-4183-1

Downloads

Issue

Vol. 1 No. 65 (2021)

Section

Статті

License

Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:

  1. Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.

  2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.

  3. Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).