کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
432398 688881 2013 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Oblivious algorithms for multicores and networks of processors
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Oblivious algorithms for multicores and networks of processors
چکیده انگلیسی


• Introduce the notion of multicore-oblivious algorithms.
• Propose a hierarchical multi-level caching model for multicores.
• Present efficient multicore-oblivious algorithms for matrix transposition, FFT, sorting, the Gaussian Elimination Paradigm, list ranking, and connected components.
• Show that several of our multicore-oblivious algorithms translate into efficient network-oblivious algorithms.

We address the design of algorithms for multicores that are oblivious to machine parameters. We propose HM, a multicore model consisting of a parallel shared-memory machine with hierarchical multi-level caching, and we introduce a multicore-oblivious approach to algorithms and schedulers for HM. A multicore-oblivious algorithm is specified with no mention of any machine parameters, such as the number of cores, number of cache levels, cache sizes and block lengths. However, it is equipped with a small set of instructions that can be used to provide hints to the run-time scheduler on how to schedule parallel tasks. We present efficient multicore-oblivious algorithms for several fundamental problems including matrix transposition, FFT, sorting, the Gaussian Elimination Paradigm, list ranking, and connected components. The notion of a multicore-oblivious algorithm is complementary to that of a network-oblivious algorithm, introduced by Bilardi et al. (2007)  [8] for parallel distributed-memory machines where processors communicate point-to-point. We show that several of our multicore-oblivious algorithms translate into efficient network-oblivious algorithms, adding to the body of known efficient network-oblivious algorithms.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 73, Issue 7, July 2013, Pages 911–925
نویسندگان
, , , ,