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

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

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

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

مقالات

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

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

www.irantarjomeh.com

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

چکیده

دو الگوریتم موازی ساده و کارآمد برای مشکل درخت پوشای مینیمم در این مبحث ارائه شده است. هر دو الگوریتم از وظیفه O(m log n)w برخوردار می باشند. اولین الگوریتم در زمانO(log² n) بر روی یک سیستم EREW PRAM پیاده شده و الگوریتم دوم نیز در زمان O(log n) بر روی سیستم CommonCRCW PRAM اجرا می شود.

کلمات کلیدی: درخت پوشای مینیمم (کمینه)، ماشین دسترسی تصادفی موازی

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

۱- مقدمه

مشکل درخت پوشای کمینه / مینیمم یکی از اساسی ترین و گسترده ترین مشکلات مطرح شده در ارتباط با بهینه سازی شبکه، با کاربردهای تئوریکی و عملی بسیار، می باشد [۱]. با توجه به گراف متصل G، با n ـ رأس و m ـ یال ، با وزن های حقیقی یال، مشکل درخت پوشای مینیمم (MST) یافتن درخت پوشای دارای مجموع وزن حداقلی یا کمینه در بین کلیه درخت های پوشای G می باشد.

الگوریتم های ارائه شده برای مشکل MST از اوایل سال ۱۹۲۶ به بعد توسعه یافته اند. سه رویکرد اصلی در این زمینه مد نظر هستند که عبارتند از: الگوریتم کروسکال، الگوریتم سولین، و الگوریتم پریم [۱]. کلیه این الگوریتم ها ساده بوده و به راحتی قابلیت پیاده سازی آنها در زمان O(m log n) وجود دارد [۱]. بعلاوه، نوعی نگارش سریعتر الگوریتم سولین نیز در مرجع [۱۶] عرضه شده است که در زمان O(m log log n) اجرا می شود. بهترین الگوریتم ترتیبی (گونه مرتبط با رویکرد پریم) در زمان O(m log b(m, n)) اجرا می گردد [۱۱]، که در آن b(m, n) = min {i: log⁽ⁱ⁾ n £ m/n} حاصل می شود. کلیه الگوریتم های فوق به صورت قطعی بوده و بر روی یک مدل محاسباتی ماشین دارای دسترسی تصادفی هزینه ـ واحد (کلاسیک) (RAM) اجرا می شوند، که در آن تنها عملیات مجاز بر روی وزن های یال مقایسات باینری می باشد. در این رابطه در صورتی که قابلیت ارائه ویژگی های تصادفی وجود داشته باشد می توان الگوریتم های بهتر بر مبنای ویژگی های خطی ـ زمانی را در نظر داشته [۱۴]، و اقدم به بکارگیری مدل های قدرتمند محاسباتی بیشتری نمود [۱۰].

در این مقاله، ما نسبت به بررسی مشکل MST برای مدل محاسبه موازی ماشین با دسترسی تصادفی موازی (PRAM) اقدام می نماییم (یعنی نگارش موازی مدل RAM هزینه واحد). بر این مبنا، مدل PRAM تعدادی از پردازشگرها را بکار می گیرد که قابلیت کار همزمان با یکدیگر و برقراری ارتباط، از طریق عمل خواندن از یا نوشتن بر یک حافظه عمومی (به اشتراک گذاشته شده)، را فراهم می آورند. مدل PRAM دارای سه گونه مختلف منوط به چگونگی دسترسی همزمان به موقعیت یکسان حافظه به وسیله بیش از یک پردازنده می باشد:…

ما عقیده داریم که قدرت الگوریتم های ما بر مبنای دو حقیقت می باشد: (۱) آنها از نقطه نظر مجانبی نتایج بهتری از رویکردهای قبلی w.r.t. ارائه می دهند و (۲) آنها ساده بوده و در نتیجه پیاده سازی آنها آسان است (مخصوصاً اولین الگوریتم) بدین روش که پیاده سازی آنها بر مبنای روتین های اساسی و کاملاً درک شده است (همانند محاسبات پیشوندی، رتبه بندی لیست، مرتب سازی) که می بایست در هر گونه کتابخانه الگوریتم های ترکیبی موازی وجود داشته باشند.

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

۲- ویژگی های مقدماتی

در این مقاله، اجازه دهید تا G = (V, E) به عنوان گراف غیرجهت دار متصل به شمار آید که در آن n = |V| و m = |E| صادق خواهد بود. به علاوه اجازه دهید تا wt : E ® IR نیز به عنوان تابع وزن برای یال های G به شمار آید. بدون از دست دادن کلیت، ما در نظر می گیریم که هیچگونه دو یالی دارای وزن یکسان نمی باشند. در غیر اینصورت، ما می بایست در نظر بگیریم که ویژگی سه گانه áwt(e), u, vñ به عنوان وزن یال e = (u, v) در نظر بوده و اقدام به مقایسه وزن های یال با استفاده  از  ترتیب  لغت  نویسی  نماییم. ما  در  نظر می گیریم که G شاخص لیست مجاورت خود را ارائه نموده است، یعنی آنکه رأس ها در یک آرایه ارائه شده و هر رأس v دارای لیست مرتبط با خود یعنی A(v) از یال های یکسان خود می باشد. به علاوه، از آنجایی که هر یال (u, v) در A(u) دارای یک یال جفتی (v, u) در A(v) می باشد، یک جفت اشاره گر mate(u, v) نیز وجود خواهد داشت که به موقعیت (v, u) واقع در A(v) اشاره می نماید.

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

۳- الگوریتم EREW PRAM

