پیاده سازی موازی الگوریتم ها

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

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

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

مقالات

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

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

www.irantarjomeh.com

پیاده سازی موازی الگوریتم ها برای یافتن مولفه های همبند در گراف ها (Preprint)

چکیده

در این مقاله ما رویه پیاده سازی چندین الگوریتم گراف موازی برای یافتن مولفه های همبند را تشریح می نماییم. راهکار پیاده سازی ما، با توجه به پردازش مجازی، با بهره گیری از یک پردازنده ـ ۱۶۳۸۴ ـ MasPar MP-1 و با استفاده از زبان MPL انجام شد. بر این راستا، ما داده های آزمایشی گسترده ای را در ارتباط با ویژگی های کد نویسی این سیستم ارائه نموده ایم.

در پروژه های قبلی [۲۱، ۲۲، ۲۳] راهکار پیاده سازی یک کتابخانه متشکل از الگوریتم های قابل گسترش گراف موازی را گزارش نمودیم. در این زمینه، ما رویه های مرتبط با پیاده سازی کلی و تکنیک های تنظیم متناسب این مولفه،  بدون تلاش چندان در ارتباط با بهینه سازی هر کدام از روتین ها به صورت منحصربفرد، را ارائه نمودیم. ما همچنین مسئله پیاده سازی پردازش مجازی را نیز مد نظر قرار داده ایم.

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

پیاده سازی موازی الگوریتم ها

۱- مقدمه

در خلال دهه گذشته تحقیقات زیادی به صورت تئوریکی در ارتباط با طراحی الگوریتم گراف موازی با قابلیت مناسب و با راندمان بالا انجام شده است [۲۵، ۲۷، ۳۱، ۴۶]. الگوریتم های موازی که در زمان های مختلف چند جانبه با پردازنده های متعدد خطی یا نیمه خطی اجرا  می شوند برای برخی از مشکلات اساسی در ارتباط با گراف های غیرجهت دار شامل مولفه های همبند و جنگل پوشا [۲، ۵، ۷، ۱۳، ۱۶، ۱۷، ۲۴، ۲۶، ۴۲] جنگل پوشای حداقلی (MSF) [2، ۵، ۶] تجزیه گوشی و اتصال پذیری ۲- یالی [۳۲، ۳۷، ۴۳]، تجزیه گوشی باز و همچنین ویژگی های دو هم بندی [۳۲، ۳۷، ۴۳، ۵۲]، سه هم بندی [۱۲، ۳۶] و قابلیت مسطح بودگی [۴۴] ارائه شده اند. تمامی این الگوریتم ها، (به استثنای برخی از الگوریتم های MSF) دارای ویژگی های دیگری نیز می باشند که به صورت سریال در الگوریتم های ترتیبی زمان خطی ارائه شده اند. با این وجود، این الگوریتم ها کاملاً متفاوت از الگوریتم های زمان خطی اولیه بر مبنای جستجوی عمقی / جستجوی اول عمق [۵۱] می باشند و علت تمایز آنها بدین صورت مطرح می شود که آنها از نظر ساختاری کاملاً به صورت مدولار یا پیمانه ای هستند. به طور مثال، الگوریتم مرتبط با تجزیه گوشی اقدام به فراخوانی روتین های فرعی برای مشکلات متعدد اصلی می نماید، نظیر: مولفه های همبند، جنگل پوشا، تکنیک درختان تور اویلر [۵۲]، کمترین والدین مشترک در درختان [۴۷، ۵۲] و حداقل محدوده یا برد [۴۷، ۵۲]. الگوریتم های پیچیده تر، نظیر الگوریتم های مرتبط با ویژگی های سه هم بندی و مسطح بودگی نیز اقدام به فراخوانی روتین های فرعی برای تجزیه گوشی باز همراه با روتین های فرعی مرتبط با مشکلات اساسی تر نموده اند. بنابراین پیاده سازی الگوریتم های موازی برای گراف های بدون جهت می بایست در یک حالت پایین به بالا اعمال شوند، که شروع آن با پیاده سازی راهکارهای اولیه می باشد و متعاقباً قابلیت ایجاد الگوریتم های پیچیده تر نیز به وجود خواهد آمد. با استفاده از این استراتژی، ما نسبت به پیاده سازی الگوریتم های موازی کارآمد برای چندین مورد مشکلات ترکیبی و گراف اقدام نمودیم [۲۱، ۲۲، ۲۳]

