Efficient Reordering of Multiple Memory Operations in a Multithreaded Program
This paper is devoted to various methods of constructing all kinds of linear orders for partially ordered sets. The complexity of the problem lies in the fact that even for a set of small size, constructing and checking for any feature of its possible linear orders can lead to the need of enumeratio...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
The Fund for Promotion of Internet media, IT education, human development «League Internet Media»
2024-03-01
|
| Series: | Современные информационные технологии и IT-образование |
| Subjects: | |
| Online Access: | https://sitito.cs.msu.ru/index.php/SITITO/article/view/1068 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850060530606145536 |
|---|---|
| author | Ilya Andreev Konstantin Vladimirov |
| author_facet | Ilya Andreev Konstantin Vladimirov |
| author_sort | Ilya Andreev |
| collection | DOAJ |
| description | This paper is devoted to various methods of constructing all kinds of linear orders for partially ordered sets. The complexity of the problem lies in the fact that even for a set of small size, constructing and checking for any feature of its possible linear orders can lead to the need of enumeration of huge number of options. A special case of this general problem is the construction of all possible reorderings for memory operations in multithreaded programs, taking into account the memory model. The goal of this work is to reduce the search space in this case. An important practical example is the consideration of memory models that allow buffering of downloads. In this case, it becomes possible to establish equivalence classes over permutations of operations. This in turn is of great importance for memory verification in multithreaded systems. Today, litmus tests are used for this type of verification, which have their limitations. In this paper, an algorithm is proposed that takes into account equivalence classes when reordering memory operations, which can significantly reduce both the number of necessary permutations and the time spent on their enumeration. The results of the study allow us to effectively generalize the concept of litmus tests to arbitrary partially ordered sets and significantly expand their applicability. |
| format | Article |
| id | doaj-art-26bf7082d85f4841aaeab5a3afedadab |
| institution | DOAJ |
| issn | 2411-1473 |
| language | Russian |
| publishDate | 2024-03-01 |
| publisher | The Fund for Promotion of Internet media, IT education, human development «League Internet Media» |
| record_format | Article |
| series | Современные информационные технологии и IT-образование |
| spelling | doaj-art-26bf7082d85f4841aaeab5a3afedadab2025-08-20T02:50:32ZrusThe Fund for Promotion of Internet media, IT education, human development «League Internet Media»Современные информационные технологии и IT-образование2411-14732024-03-0120114915610.25559/SITITO.020.202401.149-156Efficient Reordering of Multiple Memory Operations in a Multithreaded ProgramIlya Andreev0https://orcid.org/0000-0001-6450-7917Konstantin Vladimirov1https://orcid.org/0000-0003-0925-1300Moscow Institute of Physics and Technology (National Research University), Dolgoprudny, RussiaMoscow Institute of Physics and Technology (National Research University), Dolgoprudny, RussiaThis paper is devoted to various methods of constructing all kinds of linear orders for partially ordered sets. The complexity of the problem lies in the fact that even for a set of small size, constructing and checking for any feature of its possible linear orders can lead to the need of enumeration of huge number of options. A special case of this general problem is the construction of all possible reorderings for memory operations in multithreaded programs, taking into account the memory model. The goal of this work is to reduce the search space in this case. An important practical example is the consideration of memory models that allow buffering of downloads. In this case, it becomes possible to establish equivalence classes over permutations of operations. This in turn is of great importance for memory verification in multithreaded systems. Today, litmus tests are used for this type of verification, which have their limitations. In this paper, an algorithm is proposed that takes into account equivalence classes when reordering memory operations, which can significantly reduce both the number of necessary permutations and the time spent on their enumeration. The results of the study allow us to effectively generalize the concept of litmus tests to arbitrary partially ordered sets and significantly expand their applicability.https://sitito.cs.msu.ru/index.php/SITITO/article/view/1068multithreadingreordering of operationsmemory modelslinear orderlitmus tests |
| spellingShingle | Ilya Andreev Konstantin Vladimirov Efficient Reordering of Multiple Memory Operations in a Multithreaded Program Современные информационные технологии и IT-образование multithreading reordering of operations memory models linear order litmus tests |
| title | Efficient Reordering of Multiple Memory Operations in a Multithreaded Program |
| title_full | Efficient Reordering of Multiple Memory Operations in a Multithreaded Program |
| title_fullStr | Efficient Reordering of Multiple Memory Operations in a Multithreaded Program |
| title_full_unstemmed | Efficient Reordering of Multiple Memory Operations in a Multithreaded Program |
| title_short | Efficient Reordering of Multiple Memory Operations in a Multithreaded Program |
| title_sort | efficient reordering of multiple memory operations in a multithreaded program |
| topic | multithreading reordering of operations memory models linear order litmus tests |
| url | https://sitito.cs.msu.ru/index.php/SITITO/article/view/1068 |
| work_keys_str_mv | AT ilyaandreev efficientreorderingofmultiplememoryoperationsinamultithreadedprogram AT konstantinvladimirov efficientreorderingofmultiplememoryoperationsinamultithreadedprogram |