Применение алгоритмических скелетов для проектирования параллельных алгоритмов акторного типа
Аннотация
В работе предлагается метод проектирования параллельных алгоритмов. Цель метода – обеспечение точности описания алгоритмов без зависимости от языка программирования и архитектуры параллельной вычислительной системы, используя понятную программисту алгоритмическую форму описания. Цель достигнута путем адаптации алгоритмических скелетов Коула для представления структуры и модели акторов Хьюитта для представления семантики параллельных алгоритмов.
Идея метода изложена на примере проектирования параллельного алгоритма сортировки. В исходном алгоритме выделяется код, определяющий порядок вызова блоков сравнения и перестановки элементов сортируемой последовательности. Метод распараллеливания для этого кода применим при распараллеливании семейства последовательных алгоритмов с различными блоками сравнения и перестановки. Проектирование заключается в записи алгоритма в такой последовательной форме, для которой известен метод распараллеливания. Данная последовательная форма алгоритма может быть достаточно общей, независимо выполняется сортировка или другие вычисления. Для этого форма последовательного алгоритма приводится в соответствие с некоторой абстрактной моделью параллельных вычислений. В качестве такой модели нами предложена алгоритмическая интерпретация модели акторов. Представлен подробный пример применения метода. На основе алгоритмической интерпретации модели акторов описан параллельный вычислительный процесс алгоритма сортировки.
Алгоритмическая интерпретация модели акторов отличает метод от функциональных и объектно-ориентированных интерпретаций. Метод базируется на фундаментальном понятии последовательного алгоритма, что обеспечивает свободу выбора программной реализации, не требует примитивов синхронизации и коммуникации. Для проектирования используется один базовый скелет для всех алгоритмов вместо системы скелетов в методе Коула.
Особенности метода обеспечивают его применимость при проектировании алгоритмов многозадачных вычислений и алгоритмов управления потоками работ. Наш опыт применения метода подтверждает эффективность разработанных на его основе программ для широкого класса параллельных архитектур от одиночных мультипроцессорных до гибридных облачных систем.
Литература
[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
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
