مقاله در مورد یک الگوریتم موازی و ساده برای مساله‌ی کوتاهترین مسیر تک - منبع بر روی گراف مسطح

بخشی از مقاله

يك الگوريتم موازي و ساده براي مساله‌ي
كوتاهترين مسير تك-منبع
بر روي گراف مسطح

چكيده
در اين مقاله يك الگوريتم ساده براي مسئله‌ي كوتاهترين مسير تك-منبع در يك گراف مسطح با يالهاي با وزن غير‌منفي ارائه خواهيم داد. الگوريتم مزبور در زمان و با انجام ، ، عمل بر روي مدل EREW PRAM اجرا مي‌شود. نقطه قوت الگوريتم در سادگي آن است كه آنرا براي پياده‌سازي و استفاده ، در عمل بسيار كارامد مي‌سازد. در اين مقاله ساختار داده‌هايي براي پياده‌سازي اين الگوريتم بر روي EREW PRAM ارايه شده است. مي‌توان اين الگوريتم را با انجام تغييراتي بر روي مدل برنامه‌نويسي MPI به سادگي پياده كرد. الگوريتم ما بر اساس ناحيه‌بندي گراف ورودي و استفاده از روش موازي الگوريتم دايسترا ، بنا شده است.

1 مقدمه
مساله‌ي كوتاهترين مسير يك مساله‌ي زيربنايي و مهم در بهينه‌سازي تركيبياتي است كه از ارزش عملي و تئوري زيادي برخوردار است. براي يك گراف جهت‌دار كه شامل n راس و m يال است، مساله‌ي كوتاهترين مسير عبارت است از پيدا كردن يك مسير با كمترين وزن بين هر دو راس u و v كه در مجموعه‌ي راسها وجود دارند. وزن مسير u-v برابر مجموع وزن يالهاي بين آنهاست. وزن كوتاهترين مسير بين u-v ، فاصله از u تا v ناميده مي‌شود. مساله‌ي كوتاهترين مسير، بر حسب جفت راسهاي u و v و نحوه‌ي وزن‌گذاري يالهاي گراف به گونه‌هاي مختلفي تقسيم مي‌شود.

اگرچه الگوريتم‌هاي سريال كارا براي بيشتر اين گونه مسايل وجود دارند اما هنوز فقدان يك الگوريتم موازي كارا براي آن احساس مي‌شود؛ الگورتيم كارا ، يعني الگوريتمي كه ميزان كار انجام شده توسط آن براي حل مساله معادل يا نزديك به تعداد كاري باشد كه توسط بهترين الگوريتم سريال لازم است (منظور از كار، مجموع تمام كارهايي است كه توسط پروسسورها انجام مي‌شود).

طراحي يك الگوريتم كارا براي مساله‌ي كوتاهترين مسير ، يك مساله‌ي حل نشده‌ي مهم را در پردازش موازي تشكيل مي‌دهد. يكي از دلايل ممكن براي نبود چنان الگوريتمي مي‌تواند اين باشد كه بيشتر تاكيدها بر روي به دست آودردن يك الگوريتم خيلي سريع (يعني NC) قرار گرفته است. به هر حال در اغلب موقعيتهاي عملي، كه تعداد پروسسورهاي موجود ثابت و خيلي كوچكتر از انداز

ه‌ي مساله‌اي است كه در دست داريم ، هدف اصلي و ابتدايي ما اينست كه يك الگوريتم work-efficient (به‌جاي الگوريتم خيلي سريع) داشته باشيم؛ چرا كه در چنان مواردي زمان اجرا بر كاري كه بين پروسسورها تقسيم مي‌شود غالب است. اگر چنان الگوريتمي ساير پارامترهاي خاص مانند سادگي و پياده‌سازي راحت را داشته باشد از اهميت ويژه‌اي برخوردار خواهد بود.

يكي از گونه‌هاي مهم مساله‌ي كوتاهترين مسير ، مساله‌ي كوتاهترين مسير تك-منبع يا درخت كوتاهترين مسير است : با داشتن يك گراف جهت‌دار كه شامل n راس و m يال و يك راس مشخص كه منبع ناميده مي‌شود، است، مساله‌ي ما عبارت است از پيدا كردن كوتاهترين مسير از s به تمام راسهاي ديگر در G . مساله‌ي كوتاهترين مسير تك-منبع يك راه حل سريال كارا دارد مخصوصا وقتي كه G هيچ راس منفي نداشته باشد. در اين مورد مساله مي‌تواند توسط الگوريتم دايسترا در زمان با استفاده از هيپ فيبوناچي يا يك ساختار داده‌ي صف اولويت با زمان حدي مشابه، حل شود[2] .
در اين مقاله ما براي مساله‌ي كوتاهترين مسير تك-منبع بر روي يك گراف مسطح G با وزن يال

