skip to Main Content
مرتب سازی در GPU ها برای مجموعه داده های بزرگ مقیاس: مقایسه کامل

مرتب سازی در GPU ها برای مجموعه داده های بزرگ مقیاس: مقایسه کامل

عنوان انگلیسی: Sorting on GPUs for large scale datasets: A thorough comparison
سال نشر: ۲۰۱۲
نویسنده: Gabriele Capannini, Fabrizio Silvestri, Ranieri Baraglia
رشته های مرتبط: کامپویتر ، مدیریت ، معماری
تعداد صفحه فارسی: ۳۳ – تعداد صفحه انگلیسی: ۱۵
شناسه: ۱۰.۱۰۱۶/j.ipm.2010.11.010
دانشگاه: Information Science and Technology Inst., via G. Moruzzi 1, 56100 Pisa, Italy
نشریه: Information Processing & Management

چکیده

گرچه مرتب سازی در بسیاری از کارهای تحقیقاتی مطالعه شده است، هنوز دارای چالش است به ویژه اگر پیامدهای تکنولوژی های پردازشگر نوین مانند چندهسته ای ها را بدانیم (به عبارتی GPUها، Cell/BE، چند هسته ای، و غیره). در این مقاله، الگوریتم های مختلف برای مرتب سازی اعداد صحیح در رویه چندپردازشگری را مقایسه کردیم و دوام انها در مجموعه داده های بزرگ مقیاس را مورد بحث قرار دادیم( مانند آنهایی که با موتور جستجو مدیریت شدند). به منظور بهره برداری کامل از توانایی معماری زمینه، ما یک نسخه بهینه از شبکه مرتب کننده در مدل-k طراحی کردیم، مدل محاسباتی نوین که برای لحاظ نمودن تمامی ویژگی های مهم معماری چند هسته ای طراحی شده است. مطابق مدل-k، نقشه برداری شبکه مرتب سازی پیوسته سه جنبه مهم معماوری های چند هسته ای را بهبود بخشیده است، به عبارت دیگر، بهره برداری پردازشگر، و استفاده از پهنای باند حافظه چیپ روشن/ چیپ خاموش. بعلاوه، ما قادریم تا به یک پیچیدگی فضایی Θ (۱) برسیم. به طور تجربی راه حل های خود را با تکنیک های صنعتی( به نام های Quiksort و Radixsort) در GPU  ها مقایسه کردیم. همچنین ما پیچیدگی در مدل –k را برای چنین الگوریتم هایی مقایسه کردیم. ارزیابی صورت گرفته تاکید کرد که شبکه مرتب سازی پیوسته ما از Quiksort سریعتر و از radix کندتر است، هنوز به عنوان یک راه حل درجا، نسبت به دو الگوریتم دیگر حافظه کمتری استفاده می کند.

Abstract

Although sort has been extensively studied in many research works, it still remains a challenge in particular if we consider the implications of novel processor technologies such as manycores (i.e. GPUs, Cell/BE, multicore, etc.). In this paper, we compare different algorithms for sorting integers on stream multiprocessors and we discuss their viability on large datasets (such as those managed by search engines). In order to fully exploit the potentiality of the underlying architecture, we designed an optimized version of sorting network in the K-model, a novel computational model designed to consider all the important features of many-core architectures. According to K-model, our bitonic sorting network mapping improves the three main aspects of many-core architectures, i.e. the processors exploitation, and the on-chip/off-chip memory bandwidth utilization. Furthermore we are able to attain a space complexity of Θ(۱). We experimentally compare our solution with state-of-the-art ones (namely, Quicksort and Radixsort) on GPUs. We also compute the complexity in the K-model for such algorithms. The conducted evaluation highlight that our bitonic sorting network is faster than Quicksort and slightly slower than radix, yet being an in-place solution it consumes less memory than both algorithms.

۵۰,۰۰۰ ریال – خرید
امتیاز شما:
(No Ratings Yet)
Back To Top