Adding Parallelism to Sequential Programs – a Combined Method

Authors

Abstract

The article outlines a contemporary method for creating software for multi-processor computers. It describes the identification of parallelizable sequential code structures. Three structures were found and then carefully examined. The algorithms used to determine whether or not certain parts of code may be parallelized result from static analysis. The techniques demonstrate how, if possible, existing sequential structures might be transformed into parallel-running programs. A dynamic evaluation is also a part of our process, and it can be used to assess the efficiency of the parallel programs that are developed. As a tool for sequential programs, the algorithms have been implemented in C#. All proposed methods were discussed using a common benchmark.

Author Biographies

Wiktor Bohdan Daszczuk, Warsaw University of Technology Institute of Computer Science

Wiktor B. Daszczuk was born in Olsztyn, Poland, in 1958. Joint Eng. and M.S. degree in computer science and technology from Warsaw University of Technology, Warsaw, Poland, 1982 Ph.D. in computer science from Warsaw University of Technology, Warsaw, Poland, 2003 D.Sc in computer science from Warsaw University of Technology, Warsaw, Poland, 2020 1982 to 1990 in the industry 1990 to 2003 - Research Assistant with the Institute of Computer Science, Warsaw University of Technology 2003 to now - Assistant Professor in t Institute of Computer Science, Warsaw University of Technology

Research interest includes the specification and verification of distributed systems and modeling of urban transport systems. Author of more than 70 publications, including a monograph, articles, conference papers and research reports. He leaded the development of PowerWatch plant monitoring system, Feniks simulator of autonomous transport systems, and Dedan verification environment. Dr. Daszczuk received Siemens Prize for Applied Research concerning PowerWatch system in 1997 and Polish Prime Minister Award for Scientific Research in Eco-Mobility project in 2016

Denny Bogdan Czejdo, Fayetteville State University, Department of Mathematics and Computer Science

Dr. Bogdan Denny Czejdo is a Belk Distinguished Professor of Science and Technology at Fayetteville State University, North Carolina. He holds a Ph.D. from Warsaw Technical University, Poland, with expertise in computer science. His research spans databases, visual languages, knowledge-based systems, robotics, computer vision, cyber-security, and geo-spatial intelligence. With over 150 publications, he collaborates nationally and locally with universities and Oak Ridge National Laboratories. Early in his career, he developed visual languages for the ER model, later applying these techniques to automatic software generation. He also contributed significantly to data integration, particularly in medical army databases, enabling improved statistical analysis, notably in non-battle military injury rates.

Wojciech Grześkowiak, Warsaw University of Technology Institute of Computer Science

Wojciech Grześkowiak – Graduate of the Warsaw University of Technology and the Warsaw School of Economics. While still a student, he worked as a Project Manager at Samsung R&D Poland, including on the first versions of Android.

In 2012, he founded his first data analytics company. Since 2018, he has been creating Trustisto.com - a marketing automation tool for online stores that uses "social proof" and "fear of missing out" as techniques to optimize conversions.

References

C. Campbell, R. Johnson, A. Miller, and S. Toub, Parallel Programming with Microsoft .NET: Design Patterns for Decomposition and Coordination on Multicore Architectures, 1st ed. Redmond, WA: Microsoft Press, 2010. ISBN: 978-0-7356-5159-3

ECMA_International, “C# language speification,” 2002. [Online]. Available: https://www.ecma-international.org/publications-and-standards/standards/ecma-334/.

A. J. Bernstein, “Analysis of Programs for Parallel Processing,” IEEE Trans. Electron. Comput., vol. EC-15, no. 5, pp. 757–763, Oct. 1966. DOI:https://doi.org/10.1109/PGEC.1966.264565

G. M. Amdahl, “Validity of the single processor approach to achieving large scale computing capabilities,” in spring joint computer conference on - AFIPS ’67 Atlantic City, NJ, April 18-20, 1967, 1967, p. 483. DOI:https://doi.org/10.1145/1465482.1465560

J. L. Gustafson, “Reevaluating Amdahl’s law,” Commun. ACM, vol. 31, no. 5, pp. 532–533, May 1988. DOI:https://doi.org/10.1145/42411.42415

M. Danelutto, J. D. Garcia, L. M. Sanchez, R. Sotomayor, and M. Torquati, “Introducing Parallelism by Using REPARA C++11 Attributes,” in 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP), Heraklion, Greece, 17-19 Feb 2016, 2016, pp. 354–358. DOI:https://doi.org/10.1109/PDP.2016.115

