الگوریتم موازی درخت پوشای مینیمم

الگوریتم موازی درخت پوشای مینیمم – ایران ترجمه – Irantarjomeh

مقالات ترجمه شده آماده گروه کامپیوتر

مقالات ترجمه شده آماده کل گروه های دانشگاهی

مقالات

چگونگی سفارش مقاله

الف – پرداخت وجه بحساب وب سایت ایران ترجمه(شماره حساب)ب- اطلاع جزئیات به ایمیل irantarjomeh@gmail.comشامل: مبلغ پرداختی – شماره فیش / ارجاع و تاریخ پرداخت – مقاله مورد نظر --مقالات آماده سفارش داده شده پس از تایید به ایمیل شما ارسال خواهند شد.

www.irantarjomeh.com

یک الگوریتم موازی جدید برای درخت پوشای مینیمم

چکیده

این مقاله نسبت به ارائه یک الگوریتم جدید برای یافتن درخت پوشای مینیمم (MST)  یک گراف وزن دار، که به صورت ذاتی، بر خلاف الگوریتم Kruskal، موازی می باشد، اقدام می نماید. در ارتباط با زمان اجرای این الگوریتم باید بیان داشت که چنین زمانی سریعتر از الگوریتم های کروسکال (Kruskal) و بروکا (Boruvka) می باشد. با این وجود، الگوریتم پریم (Prim) به میزان اندکی سریعتر از الگوریتم پیشنهادی است. پیاده سازی موازی الگوریتم پیشنهادی در حافظه به اشتراک گذاشته  نیز  بهتر از  الگوریتم  موازی  بروکا  می باشد، اما با الگوریتم موازی پریم قابل قیاس می باشد.

کلمات کلیدی: درخت پوشای مینیمم، الگوریتم موازی

الگوریتم موازی درخت پوشای مینیمم

۱- مقدمه

مشکل درخت پوشای مینیمم (MST) برای نمودار وزن دار به شرح ذیل تعریف می شود:

با در نظرگیری یک گراف متصل جهت دار G = (V, E w) که در آن V: تعیین رأس ها، E: تعیین یال ها و w: V´V®R تابع وزن می باشد. مشکل درخت پوشای مینیمم یافتن یک درخت پوشا با وزن کلی حداقلی می باشد. این مسئله MST دارای کاربردهایی در ارتباط با مسایل ترکیبی با توجه به برنامه های کاربردی عملی در چیدمان  VLSI،  ارتباطات بیسیم، تصویربرداری پزشکی [۸]، ویفر شیمیایی [۲]، مشکل درخت اشتاینر و بسیاری دیگر از کاربردهای تئوریکی مربوط به گراف می باشد [۶، ۷، ۱۱]. الگوریتم های متعددی به صورت سریال و موازی برای MST وجود دارند. اولین الگوریتم سریال برای یافتن MST به وسیله بروکا ارائه شد [۸]. این الگوریتم با ساختار موازی قابلیت موازی سازی آسان را ارائه می نماید. دو مورد دیگر الگوریتم های MST که به دفعات زیاد مورد استفاده قرار گرفته اند شامل الگوریتم کروسکال و الگوریتم پریم می باشند [۴]. اما آنها از نقطه نظر موازی سازی دارای مشکلاتی هستند. به واسطه طبیعت ذاتی موازی، بسیاری از فرمول بندی های موازی بروکا در اینگونه مباحث ارائه شده است.

این مباحث شامل مطالعات Chung و همکاران [۱۰] و Chong و همکاران [۳] می باشد. اخیراً یک رویکرد ترکیبی پریم و بروکا به وسیله Bader و همکاران در مرجع [۵] ارائه شده است. در مراجع [۱، ۵] بسیاری از گونه های موازی الگوریتم پریم نیز مورد بحث قرار گرفته اند.

MST موازی که به وسیله R. Setia و همکاران [۹] ارائه شد با استفاده از فرایندهای نخ کشی و سیگنال posix پیاده شده است. آنها از ویژگی برش گراف جهت رشد درخت از طریق نخ های متعدد استفاده نموده و در نهایت درختان به هنگام تلاقی ترکیب یا مرج گردیدند. فرمول بندی موازی بروکا از یک الگوریتم پرش اشاره گر [۱۰] برای تشکیل اجزای متصل استفاده می نماید که تا اندازه ای پیچیده می باشد. Bader و همکاران [۵] اقدام به پیاده سازی الگوریتم موازی پریم در فضای به اشتراک گذاشته شده حافظه با استفاده از هسته های متعدد نمودند. آنها از ساختار داده های لیست انعطاف پذیر مجاورت استفاده نمودند که ساده تر از الگوریتم پرش اشاره گر بروکا می باشد که در مرجع [۱۰] مورد بحث قرار گرفته است. از این مطالعه، چنین موضوعی مشخص می گردد که نوعی شکاف بین زمان اجرای الگوریتم بروکا و پریم وجود دارد. الگوریتم بروکا، به بهای زمان اجرای آهسته تر، دارای ساختار موازی بیشتری در مقایسه با الگوریتم پریم می باشد.

