Method of managing the execution of tasks of a multithreaded program according to a given dependency graph

K.P. Nesterenko, I.V. Stetsenko

Abstract


Performance is one of the main non-functional requirements for software. As a result of the increase in the number of cores in central processing units in recent decades, the use of multithreading technology has become a primary means of improving software performance. This study analyzes the problems that arise from developing multithreaded programs and ways to address them. A method for managing the execution of tasks in a multithreaded program based on a given dependency graph is proposed and its implementation in the C++ language is demonstrated. Its aim is to reduce the resource intensity of software development and increase its reliability by addressing problems typical of developing multithreaded programs. The results of experimental research on a test set of tasks are provided, demonstrating increased performance through the use of the proposed method.

Prombles in programming 2024; 2-3: 239-246


Keywords


software; multithreading; performance; reliability; dependency graph; parallel computing; С++

References


S. Borkar, and Chien, A. (2011) 'The Future of Microprocessors', Communications of the ACM,54, 67-77. CrossRef

Yuan L., (2006) 'Multithreaded programming challenges, current practice, and languages/tools support', in 2006 IEEE Hot Chips 18 Symposium (HCS), Stanford, CA, 2006, pp. 1-134. CrossRef

Gregoire, M. (2021) 'Multithreaded Programming with C++', in Professional C++, 5th Edition. John Wiley & Sons, pp. 915-967. CrossRef

Fraser, K. and Harris, T. (2007) 'Concurrent programming without locks', ACM Transactions on Computer Systems, 25, 2, 5-es. CrossRef

Chabbi, M. and Ramanathan, M. (2022) "A study of real-world data races in Golang", in Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI 2022), pp. 474-489. CrossRef

Kahlon, V. et el. (2007), "Fast and Accurate Static Data Race Detection for Concurrent Programs", Lecture Notes in Computer Science, 4590, 226-239. CrossRef

Chen, L. et el. (2023). Data Race Detection Using Large Language Models' in SC-W '23: Proceedings of the SC'23 Workshops of The International Conference on High Performance Computing, Network, Storage, and Analysis, pp. 215-223. CrossRef

Netzer, R. and Miller, B. (1992) 'What are Race Conditions?: Some Issues and Formalizations', ACM letters on programming languages and systems, 1, pp. 74-88. CrossRef

Flanagan, C. and Freund, S. (2001). "Detecting Race Conditions in Large Programs" in PASTE'01: Proceedings of the 2001 ACM SIGPLANSIGSOFT workshop on Program analysis for software tools and engineering, pp. 90-96. CrossRef

Yousaf, M. et el. (2021) "Efficient Identification of Race Condition Vulnerability in C Code by Abstract Interpretation and Value Analysis" in IEEE International Conference on Cyber Warfare and Security. CrossRef

Ortega-Arjona, J.L. (2004) "The Manager Workers Pattern" in European Conference on Pattern Languages of Programs, pp. 53-64.

Singhal, M. (1989) 'Deadlock detection in distributed systems', Computer, 22, pp. 37-48. CrossRef

Park, Y., Scheuermann, P. and Tung, H. L. (1995), 'A Distributed Deadlock Detection and Resolution Algorithm Based on A Hybrid Wait-for Graph and Probe Generation Scheme', in CIKM '95: Proceedings of the fourth international conference on Information and knowledge management, pp. 378-386. CrossRef

Jabbour, R. and Elhajj, I. (2008) "SAF-PS: Starvation Avoidance for Priority Scheduling" in 2008 5th International Multi-Conference on Systems, Signals and Devices, SSD'08, pp. 1-6. CrossRef

Gawanmeh, A. et el. (2021). Starvation Avoidance Task Scheduling Algorithm for Heterogeneous Computing Systems. CrossRef

Abbaspour, S. et el. (2016) "A Model for Systematic Monitoring and Debugging of Starvation Bugs in Multicore Software".

Nesterenko, A. (2012) "Cycle detection algorithms and their applications", Journal of Mathematical Sciences, 182, pp. 518-526. CrossRef

Blieberger, J., Burgstaller, B., Scholz, B. (2003), "Busy Wait Analysis", Lecture Notes in Computer Science, 2655, pp. 142-152. CrossRef




DOI: https://doi.org/10.15407/pp2024.02-03.239

Refbacks

  • There are currently no refbacks.