Investigation of the parameters of discrete particle swarm optimization method for problem of finding of optimal tile sizes in program loops

Authors

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

DOI:

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

Keywords:

parallel programs, program parallelization, particle swarm optimization, tiling

Abstract

The article is devoted to software optimization methods. The article considers levels of software optimization and reveals main methods of optimization of computational loops. The authors describe the method of tiling method as one of promising optimization methods. Using of the method on the test programs often shows an acceleration of program execution time. However, tiling method itself is parametric and with using of different sizes of tiles an execution time of test programs also varies significantly. In the same time, dependence between program execution time and chosen tile size is not obvious and does not have similar patterns for the different test programs. The authors proposed to use Discrete Particle Swarm Optimization Method as optimization method which allows to find a local or global minimum of program execution time for the different nature of relationship between tiles and execution time. The article investigates an influence of the behavioral coefficients of Discrete Particle Swarm Optimization Method on speed and character of finding of minimum execution time. As a result of investigation, the graphs of searching for optimal value of particles of swarm are demonstrated. The authors conclude that there are difficulties to choose the coefficients that provide not fast but consistent convergence of swarm's particles to minimum and they propose a set of coefficients that shows the desired behavior of particles.

References

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.

Downloads

Issue

Vol. 2 No. 64 (2020)

Section

Статті

License

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

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

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

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