دانش رسان |
مرکز علم و دانش کشور مقاله در مورد یک الگوریتم موازی و ساده برای مساله‌ی کوتاهترین مسیر تک-منبع بر روی گراف مسطح
در حال بارگذاری
توجه : به همراه فایل word این محصول فایل پاورپوینت (PowerPoint) و اسلاید های آن به صورت هدیه ارائه خواهد شد
مقاله در مورد یک الگوریتم موازی و ساده برای مساله‌ی کوتاهترین مسیر تک-منبع بر روی گراف مسطح دارای ۲۶ صفحه می باشد و دارای تنظیمات در microsoft word می باشد و آماده پرینت یا چاپ است
فایل ورد مقاله در مورد یک الگوریتم موازی و ساده برای مساله‌ی کوتاهترین مسیر تک-منبع بر روی گراف مسطح کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه و مراکز دولتی می باشد.
توجه : در صورت مشاهده بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل ورد می باشد و در فایل اصلی مقاله در مورد یک الگوریتم موازی و ساده برای مساله‌ی کوتاهترین مسیر تک-منبع بر روی گراف مسطح،به هیچ وجه بهم ریختگی وجود ندارد
بخشی از متن مقاله در مورد یک الگوریتم موازی و ساده برای مساله‌ی کوتاهترین مسیر تک-منبع بر روی گراف مسطح :
یک الگوریتم موازی و ساده برای مساله‌ی
کوتاهترین مسیر تک-منبع
بر روی گراف مسطح
چکیده
در این مقاله یک الگوریتم ساده برای مسئله‌ی کوتاهترین مسیر تک-منبع در یک گراف مسطح با یالهای با وزن غیرمنفی ارائه خواهیم داد. الگوریتم مزبور در زمان و با انجام ، ، عمل بر روی مدل EREW PRAM اجرا می‌شود. نقطه قوت الگوریتم در سادگی آن است که آنرا برای پیاده‌سازی و استفاده ، در عمل بسیار کارامد می‌سازد. در این مقاله ساختار داده‌هایی برای پیاده‌سازی این الگوریتم بر روی EREW PRAM ارایه شده است. می‌توان این الگوریتم را با انجام تغییراتی بر روی مدل برنامه‌نویسی MPI به سادگی پیاده کرد. الگوریتم ما بر اساس ناحیه‌بندی گراف ورودی و استفاده از روش موازی الگوریتم دایسترا ، بنا شده است.
۱ مقدمه
مساله‌ی کوتاهترین مسیر یک مساله‌ی زیربنایی و مهم در بهینه‌سازی ترکیبیاتی است که از ارزش عملی و تئوری زیادی برخوردار است. برای یک گراف جهت‌دار که شامل n راس و m یال است، مساله‌ی کوتاهترین مسیر عبارت است از پیدا کردن یک مسیر با کمترین وزن بین هر دو راس u و v که در مجموعه‌ی راسها وجود دارند. وزن مسیر u-v برابر مجموع وزن یالهای بین آنهاست. وزن کوتاهترین مسیر بین u-v ، فاصله از u تا v نامیده می‌شود. مساله‌ی کوتاهترین مسیر، بر حسب جفت راسهای u و v و نحوه‌ی وزن‌گذاری یالهای گراف به گونه‌های مختلفی تقسیم می‌شود.
اگرچه الگوریتمهای سریال کارا برای بیشتر این گونه مسایل وجود دارند اما هنوز فقدان یک الگوریتم موازی کارا برای آن احساس می‌شود؛ الگورتیم کارا ، یعنی الگوریتمی که میزان کار انجام شده توسط آن برای حل مساله معادل یا نزدیک به تعداد کاری باشد که توسط بهترین الگوریتم سریال لازم است (منظور از کار، مجموع تمام کارهایی است که توسط پروسسورها انجام می‌شود).
طراحی یک الگوریتم کارا برای مساله‌ی کوتاهترین مسیر ، یک مساله‌ی حل نشده‌ی مهم را در پردازش موازی تشکیل می‌دهد. یکی از دلایل ممکن برای نبود چنان الگوریتمی می‌تواند این باشد که بیشتر تاکیدها بر روی به دست آودردن یک الگوریتم خیلی سریع (یعنی NC) قرار گرفته است. به هر حال در اغلب موقعیتهای عملی، که تعداد پروسسورهای موجود ثابت و خیلی کوچکتر از انداز
ه‌ی مساله‌ای است که در دست داریم ، هدف اصلی و ابتدایی ما اینست که یک الگوریتم work-efficient (به‌جای الگوریتم خیلی سریع) داشته باشیم؛ چرا که در چنان مواردی زمان اجرا بر کاری که بین پروسسورها تقسیم می‌شود غالب است. اگر چنان الگوریتمی سایر پارامترهای خاص مانند سادگی و پیاده‌سازی راحت را داشته باشد از اهمیت ویژه‌ای برخوردار خواهد بود.
یکی از گونه‌های مهم مساله‌ی کوتاهترین مسیر ، مساله‌ی کوتاهترین مسیر تک-منبع یا درخت کوتاهترین مسیر است : با داشتن یک گراف جهت‌دار که شامل n راس و m یال و یک راس مشخص که منبع نامیده می‌شود، است، مساله‌ی ما عبارت است از پیدا کردن کوتاهترین مسیر از s به تمام راسهای دیگر در G . مساله‌ی کوتاهترین مسیر تک-منبع یک راه حل سریال کارا دارد مخصوصا وقتی که G هیچ راس منفی نداشته باشد. در این مورد مساله می‌تواند توسط الگوریتم دایسترا در زمان با استفاده از هیپ فیبوناچی یا یک ساختار داده‌ی صف اولویت با زمان حدی مشابه، حل شود[۲] .
در این مقاله ما برای مساله‌ی کوتاهترین مسیر تک-منبع بر روی یک گراف مسطح G با وزن یال
حقیقی و غیرمنفی ، یک الگوریتم ساده ارایه می‌دهیم که پیاده‌سازی آن راحت است. با مصالحه‌ای بر زمان اجرا ، الگوریتمی (قطعی) ارایه می‌دهیم که از لحاظ work-efficiency بهبودی بر الگوریتمهای قبل از آن باشد. این الگوریتم که با جزییات کامل و اثبات در [۱] ارایه شده است. در اینجا ما آن الگوریتم را با توضیحات بیشتر توضیح می‌دهیم. به‌طور دقیقتر الگوریتم مزبور بر روی EREW PRAM در زمان و با انجام عمل ، اجرا می‌شود که .
مانند الگوریتمهای کوتاهترین مسیر تک-منبع قبلی ، الگوریتم حاضر بر اساس ناحیه‌بندی گراف و
تبدیل مساله به یک دسته از مسایل کوتاهترین مسیر بر روی ناحیه‌ها، عمل می‌کند. عملکرد الگوریتم ما به این صورت است که با داشتن یک ناحیه‌بندی از گراف، ما برای هر ناحیه الگوریتم دایسترا را بکار می‌بریم و در پایان ، الگوریتم دایسترا را بر روی گراف کمکی که با استفاده از اطلاعات کوتاهترین مسیر در نواحی ساخته شده ، اجرا می‌کنیم. جزییات این الگوریتم در بخشهای بعدی آمده است. با تولید کپی‌های مناسب و کافی از یالهای گراف ، از خواندن و نوشتن همزمان پروسسورها در حافظه جلوگیری می‌شود. همانطور که گفتیم ما در الگوریتم خود نیازمند یک ناحیه‌بندی از گراف ورودی هستیم که برای محاسبه‌ی این ناحیه‌بندی ، ما یک پیاده‌سازی EREW PRAM از الگوریتم ارائه شده در [۳] را ارایه می‌دهیم. این پیاده‌سازی خاص، یک ناحیه‌بندی از گراف مطابق با نیاز الگوریتم ما را محاسبه می‌کند. در این الگوریتم هم فرض می‌شود که گراف ورودی مسطح است.
مهمترین امتیاز الگوریتم ما سادگی آن است که پیاده‌سازی آنرا راحت می‌کند، طوری که پیاده‌سازی آن بر اساس روتینهای زیربنایی و قابل فهم ، همانطور که در ادامه گفته خواهد شد، استوار است که می‌توان آنها را در همه‌ی کتابخانه‌های الگوریتمهای موازی یافت. می‌توان این الگوریتم را با انجام تغییراتی بر روی مدل برنامه نویسی MPI به راحتی پیاده کرد. ذکر این نکته حایز اهمیت است که برای ماشینی که اجازه‌ی خواندن و نوشتن همزمان را می‌دهد، الگوریتم ما می‌تواند به‌طرز قابل توجهی ساده‌تر شود؛ بخاطر اینکه دیگر ایجاد کپی‌های فراوان از گراف ورودی برای خواندن همروند لازم نیست.
ما در بخش بعدی ، تعاریف را ارایه می‌دهیم و برخی از نکات ابتدایی در مورد جداساز‌ها (separator) و ناحیه‌بندی گراف مسطح را بیان می‌کنیم. الگوریتم ما در بخش ۳ ارایه شده است. در بخش ۴ هم جزییات مربوط به پیاده‌سازی بدست آوردن یک ناحیه‌بندی از گراف را توضیح می‌دهیم. در بخش ۵ در مورد پیاده‌سازی الگوریتم بر روی MPI صحبت می‌کنیم. نتیجه‌گیری و جمع‌بندی هم در بخش ۶ ارایه شده است.
۲ مقدمات اولیه
در ادامه‌ی این مقاله فرض کنید یک گراف جهت دار مسطح با وزن یالهای حقیقی و غیر منفی است که راس و یال دارد (گراف را مسطح در نظر گرفتیم). در ادامه وقتی ما در مورد خصوصیات جداساز گراف G صحبت می‌کنیم، ما به گراف غیرجهت‌دار G اشاره داریم که با حذف جهت از یالهای آن به‌دست می‌آید (یعنی جداساز را بر روی گراف غیرجهت‌دار پیدا می‌کنیم). اما وقتی ما در مورد کوتاهترین مسیر صحبت می‌کنیم، به‌هر حال ما جهت یالها را به حساب می‌آوریم.
تعریف ۱ جداسازِ یک گراف ، برابر است با زیر مجموعه‌ای مانند C از ، که بخشهای حذف‌شده از را به دو زیر مجموعه‌ی جدا از هم A و B تقسیم می‌کند، بطوریکه هر مسیر از یک راس در A به یک راس در B ، حداقل شامل یک راس از C باشد.
به هر کدام از راسهای گراف یک عدد نسبت می‌دهیم و به آن ارزش راس می‌گوییم. ارزش هر راس را برابر در نظر می‌گیریم که n برابر تعداد راسهای گراف است. این برای آن است که هنگام تقسیم گراف به بخشهای جدا از هم آنرا بصورت متوازن تقسیم کنیم. فرض کنید ، نشان دهنده‌ی ارزش راس باشد. آنگاه ارزش زیرمجموعه‌ی ، بصورت نشان داده خواهد شد .
در شکل ۱ یک جداساز نمونه برای گراف نشان داده شده است.
Lipton و Tarjan در قضیه‌ی زیر ، [۴] ، نشان دادند که اندازه‌ی جداساز گراف می‌تواند کوچک باشد.
قضیه ۱ (قضیه‌ی جداساز مسطح) فرض کنید یک گراف n راسی مسطح است با ارزش‌های غیرمنفی بر روی راسهای آن که مجموع آنها برابر ۱ است؛ آنگاه یک جداساز S برای G وجود دارد که V را به دو مجموعه‌ی و تقسیم می‌کند ، به طوری که و هر کدام از و ، حداکثر مجموع ارزش را دارند.
شکل ۱ . یک جداساز برای گراف که نودهای آن با رنگ
خاکستری نشان داده شده‌اند.
ما جداساز S را یک جداسازِ برای G می‌نامیم.
تعریف ۲ ناحیه‌بندی یک گراف یعنی تقسیم بندی راسهای گراف به نواحی جداگانه ، بطوریکه : (۱) هر راسی یا درونی باشد، یعنی متعلق به دقیقا یک ناحیه باشد، یا مرزی باشد، یعنی حداقل بین دو ناحیه مشترک باشد؛ (۲) هیچ یالی بین دو راس درونی که متعلق به نواحی مختلف هستند، موجود نباشد. برای هر عدد صحیح ، ، یک تقسیم-r گراف G ، یعنی تجزیه‌ی ناحیه‌ای G به ناحیه، که هر ناحیه حداکثر راس و حداکثر راس مرزی داشته باشد ( و ضریبهای ثابت هستند).
شکل ۲ یک ناحیه‌ی بندی نوعی برای یک گراف را نشان داده است.
شکل ۲ . ناحیه‌بندی گراف به ۳ ناحیه‌ی مجزا
روالهای مورد نیاز الگوریتم ما عبارتند از: (۱) الگوریتم دایسترا (نسخه‌ی سریال و موازی) که توسط یک ساختار داده‌ی هیپ (مثلا باینری هیپ) پیاده‌سازی شده است. (۲) یک پیاده‌سازی استاندارد الگوریتم محاسبه‌ی پیشوند (یا پیشوند بخشی ) و مرتب‌سازی؛ و (۳) الگوریتم موازی جداساز مسطح که توسط Gazit و Miller در [۵] ارایه شده ؛ نسخه‌ی پیاده‌سازی EREW PRAM این الگوریتم در بخش ۴ داده شده است.
دو زیرروال اصلی که توسط الگوریتم ما فراخوانی می‌شوند عبارتند از: (۱) الگوریتم سریال دایسترا ؛ که ما آنرا در داخل الگوریتم خودمان ، بر روی گراف H با راس منبع s به صورت ، فراخوانی خواهیم کرد. (۲) نسخه‌ی موازی الگوریتم دایسترا ؛ این الگوریتم بر روی گراف در زمان با استفاده از پروسسور روی EREW PRAM اجرا می‌شود (که و ) . برای فراخوانی الگوریتم دایسترای موازی ، برای و راس مبدا s از عبارت استفاده می‌کنیم. در اینجا فرض می‌کنیم که خواننده با الگوریتم دایسترا آشناست. برای یادآوری می‌توانید به [۲] مراجعه کنید.
الگوریتم دایسترای موازی : نسخه‌ی موازی‌شده‌ی الگوریتم دایسترا که دایسترای موازی نامیده می‌شود، سرراست و قابل فهم است و با بروز رسانی برچسب‌های فاصله بصورت موازی انجام می‌پذیرد. ایده‌ی اصلی الگوریتم بصورت زیر است : فرض کنید که هر پروسسور P
یک هیپ مخصوص به خود دارد که می‌تواند اعمال Insert و DecreaseKey را در زمان ثابت و اعمال Find و DeleteMin را در بدترین حالت در زمان انجام دهد (برای یاد آوری اعمال فوق به [۲] نگاه کنید). فرض کنید یک راس با کوچکترین فاصله انتخاب شود و قبل از شروع تکرار بعدی به P پروسسور فرستاده (broadcast) شود. لیست مجاورت راس انتخاب شده ، به P بخش با اندازه‌های مساوی تقسیم می‌شود بطوریکه فاصله‌ی راسهای مجاور بتواند بطور موازی در زما
ن به‌روز شود (d درجه‌ی راس انتخاب‌شده است). هر پرسسوری که یک راس را به روز رسانده است ، آن را در داخل هیپ خصوصی خودش Insert می‌کند (یا عمل DecreaseKey را بر روی آن انجام می‌دهد)، و دوباره از هیپ خصوصی خودش یک راس با کوچکترین برچسب را انتخاب می‌کند. در تکرار بعدی، پروسسورها بطور دسته جمعی با انجام یک عمل محاسبه‌ی پیشوند ، را
سی را که در کل کوچکترین فاصله را دارد را انتخاب می‌کنند. راس انتخاب‌شده از تمام هیپ‌هایی که در آن است حذف می‌شود. حال تکرار بعدی می‌تواند آغاز شود. پیاده‌سازی الگوریتم فوق راحت است: هر پروسسوری یک هیپ محلی دارد بطوریکه می‌تواند یک نسخه‌ی سریال از الگوریتم را مورد استفاده قرار دهد. تنها عمل موازی که مورد نیاز است ، عمل محاسبه‌ی پیشوند است.
لازم به ذکر است که ، استفاده از هر هیپی با بدترین زمان برای اعمال آن (مثلا هیپ دودویی)، خواست ما را برآورده می‌سازد. همانطور که در بخش ۳ خواهیم دید، کار انجام شده توسط این نسخه از پیاده‌سازی الگوریتم دایسترای موازی ، ، بطور مجانبی از کارهایی که توسط سایر مراحل الگوریتم انجام می‌شود کمتر است (برای اینکه ).
۳ الگوریتم کوتاهترین مسیر
در این بخش ما الگوریتم خود را برای حل مساله‌ی کوتاهترین مسیر تک-منبع بر روی گراف مسطح G با وزن یال غیرمنفی ، ارایه می‌دهیم. ما فرض می‌کنیم که گراف G دارای یک تقسیم-r معلوم است (تعریف ۲ را ببینید). در بخش ۴ نشان خواهیم داد که چگونه می‌توان یک تقسیم-r برای گراف یافت. فعلا فرض می‌کنیم جنین تقسیمی را داریم.
فرض کنید که راس منبعی باشد که می‌خواهیم درخت کوتاهترین مسیر را برای آن حساب کنیم. بطور خلاصه الگوریتم ما بصورت زیر عمل می‌کند :
در داخل هر ناحیه ، برای هر راس مرزی v ، یک درخت کوتاهترین مسیر با ریشه‌ی v محاسبه می‌شود. این محاسبات بصورت همروند با استفاده از الگوریتم دایسترا بر روی نواحی انجام می‌شود. در ناحیه‌ای که شامل s است ، اگر s یک راس مرزی نباشد، یک محاسبه‌ی اضافی باید انجام شود. سپس G را به تبدیل می‌کنیم. گراف شامل موارد زیر است : راس مبدا s ؛ تمام راسهای مرزی بر روی نواحی G ؛ یالهای بین هر دو راس مرزی که به ناحیه‌ی یکسانی از G تعلق دارند که وزنهای آنها معادل با فاصله‌ی آنها در داخل ناحیه است (اگر مسیر بین آنها وجود نداشته باشد، یال متناظر آن برابر قرار داده می‌شود)؛ در درون ناحیه‌ای که شامل s است ، مثلا ناحیه‌ی ، یالهای بین s و راسهای مرزی نیز در شامل می‌شوند که وزن این یالها برابر با فاصله‌ی راسهای مرزی از s است. بعد از بدست آوردن ، یک محاسبه برای بدست آوردن کوتاهترین مسیر تک-منبع با استفاده از الگوریتم موازی دایسترا بر روی آن انجام می‌دهیم که در نتیجه ، کوتاهترین مسیر از s به تمام راسهای دیگر ، یعنی تمام راسهای مرزی در G ، محاسبه می‌شود. بعد از این مرحله، سرانجام کوتاهترین مسیر از s به باقی‌مانده‌ی راسها در G (یعنی راسهای درونی) بصورت موازی محاسبه می‌شود. برای محاسبه‌ی فاصله‌ی هر راس درونی ، از اطلاعات راسهای مرزی ناحیه‌ی متعلق به آن استفاده می‌شود. جزییات پیاده‌سازی الگوریتم ما بصورت زیر است :
ورودی: یک گراف جهت‌دار مسطح ، و یک راس منبع مشخص ، و یک تقسیم-r از گراف به نواحی ، و . فرض کنید مجموعه‌ی راسهای باشد و مجموعه‌ی راسهای مرزی باشد. و مجموعه‌ی را برابر مجموعه‌ی تمام راسهای مرزی در نظر بگیرید. و همچنین برای را ، برابر مجموعه‌ای از ناحیه‌ها در نظر بگیرید که راس مرزی v متعلق به آنهاست. بدون از دست دادن کلیت مساله فرض کنید . اگر s یک راس مرزی باشد آنگاه بطور دلخواه از میان یکی از ناحیه‌هایی که s بین آنها مشترک است انتخاب می‌شود.
گراف ورودی به‌صورت مجموعه‌ای از لیستهای مجاورت که در آرایه A ذخیره شده‌اند، نشان داده می‌شود بطوریکه راسهای مجاور راس یک بخش متوالی در آرایه را تشکیل می‌دهد که آنرا بصورت نشان می‌دهیم (شکل ۳ را نگاه کنید). برای راحت کردن تولید کپی‌های مورد نیاز از گراف ، گراف ورودی به ساختار داده‌های زیر مجهز شده است: هر راس داخلی ناحیه‌ی (یعنی راسی که در قرار دارد) یک برچسب دارد که نشان دهنده‌ی ناحیه‌ای است که به آن تعلق دارد. مجموعه‌ی راسهای
مرزی (یعنی ) بصورت یک آرایه نشان داده می‌شود. همچنین تمام راسهای مرزی ،C، بصورت یک آرایه نشان داده می‌شوند. فرض می‌شود که تمام راسهای مجاور راس مرزی ، که متعلق به یک ناحیه هستند، یک بخش متوالی از راسها را در ایجاد می‌کنند. راسهای مرزیِ مجاورِ راس که آن
ها را با نشان می‌دهیم ، متعلق به چند ناحیه هستند که بطور دلخواه در درون یکی از بخشها قرار می‌گیرند. هر راس دو اشاره‌گر به دارد، یکی به راس ابتدایی و یکی به راس انتهایی در بخش متوالی از راسها در آرایه، که به تعلق دارد، اشاره می‌کند. هر یک اشاره‌گر به آرایه‌ی ، که شامل ناحیه‌هایی است که v در آنها یک راس مرزی است، دارد. سرانجام هر راس مرزی یک اشاره‌گر به محل در آرایه‌ی دارد. نمایش ساختار داده‌های مربوط به تقسیم-r در شکل ۳ نشان داده شده است.
شکل ۳ . ساختار داده‌های لازم برای ارایه‌ی تقسیم-r
در شریطی که یک راس مرزی متعلق به نواحی متعددی است، بخش‌بندی لیستهای مجاورت راسهای مرزی، به پروسسورها اجازه می‌دهد که بطور همروند بتوانند به داده‌های مربوط بهعمل می‌آید.
خروجی: یک درخت کوتاهترین مسیر که ریشه‌ی آن s است. درخت کوتاهترین مسیر در قالب آرایه‌های و بازگردانده می‌شود؛ در ، فاصله از s تا v ذخیره می‌شود و در ، پدر v در درخت کوتاهترین مسیر نگهداری می‌شود.
Method:
۱. Initiliation
۲. Computation of shortest path s inside regions
۳. Computation of shortest path tree inside
۴. Contraction of into
۵. Computation of shortest path tree in
End of Algorithm.
اکنون پیاده‌سازی هر مرحله از الگوریتم فوق را تشریح می‌کنیم.
۱ مقدار دهی اولیه . ما ابتدا از هر ناحیه‌ی به تعداد تا کپی ، تولید می‌کنیم. وقتی که ما کوتاهترین مسیر را در داخل هر ناحیه حساب می‌کنیم ، این کپی‌ها لازم هستند. را به عنوان kامین کپی از ناحیه‌ی در نظر بگیرید ( ) ، که وابسته به kامین راس مرزی ، ، است. وقتی ما در مرحله‌ی ۲ ، درخت کوتاهترین مسیر را در با ریشه‌ی محاسبه می‌کنیم ، این کپی ، مورد نیاز خواهد بود. برای هر ، دو آرایه‌ی و ، متناظر می‌شود؛ فاصله‌ی کوتاهترین مسیر در را نگهداری می‌کند ، و پدر u در درخت کوتاهترین مسیر با ریشه‌ی ، را نگه می‌دارد.
۱۰۱ for all , , do in parallel
۱.۰۲ Make copies of ;
۱.۰۳ endfor
۱.۰۴ for all , do in parallel
۱.۰۵ Make copies of the segment of containing the vertices
belonging to ;
۱.۰۶ endfor
۱.۰۷ for all , do in parallel
۱۰۸ Allocate space for the arrays and ;
۱.۰۹ endfor
۱.۱۰ for all , , do in parallel
۱.۱۱ if then else ;
۱.۱۲ ;
۱.۱۳ endfor
مراحل ۱۰۱-۱۰۳ و ۱۰۴-۱۰۶ با استفاده از روش محاسبه‌ی پیشوند بخشی انجام می‌شوند. پیاده‌سازی مراحل ۱۰۴-۱۰۶ مشابه آن است. در ادامه در مورد پیاده سازی مراحل ۱۰۱-۱۰۳ صحبت خواهیم کرد. ابتدا یک آرایه ساخته می‌شود که تعداد کپی‌های تولید‌شده، یعنی را برای هر راس ، نگه می‌دارد. آرایه‌ی جدید راسها، ، ایجاد می‌شود. با استفاده از عمل محاسبه‌ی پیشوند
ی اندازه‌ی ، محاسبه می‌شود. این آرایه به بخشهای تقسیم می‌شود که برای هر ، می‌تواند تا کپی از u نگهداری کند. یک اشاره‌گر به در اولین محل از ذخیره می‌شود. با محاسبه‌ی پیشوند بخشی بر روی ، هر کدام از این اشاره‌گرها به تمام کپی‌های u ارسال می‌شوند. در یک روش
مشابه، آرایه‌ی مجاورت A ، به یک آرایه‌ی کپی می‌شود بطوریکه هر به تعداد تا کپی از هر راس مجاورش داشته باشد. فرض کنید نشان‌دهنده‌ی محل ذخیره‌شدن اشاره‌گر به kامین کپی u ، یعنی ، باشد. حال lامین راس همسایه‌ی در می‌تواند با اضافه‌کردن مقدار به بدست آید. بنابرا
ین هر کپی از u می‌تواند به کپی‌های راسهای همسایه‌ی u ، بدون خواندن همروند دسترسی پیدا کند.
۲ محاسبه‌ی کوتاهترین مسیر در داخل ناحیه‌ها. برای هر راس مرزی در ناحیه‌ی ، یک درخت کوتاهترین مسیر تک-منبع با راس مبدا در با استفاده از الگوریتم سریال دایسترا ، محاسبه می‌شود. در حین اجرای الگوریتم، هر زمان که یک راس مرزی ، ، از انتخاب می‌شود، فقط آن بخش از راسهای مجاور آن که در قرار دارند مرور می‌شوند.
۲۰۱ for all , , do in parallel
۲.۰۲ Run ;
۲.۰۳ for all do in parallel
۲.۰۴ store the distance of a shortest path in ;
۲.۰۵ store the parent of u in the shortest path tree rooted at in ;
۲.۰۶ endfor
۲.۰۷ endfor
۳ محاسبه‌ی درخت کوتاهترین مسیر در داخل . اگر s یک راس مرزی نباشد، مساله‌ی کوتاهترین مسیر تک-منبع با راس منبع s در ناحیه‌ی محاسبه می‌شود که در نتیجه‌ی آن آرایه‌ی فاصله‌ها ، ، و آرایه‌ی پدرها ، ایجاد می‌شوند. ، فاصله‌ی کوتاهترین مسیر s-x در را نگه می‌دارد و یک اشاره‌گر به پدر x در درخت کوتاهترین مسیر در با ریشه‌ی s ، را نگهداری می‌کند.
۳۰۱ if then run resulting in arrays and ;
۴ تبدیلG به و محاسبه‌ی درخت کوتاهترین مسیر در . این مرحله گراف G را به گراف تبدیل می‌کند طوریکه شامل اجزای زیر است: راس منبع s ؛ تمام راسهای مرزی G ؛ برای هر دو راس مرزی و که به ناحیه‌ی یکسانی تعلق دارند، یک راس در از به با وزنی معادل با فاصله‌ی آنها در وجود دارد؛ اگر s یک راس مرزی نباشد، آنگاه یالهایی از s به تمام راسهای مرزی در ناحیه‌ی با وزنی معادل با فاصله‌ی آنها از s ، به افزوده می‌شود. بعد از بدست آوردن ، مساله‌ی کوتاهترین م
سیر تک-منبع با منبع s ، روی با استفاده از الگوریتم دایسترای موازی حل می‌شود که در نتیجه‌ی آن آرایه‌ی فاصله ، و آرایه‌ی پدر، ، بدست می‌آیند. می‌دانیم که ، فاصله‌ی s تا x در را ذخیره می‌کند و ، اشاره‌گر به پدر x در درخت کوتاهترین مسیر را نگه می‌دارد. بعد از انجام این مرحله فاصله از s تاهر کدام از راسهای مرزی G بدست آمده است.
۴۰۱ ; ;
۴۰۲ for all , , do in parallel
۴.۰۳ for all pairs , do in parallel
۴.۰۴ Add edge to with weight equal to ;
۴.۰۵ endfor
۴.۰۶ endfor
۴.۰۷ if then
۴.۰۸ for all do in parallel
۴.۰۹ Add edge to with weight equal to ;
۴.۱۰ endfor
۴۱۱ ;
۴۱۲ Run , resulting in arrays and
لیست مجاورتی بصورت زیر ساخته می‌شود (مراحل ۴۰۴ و ۴۰۹) : آرایه‌ی که شامل نواحی‌ای است که راس مرزی متعلق به آن است ، را در نظر بگیرید. برای هر مدخل (entry) از این آرایه، ما یک آرایه به اندازه‌ی را مشترک می‌کنیم (شکل ۴ را ببینید). راس را در محل ام این آرایه ذخیره کنید.
شکل ۴ . ساختن
حال ، بصورت آرایه‌ای نشان داده می‌شود که تمام راسهای مجاور یک بخش متوالی را در آرایه C ایجاد می‌کنند. این راسهای مجاور را می‌توان توسط یک عمل محاسبه‌ی پیشوندی بر روی آرایه‌های ، در راستای آرایه‌های آن ، ساخت. اگر s یک راس مرزی نباشد، باید بخش جدیدی به افزوده شود که تمام یالهای ، ، را شامل شود ، که کار زیادی نیست. توجه کنید که ممکن است شامل یالهای چندگانه باشد، یعنی در حالتی که راسهای مرزی و هر دو متعلق به یک ناحیه باشند، اما این هیچ تاثیری بر درستی یا پیچیدگی اجرای الگوریتم دایسترای موازی در مرحله‌ی ۴۱۲ نمی‌گذارد. هر وقت که اشاره‌گر ، ، به روز شد، در کنار پدر x ، ناحیه‌ای که یال به آن تعلق دارد را نیز نگهداری می‌کنیم. این کار به ما اجازه می‌دهد که بتوانیم در مرحله‌ی ۵ ، اشاره‌گر به نودهای پدر را برای بدست آوردن درخت کوتاهترین مسیر استخراج کنیم.
۵ محاسبه‌ی درخت کوتاهترین مسیر در . برای محاسبه‌ی درخت کوتاهترین مسیر، در G با راس منبع s ، باید کوتاهترین مسیر در G از s به تمام راسهای (اعم از راسهای درونی
و مرزی)، را پیدا کنیم و آنرا در ذخیره کنیم. همچنین باید اشاره‌گر پدر برای هر x در درخت کوتاهترین مسیر را در نگهداری کنیم.
برای محاسبه‌ی فاصله‌ها از به راسهای داخلی و همچنین یافتن اشاره‌گرها به نودهای پدر به صورت زیر عمل می‌کنیم : برای هر راس درونی ، در ناحیه‌ی ، در آرایه‌ی جستجو می‌کنیم تا یک راس مرزی را پیدا کنیم که مجموع فاصله‌های (که در مرحله‌ی ۴ حساب شد) و (که در مرحله
ی ۲ حساب شد) را به حداقل برساند. این حداقل فاصله را در ذخیره می‌کنیم. پدر u در درخت ، یعنی ، همان پدر u در درخت کوتاهترین مسیر در با منبع است، بجز حالت خاصی که در آن و u یک راس درونی باشد. این محاسبات در مراحل ۵۱۰-۵۱۳ انجام می‌شوند و برای حالت خاص محاسبات در مراحل ۵۲۱-۵۲۵ انجام می‌شود که در ادامه در مورد آن توضیح می‌دهیم. فاصله
از s به تمام راسهای مرزی در مرحله‌ی ۴ محاسبه شده و در آرایه‌ی ذخیره شده است. از اینرو تمام آنچه که ما باید برای راسهای مرزی انجام دهیم محاسبه‌ی اشاره‌گرهای پدر است. برای هر راس مرزی ، ما به پدر آن ، در درخت کوتاهترین مسیر در با ریشه‌ی s نگاه می‌کنیم و چک می‌کنیم که آیا یال متعلق به است یا نه (این اطلاعات توسط الگوریتم دایسترا در مرحله‌ی ۴ ذخیره شده است). اگر یال متعلق به نبود آنگاه ما هیچ کاری انجام نمی‌دهیم، برای اینکه کوتاهترین مسیر از درون عبور نمی‌کند. در غیر اینصورت اگر یال متعلق به بود ، ما بین حالتهای و تمایز قایل می‌شویم. در حالت اول ، ، داریم و پدر در همان پدر در درخت کوتاهترین مسیر در با ریشه‌ی است که در ذخیره شده است. در حالت دوم ما دوباره چک می‌کنیم که آیا s یک راس مرزی است یا نه. اگر ، آنگاه یال متعلق به است و از اینرو ما به حالت اول برمیگردیم ، یعنی ( ) و . اگر ، مانند قبل ( ) ، اما پدر در مساوی با (همانطور که در مرحله‌ی ۳ حساب شد) خواهد بود. این محاسبات ، با توجه به راسهای مرزی در مراحل ۵۱۴-۵۱۹ انجام شده است.
سرانجام، در حالتی که s یک راس مرزی نیست، ممکن است اطلاعات مربوط به فاصله و نود پدر، که تا کنون برای راسهای درونی در محاسبه شده، درست نباشد؛ برای اینکه ، برای ، وزن کوتاهترین مسیر را که حداقل از یک راس مرزی عبور می‌کند را ذخیره می‌کند، در حالی که ممکن است کوتاهترین مسیر واقعی تماماً در ناحیه‌ی بماند. این مشکل می‌تواند با بروز رسانی به و به اصلاح شود در حالی که است. این محاسبات با توجه به راسهای داخلی ، در مراحل ۵۲۱-۵۲۵ ، انجام شده است.
یک مرحله‌ی پبش‌محاسباتی به منظور جلوگیری از دسترسی همزمان حافظه لازم است. برای جلوگیری از خواندن همروند آرایه‌ی در مرحله‌ی ۵۱۱ باید به تعداد تا کپی از هر مقدار برای هر راس مرزی ایجاد شود (مراحل ۵۰۱-۵۰۴) . برای جلوگیری از خواندن همروند اشاره‌گرهای پدر در آرایه
ی در مرحله‌ی ۵۱۶ ، یک کپی از برای هر کدام از تا ناحیه‌ای که راس مرزی به آن تعلق دارد، ایجاد می‌شود (مراحل ۵۰۵-۵۰۸). عمل کپی کردن و با استفاده از محاسبه‌ی پیشوند بخشی انجام می‌شود.
۵۰۱ for all , , do in parallel
۵.۰۲ Make copies of ;
۵.۰۳ Let denote the uth copy of for ;
۵.۰۴ endfor
۵.۰۵ for all do in parallel
۵.۰۷ Let denote the copy of for region ;
۵.۰۸ endfor
۵.۰۹ for all do in parallel
۵۱۰ for all do in parallel
۵.۱۱
۵.۱۲ ;
۵.۱۳ endfor
۵.۱۴ for all do in parallel
۵.۱۵ ;
۵.۱۶ Let ;
۵.۱۷ if edge belong to then
۵.۱۸ if and then else ;
۵.۱۹ endfor
۵.۲۰ endfor
۵۲۱ if then
۵.۲۲ for all do in parallel
۵.۲۳ if then
۵.۲۴ ; ;
۵.۲۵ endfor
قضیه ۲ . مساله‌ی کوتاهترین مسیر تک-منبع در یک گراف n-راسی مسطح با وزن یال غیر منفی، می‌تواند در زمان با انجام تعداد عمل در EREW PRAM حل شود.
اثبات در [۱] .
با قرار دادن ، برای هر ، خواهیم داشت :
قضیه ۳ . بر روی یک گراف n-راسی مسطح ، مساله‌ی کوتاهترین مسیر تک-منبع می‌تواند در زمان با انجام تعداد عمل بر روی EREW PRAM حل شود.
۴ بدست آوردن ناحیه‌بندی گراف بصورت موازی
در این بخش ما یک پیاده‌سازی از الگوریتم ارایه شده در [۳] را بر روی EREW PRAM برای پیدا کردن یک تقسیم-r از یک گراف مسطح ارایه می‌دهیم. اصلی‌ترین زیر روالی که در این الگوریتم استفاده می‌شود ، پیدا کردن یک جداساز برای گراف G است. برای مساله‌ی پیدا کردن جداساز ، یک الگوریتم موازی work-optimal توسط Gazit و Miller در [۵] ارایه شده است. این الگوریتم یک موازی‌سازی زیرکانه از الگورتم سریال Lipton و Tarjan است که در [۴] ارایه شده و در زمان با انجام عمل اجرا می‌شود. ما در بخش ۴-۳ یک پیاده سازی از الگوریتم را برای پیدا کردن تقسیم-r ارایه می‌دهیم. در ادامه برای سادگی از ضریب ثابت در اندازه‌ی جداساز صرف‌نظر می‌کنیم.
۴-۱ الگوریتم سریال Lipton-Tarjan برای یافتن جداساز در گراف
برای بهتر فهمیدن الگوریتم موازی Gazit-Miller باید ابتدا الگوریتم سریال Liption-Tarjan را بلد باشیم. همانطور که گفتیم الگوریتم Gazit-Miller نسخه‌ی موازی شده‌ی این الگوریتم است.
فرض کنید یک گراف مسطح متصل است. الگوریتم Lipton-Tarjan با انتخاب یک راس دلخواه شروع
می‌شود و سپس از s شروع به جستجوی اول سطح می‌کند (BFS) . به راسهای V یک عدد متناظر با سطح (level) آنها نسبت داده می‌شود که بیانگر اینست که آنها بر روی درخت BFS ساخته شده ، در چه سطحی قرار دارند (سطح s برابر صفر است). را برابر بیشترین سطح محاسبه‌شده و را برابر مجموعه‌ی راسها در سطح l در نظر بگیرید. خصوصیت BFS اینست که هر یک جداساز G است.
فرض کنید سطح میانی باشد، یعنی، ، اما نتیجتا ، . مشکل اینجاست که ممکن است تعداد
نودهای سطح میانی بیش از حد مطلوب باشد. اگر ، آنگاه الگوریتم متوقف می‌شود چرا که واضحا همان جداساز مورد نظر ماست. در غیر اینصورت باید سطوح و وجود داشته باشند بطوریکه (برش اول) و (برش آخر) و ، ، و (توجه کنید که ممکن است برابر با سطح تهی باشد). حذف کردن برش‌های اول و آخر، را به سه مجموعه تقسیم می‌کند:
, , .
اگر ، آنگاه جداساز مورد نظر برابر با ، و برابر با سنگین‌ترین مجموعه از بین مجموعه‌های A ، B و C ، و برابر با اجتماع دو مجموعه‌ی سبک دیگر خواهند بود (منظور از سنگین‌ترین مجموعه، مجموعه‌ایست که مجموع ارزش راسهای آن بیشتر باشد). به‌هر حال اگر ، آنگاه B باید باز هم بیشتر جدا شود. از آنجاییکه کافیست تا یک جداساز برای B با راس پیدا کنیم، بطوریکه بخشهای حاصل از تقسیمB حداکثر ارزش را داشته باشند. برای اینکه اگر ما چنین جداسازی را ( ) داشته باشیم، آنگاه جداساز مورد نظر برای گرافG برابر خواهد بود و . برابر با بخش سنگین‌ترB و برابر با اجتماع دو مجموعه‌ی سبک دیگر خواهند بود. واضح است که و ، هر دو حداکثر ارزش را خواهند داشت.
برای پیدا کردن باید یک گراف مسطح مانند زیر بسازید: تمام راسهای موجود در را به همراه یالهای وابسته به آنها از G حذف کنید. تمام راسهای موجود در را در یک راس تنهای با ارزش صفر فشرده کنید، یعنی تمام راسهای موجود در A را با جایگزین کنید و یالهایی از به راسهای موجود در رسم کنید.
به راحتی می‌توان نشان داد که یک درخت پوشای T با قطر حداکثر دارد. برای این منظور می‌توان گفت : چون ریشه‌ی Tاست و تمام راسها در حداکثر فاصله‌ی BFS معادل با را از دارند، در نتیجه، جداساز مورد نظر، ، می‌تواند با انجام عملیات بر روی گراف پیدا شود. حد مرزی از حد مرزی قطر Tحاصل می‌شود.
۴-۲ الگوریتم موازی Gazit-Miller برای یافتن جداساز در گراف
مشکل اصلی در موازی‌سازی روش Lipton-Tarjan ، محاسبه‌ی درخت BFS با ریشه‌ی دلخواه s است : یا باید به مساله‌ی زمان بپردازیم که منجر به یک الگوریتم موازی می‌شود که از نظر کارایی بسیار بد عمل می‌کند یا اینکه توجه خود را به میزان کار انجام شده معطوف کنیم که منجر به یک الگوریتم موازی بدون تسریع (speedup) می‌شود.
- در صورتی که به هر دلیلی موفق به دانلود فایل مورد نظر نشدید با ما تماس بگیرید.
