کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951539 | 1441477 | 2017 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Designing and implementing a heuristic cross-architecture combination for graph traversal
ترجمه فارسی عنوان
طراحی و پیاده سازی ترکیبی معماری ترکیبی اکتشافی برای پیاده سازی گراف
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Breadth-First Search (BFS) is widely used in real-world applications including computational biology, social networks, and electronic design automation. The most effective BFS approach has been shown to be a combination of top-down and bottom-up approaches. Such hybrid techniques need to identify a switching point which is conventionally found through expensive trial-and-error and exhaustive search routines. We present an adaptive method based on regression analysis that enables dynamic switching at runtime with little overhead. We improve the performance of our method by exploiting popular heterogeneous platforms and efficiently design the approach for a given architecture. A 155Ã speedup is achieved over the standard top-down approach on GPUs. Our approach is the first to combine top-down and bottom-up across different architectures. Unlike combination on a single architecture, a mistuned switching point may significantly decrease the performance of cross-architecture combination. Our adaptive method can predict the switching point with high accuracy, leading to 7Ã speedup compared to the switching point in average case (1000 switching points).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 108, October 2017, Pages 95-105
Journal: Journal of Parallel and Distributed Computing - Volume 108, October 2017, Pages 95-105
نویسندگان
Yang You, Haohuan Fu, David Bader, Guangwen Yang,