حقيقي و غيرمنفي ، يك الگوريتم ساده ارايه مي‌دهيم كه پياده‌سازي آن راحت است. با مصالحه‌اي بر زمان اجرا ، الگوريتمي (قطعي) ارايه مي‌دهيم كه از لحاظ work-efficiency بهبودي بر الگوريتمهاي قبل از آن باشد. اين الگوريتم كه با جزييات كامل و اثبات در [1] ارايه شده است. در اينجا ما آن الگوريتم را با توضيحات بيشتر توضيح مي‌دهيم. به‌طور دقيقتر الگوريتم مزبور بر روي EREW PRAM در زمان و با انجام عمل ، اجرا مي‌شود كه .
مانند الگوريتمهاي كوتاهترين مسير تك-منبع قبلي ، الگوريتم حاضر بر اساس ناحيه‌بندي گراف و

تبديل مساله به يك دسته از مسايل كوتاهترين مسير بر روي ناحيه‌ها، عمل مي‌كند. عملكرد الگوريتم ما به اين صورت است كه با داشتن يك ناحيه‌بندي از گراف، ما براي هر ناحيه الگوريتم دايسترا را بكار مي‌بريم و در پايان ، الگوريتم دايسترا را بر روي گراف كمكي كه با استفاده از اطلاعات كوتاهترين مسير در نواحي ساخته شده ، اجرا مي‌كنيم. جزييات اين الگوريتم در بخشهاي بعدي آمده است. با توليد كپي‌هاي مناسب و كافي از يالهاي گراف ، از خواندن و نوشتن همزمان پروسسورها در حافظه جلوگيري مي‌شود. همانطور كه گفتيم ما در الگوريتم خود نيازمند يك ناحيه‌بندي از گراف ورودي هستيم كه براي محاسبه‌ي اين ناحيه‌بندي ، ما يك پياده‌سازي EREW PRAM از الگوريتم ارائه شده در [3] را ارايه مي‌دهيم. اين پياده‌سازي خاص، يك ناحيه‌بندي از گراف مطابق با نياز الگوريتم ما را محاسبه مي‌كند. در اين الگوريتم هم فرض مي‌شود كه گراف ورودي مسطح است.
مهمترين امتياز الگوريتم ما سادگي آن است كه پياده‌سازي آنرا راحت مي‌كند، طوري كه پياده‌سازي آن بر اساس روتينهاي زيربنايي و قابل فهم ، همانطور كه در ادامه گفته خواهد شد، استوار است كه مي‌توان آنها را در همه‌ي كتابخانه‌هاي الگوريتمهاي موازي يافت. مي‌توان اين الگوريتم را با انجام تغييراتي بر روي مدل برنامه نويسي MPI به راحتي پياده كرد. ذكر اين نكته حايز اهميت است كه براي ماشيني كه اجازه‌ي خواندن و نوشتن همزمان را مي‌دهد، الگوريتم ما مي‌تواند به‌طرز قابل توجهي ساده‌تر شود؛ بخاطر اينكه ديگر ايجاد كپي‌هاي فراوان از گراف ورودي براي خواندن همروند لازم نيست.

ما در بخش بعدي ، تعاريف را ارايه مي‌دهيم و برخي از نكات ابتدايي در مورد جداساز‌ها (separator) و ناحيه‌بندي گراف مسطح را بيان مي‌كنيم. الگوريتم ما در بخش 3 ارايه شده است. در بخش 4 هم جزييات مربوط به پياده‌سازي بدست آوردن يك ناحيه‌بندي از گراف را توضيح مي‌دهيم. در بخش 5 در مورد پياده‌سازي الگوريتم بر روي MPI صحبت مي‌كنيم. نتيجه‌گيري و جمع‌بندي هم در بخش 6 ارايه شده است.

2 مقدمات اوليه
در ادامه‌ي اين مقاله فرض كنيد يك گراف جهت دار مسطح با وزن يالهاي حقيقي و غير منفي است كه راس و يال دارد (گراف را مسطح در نظر گرفتيم). در ادامه وقتي ما در مورد خصوصيات جداساز گراف G صحبت مي‌كنيم، ما به گراف غيرجهت‌دار G اشاره داريم كه با حذف جهت از يالهاي آن به‌دست مي‌آيد (يعني جداساز را بر روي گراف غيرجهت‌دار پيدا مي‌كنيم). اما وقتي ما در مورد كوتاهترين مسير صحبت مي‌كنيم، به‌هر حال ما جهت يالها را به حساب مي‌آوريم.

تعريف 1 جداسازِ يك گراف ، برابر است با زير مجموعه‌اي مانند C از ، كه بخشهاي حذف‌شده از را به دو زير مجموعه‌ي جدا از هم A و B تقسيم مي‌كند، بطوري‌كه هر مسير از يك راس در A به يك راس در B ، حداقل شامل يك راس از C باشد.

