Тестування роботи точного алгоритму для задачі про суму підмножини на різних персональних комп’ютерах
У цій роботі досліджується продуктивність точного алгоритму для NP-повної задачі про підмножину сум на різних персональних комп'ютерах. Задача про підмножину сум запитує, чи існує підмножина заданої множини цілих чисел, сума якої дорівнює заданому цільовому значенню. Пошук точних рішень для ве...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Oles Honchar Dnipro National University
2024-06-01
|
| Series: | Challenges and Issues of Modern Science |
| Subjects: | |
| Online Access: | https://cims.fti.dp.ua/j/article/view/139 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1823858830854848512 |
|---|---|
| author | Михайло Ленський Ганна Михальчук |
| author_facet | Михайло Ленський Ганна Михальчук |
| author_sort | Михайло Ленський |
| collection | DOAJ |
| description |
У цій роботі досліджується продуктивність точного алгоритму для 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 рази швидше, ніж на найслабшій протестованій системі. Оптимальна кількість потоків варіюється для різних розмірів вхідних даних і графічних процесорів. Масивний паралелізм, спеціалізована архітектура та висока пропускна здатність пам'яті графічних процесорів сприяють їхній ефективності для цієї високо паралелізованої задачі. Запропонований алгоритм може бути використаний як основа для вирішення інших пов'язаних задач.
|
| format | Article |
| id | doaj-art-3a03e146ec294fa085f413176dcc667c |
| institution | Kabale University |
| issn | 3083-5704 |
| language | English |
| publishDate | 2024-06-01 |
| publisher | Oles Honchar Dnipro National University |
| record_format | Article |
| series | Challenges and Issues of Modern Science |
| spelling | doaj-art-3a03e146ec294fa085f413176dcc667c2025-02-11T09:52:16ZengOles Honchar Dnipro National UniversityChallenges and Issues of Modern Science3083-57042024-06-012Тестування роботи точного алгоритму для задачі про суму підмножини на різних персональних комп’ютерахМихайло Ленський0https://orcid.org/0009-0001-1445-2142Ганна Михальчук1https://orcid.org/0000-0002-5476-6349Дніпровський національний університет імені Олеся ГончараДніпровський національний університет імені Олеся Гончара У цій роботі досліджується продуктивність точного алгоритму для 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 рази швидше, ніж на найслабшій протестованій системі. Оптимальна кількість потоків варіюється для різних розмірів вхідних даних і графічних процесорів. Масивний паралелізм, спеціалізована архітектура та висока пропускна здатність пам'яті графічних процесорів сприяють їхній ефективності для цієї високо паралелізованої задачі. Запропонований алгоритм може бути використаний як основа для вирішення інших пов'язаних задач. https://cims.fti.dp.ua/j/article/view/139задача про підмножину сумпаралельний алгоритмграфічний процесорпродуктивність |
| spellingShingle | Михайло Ленський Ганна Михальчук Тестування роботи точного алгоритму для задачі про суму підмножини на різних персональних комп’ютерах Challenges and Issues of Modern Science задача про підмножину сум паралельний алгоритм графічний процесор продуктивність |
| title | Тестування роботи точного алгоритму для задачі про суму підмножини на різних персональних комп’ютерах |
| title_full | Тестування роботи точного алгоритму для задачі про суму підмножини на різних персональних комп’ютерах |
| title_fullStr | Тестування роботи точного алгоритму для задачі про суму підмножини на різних персональних комп’ютерах |
| title_full_unstemmed | Тестування роботи точного алгоритму для задачі про суму підмножини на різних персональних комп’ютерах |
| title_short | Тестування роботи точного алгоритму для задачі про суму підмножини на різних персональних комп’ютерах |
| title_sort | тестування роботи точного алгоритму для задачі про суму підмножини на різних персональних комп ютерах |
| topic | задача про підмножину сум паралельний алгоритм графічний процесор продуктивність |
| url | https://cims.fti.dp.ua/j/article/view/139 |
| work_keys_str_mv | AT mihajlolensʹkij testuvannârobotitočnogoalgoritmudlâzadačíprosumupídmnožininaríznihpersonalʹnihkompûterah AT gannamihalʹčuk testuvannârobotitočnogoalgoritmudlâzadačíprosumupídmnožininaríznihpersonalʹnihkompûterah |