Остання редакція: 2026-01-31
Анотація
У роботі розглянуто розробку та дослідження паралельного k-арного алгоритму пошуку, який є адаптацією класичного методу бінарного пошуку для багатоядерних архітектур на основі стратегії «Розділяй і володарюй» (Divide and Conquer). Проаналізовано проблему «стіни пам’яті» (Memory Wall) та обмеження продуктивності послідовних алгоритмів. Розроблено програмну реалізацію алгоритму мовою C++ з використанням технології OpenMP, побудовано математичну модель, що враховує накладні витрати на синхронізацію. Проведено експериментальне тестування на масивах до 100 млн елементів. Результати показали, що хоча паралельний алгоритм значно випереджає лінійний пошук, на примітивних типах даних його ефективність обмежується системним оверхедом порівняно з бінарним пошуком
Ключові слова
Посилання
1.Leskovec J., Rajaraman A., Ullman J. D. Mining of Massive Datasets. 3rd ed. Cambridge : Cambridge University Press, 2020. 565 p.
2.Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms. 4th ed. Cambridge : MIT Press, 2022. 1312 p.
3.Hager G., Wellein G. Introduction to High Performance Computing for Scientists and Engineers. Boca Raton : CRC Press, 2010. 356 p.
4.Марченко О. І., Марченко О. О. Структури даних та алгоритми : підручник. Частина 1. Київ : КПІ ім. Ігоря Сікорського, 2024. 268 с.
5.Hennessy J. L., Patterson D. A. Computer Architecture: A Quantitative Approach. 6th ed. San Francisco : Morgan Kaufmann, 2019. 936 p.
6.Мельник А. О. Архітектура комп’ютера : підручник. Луцьк : Волинська обласна друкарня, 2008. 470 с.
7.Креневич А. П. Алгоритми і структури даних : підручник. Київ : ВПЦ "Київський університет", 2021. 200 с.
8.Grama A., Gupta A., Karypis G., Kumar V. Introduction to Parallel Computing. 2nd ed. Harlow: Pearson Education,2003. 856.
9.Knuth D. E. The Art of Computer Programming. Vol. 3: Sorting and Searching. 2nd ed. Reading, Massachusetts : Addison-Wesley, 1998. 780 p.
10.The OpenMP API specification for parallel programming. URL: http://www.openmp.org.
11.Шпак З. Я. Програмування мовою C++: підручник. Львів: Видавництво Львівської політехніки, 2011. 436 с.
12.Технічна документація Microsoft. URL: https://docs.microsoft.com/uk-ua/.