Тестування роботи точного алгоритму для задачі про суму підмножини на різних персональних комп’ютерах

Анотація

У цій роботі досліджується продуктивність точного алгоритму для NP-повної задачі про підмножину сум на різних персональних комп'ютерах. Задача про підмножину сум запитує, чи існує підмножина заданої множини цілих чисел, сума якої дорівнює заданому цільовому значенню. Пошук точних рішень для великих випадків є обчислювально складним через експоненційне зростання можливих підмножин. Запропонований алгоритм використовує паралельний підхід з поверненням назад, який складається з фази пошуку в ширину, виконуваної на процесорі, і фази пошуку в глибину, виконуваної на графічному процесорі. Фаза пошуку в ширину починається з порожньої підмножини, поступово додаючи елементи та зберігаючи проміжні підмножини і суми в черзі. Правила обрізання гілок відкидають непродуктивні підмножини. Коли досягається глибина пошуку, черга передається в пам'ять графічного процесора, і декілька потоків виконують паралельні пошуки в глибину на різних піддеревах, використовуючи стек для проміжних підмножин і сум. Фаза пошуку в глибину дотримується тієї ж логіки обрізання. Вона завершується, коли всі потоки завершують свою роботу або знаходиться рішення. Алгоритм був реалізований на C# з використанням бібліотеки ILGPU, яка забезпечує високорівневі абстракції для програмування на графічних процесорах. Тести продуктивності проводилися на трьох персональних комп'ютерах з різними конфігураціями CPU та GPU: Intel Core i5-8250U з Nvidia GeForce MX150, AMD Ryzen 7 5800H з Nvidia GeForce GTX 1650, та AMD Ryzen 5 7600 з Nvidia GeForce RTX 4070 Ti SUPER. Результати демонструють значне прискорення, досягнуте завдяки паралелізації на графічних процесорах у порівнянні з послідовним виконанням на процесорі. Для вхідної множини з 1000 елементів найшвидший час становив 567 мс на RTX 4070 Ti SUPER з 16384 потоками, що майже в 12 разів швидше, ніж виконання на процесорі того ж комп'ютера, і в 43 рази швидше, ніж на найслабшій протестованій системі. Оптимальна кількість потоків варіюється для різних розмірів вхідних даних і графічних процесорів. Масивний паралелізм, спеціалізована архітектура та висока пропускна здатність пам'яті графічних процесорів сприяють їхній ефективності для цієї високо паралелізованої задачі. Запропонований алгоритм може бути використаний як основа для вирішення інших пов'язаних задач.