…

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

تحقیقات مرتبط در زمینه الگوریتم های ترکیبی در ماشین های کاملاً موازی را می توان در مراجع [۱، ۳، ۴، ۸، ۹، ۱۰، ۱۱، ۱۵، ۱۶، ۱۸، ۱۹، ۳۰، ۳۸، ۳۹، ۴۱، ۴۸] یافت. به علاوه تحقیقی نیز در زمینه پیاده سازی الگوریتم های ترکیبی بر روی یک کامپیوتر سوپر بردار [۱۶، ۴۵، ۴۹] و این مورد نیز بر روی یک ماشین دارای حافظه توزیعی نیز انجام شده است [۲۹].

ادامه این مقاله به شرح ذیل سازماندهی شده است. بخش ۲ تشریح کننده الگوریتم های پیاده شده، متشکل از الگوریتمی که ما برای این پروژه ابداع نموده ایم، می باشد. بخش ۳ راهکارهای کلی تکنیک های تعدیلی مناسب یا میزان سازی دقیق برای برنامه ارائه شده از سوی ما را تشریح می نماید. بخش ۴ توصیف کننده طرح مورد آزمایش می باشد. بخش ۵ عملکرد داده ها را ارائه می نماید. در نهایت بخش ۶ ویژگی های مربوط به نتیجه گیری را عرضه خواهد داشت.

پیاده سازی موازی الگوریتم ها

۲- الگوریتم ها

با توجه به لیستی از رأس ها و یال ها در یک گراف، یک الگوریتم برای یافتن مولفه های همبند اقدام به تخصیص عدد جزء منحصربفرد c(u) به هر رأس u می نماید. دو رأس u و v در جزء یکسانی قرار خواهند داشت آن هم در صورتی که صرفاً c(u) = c(v) حاصل شود. علاوه بر محاسبه c(u) برای هر رأس u، راهکار پیاده سازی مورد نظر ما برای یافتن مولفه های همبند نیز سبب حاصل آوردن مجموع کلی مولفه های همبند در گراف ورودی خواهد شد. در این بخش، ما چهار الگوی موازی را تشریح می نماییم که در  این مبحث پیاده سازی شده اند.

کلیه الگوریتم های موازی اعمالی از تکنیک “قلاب اندازی و پرش اشاره گر” برای یافتن مولفه های همبند استفاده نموده اند. از آنجایی که کد برنامه ما می بایست مراقب رأس های ایزوله / منفک در زمان شروع محاسبه باشد، ما در اینجا برای راحتی این موضوع را فرض می نماییم که هیچگونه رأس منفکی در گراف ورودی وجود ندارد. اجرای  این  نوع  از  محاسبه  برحسب رویه های تکرار  شده  می باشد. در هر بار تکرار،  عملیات قلاب اندازی و پرش اشاره گر  اعمال  می شوند. در ابتدا، هر رأس به صورت خود به خود به یک مجموعه مختلف تخصیص می یابد. در طول فرایند اجرا، در صورتی که دو مجموعه رأس ها به نظر متعلق به یک مولفه همبند باشند، بنابر این،  این دو مجموعه ترکیب  خواهند  شد. ما  فرایند  ترکیب را تا  زمانی  ادامه  می دهیم تا کلیه رأس ها در هر مولفه همبند در یک مجموعه مشابه و یکسان قرار گیرند. ساختار داده برای یک مجموعه از رأس در طی فرایند اجرایی به صورت حلقه درختی می باشد، که در آن هر رأس در هر مجموعه دارای یک اشاره گر به سمت خارج می باشد که به رأس دیگری در این مجموعه اشاره دارد، البته با این محدودیت که دقیقاً یک رأس دارای یک اشاره گری است که به خود اشاره می نماید. …