B. Chapman, G. Jost, and R. van der Pas, Using OpenMP - Portable Shared Memory Parallel Programming. Cambridge, MA: MIT Press, 2007. ISBN: 978-0-262-53302-7

R. Atre, A. Jannesari, and F. Wolf, “Brief Announcement: Meeting the Challenges of Parallelizing Sequential Programs,” in 29th ACM Symposium on Parallelism in Algorithms and Architectures, Washington, DC, 24 - 26 July 2017, 2017, pp. 363–365. DOI:https://doi.org/10.1145/3087556.3087592

D. Dig, “A Refactoring Approach to Parallelism,” IEEE Softw., vol. 28, no. 1, pp. 17–22, Jan. 2011. DOI:https://doi.org/10.1109/MS.2011.1

Z. Li, “Discovery of Potential Parallelism in Sequential Programs,” PhD thesis, Technische Universität Darmstadt, Department of Computer Science, 2016. [Online] Available: https://tuprints.ulb.tu-darmstadt.de/5741/7/thesis.pdf

F. Allen, M. Burke, R. Cytron, J. Ferrante, and W. Hsieh, “A framework for determining useful parallelism,” in 2nd international conference on Supercomputing - ICS ’88, St. Malo, France, 1 June 1988, 1988, pp. 207–215. DOI:https://doi.org/10.1145/55364.55385

T.-W. Huang, C.-X. Lin, G. Guo, and M. Wong, “Cpp-Taskflow: Fast Task-Based Parallel Programming Using Modern C++,” in 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), Rio de Janeiro, Brazil, 20-24 May 2019, 2019, pp. 974–983. DOI:https://doi.org/10.1109/IPDPS.2019.00105

Hongtao Zhong, Mojtaba Mehrara, Steve Lieberman, and Scott Mahlke, “Uncovering hidden loop level parallelism in sequential applications,” in 2008 IEEE 14th International Symposium on High Performance Computer Architecture, Salt Lake City, UT, 16-20 Feb 2008, 2008, pp. 290–301. DOI:https://doi.org/10.1109/HPCA.2008.4658647

A. W. Lim and M. S. Lam, “Maximizing parallelism and minimizing synchronization with affine partitions,” Parallel Comput., vol. 24, no. 3–4, pp. 445–475, May 1998. DOI:https://doi.org/10.1016/S0167-8191(98)00021-0

Z. Li, R. Atre, Z. Huda, A. Jannesari, and F. Wolf, “Unveiling parallelization opportunities in sequential programs,” J. Syst. Softw., vol. 117, pp. 282–295, Jul. 2016. DOI:https://doi.org/10.1016/j.jss.2016.03.045

G. Tagliavini, D. Cesarini, and A. Marongiu, “Unleashing Fine-Grained Parallelism on Embedded Many-Core Accelerators with Lightweight OpenMP Tasking,” IEEE Trans. Parallel Distrib. Syst., vol. 29, no. 9, pp. 2150–2163, Sep. 2018. DOI:https://doi.org/10.1109/TPDS.2018.2814602

S. Rul, H. Vandierendonck, and K. De Bosschere, “A profile-based tool for finding pipeline parallelism in sequential programs,” Parallel Comput., vol. 36, no. 9, pp. 531–551, Sep. 2010. DOI:https://doi.org/10.1016/j.parco.2010.05.006

A. Fonseca, B. Cabral, J. Rafael, and I. Correia, “Automatic Parallelization: Executing Sequential Programs on a Task-Based Parallel Runtime,” Int. J. Parallel Program., vol. 44, no. 6, pp. 1337–1358, Dec. 2016. DOI:https://doi.org/10.1007/s10766-016-0426-5

Z.-H. Du, C.-C. Lim, X.-F. Li, C. Yang, Q. Zhao, and T.-F. Ngai, “A cost-driven compilation framework for speculative parallelization of sequential programs,” ACM SIGPLAN Not., vol. 39, no. 6, pp. 71–81, Jun. 2004. DOI:https://doi.org/10.1145/996893.996852

Chen Tian, Min Feng, V. Nagarajan, and R. Gupta, “Copy or Discard execution model for speculative parallelization on multicores,” in 41st IEEE/ACM International Symposium on Microarchitecture, Como, Italy, 08-12 Nov. 2008, 2008, pp. 330–341. DOI:https://doi.org/10.1109/MICRO.2008.4771802

Microsoft, “Thread-Safe Collections.” [Online]. Available: https://learn.microsoft.com/en-us/dotnet/standard/collections/thread-safe/.

