کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874933 | 1441464 | 2018 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Memory efficient parallel algorithm for optimal DAG structure search using direct communication
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We present a novel parallel algorithm that solves the optimal directed acyclic graph search problem using less memory as compared to existing algorithms. Using a dynamic programming approach, the time and space complexity of the problem is found to be O(nâ
2n), where n represents the number of vertices. The previous algorithm uses adjacent communication to efficiently exchange data between computation nodes. However, it consumes too much memory, and thus is capable of solving up to n=36. Our novel algorithm, ParaOS-DC, employs direct communication to reduce the memory consumption; this is the main cause of the inefficiency of the previous algorithm. Through computational experiments, we confirmed that our proposed algorithm is much faster than the previous algorithm when memory is insufficient. We also succeeded in solving a problem for n=37 without any constraints, which is the largest problem size solved in literature till date.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 119, September 2018, Pages 27-35
Journal: Journal of Parallel and Distributed Computing - Volume 119, September 2018, Pages 27-35
نویسندگان
Yoshinori Tamada,