…

ادامه این مقاله به شرح ذیل سازماندهی شده است: بخش ۲ سوابق ضروری را مورد بازنگری قرار می دهد. بخش ۳ ارائه دهنده  الگوریتم های MST ترتیبی و موازی پیشنهادی است. بخش ۴ فرمول بندی موازی الگوریتم جدید را مورد بررسی قرار می دهد. در نهایت نتیجه گیری در بخش ۵ عرضه می شود.

الگوریتم موازی درخت پوشای مینیمم

۲- سابقه

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

الف. الگوریتم بروکا [۱۰]

این الگوریتم که تحت عنوان الگوریتم سولین نیز شناخته می شود با ویژگی های تکرارپذیر قابلیت ایجاد یک درخت پوشای مینیمم با استفاده از مراحل ذیل را خواهد داشت:

الگوریتم ۱

مرحله ۱ (انتخاب سبکترین): هر رأس اقدام به انتخاب یالی می نماید که دارای سبکترین وزن متلاقی با آن باشد. هر کدام از اجزای متصل ایجادی دارای یک چرخه با اندازه دو،  بین دو رأس می باشند و هر کدام نیز می توانند یال یکسانی را برگزینند. از بین این ویژگی، موردی که دارای عدد کوچکتری می باشد به عنوان ریشه آن جزء برگزیده شده و چرخه حذف می گردد. متعاقباً این جزء به عنوان یک درخت مشخص می گردد.

مرحله ۲ (یافتن ریشه): هر رأس اقدام به مشخص نمودن ریشه درختی که به آن تعلق دارد می نماید.

مرحله ۳ (تغییر نام رأس ها): در لیست های یال، هر رأس با توجه به نام ریشه جزئی که به آن تعلق دارد تغییر نام خواهد داشت.

…

ب. الگوریتم پریم [۴]

الگوریتم پریم قابلیت رشد درخت پوشای مینیمم یک گراف وزن دار G = (V, E, w) از یک رأس فرضی “r” به عنوان ریشه را خواهد داشت. بنابراین مؤلفه های ذیل در الگوریتم پریم بکار گرفته می شوند.

برای uÎV، با کلید [u]: کلید مرتبط با u است.

p[u]: کلید در ارتباط با والدین u می باشد.

Q: صف اولویت دارای کلید با توجه به مقدار کلید [u]، “ uÎV، می باشد.

Adj[u]: لیست مجاور u.

W(u, v): وزن یال (u, v) Î E.

مراحل الگوریتم پریم به شرح ذیل می باشند:

ج. الگوریتم کروسکال [۴]

این الگوریتم در ابتدا اقدام به یافتن یک یال ایمن نموده و متعاقباً آن را به درخت در حال رشد اضافه می نماید و برای این کار اقدام به یافتن کلیه یال هایی خواهد نمود که قابلیت اتصال به هر درخت در این جنگل را داشته باشند، یک یال (u, v) دارای حداقل وزن. چنین موردی از ساختار داده های مجموعه ـ منفصل جهت تأمین چندین مجموعه منفصل از اجزا اقدام می نماید. هر یک از این مجموعه ها حاوی رأس هایی در یک درخت متعلق به جنگل کنونی می باشند. عملیات FIND-SET(u) قابلیت بازگرداندن یک جزء شاخص از این مجموعه که حاوی u می باشد را خواهد داشت. بنابراین، ما قابلیت مشخص سازی این موضوع را خواهیم داشت که آیا دو رأس u و v متعلق به یک درخت مشخص می باشد یا خیر وبرای این کار این موضوع را تست خواهیم نمود که آیا FIND-SET(u) مساوی با FIND-SET(v) می باشد یا خیر. بر این مبنا، برای ترکیب درخت ها از راهکار UNION استفاده می شود.

الگوریتم موازی درخت پوشای مینیمم

۳- الگوریتم درخت پوشای مینیمم (MST) پیشنهادی

