Asynchronous round-robin tournament algorithms for many-task data processing applications

S.V. Vostokin, I.V. Bobyleva

Abstract


The article discusses the constructing of tasks dependencies graphs for many-task applications that perform parallel asynchronous data processing on the principle of round-robin sport tournament. The following components of the technique are described: the family of round robin algorithms is defined in the form of an algorithmic skeleton; a method for synthesizing a graph of a round-robin tournament using the basic sequential algorithm is proposed; it is shown how to use the graphs for the implementation of parallel and asynchronous computing process. A graphical interpretation of the round-robin tournament procedures is considered, on which it is possible to build analytical estimates of the tournament time. The technique is illustrated by three examples of constructing specific tournament algorithms: the tournament without additional restrictions, the simple sorting tournament, and the optimized sorting tournament. We build the algorithms for constructing task dependencies graphs for these three tournaments. The principle of implementing asynchronous parallel computing according to the graphs are considered. Using the graphical interpretation, the number of rounds and the speedup was calculated for each of the listed tournaments. The technique is recommended for a wide class of parallel architectures including clusters, desktop grids, and hybrid clouds.


Full Text:

PDF (Russian)

References


I. Raicu, I.T. Foster, and Y. Zhao, “Many-task computing for grids and supercomputers,” 2008 workshop on many-task computing on grids and supercomputers. IEEE, 2008, pp. 1-11.

E. Ayguadé, N. Copty, A. Duran, J. Hoeflinger and Y. Lin, “The design of OpenMP tasks,” IEEE Transactions on Parallel and Distributed Systems, 2009, vol. 20, no. 3, pp. 404-418.

A. D. Robison, “Composable parallel patterns with intel cilk plus ,” Computing in Science & Engineering, 2013, vol. 15, no. 2, pp. 66-71.

M. Voss, R. Asenjo, J. Reinders, Pro TBB: C++ Parallel Programming with Threading Building Blocks. Apress, 2019.

O. S. Zaikin, M. A. Posyipkin, A. A. Semёnov, N. P. Hrapov, “Opyit organizatsii dobrovolnyih vyichisleniy na primere proektov OPTIMA@ home i SAT@ home.” Vestnik Nijegorodskogo universiteta im. NI Lobachevskogo, 2012, vol. 5, no. 2.

O. Sukhoroslov, S. Volkov, A. Afanasiev , “A web-based platform for publication and distributed execution of computing applications,” 14th International Symposium on Parallel and Distributed Computing. IEEE, 2015, pp. 175-184.

D. Thain, T. Tannenbaum, M. Livny, “Distributed Computing in Practice: The Condor Experience,” Concurrency and Computation: Practice and Experience, 2005, vol. 17, no. 2-4, pp. 323-356.

V. V. Voevodin, YU. A. Joludev, S. I. Sobolev, K. S. Stefanov, “Evolyutsiya sistemyi metakompyutinga X-Com,” Vestnik Nijegorodskogo universiteta im. NI Lobachevskogo, 2009, no. 4.

J.C. Régin, M. Rezgui, A. Malapert , “Embarrassingly parallel search,” International Conference on Principles and Practice of Constraint Programming, 2013, pp. 596-610.

I. V. Lazarev, O. V. Suhoroslov, “Ispolzovanie workflow-metodologii dlya opisaniya protsessa raspredelennyih vyichisleniy,” Trudyi Instituta sistemnogo analiza Rossiyskoy akademii nauk 14, 2005, pp. 26-70.

M. Cole, “Bringing skeletons out of the closet: a pragmatic manifesto for skeletal parallel programming,” Parallel computing, 2004, vol. 30, no. 3, pp. 389-406.

H. González‐Vélez, M. Leyton, “A survey of algorithmic skeleton frameworks: high-level structured parallel programming enablers,” Software: Practice and Experience, 2010, vol. 40 no.12, pp. 1135-1160.

J. Dean,S. Ghemawat, “MapReduce: simplified data processing on large clusters,” Communications of the ACM, 2008, vol. 51, no. 1, pp. 107-113.

S. Goyal, “Public vs private vs hybrid vs community-cloud computing: a critical review,” International Journal of Computer Network and Information Security, 2014, vol. 6, no 3, pp. 20.

C. Moretti, J. Bulosan, D. Thain, , P.J. Flynn, “All-pairs: an abstraction for data-intensive cloud computing,” International Symposium on Parallel and Distributed Processing. IEEE, 2008, pp. 1–11.

W. Suksompong, “Scheduling asynchronous round-robin tournaments,” Operations Research Letters, 2016, vol. 44, no 1, pp. 96-100.

S.V. Vostokin, I.V. Bobyleva, “Using the bag-of-tasks model with centralized storage for distributed sorting of large data array,” CEUR Workshop Proceedings, 2019, vol. 2416, pp. 199-203.

S.V. Vostokin, I.V. Bobyleva, “Building an Algorithmic Skeleton for Block Data Processing on Enterprise Desktop Grids,” Communications in Computer and Information Science, 2019, vol. 1129 CCIS, pp. 678-689.

E. Lucas, “Les jeux de demoiselles,” Récréations Mathématiques (in French), Paris: Gauthier-Villars, 1883, pp. 161–197.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162