۲-۱٫ الگوریتم Awerbuch و Shiloach

الگوریتم ارائه شده به وسیله Awerbuch و Shiloach [2] در شکل نشان داده شده در الگوریتم ۱ مشخص شده است. در هر بار تکرار فرایند قلاب گذاری و پرش اشاره گر در این الگوریتم، دو هوک یا قلاب اعمال می شوند.  اولین  قلاب،  که  تحت عنوان  قلاب گذاری  ستاره ای  شرطی  می باشد، سبب خواهد شد تا ریشه یک ستاره ریشه دار به یک لوپ یا حلقه درختی اشاره نماید. به منظور ممانعت از آن که دو ستاره ریشه دار قابلیت قلاب به یکدیگر را داشته باشند، این الگوریتم نیازمند آن خواهد بود تا ریشه ستاره قلاب گذاری دارای تعداد راس کمتری در مقایسه با تعداد راسی باشد که به آن اشاره می نماید. قلاب دومی، که تحت عنوان قلاب گذاری ستاره غیر شرطی تلقی می شود، سبب می شود تا ریشه یک ستاره ریشه دار به یک لوپ درختی اشاره داشته باشد که متعلق به خود آن تلقی نمی شود.

توجه داشته باشید که مراحل ۱-۱ و ۲-۱ به عنوان عملیات نوشتاری هم زمان تلقی می شوند. بعلاوه توجه شود که این الگوریتم نیازمند کنترل این موضوع می باشد که کدام یک از راس ها در ستاره های ریشه دار قرار دارند. چنین موردی را می توان با استفاده دو فرآیند خواندن هم زمان و یک فرآیند نوشتن متقارن به شرح ذیل انجام داد. با استفاده از یک فرایند خواندن هم زمان، هر راس قابلیت یافتن جد خود (یعنی، پدر و مادر والدین خود) را خواهد داشت. برای هر راس که جد بزرگ آن متفاوت از والدین باشد، ما اقدام به مارک دار سازی یا علامت گذاری یک پرچم f (نوشتن هم زمان) برای آن جد خواهیم نمود. هر راسی که مارک دار شد در ستاره ریشه ای قرار ندارد. هر راس غیر مارک دار قابلیت خواندن پرچم f از جد خود را خواهد داشت. راس های بدون مارک که اجداد آنها مارک دار شده اند نیز در ستاره های ریشه دار قرار ندارند.

۲-۲٫ الگوریتم Shiloach و Vishkin

الگوریتم بعدی که ما اقدام به پیاده سازی آن می نماییم (الگوریتم ۲) به وسیله Shiloach و Vishkin [50] و در فصل ۵-۱-۳ مبحث JaJa [25] ارائه شده است. در هر کدام از فرایندهای تکرار قلاب گذاری و پرش اشاره گر در  این  الگوریتم،  دو  قلاب  همانند  الگوریتم ۱  اجرا  می شوند. اولین قلاب، که تحت عنوان قلاب شرطی خوانده می شود، مشابه با فرایند قلاب گذاری ستاره ای شرطی می باشد که در الگوریتم ۱ تشریح شد، به استثنای آن که ریشه یک لوپ درختی (به جای یک ستاره ریشه دار) به گونه ای ایجاد می شود تا قابلیت اشاره به لوپ درخت دیگر را داشته باشد. لوپ دوم مشابه با فرایند قلاب گذاری ستاره ای غیر شرطی می باشد که در الگوریتم ۱ توصیف شد. این الگوریتم می بایست قابلیت کنترل این موضوع را داشته باشد که کدام یک از راس ها در طی فرایند تکرار صرفاً یک بار، به جای دو بار پدیدار شدن در الگوریتم ۱، ارائه می گردند.

۲-۳٫ یک الگوریتم قطعی پالایش شده

