One Approach for Parallel Algorithms Representation

Year 2017, , 30 - 33, 01.09.2017

Atanaska D. Bosakova-ardenska

https://doi.org/10.17694/bajece.334294

Abstract

This paper presents one
approach for parallel algorithms representation. The proposed model is practice
oriented and its name is AMPA (Agenda Model for Parallel Algorithms) due to
basic blocks organization like a schedule. The model uses classical Master/Slave
paradigm. One parallel merge sorting algorithm based on quick sort is presented
with the discussed AMPA model and also three known representation approaches
(description with natural language, pseudo code and PRAM). A survey of professional
opinion about AMPA and other approaches is conducted. The results show that
most of the interviewed people choose
AMPA as the best way to understand the algorithm.

Keywords

Master-slave, Merge sort, Parallel algorithms, PRAM, Programming model, Pseudo code

References

• [1] Kirtzic J. S., O. Daescu, A parallel algorithm development model for the GPU architecture, Proc. of International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA), 2012.
• [2] Valiant L., A bridging model for multi-core computing, Journal of Computer and System Sciences, vol. 77, no. 1, pp. 154–166, 2011.
• [3] Luebke D., CUDA: Scalable parallel programming for high-performance scientific computing, 5th IEEE International Symposium on Biomedical Imaging: From Nano to Macro, Paris, pp. 836-838, 2008.
• [4] Yukiya Aoyama, Jun Nakano, “RS/6000 SP: Practical MPI Programming”, International Technical Support Organization, IBM, 1999.
• [5] Seyed H. Roosta, Parallel Processing and Parallel Algorithms: theory and computation, Springer, ISBN 0-387-98716-9, 2000.
• [6] Wilkinson B. and Allen M., Sorting Algorithms, Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers, Prentice-Hall, 1999 [7] Sahni S. and G. Vairaktarakis, The master-slave paradigm in parallel computer and industrial settings, Journal of Global Optimization, 9, pp. 357–377, 1996.
• [8] Baldo L., L. Brenner, L. G. Fernandes, P. Fernandes, A. Sales, Performance Models For Master/Slave Parallel Programs, Electronic Notes in Theoretical Computer Science, 2004.
• [9] Mostaghim S., J. Branke, A. Lewis, H. Schmeck, Parallel Multi-objective Optimization using Master-Slave Model on Heterogeneous Resources, Proceedings of the IEEE Congress on Evolutionary Computation, 2008.
• [10] Cazenave T., Nicolas Jouandeau, A Parallel Monte-Carlo Tree Search Algorithm, Computers and Games, 2008.
• [11] Shuping LIU, Yanliu CHENG, The Design and Implementation of MPI Master-Slave Parallel Genetic Algorithm, International Conference on Education Technology and Computer (ICETC2012), 2012.
• [12] Depolli M., R. Trobec, B. Filipiˇc, Asynchronous Master-Slave Parallelization of Differential Evolution for Multiobjective Optimization, Evolutionary Computation 21 (2), pp. 261–291, 2013.
• [13] Krichene H., M. Baklouti, Jean-Luc Dekeyser, Ph. Marquet, M. Abid, Master-Slave Control structure for massively parallel System on Chip, DSD SEAA - 16th Euromicro Conference on Digital System Design, Sep 2013, Santander, Spain. 2013.
• [14] Scrucca L., On some extensions to GA package: Hybrid optimisation, parallelisation and islands evolution, The R Journal 9(1), pp.187-206, 2017.
• [15] Jiaxing Qu, Guoyin Zhang, Zhou Fang, Jiahui Liu, A Parallel Algorithm of String Matching Based on Message Passing Interface for Multicore Processors, International Journal of Hybrid Information Technology, Vol.9, No.3, pp. 31-38, 2016.
• [16] Jiahui Liu, Dahua Song, Yiqiu Xu, A Parallel Encryption Algorithm for Dual-core Processor Based on Chaotic Map, Proceedings of SPIE - The International Society for Optical Engineering SPIE Proceedings, 2012.
• [17] Hoare C.A.R., Quicksort, The Computer Journal, vol. 5, pp 10-16, 1962.
• [18] JaJa Joseph, An Introduction to Parallel Algorithms, Addison-Wesley publishing company, 1992.