دانلود الگوریتم های بهینه انتشار برای همبندی های مبتنی بر Mesh در فایل ورد (word)

پیشنهاد مقاله درس پردازش موازی
الگوریتم‏های بهینه انتشار برای همبندی‏های مبتنی بر Mesh

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

چكیده
در این مقاله یك الگوریتم ساده برای مسئله‌ی كوتاهترین مسیر تك-منبع  در یك گراف مسطح با یالهای با وزن غیر‌منفی ارائه خواهیم داد. الگوریتم مزبور در زمان   و با انجام  ،  ، عمل بر روی مدل 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. محاسبه‌ی كوتاهترین مسیر در داخل ناحیه‌ها. برای هر راس مرزی  در ناحیه‌ی ، یك درخت كوتاهترین مسیر تك-منبع با راس مبدا  در  با استفاده از الگوریتم سریال دایسترا ، محاسبه می‌شود. در حین اجرای الگوریتم، هر زمان كه یك راس مرزی  ،  ، از  انتخاب می‌شود، فقط آن بخش از راسهای مجاور آن كه در  قرار دارند مرور می‌شوند...

منابع و مآخذ

1.    J. L. Träff, C. D. Zaroliagis,  A Simple Parallel Algorithm for the Single-Source Shortest Path Problem on Planar Digraphs , Journal of Parallel and Distributed Computing 60, 1103-1124 (2000).
2.    T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introuduction to Algorithms (second edition), chapter 24, McGraw-Hill Book Company.
3.    G. N. Fredrickson, Fast algorithms for shortest path in planar graphs with applications, SIAM J. Comput. 16, 6 (1987), 1004-1022.
4.    R. j. Lipton and R. E. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36, 2 (1979), 177-189.
5.    H. Gazit and G. L. Miller, An  optimal parallel algorithm for a separator for planar graphs, Unpublished manuscript, 1987.