دانلود مقاله یک الگوریتم مرتب سازی موازی برای اتوماتای سلولی خطی

بخشی از مقاله

چکیده:
مرتـبسـازي یکـی از مـسائل کـاربردي در بـسیاري از علـوم

مهندسی میباشد. به همین جهت الگوریتمهاي متنوعی از مرتبسـازي با دیدگاههاي متفاوت و پیچیدگیهاي مختلف گـزارش شـده اسـت. در این مقاله دو الگوریتم مرتبسازي جدید بـراي اتوماتـاي سـلولی خطـی پیشنهاد شده است. این دو الگوریتم در مقایسه با تنها الگوریتم گـزارش شده براي اتوماتاي سلولی خطی از نوع همـسایگی، شـعاع همـسایگی و قوانین متفـاوتی برخـوردار اسـت، همچنـین سـاختار اتوماتـاي سـلولی استفاده شده در آن نیازي به حافظه اضـافینـدارد بـراي مرتـبسـازي .

الگوریتمهاي معرفیشده در مقایسه بـا تنهـا الگـوریتم گـزارش شـده از همسایگی کوچکتري برخوردار میباشند و نیازمنـد محاسـبات کمتـري براي مرتبسازي میباشند.

واژههاي کلیدي: الگوریتمهاي مرتبسازي، پردازش موازي، اتوماتاي

سلولی.

page7-1 ﻣﻘﺪﻣﻪ

اتوماتاي سلولی، مدلی مبتنی بر ساختار سـلولی بـوده کـه رفتـارش بـر اساس ارتباط محلی استوار میباشد. هر سلول بر اساس اطلاعات محلی، اطلاعات موجود در خود را پردازش میکنـد. قـوانین محلـی حـاکم بـر اتوماتاي سلولی در هر مرحله، وضعیت جدید هر سـلول را بـا توجـه بـه وضعیت همسایههاي مجاور سلول بدست می آورد .[1] تنـوع و سـادگی کارکرد اتوماتاي سلولی، امکان استفاده در علوم مختلفی مانند، فیزیـک، ریاضی، کامپیوتر و حتی بیولوژیک را فراهم ساخته است. ارتباط محلـی از طریق تعامل همسایگی، پـردازش محلـی اطلاعـات از طریـق قـوانین محلی حاکم، پردازش موازي اطلاعات در تمـامی سـلولهـا بـه صـورت همزمان و توزیعی بودن پردازش اطلاعات موجب گـسترش اتوماتـاهـاي سلولی در زمینههاي مختلف کاربردي، شـبیهسـازي و تحقیقـاتی شـده است. یکی از موارد مورد توجه محققین، حل مسائل پایه ماننـد مـسائل مرتبط به گراف، مرتبسازي اعداد و تولید زنجیره اعداد تصادفی توسـط اتوماتاي سلولی میباشد.

مرتبسازي داده هـا یکـی از مـسائل مـورد توجـه در کـاربردهـاي متنوعی چون پردازش تصاویر، محاسبات گرافهـا، مـسائل پایگـاه داده،

کاربردهاي اندازهگیري و از این دست می باشد. مـیتـوان الگـوریتمهـاي مرتبسازي را به دوسته الگوریتمهاي ترتیبـی و الگـوریتمهـاي مـوازي تقسیم نمود. الگوریتمهاي موازي از دیدگاه نحـوه حـل مـسئله و مـوارد مورد استفاده آن به دو دسته الگوریتمهاي بر مبناي مدلهاي ریاضـی و الگوریتمهاي وابسته به بستر پیادهسازي تقسیم میشوند. الگوریتمهـاي بر مبناي ماشینهاي SIMD از دسته الگـوریتمهـاي وابـسته بـه بـستر پیادهسازي میباشند. در ایـن الگـوریتمهـاعمومـاً آرایـه یـک بعـدي از پردازندهها از طریق الگوریتم انتقال زوج و فرد1، n عنـصر دادهاي را بـا استفاده از n پردازنده مقایـسه و مرتـب مـینماینـد. دسـتهاي دیگـر از الگوریتمهاي وابسته به بستر بر اساس ماشینهاي موازي MIMD و بر مبناي الگوریتم مرتبسازي سریع2 میباشند. بسیاري از الگـوریتمهـاي ترتیبــی ماننــد مرتــب ســازي انتخــابی3، مرتــبســازي ترکیبــی4 و یــا مرتــبســازي ســریع بــا راهکارهــاي متنــاظر بــا پــردازش مــوازي، در سیستمهاي موازي مورد استفاده قرار گرفتهاند .[3-9]

