Parallel algorithms optimization using Actor Model

А.Yu. Doroshenko, E.M. Tulika

Abstract


Introduced methods and instrumentation tools for actor model applied to block recursive algorithms optimization. Created formal model of distribution and coordination of the tasks in computation cluster as asynchronous reactive processes with message-passing represented with an actor model and choreography of actors. Created declarative definitions of algorithms which compiles to the system of actors. Proposed scheme of data placement in a cluster using prioritization of block-recursive operations to reduce idling time, data movement, with increased parallelism in situation of high-speed processors and reduced network bandwidth. Implemented adaptive adjustment of the data placement in a cluster at run time to account for current cluster load. Created autotuning of the actor placement in а cluster which uses statistics of previous runs for optimization. Usage of choreography of actors allows to remove central coordinating element and to avoid hard dependencies between cluster nodes, which provides flexible data placement, improves fault tolerance with no single point of failure and allows to use self-healing. 

Problems in programming 2020; 2-3: 126-137

 


Keywords


block recursive algorithms; cloud computing; actor model; actor choreography; autotuning of actor choreography

Full Text:

PDF (Ukrainian)

References


Song Fengguang, Asim YarKhan, and Jack Dongarra. "Dynamic task scheduling for linear algebra algorithms on distributed-memory multicore systems." Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis. IEEE, 2009.

Dongarra J.J., Robert Van De Geijn, and David Walker. LAPACK Working Note 43: A Look at Scalable Dense Linear Algebra Libraries. University of Tennessee, Computer Science Department, 1992.

Seeger Matthias, et al. "Auto-differentiating linear algebra." arXiv preprint arXiv:1710.08717 (2017).

Liu Jun, Yang Liang, and Nirwan Ansari. "Spark-based large-scale matrix inversion for big data processing." IEEE Access 4 (2016):

–2176.

Hoque Reazul, et al. "Dynamic task discovery in parsec: A data-flow task-based runtime." Proceedings of the 8th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems. 2017.

Misra Chandan, et al. "SPIN: A fast and scalable matrix inversion method in apache spark." Proceedings of the 19th International Conference on Distributed Computing and Networking. 2018.

Song Fengguang, et al. "Scalable tile communication-avoiding QR factorization on multicore cluster systems." SC'10: Proceedings of the 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE, 2010.

Buttari Alfredo, et al. "Parallel tiled QR factorization for multicore architectures." Concurrency and Computation: Practice and Experience 20.13 (2008): 1573–1590.

Cao Quinglei, et al. "Performance Analysis of Tile Low-Rank Cholesky Factorization Using PaRSEC Instrumentation Tools." 2019 IEEE/ACM International Workshop on Programming and Performance Visualization Tools (ProTools). IEEE, 2019.

Zheng Weijian, et al. "Scaling Up Parallel Computation of Tiled QR Factorizations by a Distributed Scheduling Runtime System and Analytical Modeling." Parallel Processing Letters 28.01 (2018): 1850004.

Ballard Grey, et al. "Communication-optimal parallel and sequential Cholesky decomposition." SIAM Journal on Scientific Computing 32.6 (2010): 3495–3523.

Ltaief Hatem, et al. "A scalable high performant Cholesky factorization for multicore with GPU accelerators." International Conference on High Performance Computing for Computational Science. Springer, Berlin, Heidelberg, 2010.

Eugene Tulika, Anatoliy Doroshenko, Kostiantyn Zhereb, Adaptation of Legacy Fortran Applications to Cloud Computing. Proceedings of the 12th International Conference on ICT in Education, Research and Industrial Applications. Integration, Harmonization and Knowledge Transfer. Kyiv, Ukraine, June 21–24. 2016. P. 119–126.

Eugene Tulika, Anatoliy Doroshenko, and Kostiantyn Zhereb, Using Choreography of Actors and Rewriting Rules to Adapt Legacy Fortran Programs to Cloud Computing. In “Information and Communication Technologies in Education, Research, and Industrial Applications”, A. Ginige et al. (Eds.): ICTERI 2016, CCIS 783, Springer International Publishing AG, 2017. P. 1–21.


Refbacks

  • There are currently no refbacks.