در این بخش ما نسبت به ارائه یک الگوریتم ترتیبی برای یافتن درخت پوشای مینیمم یک گراف متصل G=(V, E, w) اقدام می نماییم. متعاقباً، زمان اجرای آن با توجه به زمان اجرای الگوریتم های کروسکال، پریم و بروکا را مورد بحث قرار خواهیم داد.

­

الگوریتم ۴٫

1. الگوریتم پیشنهادی دارای گراف ورودی G می باشد و کاربرد الگوریتم بروکا مرحله ۱ الی مرحله ۳ را تا زمانی ادامه خواهد داد که تعداد ابر رأس ها به یک مقدار آستانه n₀ ³۲ کاهش یابد.

2. برای n₀ ³۲، اجازه دهید تا G¢=(V¢, E¢) به عنوان گراف متعدد حاصله از مرحله ۱ مشخص شود، که در آن (|V¢|=n₀) صادق خواهد بود. متعاقباً قابلیت بکارگیری الگوریتم پریم ترتیبی برای G¢ به منظور حاصل آوردن MST T¢ مرتبط با G وجود دارد. توجه داشته باشید که رأس های T¢ به عنوان ابر رأس های G به شمار می آیند.

3. به منظور حاصل آوردن MST مرتبط با G، لازم است تا اقدام به انجام فرایند خوشه برداری رأس های T¢ نماییم تا آنکه اندازه های آنها به یک تقلیل یابد.

از آنجایی که در الگوریتم پیشنهادی مرحله ۱ و ۲ تحت عنوان الگوریتم های بازگشتی خوانده می شوند و آنها به عنوان مراحل مستقل الگوریتم Brouvaka به شمار می آیند، بنابراین آنها را می توان به راحتی در سیستم چند پردازنده به صورت موازی ارائه داد، که در آن فرایند موازی سازی مرحله ۳مدنظر نخواهد بود، چرا که این فرایند صرفاً برای یکبار بر روی تعداد محدودی از ابر رأس های گراف متعدد  در  چرخه حیات  الگوریتم  اعمال می شود. بنابراین، برخلاف الگوریتم های کلاسیک پریم و کروسکال، الگوریتم ترتیبی ما دارای ساختار موازی بیشتری می باشد و مستعد پیشرفت الگوریتم های موازی بر روی شبکه های به هم پیوسته مختلف می باشد.

الگوریتم موازی درخت پوشای مینیمم

۴- فرمول بندی موازی الگوریتم جدید

در این بخش، ما یک الگوریتم موازی را برای درخت پوشای مینیمم پیشنهادی در حافظه به اشتراک گذاشته شده با استفاده از ساختار داده های FAL بحث شده در مرجع [۱] مورد بررسی قرار می دهیم. در اینجا ما از الگوریتم های بروکا و پریم با استفاده از ساختار داده FAL بهره جستیم. با توجه به استفاده از بخش اصلی MST و با بکارگیری الگوریتم بروکا، در این فرمول بندی موازی، پردازنده ها مرحله ۱ و مرحله ۲ الگوریتم ۴ (بخش ۳) بر روی مجموعه مختلف رأس ها به صورت همزمان اجرا می شوند.

ما به هنگامی بیان می داریم که یک درخت در حال رشد است که یک یال سبک وزن با قابلیت اتصال یک درخت به یک رأس را داشته باشد. به هنگامی که کلیه رأس ها (تخصیص یافته برای یک پردازنده) برای زیر درخت ها یا درخت های فرعی بالغ بکار گرفته شدند، ما قابلیت اتصال هر درخت فرعی به یک ابر رأس را خواهیم داشت (مرحله ۲ از الگوریتم ۴) و مراحل ۱ و ۲ را به صورت بازگشتی بر روی چند گراف حاصله  فراخوانده تا آنکه یک چند گراف با اندازه کوچک مکفی حاصل شود. به هنگامی که اندازه این چند گراف در حد کفایت کوچک باشد، یکی از پردازنده ها اقدام به اجرای الگوریتم پریم ترتیبی می نماید (مرحله ۳ از الگوریتم ۴) تا قابلیت یافتن MST بهترین چند گراف را داشته باشد. متعاقباً ابر رأس ها خوشه برداری شده تا قابلیت یافتن MST گراف اصلی به وجود آید. توصیف فرمول بندی موازی ما در الگوریتم ۵ ارائه شده است.

الگوریتم موازی درخت پوشای مینیمم

۵- نتیجه گیری

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