به هر كدام از راسهاي گراف يك عدد نسبت مي‌دهيم و به آن ارزش راس مي‌گوييم. ارزش هر راس را برابر در نظر مي‌گيريم كه n برابر تعداد راسهاي گراف است. اين براي آن است كه هنگام تقسيم گراف به بخش‌هاي جدا از هم آنرا بصورت متوازن تقسيم كنيم. فرض كنيد ، نشان دهنده‌ي ارزش راس باشد. آنگاه ارزش زيرمجموعه‌ي ، بصورت نشان داده خواهد شد .

در شكل 1 يك جداساز نمونه براي گراف نشان داده شده است.
Lipton و Tarjan در قضيه‌ي زير ، [4] ، نشان دادند كه اندازه‌ي جداساز گراف مي‌تواند كوچك باشد.

قضيه 1 (قضيه‌ي جداساز مسطح) فرض كنيد يك گراف n راسي مسطح است با ارزش‌هاي غيرمنفي بر روي راسهاي آن كه مجموع آنها برابر 1 است؛ آنگاه يك جداساز S براي G وجود دارد كه V را به دو مجموعه‌ي و تقسيم مي‌كند ، به طوري كه و هر كدام از و ، حداكثر مجموع ارزش را دارند.

شكل 1 . يك جداساز براي گراف كه نودهاي آن با رنگ
خاكستري نشان داده شده‌اند.
ما جداساز S را يك جداسازِ براي G مي‌ناميم.

تعريف 2 ناحيه‌بندي يك گراف يعني تقسيم بندي راسهاي گراف به نواحي جداگانه ، بطوريكه : (1) هر راسي يا دروني باشد، يعني متعلق به دقيقا يك ناحيه باشد، يا مرزي باشد، يعني حداقل بين دو ناحيه مشترك باشد؛ (2) هيچ يالي بين دو راس دروني كه متعلق به نواحي مختلف هستند، موجود نباشد. براي هر عدد صحيح ، ، يك تقسيم-r گراف G ، يعني تجزيه‌ي ناحيه‌اي G به ناحيه، كه هر ناحيه حداكثر راس و حداكثر راس مرزي داشته باشد ( و ضريبهاي ثابت هستند).

شكل 2 يك ناحيه‌ي بندي نوعي براي يك گراف را نشان داده است.

شكل 2 . ناحيه‌بندي گراف به 3 ناحيه‌ي مجزا

روالهاي مورد نياز الگوريتم ما عبارتند از: (1) الگوريتم دايسترا (نسخه‌ي سريال و موازي) كه توسط يك ساختار داده‌ي هيپ (مثلا باينري هيپ) پياده‌سازي شده است. (2) يك پياده‌سازي استاندارد الگوريتم محاسبه‌ي پيشوند (يا پيشوند بخشي ) و مرتب‌سازي؛ و (3) الگوريتم موازي جداساز مسطح كه توسط Gazit و Miller در [5] ارايه شده ؛ نسخه‌ي پياده‌سازي EREW PRAM اين الگوريتم در بخش 4 داده شده است.
دو زيرروال اصلي كه توسط الگوريتم ما فراخواني مي‌شوند عبارتند از: (1) الگوريتم سريال دايسترا ؛ كه ما آنرا در داخل الگوريتم خودمان ، بر روي گراف H با راس منبع s به صورت ، فراخواني خواهيم كرد. (2) نسخه‌ي موازي الگوريتم دايسترا ؛ اين الگوريتم بر روي گراف در زمان با استفاده از پروسسور روي EREW PRAM اجرا مي‌شود (كه و ) . براي فراخواني الگوريتم دايستراي موازي ، براي و راس مبدا s از عبارت استفاده مي‌كنيم. در اينجا فرض مي‌كنيم كه خواننده با الگوريتم دايسترا آشناست. براي يادآوري مي‌توانيد به [2] مراجعه كنيد.
الگوريتم دايستراي موازي : نسخه‌ي موازي‌شده‌ي الگوريتم دايسترا كه دايستراي موازي ناميده مي‌شود، سرراست و قابل فهم است و با بروز رساني برچسب‌هاي فاصله بصورت موازي انجام مي‌پذيرد. ايده‌ي اصلي الگوريتم بصورت زير است : فرض كنيد كه هر پروسسور P