الگوریتم ۳ به عنوان یک الگوریتم قطعی پالایش شده / ادیت شده به شمار می آید که ما برای این پروژه مد نظر قرار داده ایم. در هر بار تکرار فرایند قلاب گذاری و پرش اشاره گر در این الگوریتم، تنها یک قلاب اعمال می شود. چنین موردی به عنوان قلاب گذاری ستاره ای شرطی و مشابه با مورد ارائه شده در الگوریتم ۱ به شمار می آید، به استثنای آن که به هنگامی که دو ستاره ریشه دار سعی در قلاب زنی یا اتصال به یکدیگر می نمایند، قاعده شکستن گره قابلیت اعمال تغییرات بین دو قاعده ذیل را داشته باشد: در تکرارهای اعداد زوج، چنین الگوریتمی بیشتر در طلب ستاره ریشه داری خواهد بود که دارای تعداد راس بزرگ تری می باشد، در حالی که در تکرارهای عدد فرد، این الگوریتم بیشتر به دنبال ستاره ریشه داری می باشد که دارای تعداد راس کوچک تری است. این مورد سبب تضمین قطع فرایند در یک تعداد لوگاریتمی تکرارها خواهد شد. توجه داشته باشید که این الگوریتم سعی در ایجاد توازن در بین مقدار ویژگی های انجام شده در ارتباط با تعداد لوپ های درختی کاهش یافته در هر تکرار  می نماید. بنابراین شاهد تنها یک قلاب یا هوک در هر تکرار هستیم.

۲-۴٫ یک الگوریتم تصادفی ساده

الگوریتم ۴ به عنوان یک الگوریتم تصادفی ساده به شمار می آید (به فصل ۴-۳ در مرجع [۴۶] رجوع شود)، که از کنترل ستاره های ریشه دار اجتناب نموده آن هم از طریق اطمینان از آنکه هر لوپ درختی به عنوان یک ستاره ریشه دار در شروع هر بار فرایند تکرار قلاب گذاری و پرش اشاره گر به شمار می آید. در هر بار تکرار، دو قلاب بین ستاره های ریشه دار اعمال می شوند. از طریق استفاده از یک بیت تصادفی در هر راس، ریشه یک ستاره ریشه دار با بیت تصادفی ۱ به گونه ای ایجاد می شود تا قابلیت اشاره به ریشه یک ستاره ریشه دار دارای بیت تصادفی ۰ وجود داشته باشد. از طریق اعمال قاعده شکستن گره با استفاده از بیت های تصادفی، بلندی هر لوپ درخت حاصله کمتر از ۴ خواهد بود. پس از پرش یک اشاره گر، کلیه لوپ های درخت با بلندی – ۳ به عنوان ستاره های ریشه دار مدنظر قرار می گیرند. این الگوریتم تصادفی ساده متفاوت از ۳ الگوریتم قبلی می باشد و علت تفاوت آن نیز صرفه جویی در انجام فرایندهای کنترل ستاره های ریشه دار در هر بار تکرار است. توجه داشته باشید که در این الگوریتم، بلندی هر لوپ درختی در بیشترین حالت ۲ پس از مرحله ۲ عددی خواهد بود. بنابراین کلیه راس ها در ستاره های ریشه دار (یا راس های منفک) پس از مرحله ۳ خواهند بود. از طریق کاربرد بیت های تصادفی جهت شکستن گره ها در فرایند قلاب گذاری، این الگوریتم از ایجاد یک لوپ یا حلقه درختی با بلندی بیشتر از ۲ اجتناب می نماید. بنابراین این امر نیز محتمل خواهد بود که چنین الگوریتمی به منظور اتمام رسانی الگوریتم نیازمند تعدادی زیادی از تکرارها باشد.

پیاده سازی موازی الگوریتم ها

۳- تکنیک های کلی میزان سازی دقیق

در این بخش، ما چندین تکنیک تعدیل یا میزان سازی دقیق را ارائه می نماییم.

۳ـ۱٫ ساختار داده های فشرده برای یال ها

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

۳ـ۲٫ روتین خاص برای تکرار اول فرایند قلاب زنی

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

۳ـ۳٫ کنترل یال های زنده