این الگوریتم در بخش کنونی به عنوان یک ویژگی موازی سازی طبیعی رویکرد سولین به شمار می آید. ما این موضوع را تشریح می نماییم که چگونه مراحل انتخاب و ادغام به صورت کارآمد بر روی یک EREW PRAM با استفاده از صرف روتین های اصلی اعمال می شوند: محاسبات پیشوند، رتبه بندی لیست و تکنیک تور اویلر. همگی آنها را می توان در زمان O(logp) و کار O(p) بر روی EREW PRAM انجام داد [۱۲، فصل ۲ و ۳]، که در آن p اندازه ورودی به حساب می آید. ذیلاً، ما اقدام به انجام محاسبات پیشوند بر روی لیست های مرتبط، به جای آرایه ها، خواهیم نمود، یعنی ما این نکته را فرض می نماییم که لیست ها قبلاً رتبه بندی شده اند. البته این مورد را نمی توان به عنوان یک مشکل به حساب آورد. چرا که رتبه بندی لیست نیازمند منابع یکسان همانند محاسبات پیشوندی می باشد.

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

۴- الگوریتم COMMON CRCW PRAM

این الگوریتم در این بخش بر مبنای الگوریتم Awerbuch Shiloach ارائه شده است [۲]. آن الگوریتم متشکل از یک ویژگی پیاده سازی مختلف رویکرد سولین می باشد. هر مؤلفه به عنوان یک درخت ریشه دار به شمار آمده و یک درخت ریشه دار با عمق ۱ تحت عنوان یک ستاره خوانده می شود. این الگوریتم نیز به خوبی کار می نماید. یک پردازنده برای هر یال (u, v) مرتبط با G در نظر گرفته شده و انجام دهنده سه مرحله تکراری می باشد تا آنکه شرط خاصی ارضا شود و پس از آن پردازنده مرتبط غیرفعال خواهد شد. این الگوریتم زمانی به انتها خواهد رسید که کلیه پردازنده ها غیر فعال شده باشند. در طی فرایند اجرای این الگوریتم، یک اشاره گر P(v) اعمال می گردد، که برای هر رأس v Î G مدنظر بوده و به والدین v در مؤلفه کنونی که حاوی v است اشاره می نماید. (به طور اولیه، P(v) = v صادق خواهد بود، یعنی هر رأس به عنوان یک ستاره مشخص می شود). هر پردازنده فعال مرتبط با یال (u, v) قابلیت اجرای مراحل ذیل را خواهد داشت:

• در صورتی که (u, v) به عنوان یک یال خارجی متعلق به یک ستاره مدنظر باشد، بنابراین پردازنده مرتبط با آن سعی در هوک نمودن یا قلاب نمودن آن به مؤلفه دیگر خواهد نمود. در بین تعداد بالقوه پردازنده های موجود (در ارتباط با یال های خارجی همان ستاره) که سعی در انجام این کار می نمایند، مورد متعاقب به عنوان پردازنده مرتبط با یال خارجی وزن مینیمم یا حداقلی تلقی خواهد شد. بر حسب لم ۱، این یال متعلق به MST می باشد.

• در نتیجه مرحله (۱) چرخه های جهت دار طول ۲ را می توان ایجاد نمود. این مورد در صورتی محقق خواهد شد که (u, v) به عنوان یک یال مطرح باشد آن هم به گونه ای که u متعلق به یک ستاره S₁ باشد و v متعلق به یک ستاره S₂ تلقی شود، و بنابراین یال خارجی وزن دار حداقلی یا مینیمم برای هر دوی S₁ و S₂ مدنظر خواهد بود. از این رو، در این مرحله، این نوع از چرخه های جهت دار تشخیص داده شده و به سود رأس دارای تعداد کمتر شکسته می شوند (به سادگی از طریق حذف اشاره گر رأس شماره گذاری شده کوچکتر که به رأس شماره گذاری شده بزرگتر اشاره می نماید).

• مؤلفه هایی که به عنوان ستاره ها تلقی نمی شوند قابلیت کاهش عمق خود بر حسب ضریب حداقلی ۳/۱ را خواهند داشت. چنین عملی به وسیله “فرایند میانبر سازی” اعمال می شود: در صورتی که u متعلق به یک ستاره نباشد، بنابراین P(u) = P(P(u)) حاصل خواهد شد، در غیر اینصورت پردازنده مرتبط با (u, v) غیرفعال می گردد.

تصدیق آنکه مرحله (۱) را می توان در زمان O(1) انجام داد، در صورتی که PRIORITY CRCW PRAM  استفاده  شود،  آسان خواهد بود.  دو  مرحله  دیگر  نیازمند  زمان  O(1)  می باشند، حتی در COMMON CRCW PRAM.

هم اکنون در نظر بگیرید که m ³ n log² n صحت دارد (در انتهای این بخش، ما نشان خواهیم داد که چگونه قابلیت فایق آمدن بر این فرضیه را خواهیم داشت).

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

۵- مباحث نهایی

ما دو الگوریتم موازی ساده و کارآمد از نظر کاری را برای مشکل MST ارائه نمودیم. ما عقیده داریم که سادگی آن سبب می شود تا  الگوریتم ها  را  بتوان  به صورت آسانی اعمال داشت، چرا که پیاده سازی آنها بر مبنای روتین های اساسی و کاملاً درک شده ای می باشد که احتمالاً می توان آنها را در هر کتابخانه الگوریتم های ترکیبی موازی یافت. یک محیط محتمل برای چنین راهکاری کتابخانه PAD الگوریتم های PRAM پایه و ساختارهای اطلاعاتی پایه [۱۵] می باشد که هم اکنون تحت توسعه هستند.