The Use of Algorithmic Skeletons to Design Actor-Based Parallel Algorithms
Abstract
The paper proposes a method for writing parallel algorithms. Our goal was to make a detailed description of concurrency while carrying no dependencies in programming language or underlying parallel architecture. We also wanted the description to be algorithmic, so simple for the programmer. The goal was achieved by adapting Cole's algorithmic skeletons to represent the structure and Hewitt’s actor model to represent the semantics of parallel algorithms.
We used a sorting algorithm to show the idea of the method. To get parallel sorting, one should parallelize the code that controls the order of comparison-swap operations. It is obvious, that the parallelization will be the same for algorithms with different comparison-swap operations. The design method consists in writing algorithms in a form with known parallelization. Consequently, the form of an algorithm presents concurrency. For a more general form than in the sorting example, we used an algorithmic interpretation of the actor model. Based on the algorithmic interpretation of the actor model, we described a parallel computational process of the sorting algorithm.
The algorithmic interpretation of the actor model distinguishes our method from functional and object-oriented approaches. It also makes code portable, and does not require synchronization and communication primitives. Only one skeleton is used instead of the skeleton system in Cole's method. The features of the method ensure its applicability in the design of many-task and workflow applications. The method confirms its efficiency for a wide class of parallel architectures ranges from single multiprocessor to hybrid cloud systems.
References
[2] Gibson-Robinson T., Armstrong P., Boulgakov A., Roscoe A.W. FDR3: a parallel refinement checker for CSP. International Journal on Software Tools for Technology Transfer. 2016; 18(2):149-167. (In Eng.) DOI: https://doi.org/10.1007/s10009-015-0377-y
[3] Abbassi A., Bandali A., Day, N., Serna J. A Comparison of the Declarative Modelling Languages B, Dash, and TLA+. In: 2018 IEEE 8th International Model-Driven Requirements Engineering Workshop (MoDRE), Banff, AB, 2018; p. 11-20. (In Eng.) DOI: https://doi.org/10.1109/MoDRE.2018.8
[4] Ulyantsev V., Buzhinsky I., Shalyto A. Exact finite-state machine identification from scenarios and temporal properties. International Journal on Software Tools for Technology Transfer. 2018; 20(1):35-55. (In Eng.) DOI: https://doi.org/10.1007/s10009-016-0442-1
[5] Li R., Hu H., Li H., Wu Y., Yang J. MapReduce Parallel Programming Model: A State-of-the-Art Survey. International Journal of Parallel Programming. 2016; 44(4):832-866. (In Eng.) DOI: https://doi.org/10.1007/s10766-015-0395-0
[6] Memeti S., Li L., Pllana S., Kołodziej J., Kessler C. Benchmarking OpenCL, OpenACC, OpenMP, and CUDA: Programming Productivity, Performance, and Energy Consumption. In: Proceedings of the 2017 Workshop on Adaptive Resource Management and Scheduling for Cloud Computing (ARMS-CC '17). Association for Computing Machinery, New York, NY, USA, 207; p. 1-6. (In Eng.) DOI: https://doi.org/10.1145/3110355.3110356
[7] Vostokin S.V., Bobyleva I.V. Asynchronous round-robin tournament algorithms for many-task data processing applications. International Journal of Open Information Technologies. 2020; 8(4):45-53. Available at: https://www.elibrary.ru/item.asp?id=42748925 (accessed 14.3.2020). (In Russ., abstract in Eng.).
[8] Cole M.I. Algorithmic skeletons: structured management of parallel computation. London: Pitman; 1989. (In Eng.).
[9] Hewitt C. Actor Model of Computation: Scalable Robust Information Systems. CoRR. 2010; abs/1008.1459. Available at: http://arxiv.org/abs/1008.1459 (accessed 14.3.2020). (In Eng.).
[10] Stepanov A.A., Rose D.E. From Mathematics to Generic Programming. Addison-Wesley Professional; 2014. (In Eng.).
[11] González-Vélez H., Leyton M. A survey of algorithmic skeleton frameworks: high-level structured parallel programming enablers. Software: Practice and Experience. 2010; 40(12):1135-1160. (In Eng.) DOI: https://doi.org/10.1002/spe.1026
[12] Gupta M. Akka Essentials. Packt Publishing Ltd; 2012. (In Eng.).
[13] Grossman M., Shirako J., Sarkar V. OpenMP as a High-Level Specification Language for Parallelism. In: N. Maruyama, B. de Supinski, M. Wahib (ed.) OpenMP: Memory, Devices, and Tasks. IWOMP 2016. Lecture Notes in Computer Science, vol.9903. Springer, Cham, 2016. p. 141-155. (In Eng.) DOI: https://doi.org/10.1007/978-3-319-45550-1_11
[14] Raicu I., Foster I.T., Zhao Y. Many-task computing for grids and supercomputers. In: 2008 Workshop on Many-Task Computing on Grids and Supercomputers. Austin, TX, 2008; p. 1-11. (In Eng.) DOI: https://doi.org/10.1109/MTAGS.2008.4777912
[15] Vostokin S.V., Sukhoroslov O.V., Bobyleva I.V., Popov S.N. Implementing computations with dynamic task dependencies in the desktop grid environment using Everest and Templet Web. CEUR Workshop Proceedings. 2018; 2267:271-275. Available at: http://ceur-ws.org/Vol-2267/271-275-paper-51.pdf (accessed 14.3.2020). (In Eng.).
[16] Vostokin S.V., Bobyleva I.V. Using the bag-of-tasks model with centralized storage for distributed sorting of large data array. CEUR Workshop Proceedings. 2019; 2416:199-203. Available at: http://ceur-ws.org/Vol-2416/paper26.pdf (accessed 14.3.2020). (In Eng.).
[17] Vostokin S.V., Kazakova I.V. Implementation of stream processing using the actor formalism for simulation of distributed insertion sort. Journal of Physics: Conference Series. 2018; 1096(1):012087. (In Eng.) DOI: https://doi.org/10.1088/1742-6596/1096/1/012087
[18] Popov S.N., Bobyleva I. V., Vostokin S.V. Distributed Block Sort: a Sample Application for Data Processing in Mobile ad HOC Networks. International Journal of Innovative Technology and Exploring Engineering. 2019; 8(7S2):565-568. Available at: https://www.ijitee.org/wp-content/uploads/papers/v8i7s2/G10960587S219.pdf (accessed 14.3.2020). (In Eng.).
[19] Vostokin S., Bobyleva I. Building an Algorithmic Skeleton for Block Data Processing on Enterprise Desktop Grids. In: V. Voevodin, S. Sobolev S. (ed.) Supercomputing. RuSCDays 2019. Communications in Computer and Information Science, vol.1129. Springer, Cham, 2019. p. 678-689. (In Eng.) DOI: https://doi.org/10.1007/978-3-030-36592-9_55
[20] Zandifar M., Abdul Jabbar M., Majidi A., Keyes D., Amato N.M., Rauchwerger L. Composing Algorithmic Skeletons to Express High-Performance Scientific Applications. In: Proceedings of the 29th ACM on International Conference on Supercomputing (ICS '15). Association for Computing Machinery, New York, NY, USA; 2015. p. 415-424. (In Eng.) DOI: https://doi.org/10.1145/2751205.2751241
[21] Yu J., Buyya R. A taxonomy of scientific workflow systems for grid computing. ACM SIGMOD Record. 2005; 34(3):44-49. (In Eng.) DOI: https://doi.org/10.1145/1084805.1084814
[22] Sukhoroslov O. Supporting Efficient Execution of Workflows on Everest Platform. In: V. Voevodin, S. Sobolev (ed.) Supercomputing. RuSCDays 2019. Communications in Computer and Information Science, vol.1129. Springer, Cham; 2019. p. 713-724. (In Eng.) DOI: https://doi.org/10.1007/978-3-030-36592-9_58
[23] De Koster J., Van Cutsem T., De Meuter W. 43 years of actors: a taxonomy of actor models and their key properties. In: Proceedings of the 6th International Workshop on Programming Based on Actors, Agents, and Decentralized Control (AGERE 2016). Association for Computing Machinery, New York, NY, USA; 2016. p. 31-40. (In Eng.) DOI: https://doi.org/10.1145/3001886.3001890
[24] Lamport L. Specifying systems: the TLA+ language and tools for hardware and software engineers. Addison-Wesley Longman Publishing Co; 2002. (In Eng.).
[25] Vostokin S.V. The Templet parallel computing system: specification, implementation, applications. Procedia Engineering. 2017; 201:P. 684-689. (In Eng.) DOI: https://doi.org/10.1016/j.proeng.2017.9.683
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