دستهاي دیگر از الگوریتمهاي مرتبسازي، الگوریتمهاي بر مبنـاي مدلهاي ریاضی مانند اتوماتاهاي سلولی5 و آرایههاي تپنـده[2] 6 بـوده که منفک شده از مفهوم بستر پیادهسازي میباشند. اگرچه الگوریتمهاي بر مبناي مدلهاي ریاضی از دیدگاههاي مختلف پردازش موازي حاصـل شدهاند، با این وجود بر اساس قوانین حاکم بر محیطشان، قابلیت تبدیل شدن به یکدیگر را دارا می باشند.

در الگوریتمهاي مبتنی بر اتوماتاي سلولی خطی، محیط حـاکم بـر مرتبسازي، سلولهاي اتوماتاي سلولی، همسایگیهاي سلولی و قـوانین محلی حاکم بر سلولهاي اتوماتاي سلولی میباشند. بر روي مرتبسازي از دیدگاه اتوماتاي سلولی خطی، کار زیادي صورت نگرفته و معروفترین مرتبسازي بر پایه اتوماتاي سلولی توسط گوردیلو و لونا پیـشنهاد شـده است.[10]

در الگوریتم اول گوردیلو_لونا تعداد همـسایگان مـورد بررسـی هـر سلول سه و در الگوریتم دوم گوردیلو_لونا تعداد همسایگان مورد بررسی هر سلول، پنج سلول میباشد. براي مرتـبسـازي آرایـههـا در الگـوریتم گوردیلو_لونا هر سلول نیازمند سه حافظه خواندنی و نوشتنی بـوده کـه یکی از آنها در بردارنده مقدار عددي و دو حافظـه دیگـر شـامل کنتـرل کنندههاي جابجایی مقدار عددي به سمت چپ و راست میباشند. ایـن

کنترلکننده ها علاوه بـر تعیـین جابجـایی بـراي عـدم تـصادم مقـادیر سلولها در نظر گرفته شده است. در ایـن الگـوریتمهـا در هـر مرحلـه، محتواي دو سلول اتوماتا بـا یکـدیگر بـر اسـاس قـانون حـاکم تعـویض میشوند. همچنین بر اساس ساختار جابجایی این الگـوریتمهـا، در یـک مرحله، جابجایی محتواي یک سلول به سمت چپ و راست بررسی شده

و در مرحله دوم، محتواي دو سلول همسایه بر اساس بررسی انجام شده

و مقدار دو حافظه کنترل کننده جابجایی، جابه جا میشوند.

در این مقاله دو الگوریتم مرتبسازي براي اتوماتاي سـلولی خطـی پیشنهاد شده اسـت. هـر سـلول در الگـوریتم پیـشنهادي اول داراي دو همــسایه ســمت راســت بــوده و در الگــوریتم پیــشنهادي دوم تعــداد همسایگان هر سـلول برابـر چهـار مـیباشـد. الگـوریتم دوم بـا دو نـوع همسایگی متقارن و همـسایگی نامتقـارن پیـادهسـازي شـده اسـت. دو الگــوریتم پیــشنهادي، پیچیــدگی زمــانی مــشابهی بــا الگــوریتمهــاي گوردیلو_لونا دارند، ولی از نوع همـسایگی، شـعاع همـسایگی و قـوانین متفاوتی برخوردار میباشند. همچنین در سـاختار اسـتفاده شـده بـراي مرتبسازي نیازي به حافظه اضـافی بـراي ﻛﻨﺘـﺮل ﺟﺎﺑـﻪﺟـﺎﻳﻲ مقـادیر سلولهاي همسایه وجود ندارد. الگوریتمهاي پیـشنهادي در مقایـسه بـا الگوریتمهاي گوردیلو_لونا از همسایگی کوچکتري برخوردار مـیباشـند.