يك هيپ مخصوص به خود دارد كه مي‌تواند اعمال Insert و DecreaseKey را در زمان ثابت و اعمال Find و DeleteMin را در بدترين حالت در زمان انجام دهد (براي ياد آوري اعمال فوق به [2] نگاه كنيد). فرض كنيد يك راس با كوچكترين فاصله‌ انتخاب شود و قبل از شروع تكرار بعدي به P پروسسور فرستاده (broadcast) شود. ليست مجاورت راس انتخاب شده ، به P بخش با اندازه‌هاي مساوي تقسيم مي‌شود بطوري‌كه فاصله‌ي راسهاي مجاور بتواند بطور موازي در زما

ن به‌روز شود (d درجه‌ي راس انتخاب‌شده است). هر پرسسوري كه يك راس را به روز رسانده است ، آن را در داخل هيپ خصوصي خودش Insert مي‌كند (يا عمل DecreaseKey را بر روي آن انجام مي‌دهد)، و دوباره از هيپ خصوصي خودش يك راس با كوچكترين برچسب را انتخاب مي‌كند. در تكرار بعدي، پروسسورها بطور دسته جمعي با انجام يك عمل محاسبه‌ي پيشوند ، را

سي را كه در كل كوچكترين فاصله را دارد را انتخاب مي‌كنند. راس انتخاب‌شده از تمام هيپ‌هايي كه در آن است حذف مي‌شود. حال تكرار بعدي مي‌تواند آغاز شود. پياده‌سازي الگوريتم فوق راحت است: هر پروسسوري يك هيپ محلي دارد بطوري‌كه مي‌تواند يك نسخه‌ي سريال از الگوريتم را مورد استفاده قرار دهد. تنها عمل موازي كه مورد نياز است ، عمل محاسبه‌ي پيشوند است.

لازم به ذكر است كه ، استفاده از هر هيپي با بدترين زمان براي اعمال آن (مثلا هيپ دودويي)، خواست ما را برآورده مي‌سازد. همانطور كه در بخش 3 خواهيم ديد، كار انجام شده توسط اين نسخه از پياده‌سازي الگوريتم دايستراي موازي ، ، بطور مجانبي از كارهايي كه توسط ساير مراحل الگوريتم انجام مي‌شود كمتر است (براي اينكه ).

3 الگوريتم كوتاهترين مسير

در اين بخش ما الگوريتم خود را براي حل مساله‌ي كوتاهترين مسير تك-منبع بر روي گراف مسطح G با وزن يال غيرمنفي ، ارايه مي‌دهيم. ما فرض مي‌كنيم كه گراف G داراي يك تقسيم-r معلوم است (تعريف 2 را ببينيد). در بخش 4 نشان خواهيم داد كه چگونه مي‌توان يك تقسيم-r براي گراف يافت. فعلا فرض مي‌كنيم جنين تقسيمي را داريم.
فرض كنيد كه راس منبعي باشد كه مي‌خواهيم درخت كوتاهترين مسير را براي آن حساب كنيم. بطور خلاصه الگوريتم ما بصورت زير عمل مي‌كند :
در داخل هر ناحيه ، براي هر راس مرزي v ، يك درخت كوتاهترين مسير با ريشه‌ي v محاسبه مي‌شود. اين محاسبات بصورت همروند با استفاده از الگوريتم دايسترا بر روي نواحي انجام مي‌شود. در ناحيه‌اي كه شامل s است ، اگر s يك راس مرزي نباشد، يك محاسبه‌ي اضافي بايد انجام شود. سپس G را به تبديل مي‌كنيم. گراف شامل موارد زير است : راس مبدا s ؛ تمام راسهاي مرزي بر روي نواحي G ؛ يالهاي بين هر دو راس مرزي كه به ناحيه‌ي يكساني از G تعلق دارند كه وزنهاي آنها معادل با فاصله‌ي آنها در داخل ناحيه است (اگر مسير بين آنها وجود نداشته باشد، يال متناظر آن برابر قرار داده مي‌شود)؛ در درون ناحيه‌اي كه شامل s است ، مثلا ناحيه‌ي ، يالهاي بين s و راسهاي مرزي نيز در شامل مي‌شوند كه وزن اين يالها برابر با فاصله‌ي راسهاي مرزي از s است. بعد از بدست آوردن ، يك محاسبه براي بدست آوردن كوتاهترين مسير تك-منبع با استفاده از الگوريتم موازي دايسترا بر روي آن انجام مي‌دهيم كه در نتيجه ، كوتاهترين مسير از s به تمام راسهاي ديگر ، يعني تمام راسهاي مرزي در G ، محاسبه مي‌شود. بعد از اين مرحله، سرانجام كوتاهترين مسير از s به باقي‌مانده‌ي راسها در G (يعني راسهاي دروني) بصورت موازي محاسبه مي‌شود. براي محاسبه‌ي فاصله‌ي هر راس دروني ، از اطلاعات راسهاي مرزي ناحيه‌ي متعلق به آن استفاده مي‌شود. جزييات پياده‌سازي الگوريتم ما بصورت زير است :

