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

Автор(и)

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

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##

Номер

Том 2 № 64 (2020)

Розділ

Статті

Ліцензія

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

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

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

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