Abstract
The method of constructing a schedule for parallel algorithm execution is considered in the article. This algorithm takes into account the execution time of each operation of the algorithm and the relationship of operations on the data. The method is based on an information graph in which the nodes are the operations of the algorithm, and the edges are the directions of the data transfer. As a result of the interchange of operations between computing nodes, it is possible to achieve a reduction in the execution time of the algorithm by reducing the time spent on data transfer between computing nodes and reducing the downtime of computational nodes. The algorithm can be applied both in parallel programming and in adjacent areas, for example, when scheduling tasks in distributed systems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
He, B., Tang, L., Xie, J., Wang, X., Song, A.: Parallel numerical simulations of three-dimensional electromagnetic radiation with MPI-CUDA paradigms. Math. Probl. Eng. 2015 (2015). Article ID 823426, 9 p.
Jiancheng, Q., Yiqin, L., Yu, Z.: Parallel algorithm for wireless data compression and encryption. J. Sens. 2017 (2017). Article ID 4209397, 11 p.
Gong, C., Bao, W., Tang, G., Jiang, Y., Liu, J.: A parallel algorithm for the two-dimensional time fractional diffusion equation with implicit difference method. Sci. World J. 2014 (2014). Article ID 219580, 8 p.
Ma, X., Liu, S., Xiao, M., Xie, G.: Parallel algorithm with parameters based on alternating direction for solving banded linear systems. Math. Probl. Eng. 2014 (2014). Article ID 752651, 8 p.
Hou, J., Lv, Q., Xiao, M.: A parallel preconditioned modified conjugate gradient method for large Sylvester matrix equation. Math. Probl. Eng. 2014 (2014). Article ID 598716, 7 p.
Yu, D.-X., Yang, Z.-S., Yu, Y., Jiang, X.-R.: Research on large-scale road network partition and route search method combined with traveler preferences. Math. Probl. Eng. 2013 (2013). Article ID 950876, 8 p.
Amdahl, G.M.: Validity of the single processor approach to achieving large scale computing capabilities. In: Proceedings of the AFIPS Spring Joint Computer Conference, pp. 483–485. AFIPS Press, Reston (1967)
Ware, W.: The ultimate computer. IEEE Spectr. 9, 84–91 (1972)
Grama, A., Gupta, A., Karypis, G., Kumar, V.: Introduction to Parallel Computing, 2nd edn. Addison Wesley, USA (2003)
Gergel, V.P., Strongin, R.G.: Parallel Computing for Multiprocessor Computers. NGU Publications, Nizhnij Novgorod (2003). (in Russian)
Quinn, M.J.: Parallel Programming in C with MPI and OpenMP, 1st edn. McGraw-Hill Education, New York (2003)
Wittwer, T.: An Introduction to Parallel Programming. VSSD uitgeverij, Netherlands (2006)
Tiwari, A., Tabatabaee, V., Hollingsworth, J.K.: Tuning parallel applications in parallel. Parallel Comput. 35(8–9), 475–492 (2009)
Mubarak, M., Seol, S., Qiukai, L., Shephard, M.S.: A parallel ghosting algorithm for the flexible distributed mesh database. Sci. Program. 21(1–2), 17–42 (2013)
Kruatrachue, B., Lewis, T.: Grain size determination for parallel processing. IEEE Softw. 5(1), 23–32 (1988)
Meuer, H., Strohmaier, E., Dongarra, J., Simon, H.: Top500 supercomputing sites (2015)
Yang, T., Gerasoulis, A.: DSC: scheduling parallel tasks on an unbounded number of processors. IEEE Trans. Parallel Distrib. Syst. 5(9), 951–967 (1994)
Darbha, S., Agrawal, D.P.: Optimal scheduling algorithm for distributed memory machines. IEEE Trans. Parallel Distrib. Syst. 9(1), 87–95 (1998)
Liu, C.L., Layland, J.W.: Scheduling algorithms for multiprogramming in hard real-time environment. J. ACM 20(1), 46–61 (1973)
Marte, B.: Preemptive scheduling with release times, deadlines and due times. J. ACM 29(3), 812–829 (1982)
Burns, A.: Scheduling hard real-time systems: a review. Softw. Eng. J. 6(3), 116–128 (1991)
Stankovic, J.A.: Implications of Classical Scheduling Results for Real-Time Systems. IEEE Computer Society Press, Los Alamitos (1995)
Tzen, T.H., Ni, L.M.: Trapezoid self-scheduling: a practical scheduling scheme for parallel compilers. IEEE Trans. Parallel Distrib. Syst. 4, 87–98 (1993)
Sinnen, O., Sousa, L.A.: Communication contention in task scheduling. IEEE Trans. Parallel Distrib. Syst. 16, 503–515 (2005)
Kupriyanov, M.S., Shichkina, Y.A.: Applying the list method to the transformation of parallel algorithms into account temporal characteristics of operations. In: Proceedings of the 19th International Conference on Soft Computing and Measurements, SCM 2016, 7519759, pp. 292–295 (2016). https://doi.org/10.1109/SCM.2016.7519759. ISBN: 978-146738919-8
Shichkina, Y., Kupriyanov, M., Al-Mardi, M.: Optimization algorithm for an information graph for an amount of communications. In: Galinina, O., Balandin, S., Koucheryavy, Y. (eds.) NEW2AN/ruSMART-2016. LNCS, vol. 9870, pp. 50–62. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-46301-8_5
Kwok, Y.-K., Ahmad, I.: Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Comput. Surv. (CSUR) 31(4), 406–471 (1999)
Shichkina, Y., Gushchanskiy, D., Degtyarev, A.: Information graph-based creation of parallel queries for databases. Int. J. Bus. Intell. Data Min. 13(4), 475–491 (2018). https://doi.org/10.1504/IJBIDM.2017.10004785
Shichkina, Y., Degtyarev, A., Gushchanskiy, D., Iakushkin, O.: Application of optimization of parallel algorithms to queries in relational databases. In: Gervasi, O., et al. (eds.) ICCSA 2016. LNCS, vol. 9787, pp. 366–378. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-42108-7_28
Bogdanov, A., Degtyarev, A., Korkhov, V., Gaiduchok, V., Gankevich, I.: Virtual supercomputer as basis of scientific computing. In: Horizons in Computer Science Research, vol. 11, pp. 159–198. Nova Science Publishers, Inc., New York (2015). 203 p.
Acknowledgments
The paper has been prepared within the scope of the state project “Initiative scientific project” of the main part of the state plan of the Ministry of Education and Science of Russian Federation (task No 2.6553.2017/8.9 BCH Basic Part) and partly supported by Russian Fund for Basic Research (grant No 16-07-00886).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Shichkina, Y., Awadh, AM.M.H., Storublevtcev, N., Degtyarev, A. (2018). The Construction of the Parallel Algorithm Execution Schedule Taking into Account the Interprocessor Data Transfer. In: Gervasi, O., et al. Computational Science and Its Applications – ICCSA 2018. ICCSA 2018. Lecture Notes in Computer Science(), vol 10963. Springer, Cham. https://doi.org/10.1007/978-3-319-95171-3_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-95171-3_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-95170-6
Online ISBN: 978-3-319-95171-3
eBook Packages: Computer ScienceComputer Science (R0)