ПОТОКО-БЕЗОПАСНАЯ РЕАЛИЗАЦИЯ БИТОВОГО МНОЖЕСТВА С БЫСТРОЙ ОПЕРАЦИЕЙ ИЗВЛЕЧЕНИЯ МИНИМАЛЬНОГО ЧЛЕНА

УДК 004.272.2

Карасик Олег Николаевич − кандидат технических наук, ведущий инженер. Иностранное производственное унитарное предприятие «Иссофт Солюшенз» (ул. Чапаева 5, 220034, г. Минск, Республика Беларусь). E-mail: karasik.oleg.nikolaevich@gmail.com

Прихожий Анатолий Алексеевич − доктор технических наук, профессор, профессор кафедры программного обеспечения информационных систем и технологий. Белорусский национальный технический университет (пр. Независимости 65, 220013, г. Минск, Республика Беларусь). E-mail:

prihozhy@bntu.by

DOI: https://doi.org/ 10.52065/2520-6141-2025-290-10.

 

Ключевые слова: битовое множество, потоко-безопастные структуры данных, поиск первого выставленного бита, извлечение минимального члена.

Для цитирования: Карасик О. Н., Прихожий А. А. Потоко-безопасная реализация битового множества с быстрой операцией извлечения минимального члена // Труды БГТУ. Сер. 3, Физико- математические науки и информатика. 2025. № 1 (290). С. 62–69 (На англ.). DOI: 10.52065/2520-6141-2025-290-10.

Аннотация

Потоко-безопасные компактные структуры данных остаются активной областью исследований даже сегодня, когда каждый современный ПК, игровая консоль, мобильное устройство или телевизор оснащены гигабайтами оперативной памяти и многоядерными процессорами. Битовые множества (двоичный массив индивидуально-доступных битов) имеют применение в различных отраслях, таких как операционные системы, проектирование баз данных, поиск и распределение ресурсов. Существующие реализации битовых множеств сосредоточены в основном на сжатии и кодировании битов для сокращения потребляемой памяти и дискового пространства, а также на ускорении множественных битовых операций (в частности, в областях поиска и проектирования баз данных), или на сценариях с низко- и непараллельным отслеживанием и выделением ресурсов, или на использовании битовых множеств в качестве набора уникальных целых чисел с целью вставки, удаления и проверки их наличия. В данной статье предлагается потоко-безопасная реализация битового множества, предназначенная для использования в сценариях с участием огромного количества потоков, выполняющих внушительное количество параллельных операций, таких как резервирование и отслеживание ресурсов. Высокая производительность достигается за счет использования дополнительного массива индексов и нового механизма неблокирующей синхронизации. Эксперименты, проведенные на сервере, оснащенном двумя процессорами Intel Xeon E5-2620 v4, показали ускорение в 2–6 раз по сравнению с реализацией, использующей блокировку потоков.

Скачать

Список литературы

  1. Better bitmap performance with Roaring bitmaps / S. Chambi [et al.]. Software: Practice and Experience. 2015. Vol. 46, no. 5. P. 709–719. DOI: 10.1002/spe.2325.
  2. Corrales F., Chiu D., Sawin J. Variable length compression for bitmap indices // Database and Expert Systems Applications: 22nd International Conference. 2011. Vol. 2. P. 381–395.
  3. BitFunnel: Revisiting Signatures for Search / B. Coodwin [et al.] // SIGIR'17: Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2017. P. 605–614. DOI: 10.1145/3077136.3080789.
  4. BOP: A Bitset-based Optimization Paradigm for Content-based Event Matching Algorithms (S) / W. Liang [et al.] // SEKE 2023: The 35th International Conference on Software Engineering and Knowledge Engineering. 2023. P. 487–492. DOI: 10.18293/SEKE2023-142.
  5. VanCompernolle M., Barford L., Harris F. Maximum Clique Solver Using Bitsets on GPUs // Information Technology: New Generations. 2016. P. 327–337.
  6. Gueniche T., Fournier-Viger P., Tseng V. S. Compact Prediction Tree: A Lossless Model for Accurate Sequence Prediction // Advanced Data Mining and Applications. 2013. P. 177–188.
  7. McIlroy R., Dickman P., Sventek J. Efficient dynamic heap allocation of scratch-pad memory // ISMM'08: Proceedings of the 7th international symposium on Memory management. 2008. P. 31–40.
  8. BitEA: BitVertex Evolutionary Algorithm to Enhance Performance for Register Allocation / G. S. Terci [et al.] // IEEE Access. 2024. Vol. 12. P. 115497–115514. DOI: 10.1109/ACCESS.2024.3446596.
  9. Karasik O. N., Prihozhy A. A. Cooperative multi-thread scheduler for solving large-size tasks on multi-core systems // Big Data and Advanced Analytics VI. Minsk, 2020. P. 202–212.
  10. Karasik O. N., Prihozhy A. A. Blocked algorithm of finding all-pairs shortest paths in graphs divided into weakly connected clusters // System analysis and applied information science. 2024. No. 2. P. 4–10. DOI: 10.21122/2309-4923-2024-2-4-10.
  11. Prihozhy A. A., Karasik O. N. New blocked all-pairs shortest paths algorithms operating on blocks of unequal sizes // System analysis and applied information science. 2023. No. 4. P. 4–13.
  12. Prihozhy А. А., Karasik O. N. Advanced heterogeneous block-parallel all-pairs shortest path algorithm. Труды БГТУ. Сер. 3, Физико-математические науки и информатика. 2023. № 1 (266). С. 77–83.
  13. Prihozhy А. A. Generation of shortest path search dataflow networks of actors for parallel multicore implementation // Informatics. 2023. Vol. 20, no. 2. P. 65–84.
  14. Prihozhy A. A. Optimization of data allocation in hierarchical memory for blocked shortest paths algorithms // System analysis and applied information science. 2021. No. 3. P. 40–50.
  15. Karasik O. N., Prihozhy A. A. Tuning block-parallel all-pairs shortest path algorithm for efficient multi-core implementation // System analysis and applied information science. 2022. No. 3. P. 57–65.
  16. Prihozhy A. A., Karasik O. N. Influence of shortest path algorithms on energy consumption of multicore processors // System analysis and applied information science. 2023. No. 2. P. 4–12.

Поступила 15.11.2024