Дослідження параметрів дискретного методу роя часток при пошуку оптимальних розмірів блоків розбиття циклічних операторів програм

Автор(и)

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

DOI:

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

Ключові слова:

паралельні програми, розпаралелювання програм, метод рою часток, тайлінг

Анотація

Стаття присвячена методам оптимізації програмного забезпечення. У статті розглядається рівні оптимізації програмного забезпечення і розкриваються основні методи оптимізації обчислювальних циклів. Автори описують метод розбиття обчислювальних циклів на блоки як один з перспективних методів оптимізації. Використання зазначеного методу на тестових програмах часто показує прискорення часу виконання програм. Однак сам метод розбиття на блоки є параметричним і при використанні різних розмірів блоків розбиття час виконання тестових програм також значно різниться. При цьому залежність часу виконання програм від обраного значення розмірів блоків неочевидна і не має схожих патернів для різних тестових програм. Авторами запропоновано використовувати дискретний метод рою часток як оптимізаційний метод, що дозволяє знайти локальний або глобальний мінімум часу виконання програм при різному характері залежності між розмірами блоків і часу виконання. У статті проведено дослідження впливу поведінкових коефіцієнтів дискретного методу рою часток на швидкість і характер знаходження мінімуму часу виконання. Як результат дослідження продемонстровані графіки пошуку частками рою оптимального значення. Автори роблять висновок про складність підбору коефіцієнтів, які забезпечують нешвидку, але послідовну збіжність часток рою до мінімуму і пропонують набір коефіцієнтів, які забезпечують зазначену поведінку часток.

Посилання

A. Aho, M. Lam, R. Sethi and J. Ullman, Compilers, principles, techniques, and tools. Pearson Education, Inc., 2007.

K. Kennedy, R. Allen, Optimizing Compilers for Modern Architectures – A Dependence Based Approach. San Francisco: Morgan Kaufmann Publishers, 2001.

Shinan W. Software power analysis and optimization for power-aware multicore systems: дис. канд. / Shinan Wang – Detroit, 2014. – 177 с.

Jingling X. Loop tiling for parallelism / Xue Jingling. – (Kluwer international series in engineering and computer science; SECS 575).

Pugh W. An Exact Method for Analysis of Value-based Array Data Dependences / W. Pugh, D. Wonnacott. – Univ. of Maryland, 1993.

Darte A. Combining retiming and scheduling techniques for loop parallelization and loop tiling. / A. Darte, G. Silber, F. Vivien. // Parallel Processing Letters. – 1997. – №7. – С. 379–392.

C´edric Bastoul. Code generation in the polyhedral model is easier than you think. In IEEE International Conference on Parallel Architectures and Compilation Techniques, pages 7–16, September 2004.

Uday Bondhugula. Effective Auto-matic Parallelization and Locality Optimiza-tion Using The Polyhedral model: дис. канд. / Uday Bondhugula. – The Ohio State Uni-versity, 2010. – 193 c.

U. Boundhugula, J. Ramanujam and P. Sadayappan, "Pluto: a practical and fully automatic polyhedral parallelizer and locality optimizer", Louisiana State Universi-ty, Columbus, 2007.

L. Pouchet, "PolyBench/C the Polyhedral Benchmark suite". [Electronic resource]. Available at: http://web.cse.ohio-state.edu/~pouchet/software/polybench/#description.

Сушко С.В. Summer InfoCom 2016: Матеріали II Міжнародної науково-практичної конференції, м. Київ, 1-3 чер-вня 2016 р. – К.: Вид-во «Інжиніринг», 2016. – 116 с.

Сушко С.В., Чемерис О. А. Вплив розмірів блоків розбиття операто-рів циклів на час виконання комп’ютерних программ Моделювання та інформаційні технології, 2018. – Vol. 82. – P. 110-117.

Clerc M. Particle Swarm Optimi-zation. ISTE, London, UK, 2006.

П. В. Матренин, В. Г. Секаев Системное описание алгоритмов роевого интеллекта, Программная инженерия, Теоретический и прикладной научно-технический журнал, 2013. – №12. – C. 39–45.

Ковалев И.В., Соловьев Е.В., Ковалев Д.И., Бахмарева К.К., Демиш А.В. Использование метода роя частиц для формирования состава мультиверсионно-го программного обеспечения, Приборы и системы. управление, контроль, диаг-ностика. M.: Научтехлитиздат, 2013. – №3. – C. 1-6.

G. Beni, J. Wang, Swarm Intel-ligence in Cellular Robotic Systems, Proceed. NATO Advanced Workshop on Robots and Biological Systems, Tuscany, Italy, June 26–30, 1989.

##submission.downloads##

Як цитувати

Сушко, С. В., & Чемерис, А. А. (2020). Дослідження параметрів дискретного методу роя часток при пошуку оптимальних розмірів блоків розбиття циклічних операторів програм. Проблеми iнформатизацiї та управлiння, 2(64), 59–68. https://doi.org/10.18372/2073-4751.64.15151

Номер

Том 2 № 64 (2020)

Розділ

Статті

Ліцензія

Науковий журнал дотримується принципів відкритого доступу (Open Access) та забезпечує вільний, негайний і постійний доступ до всіх опублікованих матеріалів без фінансових, технічних або юридичних обмежень для читачів.

Усі статті публікуються у відкритому доступі відповідно до ліцензії Creative Commons Attribution 4.0 International (CC BY 4.0).

Авторські права

Автори, які публікують свої роботи в журналі:

  • зберігають за собою авторські права на свої публікації;

  • надають журналу право на перше опублікування статті;

  • погоджуються на поширення матеріалів за ліцензією CC BY 4.0;

  • мають право повторно використовувати, архівувати та поширювати свої роботи (у тому числі в інституційних та тематичних репозитаріях) за умови посилання на первинну публікацію в журналі.