ورودي: يك گراف جهت‌دار مسطح ، و يك راس منبع مشخص ، و يك تقسيم-r از گراف به نواحي ، و . فرض كنيد مجموعه‌ي راسهاي باشد و مجموعه‌ي راسهاي مرزي باشد. و مجموعه‌ي را برابر مجموعه‌ي تمام راسهاي مرزي در نظر بگيريد. و همچنين براي را ، برابر مجموعه‌اي از ناحيه‌ها در نظر بگيريد كه راس مرزي v متعلق به آنهاست. بدون از دست دادن كليت مساله فرض كنيد . اگر s يك راس مرزي باشد آنگاه بطور دلخواه از ميان يكي از ناحيه‌هايي كه s بين آنها مشترك است انتخاب مي‌شود.
گراف ورودي به‌صورت مجموعه‌اي از ليستهاي مجاورت كه در آرايه A ذخيره شده‌اند، نشان داده مي‌شود بطوريكه راسهاي مجاور راس يك بخش متوالي در آرايه را تشكيل مي‌دهد كه آنرا بصورت نشان مي‌دهيم (شكل 3 را نگاه كنيد). براي راحت كردن توليد كپي‌هاي مورد نياز از گراف ، گراف ورودي به ساختار داده‌هاي زير مجهز شده است: هر راس داخلي ناحيه‌ي (يعني راسي كه در قرار دارد) يك برچسب دارد كه نشان دهنده‌ي ناحيه‌اي است كه به آن تعلق دارد. مجموعه‌ي راسهاي

مرزي (يعني ) بصورت يك آرايه نشان داده مي‌شود. همچنين تمام راسهاي مرزي ،C، بصورت يك آرايه نشان داده مي‌شوند. فرض مي‌شود كه تمام راسهاي مجاور راس مرزي ، كه متعلق به يك ناحيه هستند، يك بخش متوالي از راسها را در ايجاد مي‌كنند. راسهاي مرزيِ مجاورِ راس كه آن

ها را با نشان مي‌دهيم ، متعلق به چند ناحيه هستند كه بطور دلخواه در درون يكي از بخشها قرار مي‌گيرند. هر راس دو اشاره‌گر به دارد، يكي به راس ابتدايي و يكي به راس انتهايي در بخش متوالي از راسها در آرايه، كه به تعلق دارد، اشاره مي‌كند. هر يك اشاره‌گر به آرايه‌ي ، كه شامل ناحيه‌هايي است كه v در آنها يك راس مرزي است، دارد. سرانجام هر راس مرزي يك اشاره‌گر به محل در آرايه‌ي دارد. نمايش ساختار داده‌هاي مربوط به تقسيم-r در شكل 3 نشان داده شده است.

شكل 3 . ساختار داده‌هاي لازم براي ارايه‌ي تقسيم-r

در شريطي كه يك راس مرزي متعلق به نواحي متعددي است، بخش‌بندي ليست‌هاي مجاورت راس‌هاي مرزي، به پروسسورها اجازه مي‌دهد كه بطور همروند بتوانند به داده‌هاي مربوط بهعمل مي‌آيد.
خروجي: يك درخت كوتاهترين مسير كه ريشه‌ي آن s است. درخت كوتاهترين مسير در قالب آرايه‌هاي و بازگردانده مي‌شود؛ در ، فاصله از s تا v ذخيره مي‌شود و در ، پدر v در درخت كوتاهترين مسير نگهداري مي‌شود.
Method:
1. Initiliation
2. Computation of shortest path s inside regions
3. Computation of shortest path tree inside
4. Contraction of into
5. Computation of shortest path tree in
End of Algorithm.

اكنون پياده‌سازي هر مرحله از الگوريتم فوق را تشريح مي‌كنيم.
1. مقدار دهي اوليه . ما ابتدا از هر ناحيه‌ي به تعداد تا كپي ، توليد مي‌كنيم. وقتي كه ما كوتاهترين مسير را در داخل هر ناحيه حساب مي‌كنيم ، اين كپي‌ها لازم هستند. را به عنوان kامين كپي از ناحيه‌ي در نظر بگيريد ( ) ، كه وابسته به kامين راس مرزي ، ، است. وقتي ما در مرحله‌ي 2 ، درخت كوتاهترين مسير را در با ريشه‌ي محاسبه مي‌كنيم ، اين كپي ، مورد نياز خواهد بود. براي هر ، دو آرايه‌ي و ، متناظر مي‌شود؛ فاصله‌ي كوتاهترين مسير در را نگه‌داري مي‌كند ، و پدر u در درخت كوتاهترين مسير با ريشه‌ي ، را نگه مي‌دارد.

1.01 for all , , do in parallel
1.02 Make copies of ;
1.03 endfor
1.04 for all , do in parallel
1.05 Make copies of the segment of containing the vertices
belonging to ;
1.06 endfor
1.07 for all , do in parallel