M. Harman and R. Hierons, “An overview of program slicing,” Softw. Focus, vol. 2, no. 3, pp. 85–92, 2001. DOI:https://doi.org/10.1002/swf.41

Y. Shen, M. Peng, S. Wang, and Q. Wu, “Towards parallelism detection of sequential programs with graph neural network,” Futur. Gener. Comput. Syst., vol. 125, pp. 515–525, Dec. 2021. DOI:https://doi.org/10.1016/j.future.2021.07.001

OpenAI, “ChatGPT: Optimizing Language Models for Dialogue.” [Online]. Available: https://openai.com/blog/chatgpt/.

A. Barredo Arrieta et al., “Explainable Artificial Intelligence (XAI): Concepts, taxonomies, opportunities and challenges toward responsible AI,” Inf. Fusion, vol. 58, pp. 82–115, Jun. 2020. DOI:https://doi.org/10.1016/j.inffus.2019.12.012

D. B. Czejdo, W. B. Daszczuk, and W. Grześkowiak, “Practical Approach to Introducing Parallelism in Sequential Programs,” in 18th International Conference on Dependability of Computer Systems DepCoS-RELCOMEX, Brunów, Poland, 3-7 July 2023, 2023, pp. 13–27. DOI:https://doi.org/10.1007/978-3-031-37720-4_2

Downloads

Published

2024-04-15

Issue

Vol. 70 No. 1 (2024)

Section

Applied Informatics

License

Copyright (c) 2024 International Journal of Electronics and Telecommunications

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

1. License

The non-commercial use of the article will be governed by the Creative Commons Attribution license as currently displayed on https://creativecommons.org/licenses/by/4.0/.

2. Author’s Warranties

The author warrants that the article is original, written by stated author/s, has not been published before, contains no unlawful statements, does not infringe the rights of others, is subject to copyright that is vested exclusively in the author and free of any third party rights, and that any necessary written permissions to quote from other sources have been obtained by the author/s. The undersigned also warrants that the manuscript (or its essential substance) has not been published other than as an abstract or doctorate thesis and has not been submitted for consideration elsewhere, for print, electronic or digital publication.

3. User Rights

Under the Creative Commons Attribution license, the author(s) and users are free to share (copy, distribute and transmit the contribution) under the following conditions: 1. they must attribute the contribution in the manner specified by the author or licensor, 2. they may alter, transform, or build upon this work, 3. they may use this contribution for commercial purposes.

4. Rights of Authors

Authors retain the following rights:

- copyright, and other proprietary rights relating to the article, such as patent rights,

- the right to use the substance of the article in own future works, including lectures and books,

- the right to reproduce the article for own purposes, provided the copies are not offered for sale,

- the right to self-archive the article

- the right to supervision over the integrity of the content of the work and its fair use.

5. Co-Authorship

If the article was prepared jointly with other authors, the signatory of this form warrants that he/she has been authorized by all co-authors to sign this agreement on their behalf, and agrees to inform his/her co-authors of the terms of this agreement.

6. Termination

This agreement can be terminated by the author or the Journal Owner upon two months’ notice where the other party has materially breached this agreement and failed to remedy such breach within a month of being given the terminating party’s notice requesting such breach to be remedied. No breach or violation of this agreement will cause this agreement or any license granted in it to terminate automatically or affect the definition of the Journal Owner. The author and the Journal Owner may agree to terminate this agreement at any time. This agreement or any license granted in it cannot be terminated otherwise than in accordance with this section 6. This License shall remain in effect throughout the term of copyright in the Work and may not be revoked without the express written consent of both parties.

7. Royalties

This agreement entitles the author to no royalties or other fees. To such extent as legally permissible, the author waives his or her right to collect royalties relative to the article in respect of any use of the article by the Journal Owner or its sublicensee.

8. Miscellaneous

The Journal Owner will publish the article (or have it published) in the Journal if the article’s editorial process is successfully completed and the Journal Owner or its sublicensee has become obligated to have the article published. Where such obligation depends on the payment of a fee, it shall not be deemed to exist until such time as that fee is paid. The Journal Owner may conform the article to a style of punctuation, spelling, capitalization and usage that it deems appropriate. The Journal Owner will be allowed to sublicense the rights that are licensed to it under this agreement. This agreement will be governed by the laws of Poland.

By signing this License, Author(s) warrant(s) that they have the full power to enter into this agreement. This License shall remain in effect throughout the term of copyright in the Work and may not be revoked without the express written consent of both parties.