در الگوریتمهاي پشنهادي بر خلاف الگوریتمهاي گوردیلو_لونا، بررسـی جابجایی و جابجایی مقادیر سلولهاي همسایه بر اساس قانون حاکم بـر اتوماتاي سلولی تنها در یک مرحله صورت گرفتـه و نیازمنـد دو مرحلـه مجزا نمیباشـد. حـذف یـک مرحلـه اجرایـی موجـب افـزایش سـرعت الگوریتم مرتبسازي میشود.

ادامـه مقالـه بـدین صـورت سـازماندهی شـده اسـت. در بخـش 2

اتوماتاي سلولی به اختصار شرح داده میشود. در بخش 3 ابتدا الگـوریتم ردیلـو مرتبسـازي _لونـا و سـپس دو الگـوریتم پیـشنهادي معرفـی

میشوند. بخش 4 نتیجه گیري میباشد.

-2 اتوماتاي سلولی

اتوماتاي سلولی مـدلی ریاضـی اسـت کـه در آن چنـدین مؤلفـه سـاده براساس یک رابطه معین بـا یکـدیگر همکـاري نمـوده و توانـایی ایجـاد الگوهاي پیچیده را دارند. اتوماتاي سلولی از یـک شـبکه مـنظم سـلولی تشکیل شده که در آن هر سلول میتواندr 1 مقـدار مختلـف اختیـار نماید. سلولهاي اتوماتاي سلولی در زمانهاي گسسته و بطور همزمان و بر طبق یک قانون محلی بنام Φ بهنگام میشوند کـه در آن مقـدار هـر سلول براساس مقادیر سلولهاي همسایه تعیین میشود.

اتوماتاي سلولی براساس معیارهـاي مـورد بررسـی بـه دسـتههـاي مختلف تقسیم میگردد. براساس معیار بعد شبکه، اتوماتاي سـلولی بـه اتوماتاي سلولی یک بعدي، دوبعـدي و غیـره تقـسیم شـده و براسـاس مقدار r به اتوماتاي سـلولی دودوئـی (r 1) و اتوماتـاي سـلولی چنـد

مقــداره تقــسیم مــیشــود .[1] اتوماتــاي ســلولی d بعــدي یــک

چندتایی CA  (Z d ,φ, N,Φ) است به طوریکه:

• Z d یک شبکه از - dتاییهاي مرتب از اعداد صحیح میباشد. این

شبکه میتواند یک شبکه متناهی، نیمه متناهی یا نامتناهی باشد.

• φ {1,L, m} یک مجموعه متناهی از حالتها است.