1.08 Allocate space for the arrays and ;
1.09 endfor
1.10 for all , , do in parallel
1.11 if then else ;
1.12 ;
1.13 endfor

مراحل 1.01-1.03 و 1.04-1.06 با استفاده از روش محاسبه‌ي پيشوند بخشي انجام مي‌شوند. پياده‌سازي مراحل 1.04-1.06 مشابه آن است. در ادامه در مورد پياده سازي مراحل 1.01-1.03 صحبت خواهيم كرد. ابتدا يك آرايه ساخته مي‌شود كه تعداد كپي‌هاي توليد‌شده، يعني را براي هر راس ، نگه مي‌دارد. آرايه‌ي جديد راسها، ، ايجاد مي‌شود. با استفاده از عمل محاسبه‌ي پيشوند

ي اندازه‌ي ، محاسبه مي‌شود. اين آرايه به بخشهاي تقسيم مي‌شود كه براي هر ، مي‌تواند تا كپي از u نگه‌داري كند. يك اشاره‌گر به در اولين محل از ذخيره مي‌شود. با محاسبه‌ي پيشوند بخشي بر روي ، هر كدام از اين اشاره‌گرها به تمام كپي‌هاي u ارسال مي‌شوند. در يك روش

مشابه، آرايه‌ي مجاورت A ، به يك آرايه‌ي كپي مي‌شود بطوريكه هر به تعداد تا كپي از هر راس مجاورش داشته باشد. فرض كنيد نشان‌دهنده‌ي محل ذخيره‌شدن اشاره‌گر به kامين كپي u ، يعني ، باشد. حال lامين راس همسايه‌ي در مي‌تواند با اضافه‌كردن مقدار به بدست آيد. بنابرا

ين هر كپي از u مي‌تواند به كپي‌هاي راسهاي همسايه‌ي u ، بدون خواندن همروند دسترسي پيدا كند.

2. محاسبه‌ي كوتاهترين مسير در داخل ناحيه‌ها. براي هر راس مرزي در ناحيه‌ي ، يك درخت كوتاهترين مسير تك-منبع با راس مبدا در با استفاده از الگوريتم سريال دايسترا ، محاسبه مي‌شود. در حين اجراي الگوريتم، هر زمان كه يك راس مرزي ، ، از انتخاب مي‌شود، فقط آن بخش از راسهاي مجاور آن كه در قرار دارند مرور مي‌شوند.

2.01 for all , , do in parallel
2.02 Run ;
2.03 for all do in parallel
2.04 store the distance of a shortest path in ;
2.05 store the parent of u in the shortest path tree rooted at in ;
2.06 endfor
2.07 endfor

3. محاسبه‌ي درخت كوتاهترين مسير در داخل . اگر s يك راس مرزي نباشد، مساله‌ي كوتاهترين مسير تك-منبع با راس منبع s در ناحيه‌ي محاسبه مي‌شود كه در نتيجه‌ي آن آرايه‌ي فاصله‌ها ، ، و آرايه‌ي پدرها ، ايجاد مي‌شوند. ، فاصله‌ي كوتاهترين مسير s-x در را نگه مي‌دارد و يك اشاره‌گر به پدر x در درخت كوتاهترين مسير در با ريشه‌ي s ، را نگهداري مي‌كند.

3.01 if then run resulting in arrays and ;

4. تبديلG به و محاسبه‌ي درخت كوتاهترين مسير در . اين مرحله گراف G را به گراف تبديل مي‌كند طوريكه شامل اجزاي زير است: راس منبع s ؛ تمام راسهاي مرزي G ؛ براي هر دو راس مرزي و كه به ناحيه‌ي يكساني تعلق دارند، يك راس در از به با وزني معادل با فاصله‌ي آنها در وجود دارد؛ اگر s يك راس مرزي نباشد، آنگاه يالهايي از s به تمام راسهاي مرزي در ناحيه‌ي با وزني معادل با فاصله‌ي آنها از s ، به افزوده مي‌شود. بعد از بدست آوردن ، مساله‌ي كوتاهترين م

سير تك-منبع با منبع s ، روي با استفاده از الگوريتم دايستراي موازي حل مي‌شود كه در نتيجه‌ي آن آرايه‌ي فاصله ، و آرايه‌ي پدر، ، بدست مي‌آيند. مي‌دانيم كه ، فاصله‌ي s تا x در را ذخيره مي‌كند و ، اشاره‌گر به پدر x در درخت كوتاهترين مسير را نگه مي‌دارد. بعد از انجام اين مرحله فاصله از s تاهر كدام از راس‌هاي مرزي G بدست آمده است.