الگوریتم ۴ ارائه دهنده تکنیکی جهت رهایی از  یال های متصل کننده دو رأسی می باشد که در داخل لوپ درختی یکسانی قرار گرفته اند (یعنی موردی که قبلاً در مولفه همبند بوده است). به منظور کنترل کار می توان موارد ذیل را در نظر داشت: یک یال یا یال (u، v) به صورت مولفه همبند یکسان در نظر گرفته خواهد شد آن هم در صورتی که u و v دارای اشاره گر والدین یکسانی باشند. حال اجازه دهید تا یال (u، v) به صورت مرده تلقی شود آن هم در صورتی که اشاره گرهای کنونی والدین u و v یکسان باشند. یک یال در صورتی زنده تلقی می گردد که این ویژگی مردگی وجود نداشته باشد. در شروع هر رویه تکرار، الگوریتم مربوطه اقدام به کنترل اشاره گرهای والدینی برای نقاط انتهای یال هایی می نماید که در حال حاضر زنده هستند. یال های مرده در محاسبات متعاقب شرکت داده نخواهند شد.

۳ـ۴٫ پیاده سازی عملیات نوشتن همزمان

در این الگوریتم ها، ما نیازمند پیاده سازی عملیات فرضی / اختیاری نوشتن همزمان می باشیم. این سیستم قابلیت فراهم آوردن روتین  rsend  در  زبان MPL  را  داشته که بر مبنای آن  می توان به طور مستقیم نسبت به پیاده سازی عملیات فرضی نوشتن اقدام نمود. زمان اجرایی یک عملیات فرضی نوشتن همزمان به هنگامی افزایش می یابد که تعداد حداکثری درخواست های نوشتن همزمان بر حسب پردازنده فیزیکی افزایش می یابد. بر این مبنا یک مدل “صف ـ نوشتاری” ایجاد می گردد که در مرجع [۱۴] مورد بحث قرار می گیرد.

۳ـ۵٫ فشرده سازی یال

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

۳ـ۶٫ پرش غیرمستقیم اشاره گر

با توجه به یک لوپ درختی، عمق یک رأس u به عنوان تعداد رأس های قرار گرفته بر روی مسیر از u تا ریشه لوپ درختی به شمار می آید. اشاره گر یک رأس با عمق کمتر از یا برابر با ۲ به هنگامی که فرایند پرش اشاره گر اعمال می شود تغییر نخواهد نمود. جهت کاهش تعداد عملیات دنبال نمودن اشاره گر که در طی فرایند پرش اشاره گر رخ می دهد، ما قابلیت استفاده از راهکار پرش غیرمستقیم اشاره گر را خواهیم داشت.

توجه داشته باشید که چنین موردی قابلیت حاصل آوردن یک عملیات نوشتن همزمان به منظور کنترل این موضوع را خواهد داشت که آیا یک رأس غیر ریشه ای در یک لوپ درختی از طریق مارکدار نمودن یک پرچم برای والدین هر رأس باقی مانده است یا خیر. پس از این علامت گذاری، همانند نوشتن همزمان، رأس های بدون مارکشامل برگ ها خواهند بود. به طور ابتدا به ساکن، کلیه رأس ها به صورت فعال هستند. در طی شروع هر تکرار، ما اقدام به مارکدار نمودن برگ ها در لوپ های درخت تحت عنوان موارد “غیرفعال” می نماییم.

۳ـ۷٫ پیاده سازی فرایند خواندن همزمان

در پیاده سازی پرش اشاره گر، ما نیازمند کاربرد عملیات خواندن همزمان می باشیم. زبان MPL قابلیت ارائه یک سیستم روتینی تحت عنوان rfetch جهت پیاده سازی مستقیم این مورد را دارا می باشد. زمان اجرای یک عملیات خواندن همزمان به هنگامی افزایش خواهد یافت که تعداد حداکثری درخواست های خواندن همزمان در پردازنده فیزیکی افزایش یابد [۲۱، ۴۰]. چنین موردی تحت عنوان مدل “صف ـ خواندن” مدنظر است که در مرجع [۱۴] مورد خطاب قرار گرفته است. همانگونه که در آزمایشات انجام شده در مرجع [۲۱] مشخص شده است، یک فرایند خواندن انحصاری وابسته به عملیات خواندن همزمان با استفاده از فرایند سورت سازی دارای عملکرد بهتری در مقایسه با فرایند خواندن همزمان rfetch می باشد آن هم به هنگامی که تعداد حداکثری درخواست های خواندن همزمان بر روی پردازنده بیشتر از ۲۵۶ مورد باشد. ما در می یابیم که به هنگام اجرای پرش اشاره گر بر روی گراف های متراکم با رأس های کمتر از تعداد پردازنده های فیزیکی در این سیستم، تعداد حداکثری درخواست های خواندن همزمان بر روی پردازنده های فیزیکی کاملاً در چند تکرار آخری بزرگتر خواهد شد. بنابراین، لازم است تا قابلیت سوئیچ یا تغییر یک راهکار پیاده سازی خواندن انحصاری در طی این فاز وجود داشته باشد.

