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

توجه : به همراه فایل word این محصول فایل پاورپوینت (PowerPoint) و اسلاید های آن به صورت هدیه ارائه خواهد شد

  مقاله یک الگوریتم مرتب سازی موازی برای اتوماتای سلولی خطی دارای ۸ صفحه می باشد و دارای تنظیمات در microsoft word می باشد و آماده پرینت یا چاپ است

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

توجه : در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل ورد می باشد و در فایل اصلی مقاله یک الگوریتم مرتب سازی موازی برای اتوماتای سلولی خطی،به هیچ وجه بهم ریختگی وجود ندارد

---

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

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

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

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

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

سلولی.

page7-1 مقدمه

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

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

کاربردهای اندازهگیری و از این دست می باشد. مـیتـوان الگـوریتمهـای مرتبسازی را به دوسته الگوریتمهای ترتیبـی و الگـوریتمهـای مـوازی تقسیم نمود. الگوریتمهای موازی از دیدگاه نحـوه حـل مـسئله و مـوارد مورد استفاده آن به دو دسته الگوریتمهای بر مبنای مدلهای ریاضـی و الگوریتمهای وابسته به بستر پیادهسازی تقسیم میشوند. الگوریتمهـای بر مبنای ماشینهای SIMD از دسته الگـوریتمهـای وابـسته بـه بـستر پیادهسازی میباشند. در ایـن الگـوریتمهـاعمومـاً آرایـه یـک بعـدی از پردازندهها از طریق الگوریتم انتقال زوج و فرد۱، n عنـصر دادهای را بـا استفاده از n پردازنده مقایـسه و مرتـب مـینماینـد. دسـتهای دیگـر از الگوریتمهای وابسته به بستر بر اساس ماشینهای موازی MIMD و بر مبنای الگوریتم مرتبسازی سریع۲ میباشند. بسیاری از الگـوریتمهـای ترتیبــی ماننــد مرتــب ســازی انتخــابی۳، مرتــبســازی ترکیبــی۴ و یــا مرتــبســازی ســریع بــا راهکارهــای متنــاظر بــا پــردازش مــوازی، در سیستمهای موازی مورد استفاده قرار گرفتهاند .[۳-۹]

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

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

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

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

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

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

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

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

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

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

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

-۲ اتوماتای سلولی

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

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

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

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

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

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

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

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

Z d بوده که بردار همسایگی خوانده میشـود. بـردار همـسایگی،
موقعیت نسبی همسایگان برای هر سلول u در شبکه سلولی توسط
رابطه (۱) مشخص میشود.
(۱) } m i | i 1,;, x N (u) {u
تابع N (u) دو شرط زیر را ارضا میکند:
(۲) u Z d u N (u)
u, v Z d u N (v) v N (u)
• : قانون محلی اتوماتای سلولی بوده که به سه دسـته
m

قانون عام۷، کلیگرا۸ و کلیگرا بیرونی۹ تقسیم میشود.
در اتوماتای سلولی یک بعدی مقدار سلول i (بـرای (۱ i n در
زمان t کـه بـا ai (t)رابنـشان داده مـیشـود، طبـق طـه (۳) محاسـبه میگردد:
ai (t 1) [ai1 (t), ai (t), ai1 (t)] (3)

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

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

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

ai (t 1) [ai1 (t) ai (t) ai1 (t)] (4)

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

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

بصورت رابطه (۵) نشان داده میشود.
(۵) ai (t 1) [ai (t), ai1 (t) ai1 (t)]
بـر اسـاس تعـاریف فـوق اتوماتـای سـلولی را مـی تـوان، سیـستم

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

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

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

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

سلولی خطی

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

-۱-۳ الگوریتم مرتب سازی گوردیلو_لونا

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

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

i+1 i i-1

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

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

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

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