Comparative analysis of the effectiveness of using fine-grained and nested parallelism to increase the speedup of parallel computing in multicore computer systems

Authors

DOI:

https://doi.org/10.20535/SRIT.2308-8893.2022.2.03

Keywords:

multicore computer system, core, thread, tasks, parallelism, granularity, fork-join, speedup coefficient, fine-grained parallelism, nested parallelism, combined parallelism

Abstract

The article presents a comparative analysis of the effectiveness of using parallelism of varying granularity degrees in modern multicore computer systems using the most popular programming languages and libraries (such as C#, Java, C++, and OpenMP). Based on the performed comparison, the possibilities of increasing the efficiency of computations in multicore computer systems by using combinations of medium- and fine-grained parallelism were also investigated. The results demonstrate the high potential efficiency of fine-grained parallelism when organizing intensive parallel computations. Based on these results, it can be argued that, in comparison with more traditional parallelization methods that use medium-grain parallelism, the use of separately fine-grained parallelism can reduce the computation time of a large mathematical problem by an average of 4%. The use of combined parallelism can reduce the computation time of such a problem to 5,5%. This reduction in execution time can be significant when performing very large computations.

Author Biographies

Valerii Martell, National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute", Kyiv

Valerii Martell received a B.Sc. and the M.Sc. in Software Engineering with honors from the National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" (KPI) in 2018 and 2020 respectively and is currently working toward a Ph.D. degree at the same university. From 2017 to 2020, he was a Senior Laboratory Assistant at the Laboratory of Parallel and Distributed Computing in Computer Systems and Networks in the Department of Computer Engineering, Faculty of Informatics and Computer Science, KPI. In 2020 he also worked as a Scientific Intern with the Supercomputer of the National Academy of Sciences of Ukraine at V. M. Glushkov Institute of Cybernetics (Kyiv, Ukraine). In 2020, he was among the students awarded the Scholarship of the President of Ukraine for significant educational and scientific achievements. His current research interests include modern approaches in programming for parallel and distributed systems, high-load computing and high-load back-end technologies, computing scheduling and load balancing methods, acceleration of neural networks in clusters, and heterogeneous distributed systems.

Aleksandr Korochkin, National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute", Kyiv

Aleksandr Korochkin received a Ph.D. in Applied Mathematics from the Taras Shevchenko National University of Kyiv, Ukraine, in 1973. Since 1974 he has been with the National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute," Faculty of Informatics and Computer Science, where he is currently an Associate Professor, Head of Laboratory of Parallel and Distributed Computing in Computer Systems and Networks, and Deputy Head for Educational and Methodical Work of Department of Computer Engineering. Also, since 2000 he has been working at the National Aviation University (Kyiv, Ukraine) as an Associate Professor in the Department of Computer System and Networks, Faculty of Cybernetics, Computer and Software Engineering. Since 1994 he has been a Scientific Secretary of the Scientific and Methodological Commission of the Ministry of Education and Science of Ukraine in the field of "Computer Engineering." In 1999, he was awarded the distinction "Excellence in Education of Ukraine." Author of books "High-performance computing systems. Methodical instructions for conducting course work" (published by NAU, 2008), "Parallel and distributed computing. Laboratory Workshop. Educational and methodical manual" (Korniychuk, 2008), "Ada 95: Introduction to Programming" (Svit, 1998). His current research interests include non-autonomous arithmetic, conveyor processors, parallel programming, Hell language, organization of computational processes in parallel and distributed computer systems, and models of parallel and distributed computing.

Olga Rusanova, National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute", Kyiv

Olga Rusanova received a Ph.D. in Computer Science from the National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" (KPI), Ukraine, in 1979. Since 1980 she has been with the KPI, Faculty of Informatics and Computer Science, where she is currently an Associate Professor in the Department of Computer Engineering and Senior Scientist at the Laboratory of Parallel and Distributed Computing in Computer Systems and Networks. Also, since 2000 she has worked at the National Aviation University (Kyiv, Ukraine) as an Associate Professor in the Department of Computer System and Networks, Faculty of Cybernetics, Computer and Software Engineering. Author of books "Computing systems. Methodical instructions for conducting course work" (published by NAU, 2010), "Computer systems. Methodical instructions for conducting laboratory works" (NAU, 2008), "Software of computer systems. Features of programming and compilation." (Korniychuk, 2003). Her current research interests include the theory of parallel computing, the synthesis of parallel computer systems, the organization of calculations in parallel, clustered, heterogeneous distributed, and GRID systems, the development of methods and tools for planning the allocation of resources based on the list and duplicate algorithms, the development of software for analyzing the efficiency of cluster systems.

References

ISO 9000:2000 Quality management systems – Fundamentals and vocabulary. Available: https://www.iso.org/standard/29280.html

L. Lamport, “How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs”, IEEE Transactions on Computers, vol. C-28, no. 9, pp. 690–691, 1979. doi: 10.1109/TC.1979.1675439.

A.C. Wayne, S.J. Procter, and T.E. Anderson, “The nachos instructional operating system”, in USENIX Winter 1993 Con-ference (USENIX Winter 1993 Conference). San Diego, CA: USENIX Association, Jan. 1993. doi: 10.1.1.181.878.

B.S. Tanenbaum and H. Bos, Modern Operating Systems, 4th ed. USA: Prentice Hall Press, 2014. doi: 10.5555/2655363.

J.E. Moreira, D. Schouten, and C.D. Polychronopoulos, “The performance impact of granularity control and functional parallelism”, in Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, ser. LCPC’95, pp. 581–597. Berlin, Heidelberg: Springer-Verlag, 1995. doi: 10.5555/645673.665710.

K. Hwang, Advanced Computer Architecture: Parallelism, Scalability, Programmability, 1st ed. McGraw-HillHigher Education, 1992. doi: 10.5555/541880.

R. Miller and Q.F. Stout, Parallel Algorithms for Regular Architectures: Meshes and Pyramids. Cambridge, Mass: MITPress, 1996. doi: 10.5555/249608.

B. Blaise, Introduction to Parallel Computing. [Online]. Available: https://hpc.llnl. gov/training/tutorials/introduction-parallel-computing-tutorial/

J.L. Hennessy and D.A. Patterson, Computer Architecture, Fifth Edition: A Quantitative Approach. Morgan Kaufmann Publishers Inc., 2011. doi: 10.5555/1999263.

O. Bandman, “Composing fine-grained parallel algorithms forspatial dynamics simulation”, in Proceedings of the 8th International Conference on Parallel Computing Technologies, ser. PaCT’05, pp. 99–113. Berlin, Heidelberg: Springer-Verlag, 2005. doi: 10.1007/11535294_9.

D. Lea, “A java fork/join framework”, in Proceedings of the ACM2000 Conference on Java Grande, ser. JAVA ’00, pp. 36–43. New York, NY, USA: Association for Computing Machinery, 2000. doi: 10.1145/337449.337465.

P.E. Hadjidoukas, G.C. Philos, and V.V. Dimakopoulos, “Exploiting fine-grain thread parallelism on multicore architectures”, Sci. Program., vol. 17, no. 4, pp. 309–323, Dec. 2009. doi: 10.1155/2009/249651.

P. Czarnul, “Assessment of OpenMP master-slave implementations for selected irregular parallel applications”, Electronics, vol. 10, no. 10, 2021. doi: 10.3390/electronics10101188.

J. Ponge, Fork and Join: Java Can Excel at Painless Parallel Programming Too! [Online]. Available: https://www.oracle.com/technical-resources/articles/java/fork-join.html

O. Rusanova and A. Korochkin, “Scheduling problems for parallel and distributed systems”, Ada Lett., vol. XIX, no. 3, pp. 195–201, Sep. 1999. doi: 10.1145/319295.319323.

Downloads

Published

2022-08-30

Issue

No. 2 (2022)

Section

Progressive information technologies, high-efficiency computer systems

License

This is an open access journal which means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles in this journal without asking prior permission from the publisher or the author. This is in accordance with the BOAI definition of open access.