پیاده سازی موازی الگوریتم ها

۴- طرح آزمایشی

۴ـ۱٫ بستر محاسباتی

کلیه راهکارهای پیاده سازی موازی ما بر روی MasParMP-1 با پردازش گرهای ۱۶۳۸۴ انجام شد. کامپیوتر MasPar [33] به عنوان یک کامپیوتر متشکل از داده های متعدد با دستورالعمل واحد موازی گسترده (SIMD) به شمار می آید. کلیه پردازشگرهای موازی به صورت همزمان قابلیت اجرای دستورالعمل های یکسان در یک زمان برابر را خواهند داشت. فرآیند تشریح معماری سخت افزاری و محیط نرم افزاری MasPar MP-1 را می توان در مرجع [۲۲] ملاحظه کرد.

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

۴ـ۲٫ ورودی های آزمایش

در برنامه ما، یک نمودار غیرجهت دار به وسیله لیستی از یال ها ارائه شده است. ما برنامه های خود را با استفاده از گراف های تصادفی سه چگالی یال مختلف ارائه نموده ایم:

• گراف های متراکم که در آن

• گراف های دارای تراکم سطح متوسط که در آن m = n⁵

• گراف های پراکنده که در آن صادق است.

به منظور ایجاد یک گراف تصادفی با n رأس و m یال، ما در ابتدا اقدام به ایجاد یک گراف خالی با n رأس نمودیم. متعاقباً ما یک یال را در هر زمان با هر یال انتخابی با توجه به احتمال یکنواخت اضافه نموده تا آنکه دقیقاً m یال ایجاد شود. برای هر اندازه و پراکندگی، ما چهار گراف آزمایشی مختلف را ایجاد نمودیم. ما هر برنامه را بر روی هر گراف آزمایشی برای ۱۰ بار تکرار انجام داده و میانگین ۴۰ آزمایش را ثبت نمودیم.

ما از کلاس های خاص گراف های ذیل استفاده نمودیم که در آزمایشات انجام شده در مرجع [۱۶] گزارش شده اند.

• گریدهای پوششی دو بعدی که به صورت متناسب با ویژگی ۳۰ و ۶۰ درصدی یال ها مدنظر هستند (انتخاب شده به صورت تصادفی). بنابراین در اینجا با یک گراف m = 0.6×n به هنگامی که چگالی یال برابر با ۳۰% و m = 1.2 و به هنگامی که چگالی یال برابر با ۶۰% است روبرو هستیم.

• گریدهای پوششی سه بعدی که دارای اندازه یکسان در هر بعد با ۲۰ و ۴۰% از یال های خود می باشند (انتخابی به صورت تصادفی). بنابراین با توجه به گراف در این کلاس، ویژگی m = 0.6×n، به هنگامی که چگالی یال برابر با ۳۰% و ویژگی m = 1.2 به هنگامی که چگالی یال برابر با ۶۰% است، صادق تلقی خواهد شد.

• گراف های سه تایی یا ثالث که در آن هر رأس به صورت تصادفی قابلیت انتخاب سه مجاور را خواهد داشت. توجه داشته باشید که این گراف های ثالث به صورت چند گرافی بوده وm = 3× صحت خواهد داشت.

• گراف های تصادفی با …

پیاده سازی موازی الگوریتم ها

