Abstract

We present a simple deterministic parallel algorithm that runs on a CRCW PRAM and sorts n integers of size polynomial in n in time O(log n) using  processors. It is closer to optimality than any previously known deterministic algorithm that solves the stated restricted sorting problem in polylog time

چکیده

ما یک الگوریتم موازی قطعی ساده که روی CRCW PRAM اجرا می‌شود و n عدد صحیح را در زمان چندجمله‌ای نسبت به n با مرتبه‌ی O(log n)  و با استفاده از O(n log log n/log n)پردازنده مرتب  می‌کند، ارائه می‌کنیم. این الگوریتم نسبت به الگوریتم‌های قطعی قبلی به بهینه نزدیک‌تر است و مسئله‌ی محدود مرتب‌سازی بیان شده را در زمان poly log حل می‌کند.

1-مقدمه

واضح است که n شیء از یک مجموعه‌ی مرتب کامل می‌تواند با n پردازنده در زمان O(log n) پردازنده، حتی با یک مدل بسیار ضعیف محاسبات موازی مانند شبکه پردازنده‌ی درجه محدود(فرض کنید مقایسه‌های باینری در یک واحد زمانی انجام می‌شوند) انجام شود. بهینه بودن نتیجه به این معناست که حاصل ضرب تعداد پردازنده‌ها در زمان لازم O(n log n) است، تا با یک کران زمانی کمتر Ω(n log n) برای هر الگوریتم ترتیبی عمل کننده بر اساس درخت تصمیم مقایسه شود. بنابراین هیچ الگوریتم مرتب‌سازی موازی کلی که در زمان O(log n) کار کند نمی‌تواند با o(n) پردازنده به این زمان دست یابد...