• m } x 1 ,L, x N { ، i ∈ Z d x ، یـک زیـر مجموعـه متنـاهی از

Z d بوده که بردار همسایگی خوانده میشـود. بـردار همـسایگی،
موقعیت نسبی همسایگان براي هر سلول u در شبکه سلولی توسط
رابطه (1) مشخص میشود.
(1) } m i | i 1,..., x N (u) {u 
تابع N (u) دو شرط زیر را ارضا میکند:
(2) ∀u ∈Z d ⇒u ∈ N (u)
∀u, v ∈Z d ⇒u ∈N (v) ∧ v ∈N (u)
• →φ Φ :φ قانون محلی اتوماتاي سلولی بوده که به سه دسـته
m

قانون عام7، کلیگرا8 و کلیگرا بیرونی9 تقسیم میشود.
در اتوماتاي سلولی یک بعدي مقدار سلول i (بـراي (1 ≤ i ≤ n در
زمان t کـه بـا ai (t)رابنـشان داده مـیشـود، طبـق طـه (3) محاسـبه میگردد:
ai (t 1)  Φ[ai−1 (t), ai (t), ai1 (t)] (3)

در رابطه فوق، اگرقانون Φ فقط به مقدار همسایهها بستگی داشته

باشد آنرا قانون عام و اگر قانون Φ تابعی از مجموع مقـادیر سـلولهـاي همسایه یک سلول مرکزي باشد آنرا قانون کلـی گـراو مـینامنـد طبـق

رابطه (4) بیان می شود :

ai (t 1)  Φ[ai−1 (t)  ai (t)  ai1 (t)] (4)

در صورتی که قانون تابعی از مجموع مقادیر سلولهاي همسایه و

مقدار سلول مرکزي باشد آنـرا قـانون کلـیگـراي بیرونـی مـیگوینـد و

بصورت رابطه (5) نشان داده میشود.
(5) ai (t 1)  Φ[ai (t), ai−1 (t)  ai1 (t)]
بـر اسـاس تعـاریف فـوق اتوماتـاي سـلولی را مـی تـوان، سیـستم

محاسباتی توزیع شدهاي دانست که از عناصر پردازشـی همـسان بـسیار سادهاي شکل گرفته که از تعامل بین این عناصر ساده، بروز رفتـارهـاي پیچیـده امکـانپـذیر مـیباشـد. در ایـن سیـستم محاســباتی، قـوانین محاسباتی بر اساس همسایگی و به صورت محلی تعریف میشوند.

در این مقاله به اتوماتاي سـلولی از دیـد یـک ماشـین محاسـباتی عمومی نگریسته شده که براي حل مسئله مرتـبسـازي مـورد اسـتفاده قرار گرفته است. براي حل مسائل محاسباتی نیاز بـه سـاختمان دادهاي شامل ورودي، خروجی و یـک رویـه بـراي تبـدیل ورودي بـه خروجـی میباشد. مراحل پردازش و تبدیل ورودي به خروجی در اتوماتاي سلولی توسط انتقال حالتهاي اتوماتاي سلولی پیاده سازي میشود. هرچند در تعریف اتوماتاي سلولی استاندارد حافظه منظور نـشده اسـت، ولـی اگـر

اتوماتاي سلولی بخواهد نقش یک ماشین محاسـبهگـر عمـومی را بـازي کنداولاٌ هر سلول نیاز به تعـدادي حافظـه داشـته و همچنـین بایـستی قابلیت نوشتن مقادیر خروجی در حافظه را داشته باشد.

-3 الگوریتمهاي مرتبسازي اعداد با اتوماتاي

سلولی خطی

در این بخش ابتدا الگوریتم مرتبسازي گوردیلو_لونا شرح داده خواهـد شد، سپس دو الگوریتم پیشنهادي معرفی میشوند.

-1-3 الگوریتم مرتب سازي گوردیلو_لونا

در الگوریتمهاي گوردیلو_لونا بـا ترکیـب اتوماتـاي سـلولی بـا اتوماتـاي میلی، ماشین محاسبهگري ایجاد شده که هـر سـلول آن مجهـز بـه سـه خانه حافظه بوده و همچنین قابلیت نوشتن مقادیر خروجـی در حافظـه امکان پذیر می باشد.

همـسایگی اسـتفاده شـده در الگـوریتم مرتـبسـازي اول، از نـوع متقارن با شـعاع یـک هماننـد شـکل (1) مـیباشـد. در ایـن الگـوریتم، مرتبسازي داراي دو مرحله q0 وq1 هماننـد شـکل (2) بـوده کـه در ابتدا تمامی سلولهاي اتوماتاي سلولی در مرحله q0 قرار دارند.

i+1 i i-1

شکل(:(1 همسایگی در الگوریتم اول گوردیلو_لونا.

در انتقال از مرحله q0 به مرحله q1 ، مقدار هر سلول با مقدار دو سلول همسایهاش مقایسه شده و در صورتی که مقدار سـلول مرکـزي از مقدار سلول همسایه سمت راستش بزرگتر باشد، آن را به سمت راسـت خود و در صورتی که مقدارش از مقدار سـلول همـسایه سـمت چـپش کوچکتر باشد، آن را به سمت چپ خود انتقال میدهد. بنـابر ایـن یـک سلول میتواند، در یک زمان مقدارش را هم با همسایه سـمت راسـت و هم با همسایه سمت چپش جابجا نماید، که در ایـن صـورت تـصادم رخ میدهد.

q1 q0
شکل(:(2 مراحل اجرایی الگوریتم گوردیلو_لونا

با اعمال کنترل در جابجایی، از بـروز تـصادم مـیتـوان جلـوگیري نمود. براي این منظور در هر سلول دو حافظه بـا نـامهـاي سـد کننـده راست و چپ در نظر گرفته میشود. با این روش، هر سلولی که مقدارش کوچکتر یا مساوي مقدار سلول همسایه سمت راستش باشد، مقدار سـد کننده سمت راست خود را برابر یک و در صورتی که مقدارش کـوچکتر