۵- داده های عملکرد

ما نسبت به پیاده سازی الگوریتم های ۱ الی ۴ که در بخش ۲ توصیف شد اقدام نمودیم. کلیه برنامه های ما از ساختار داده های فشرده شده استفاده نموده اند که صرفاً برای یکبار از یال غیر جهت دار در هر کدام از آنها استفاده شده است، یعنی کاربرد یک روتین خاص برای اولین تکرار، و انجام عملکرد کنترلی برای یال های زنده. ما همچنین از پرش اشاره گر غیر مستقیم در الگوریتم ۱ و ۲ استفاده ننمودیم، چرا که ما دریافتیم که هیچگونه ارتقای عملکردی از طریق انجام این ویژگی حاصل نخواهد شد.

۵ـ۱٫ الگوریتم های قطعی

ما در ابتدا اقدام به تست ۵ کد قطعی مختلف با استفاده از ۳۸۴/۱۶ PE با چهار کیلوبایت حافظه در هر PE نمودیم.

• کد A: الگوریتم ۲

• کد B: کد A با تراکم سازی یال، اما بدون حذف یال های دوبله

• کد C : الگوریتم ۱

• کد D: کد C با تراکم سازی یال، اما بدون حذف یال های دوبله

• کد E: الگوریتم ۳ با تراکم سازی یال و پرش اشاره گر غیرمستقیم، اما بدون حذف یال های دوبله.

برای هر کد، ما اقدام به تست دو روش مختلف جهت اجرای فرایند نوشتن همزمان نمودیم. در هر نگارش، ما از یک عملیات نوشتن فرضی یا اختیاری (با استفاده از روتین rsend) استفاده نموده و در نگارش دوم ما از عملیات نوشتن همزمان دارای اولویت (با استفاده از روتین sendwith) بهره جستیم. داده های عملکرد در جدول یک نشان داده شده اند. ما مشاهده می نماییم که برای گراف های متراکم، غالب اجراها در چندین تکرار اولیه به اتمام می رسند و الگوریتم ۲ (یعنی کد A و کد B) دارای عملکرد بهتری در مقایسه با الگوریتم های دیگر هستند. الگوریتم ۱ (یعنی کد C) نیز از عملکرد بهتری در مقایسه با فرایند نوشتن با اولویت برخوردار است. الگوریتم ۳ (یعنی کد E) از عملکرد بهتری برخوردار خواهد بود آن هم به هنگامی که گراف بسیار پراکنده می باشد. ما همچنین مشاهده نمودیم که نگارش نوشتن با اولویت سبب کاهش تعداد تکرارهای ضروری برای کدنویسی در ارتباط با فرایند قطع برنامه خواهد شد. با این وجود، مجموع زمان اجرا به طور الزامی کاهش نخواهد یافت که علت آن را می توان سربار حاصله در ارتباط با پیاده سازی عملیات نوشتن همزمان با قابلیت اولویت با استفاده از روتین sendwith دانست.

حذف یال های المثنی و پیاده سازی فرایند خواندن / نوشتن همزمان ترکیبی

ما مجدداً اقدام به اجرای کد فوق با اصلاح حذف یال های تکرار شده یا دوبل در هر بار تکرار نمودیم. ما دریافتیم که عملکرد کد A تا D ارتقا نمی یابد. ما همچنین از فرایند نوشتن و خواندن همزمان ترکیبی در کد برنامه خود استفاده نمودیم. ما دریافتیم که عملکرد کد A تا D نیز چندان ارتقا نیافته است. با این حال، عملکرد کد E به میزان قابل توجهی ارتقا یافته و از عملکرد کلیه کدهای دیگر در تمامی کلاس های دیگر گراف ها بهتر است. داده عملکرد در جدول ۲ نشان داده شده است.

۵ـ۲٫ الگوریتم تصادفی

ما ویژگی های حذف یال های دوبل و پرش اشاره گر غیر مستقیم را در الگوریتم تصادفی خود بکار گرفتیم. عملکرد برنامه کدنویسی ما در جدول ۳ نشان داده شده است. بر این مبنا، ما مشاهده می نماییم که عملکرد کد تصادفی ما کمتر از بهترین نگارش قطعی، بر روی مجموعه ای از گراف های مورد آزمایشی ما، می باشد.