4.01 ; ;
4.02 for all , , do in parallel
4.03 for all pairs , do in parallel
4.04 Add edge to with weight equal to ;
4.05 endfor
4.06 endfor
4.07 if then
4.08 for all do in parallel
4.09 Add edge to with weight equal to ;
4.10 endfor

4.11 ;
4.12 Run , resulting in arrays and

ليست مجاورتي بصورت زير ساخته مي‌شود (مراحل 4.04 و 4.09) : آرايه‌ي كه شامل نواحي‌اي است كه راس مرزي متعلق به آن است ، را در نظر بگيريد. براي هر مدخل (entry) از اين آرايه، ما يك آرايه به اندازه‌ي را مشترك مي‌كنيم (شكل 4 را ببينيد). راس را در محل ام اين آرايه ذخيره كنيد.

شكل 4 . ساختن

حال ، بصورت آرايه‌اي نشان داده مي‌شود كه تمام راسهاي مجاور يك بخش متوالي را در آرايه C ايجاد مي‌كنند. اين راسهاي مجاور را مي‌توان توسط يك عمل محاسبه‌ي پيشوندي بر روي آرايه‌هاي ، در راستاي آرايه‌هاي آن ، ساخت. اگر s يك راس مرزي نباشد، بايد بخش جديدي به افزوده شود كه تمام يالهاي ، ، را شامل شود ، كه كار زيادي نيست. توجه كنيد كه ممكن است شامل يالهاي چندگانه باشد، يعني در حالتي كه راسهاي مرزي و هر دو متعلق به يك ناحيه باشند، اما اين هيچ تاثيري بر درستي يا پيچيدگي اجراي الگوريتم دايستراي موازي در مرحله‌ي 4.12 نمي‌گذارد. هر وقت كه اشاره‌گر ، ، به روز شد، در كنار پدر x ، ناحيه‌اي كه يال به آن تعلق دارد را نيز نگهداري مي‌كنيم. اين كار به ما اجازه مي‌دهد كه بتوانيم در مرحله‌ي 5 ، اشاره‌گر به نودهاي پدر را براي بدست آوردن درخت كوتاهترين مسير استخراج كنيم.

5. محاسبه‌ي درخت كوتاهترين مسير در . براي محاسبه‌ي درخت كوتاهترين مسير، در G با راس منبع s ، بايد كوتاهترين مسير در G از s به تمام راسهاي (اعم از راسهاي دروني

و مرزي)، را پيدا كنيم و آنرا در ذخيره كنيم. همچنين بايد اشاره‌گر پدر براي هر x در درخت كوتاهترين مسير را در نگهداري كنيم.
براي محاسبه‌ي فاصله‌ها از به راسهاي داخلي و همچنين يافتن اشاره‌گرها به نودهاي پدر به صورت زير عمل مي‌كنيم : براي هر راس دروني ، در ناحيه‌ي ، در آرايه‌ي جستجو مي‌كنيم تا يك راس مرزي را پيدا كنيم كه مجموع فاصله‌هاي (كه در مرحله‌ي 4 حساب شد) و (كه در مرحله‌

ي 2 حساب شد) را به حداقل برساند. اين حداقل فاصله را در ذخيره مي‌كنيم. پدر u در درخت ، يعني ، همان پدر u در درخت كوتاهترين مسير در با منبع است، بجز حالت خاصي كه در آن و u يك راس دروني باشد. اين محاسبات در مراحل 5.10-5.13 انجام مي‌شوند و براي حالت خاص محاسبات در مراحل 5.21-5.25 انجام مي‌شود كه در ادامه در مورد آن توضيح مي‌دهيم. فاصله

