کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6874916 1441463 2018 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Exploiting social network graph characteristics for efficient BFS on heterogeneous chips
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Exploiting social network graph characteristics for efficient BFS on heterogeneous chips
چکیده انگلیسی
In this paper, we assess several approaches to perform BFS on different heterogeneous chips (a multicore CPU and an integrated GPU). In particular, we propose three heterogeneous approaches that exploit the collaboration between both devices: Selective, Concurrent and Asynchronous. We identify how to take advantage of the features of social network graphs, that are a particular example of highly connected graphs-with fewer iterations and more unbalanced-, as well as the drawbacks of each algorithmic implementation. One key feature of our approaches is that they switch between different versions of the algorithm, depending on the device that collaborates in the computation. Through exhaustive evaluation we find that our heterogeneous implementations can be up to 1.56× faster and 1.32× more energy efficient with respect to the best baseline where only one device is used, being the overhead w.r.t. an oracle scheduler below 10%. We also compare with other related heterogeneous approach finding that ours can be up to 3.6× faster.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 120, October 2018, Pages 282-294
نویسندگان
, , , ,