کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4959014 | 1445465 | 2017 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A low-space algorithm for the subset-sum problem on GPU
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We present a highly scalable parallel solution for the Subset-Sum Problem on Graphics Processing Units (GPUs) that substantially reduces the memory access by the device and, consequently, decreases the total runtime. We test this algorithm only on hard instances, which require the exhaustion of the entire search space, instead of simple random benchmarks. On a GPU with only 1.2Â GB of global memory, we address hard instances with 100,000 items limited to 106 and 200 items limited to 108. Our algorithm achieves excellent runtimes outperforming the best-known practical and parallel algorithms, reaching speed-ups higher than 1000 in the best case compared to its sequential version.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 83, July 2017, Pages 120-124
Journal: Computers & Operations Research - Volume 83, July 2017, Pages 120-124
نویسندگان
V.V. Curtis, C.A.A. Sanches,