ЕФЕКТИВНІСТЬ ПЛАТФОРМИ NVIDIA CUDA ДЛЯ СИСТЕМАТИЧНОГО ПОШУКУ ПРОСТИХ ЧИСЕЛ

Анотація

Стаття присвячена дослідженню ефективності використання платформи NVIDIA CUDA для систематичного пошуку простих чисел у діапазоні 1÷10⁹. Метою роботи є оптимізація процесів пошуку та тестування простих чисел із застосуванням GPGPU. Завданнями є програмна CPU- та CUDA-реалізація алгоритмів просіювання (решето Ератосфена, колісна факторизація, решето Аткіна, решето Сундарама), ймовірнісних тестів простоти (Мілера-Рабіна, Ферма, Соловея-Штрасена, Люка-Лемера), а також порівняння їх швидкодії та масштабованості, визначення переваг і обмежень GPGPU. Реалізовано алгоритми решета Ератосфена, Сундарама, колісної факторизації, тестів Мілера-Рабіна та Люка-Лемера для CPU і GPU з використанням Visual Studio та NVIDIA CUDA Toolkit. Проведено експерименти в діапазонах від мільйона до мільярда чисел із фіксацією часу пошуку, кількості знайдених простих чисел та максимального значення. Для оцінки системних характеристик застосовано Microsoft Concurrency Visualizer, що дозволив проаналізувати споживання ресурсів CPU, рівень синхронізації та ефективність розподілу навантажень. Авторами розроблено інтегральний показник продуктивності алгоритмів пошуку, який враховує пропускну здатність, ефективність паралелізації та синхронізаційні втрати. Результати показали значне скорочення часу пошуку у CUDA-реалізаціях для алгоритмів з високим паралелізмом. Решето Ератосфена забезпечує стабільне прискорення від 2 до 8 разів, колісна факторизація – до 32 разів, тест Мілера-Рабіна – до 3 разів. Водночас GPU-підхід виявив обмеження для послідовних алгоритмів: решето Сундарама працює повільніше до 3 разів, тест Люка-Лемера – у 4 рази. Профілювання виявило високий рівень синхронізації (понад 80%), що знижує ефективність та вказує на можливість подальшої оптимізації. Також зафіксовано зменшення навантаження на CPU в середньому на 20%, що відкриває перспективи створення гібридних обчислювальних систем із поєднанням ресурсів CPU та GPU. На основі дослідження сформульовано рекомендації щодо вибору алгоритмів та підходів до їх реалізації на GPU для високопродуктивних обчислень.