از s به تمام راسهاي مرزي در مرحله‌ي 4 محاسبه شده و در آرايه‌ي ذخيره شده است. از اينرو تمام آنچه كه ما بايد براي راسهاي مرزي انجام دهيم محاسبه‌ي اشاره‌گرهاي پدر است. براي هر راس مرزي ، ما به پدر آن ، در درخت كوتاهترين مسير در با ريشه‌ي s نگاه مي‌كنيم و چك مي‌كنيم كه آيا يال متعلق به است يا نه (اين اطلاعات توسط الگوريتم دايسترا در مرحله‌ي 4 ذخيره شده است). اگر يال متعلق به نبود آنگاه ما هيچ كاري انجام نمي‌دهيم، براي اينكه كوتاهترين مسير از درون عبور نمي‌كند. در غير اينصورت اگر يال متعلق به بود ، ما بين حالتهاي و تمايز قايل مي‌شويم. در حالت اول ، ، داريم و پدر در همان پدر در درخت كوتاهترين مسير در با ريشه‌ي است كه در ذخيره شده است. در حالت دوم ما دوباره چك مي‌كنيم كه آيا s يك راس مرزي است يا نه. اگر ، آنگاه يال متعلق به است و از اين‌رو ما به حالت اول برميگرديم ، يعني ( ) و . اگر ، مانند قبل ( ) ، اما پدر در مساوي با (همانطور كه در مرحله‌ي 3 حساب شد) خواهد بود. اين محاسبات ، با توجه به راسهاي مرزي در مراحل 5.14-5.19 انجام شده است.
سرانجام، در حالتي كه s يك راس مرزي نيست، ممكن است اطلاعات مربوط به فاصله و نود پدر، كه تا كنون براي راسهاي دروني در محاسبه شده، درست نباشد؛ براي اينكه ، براي ، وزن كوتاهترين مسير را كه حداقل از يك راس مرزي عبور مي‌كند را ذخيره مي‌كند، در حالي كه ممكن است كوتاهترين مسير واقعي تماماً در ناحيه‌ي بماند. اين مشكل مي‌تواند با بروز رساني به و به اصلاح شود در حالي كه است. اين محاسبات با توجه به راسهاي داخلي ، در مراحل 5.21-5.25 ، انجام شده است.
يك مرحله‌ي پبش‌محاسباتي به منظور جلوگيري از دسترسي همزمان حافظه لازم است. براي جلوگيري از خواندن همروند آرايه‌ي در مرحله‌ي 5.11 بايد به تعداد تا كپي از هر مقدار براي هر راس مرزي ايجاد شود (مراحل 5.01-5.04) . براي جلوگيري از خواندن همروند اشاره‌گرهاي پدر در آرايه‌

ي در مرحله‌ي 5.16 ، يك كپي از براي هر كدام از تا ناحيه‌اي كه راس مرزي به آن تعلق دارد، ايجاد مي‌شود (مراحل 5.05-5.08). عمل كپي كردن و با استفاده از محاسبه‌ي پيشوند بخشي انجام مي‌شود.

5.01 for all , , do in parallel
5.02 Make copies of ;
5.03 Let denote the uth copy of for ;
5.04 endfor
5.05 for all do in parallel
5.07 Let denote the copy of for region ;
5.08 endfor
5.09 for all do in parallel

5.10 for all do in parallel
5.11
5.12 ;
5.13 endfor
5.14 for all do in parallel
5.15 ;
5.16 Let ;
5.17 if edge belong to then
5.18 if and then else ;
5.19 endfor
5.20 endfor

5.21 if then
5.22 for all do in parallel
5.23 if then
5.24 ; ;
5.25 endfor

قضيه 2 . مساله‌ي كوتاهترين مسير تك-منبع در يك گراف n-راسي مسطح با وزن يال غير منفي، مي‌تواند در زمان با انجام تعداد عمل در EREW PRAM حل شود.
اثبات در [1] .

با قرار دادن ، براي هر ، خواهيم داشت :

قضيه‌ 3 . بر روي يك گراف n-راسي مسطح ، مساله‌ي كوتاهترين مسير تك-منبع مي‌تواند در زمان با انجام تعداد عمل بر روي EREW PRAM حل شود.

4 بدست آوردن ناحيه‌بندي گراف بصورت موازي
در اين بخش ما يك پياده‌سازي از الگوريتم ارايه شده در [3] را بر روي EREW PRAM براي پيدا كردن يك تقسيم-r از يك گراف مسطح ارايه مي‌دهيم. اصلي‌ترين زير روالي كه در اين الگوريتم استفاده مي‌شود ، پيدا كردن يك جداساز براي گراف G است. براي مساله‌ي پيدا كردن جداساز ، يك الگوريتم موازي work-optimal توسط Gazit و Miller در [5] ارايه شده است. اين الگوريتم يك موازي‌سازي زيركانه از الگورتم سريال Lipton و Tarjan است كه در [4] ارايه شده و در زمان با انجام عمل اجرا مي‌شود. ما در بخش 4-3 يك پياده سازي از الگوريتم را براي پيدا كردن تقسيم-‌r ارايه مي‌دهيم. در ادامه براي سادگي از ضريب ثابت در اندازه‌ي جداساز صرف‌نظر مي‌كنيم.

4-1 الگوريتم سريال 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حاصل مي‌شود.
4-2 الگوريتم موازي Gazit-Miller براي يافتن جداساز در گراف

مشكل اصلي در موازي‌سازي روش Lipton-Tarjan ، محاسبه‌ي درخت BFS با ريشه‌ي دلخواه s است : يا بايد به مساله‌ي زمان بپردازيم كه منجر به يك الگوريتم موازي مي‌شود كه از نظر كارايي بسيار بد عمل مي‌كند يا اينكه توجه خود را به ميزان كار انجام شده معطوف كنيم كه منجر به يك الگوريتم موازي بدون تسريع (speedup) مي‌شود.