۵ـ۳٫ آزمایشات متعاقب

ما کد خود را بر روی چند مورد دیگر از کلاس های گراف مورد آزمایش قرار دادیم که نتیجه آن در بخش ۵ـ۲ مشخص شده است. داده های عملکرد برای کد E با ویژگی های حذف یال های دوبل و کاربرد عملیات نوشتن همزمان ترکیبی در جدول ۴ نشان داده شده است. داده های عملکرد برای کد تصادفی در جداول ۵ و ۶ ارائه شده اند. ما مشخص ساختیم که کد تصادفی ما دارای عملکرد بهتری در مقایسه با بهترین کدنویسی قطعی بر روی گریدها می باشد. با این وجود، کد قطعی ما همچنان از فرایند بهتری در مقایسه با کد تصادفی در ارتباط با گراف های تصادفی و گراف های سه تایی برخوردار می باشد.

۵ـ۴٫ کاربرد حافظه

با استفاده از پردازنده های فیزیکی ۱۶۳۸۴ و ۴ کیلوبایت حافظه بر حسب پردازنده فیزیکی (که به میزان ۱۶/۱ مجموع حافظه موجود می باشد)، ما قابلیت اجرای الگوریتم تصادفی خود برای هر گراف تا میزان ۵۲/۰ میلیون رأس و ۵۲/۰ میلیون یال را خواهیم داشت. این بدان معنا می باشد که ما قابلیت ذخیره سازی ۳۲ رأس و ۳۲ یال را در هر پردازنده فیزیکی خواهیم داشت. الگوریتم قطعی ما از عملکرد بهتری برخوردار می باشد، با این حال این الگوریتم نیازمند حافظه بیشتری خواهد بود. ما نشان دادیم که عملکرد برنامه قطعی ما برای گراف های تا ۲۶/۰ میلیون رأس و ۲۶/۰ یال قابل توجه می باشد. برای گراف با این اندازه، ما اقدام به ذخیره سازی ۱۶ رأس و ۱۶ یال در یک پردازنده فیزیکی می نماییم.

۵ـ۵٫ مقایسه با تحقیقات مرتبط

در مرجع [۱۶]، Greiner اقدام به گزارش نمودن چندین راهکار پیاده سازی الگوریتم های موازی جهت یافتن مولفه های همبند در یک کامپیوتر موازی حجیم CM-2 با استفاده از تعدادی از پردازنده ها (۸۱۹۲ پردازنده) و به بهره گیری از ۳۲ کیلوبایت در هر پردازنده نمود. وی همچنین یک راهکار پیاده سازی در ارتباط با یک سوپر کامپیوتر برداری Cray C-90 با استفاده از یک پردازنده را ارائه داد. Greiner نیز الگوریتم های Shiloach و Vishkin [50] و Awerbuch و Shiloach [2] همچنین الگوریتم تصادفی ساده اعمالی ما را مورد بررسی قرار دادند. Greiner از سیستم مولد شبه اعداد برای ایجاد بیت های تصادفی در کد تصادفی خود استفاده نکرده است. در مقابل، iامین بیت “تصادفی” برای یک رأس به عنوان (i مدل log₂ n) امین بیت تعداد رأس به شمار آمده است. وی اقدام به پیاده سازی تکنیک های تعدیلی نمود که شامل روتین های مشابه با تکرار اولیه قلاب گذاری ما می باشد و در بردارنده کنترل یال های زنده، و همچنین متراکم سازی یال می باشد. وی همچنین الگوریتم های ترکیبی خاصی را ارائه داد که در بردارنده ویژگی های سه الگوریتم فوق و یک الگوریتم مشخص شده در مبحث Hirchberg، Chandra و Sarwate [20] می باشد. الگوریتم ترکیبی وی دارای بهترین عملکرد برای کلاس های گراف های تست شده می باشد.

پیاده سازی موازی الگوریتم ها

۶- نتیجه گیری

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