درآمدي بــر الگوريتم‌هاي مـــوازي

[Fahim 9563]

استفان هاوکينگ، فيزيکدان مشهور، در مقدمه کتاب «تاريخچه زمان» در‌باره به کار‌گيري فرمول‌هاي رياضي در يک کتاب مي‌گويد‌: «... و در اين رهگذر گفته مي‌شد که هر معادله رياضي‌اي که در اين کتاب گنجانده شود، ميزان فروش را به نصف کاهش خواهد داد.» و اين دقيقاً همان تذكري بود كه از سوي پرهام‌ايزدپناه به من يادآوري شد! با اين حال، نوشتن از الگوريتم‌هاي موازي بدون اشاره هر چند مختصر به آناليز الگوريتم‌ها امکان‌پذير نيست. در نتيجه، اين مقاله از تکنيک‌هاي آناليز الگوريتم‌ها بهره برده است. با اين حال سعي شده تا کليت مطلب را به صورت معرفي نگه داشته و بي‌دليل به عمق بعضي مطالب وارد نشويم. پس از بيان مدل‌سازي اوليه، مراحل طراحي يک الگوريتم موازي را بيان‌کرده و سپس چهار مثال عملي درباره الگوريتم‌هاي موازي ارائه كنيم. البته، مثال‌هاي جالب و قابل بررسي در اين زمينه فراوان است و هر کدام مي‌توانند تکنيک جديدي را در زمينه طراحي الگوريتم‌هاي موازي به ما آموزش دهند. در اين مقاله چهار مثال بسيار مشهور و کلاسيک و در عين حال ساده را معرفي کرده‌ايم كه مي‌توانند نقطه شروع بسيار خوبي براي آشنايي با نحوه طراحي و پياده‌سازي الگوريتم هاي موازي محسوب شوند.اين مطلب يكي از مقالات بخش ويژه نشريه ماهنامه شبكه در شماره 115 با عنوان

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.

• ورود
• یا
• ثبت نام

مي‌باشد. جهت دريافت اين بخش ويژه به بخش پرونده‌هاي ويژه سايت مراجعه نمائيد.Cilk

کدهاي نوشته شده در اين بخش با استفاده از Cilk نوشته شده‌اند. کيلک نسخه‌اي از زبان C است که در محيط پردازش موازي مورد استفاده قرار مي‌گيرد. سينتکس اين زبان مشابه زبان C بوده که از چندين دستور اضافه مانند Spawn و Sync نيز سود مي‌برد.Spawn: اين دستور بيان مي‌کند، فراخواني رويه‌اي که پس از کلمه کليدي Spawn مي‌آيد مي‌تواند به صورت موازي با بقيه کد اجرا شود. البته Scheduler ، اجباري براي اجراي رويه به صورت موازي ندارد، بلکه اين دستور تنها به Scheduler مي‌گويد که مي‌تواند اين کار را انجام دهد.

Sync: اين دستور اجراي رويه فعلي را تا زماني که کار اجراي رويه‌هاي قبلي‌اي که به وسيله spawn فراخواني شده بودند تمام شود، متوقف مي‌سازد. به‌اين ترتيب، زماني که تمام رويه‌هاي موازي در حال اجرا کارشان به پايان رسيده و به فريم والد خود بازگشتند، اجراي رويه فعلي از سر گرفته مي‌شود.در ادامه مقاله مثال‌هاي گوناگوني از نحوه به کارگيري کيلک براي نوشتن برنامه‌هاي موازي ارائه مي‌شود.

 

مدل سازي اوليه

براي معرفي برخي از مفاهيم اوليه مورد نياز در بررسي الگوريتم‌هاي موازي به مثال مشهور فيبوناچي مراجعه مي‌کنيم.

محاسبه عدد n‌ام سري فيبوناچي

fib(n)

if n

then return n

 

x

y

 

sync

return (x+y)

البته اين کد به طور اصولي روش خوبي براي محاسبه سري فيبوناچي نيست. به دليل محاسبه چندباره هر کدام از اعداد اين سري، الگوريتم مطرح‌شده زمان اجراي نمايي دارد. اما به هر جهت براي مطرح ساختن مفاهيم موازي سازي مفيد است. سينتکس به کار رفته در اين مثال بيانگر مفهوم موازي سازي منطقي يا Logical Parallelism است، زيرا دراينجامشخص نشده که کدام Task توسط چه پردازنده‌اي انجام خواهد شد و در عوض تمركز روي محاسبات است. اين کار Scheduler است که به صورت دايناميک کارها به مجموعه‌اي از پردازنده‌ها Map كند.

 

DAG

مي‌توان جريان دستورهاي يک برنامه را به صورت يک گراف غيرمدور جهت‌دار يا DAG مدل کرد. شکل 1 گراف غير‌مدور جهت‌دار محاسباتي را براي fib(4) نشان مي‌دهد. رئوس درخت در واقع رشته‌هاي پردازشي يا Thread‌ها هستند که بيانگر بيشترين تعداد توالي دستوري است که شامل کنترل‌هاي موازي( Spawn، Return از يک رويه Spawn شده و Sync) نباشد.

 

اندازه گيري کارايي

براي اندازه‌گيري کارايي الگوريتم‌هاي موازي ابتدا بايد چندين معيار را براي اين امر معرفي كرد. در ادامه چندين قضيه و قانون معروف نيز براي درک بهتر موضوع بيان مي‌شود. براي ورود به بحث در ابتدا سعي مي‌کنيم شرايط ايده‌آل را در نظر بگيريم. يعني فرض مي‌کنيم هيچ Cache‌اي وجود نداشته و ارتباطات بين پردازنده‌ها نيز هزينه‌اي را در پي ندارد. توجه داشته باشيد که نتايج به دست آمده ممکن است تحت مفروضات متفاوت صحت نداشته باشند.

: زمان اجراي مينيمم الگوريتم روي P پردازنده

: زمان اجراي مينيمم الگوريتم روي يک پردازنده

: زمان اجراي مينيمم الگوريتم روي تعداد بي‌شماري از پردازنده‌ها که برابر با طول بلندترين مسير در DAG مرتبط با مسئله است. همچنين طول اين مسير Critical Path Length نيز ناميده مي‌شود. زيرا مسيرهاي موجود در DAG نشان دهنده توالي اجراي روتين‌ها هستند و اگر رأس A به رأس B وصل باشد تنها وقتي B مي‌تواند اجرا شود که A اجرا شده باشد. پس رئوس موجود در يک مسير نمي‌توانند به صورت موازي با يکديگر اجرا شوند. در نتيجه، بلندترين مسير بيانگر زمان اجراي کلي الگوريتم است.به عنوان مثال، براي fib(4) که DAG آن در شکل 1 مطرح شد، T1=17 (تعداد رشته‌ها) و =8 (که طول بلندترين مسير در DAG، با احتساب Thread اوليه) است. توجه داشته باشيد که در عمل رشته‌هاي‌پردازشي با استفاده از زمان اجراي واقعي خود وزن دهي خواهند شد.با استفاده از اين معيارها مي‌توان به يک کران پايين براي Tp دست يافت.

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.

• ورود
• یا
• ثبت نام

شكل 1- جريان دستورات براي Fib(4). هر دايره نشان دهنده يک Thread است. هر فلش کامل نشان دهنده توالي دستور بعدي است. هر فلش خط چين نشان دهنده يک عمل Spawn و هر فلش نقطه چين نشان دهنده يک Return از رويه Spawn شده است.

براي اثبات اين نتيجه بايد از برهان خلف استفاده کنيم. فرض کنيد که Tp

در ادامه با كمي توجه بيشتر به کران پايين مي‌توان به نتيجه جالبي رسيد. با مفروضات مطرح شده در بالا، با استفاده از P پردازنده هيچ‌گاه کمتر از برابر نمي‌شود. به بيان ديگر، بهترين عملکرد ممکن در زمان موازي سازي يک الگوريتم هنگامي حاصل مي‌شود که به نسبت تعداد پردازنده‌ها زمان کاهش يابد. نکته جالب توجه اين است که اين حکم هميشه هم درست نيست! در صورتي که مفروضات مطرح شده، يعني نداشتن Cache و نبودن هزينه ارتباط ميان پردازنده‌ها برداشته شود، ممکن است تغييرات بسيار جالب‌تري در زمان اجرا به وجود آيد. کمي بعد اين موضوع را دقيق‌تر مورد بررسي قرار مي‌دهيم.به نسبت T1/Tp براي يک الگوريتم خاص، Speedup يا تسريع گفته مي‌شود. اين نسبت نشان دهنده اين است که با استفاده از p پردازنده الگوريتم تا چه حد سريع‌تر اجرا خواهد شد. براي اين نسبت سه حالت مي‌تواند وجود داشته باشد‌:

1- که به آن تسريع خطي گفته مي‌شود.

2- که به آن تسريع فراخطي يا Superliner Speedup گفته مي‌شود.

3- که به آن تسريع پس خطي يا Sublinear Speedup گفته مي‌شود.

واقعيت اينجا است که در بيشتر موارد چيزي که در عمل براي الگوريتم‌هاي موازي به دست مي‌آيد، حالت سوم است. موارد متعددي براي کاهش کارايي الگوريتم هاي موازي مي‌تواند مطرح شود، مانند:

1- زياد بودن نسبت I/O به محاسبات

2- استفاده کردن از الگوريتم نامناسب که براي کامپيوتر موازي طراحي نشده باشد.

3- درگيري زياد بر سر حافظه ( بايد طراحي به صورتي تغيير کند که بيشتر از داده‌هاي محلي استفاده شود و ضمن اين‌كه استفاده بهينه از Cache نيز بايد لحاظ شود).

4- نسبت زياد کدهاي Sequential يا ترتيبي، قانون Amdahl به شکل دقيق‌تري اين موضوع را مورد بررسي قرار مي‌دهد.

5- سربار(Overhead) زياد موازي‌سازي؛ ساختن رشته‌هاي‌پردازشي جداگانه، ارتباط ميان پردازنده‌ها، تجميع نتايج

6- عدم تقسيم بار مناسب مسئله (load imbalance)؛ زماني که پردازنده‌ها بارکاري متفاوتي دارند، کارايي کاهش مي‌يابد.

به اين ترتيب، حالت ايده‌آل الگوريتم‌هاي موازي عموماً نزديک شدن به تسريع خطي است. اما در اين ميان تسريع فراخطي اي نيز مي‌تواند رخ دهد. سؤال اينجا است که آيا مي‌توان با استفاده از P پردازنده زمان اجرا را کمتر از 1/P برابر کرد؟

شكل 2- تسريع الگوريتم با اضافه کردن پردازنده

جواب اين سؤال مثبت است. با اين‌که تسريع فراخطي در موارد بسيار نادري اتفاق مي‌افتد، اما به هر صورت کاملاً امکان پذير است. براي اين امر مي‌توان به دلايل بسياري اشاره كرد که بارز ترين آن مسئله اضافه‌شدن حافظه Cache است. با زياد شدن تعداد پردازنده‌ها حافظه Cache در دسترس نيز افزايش پيدا مي‌کند. به اين ترتيب، در حالي که ممکن است مسئله اوليه در Cache يک پردازنده جا نشود، زيرمسئله‌ها مي‌توانند در Cache پردازنده‌ها‌ي مربوط به خود جاي گرفته و به اين ترتيب استفاده سريع‌تري را از حافظه به ارمغان بياورند. تسريع فراخطي هنگام اجراي الگوريتمي به روش عقب‌گرد(Backtracking) نيز مي‌تواند رخ دهد. زيرا ممکن است يک Thread شاخه‌اي از درخت Thread ديگر را هرس کرده و به اين ترتيب ميزان عمليات مورد انجام کمتر شود. در مسئله‌ها‌ي جست‌وجو نيز در موارد خاصي جست‌وجوي موازي مي‌تواند نتيجه‌اي بسيار سريع‌تر از جست‌وجوي خطي داشته باشد. به خصوص اگر فضاي جست‌وجو توزيع خاصي داشته باشد. تسريع تعريف شده در بالا تنها معيار قابل توجه براي ارزيابي يک الگوريتم موازي نيست. به عنوان مثال، مي‌توان زمان را ثابت فرض کرد و تعداد عملياتي را که الگوريتم موازي انجام داده با تعداد عمليات الگوريتم سري مقايسه كرد. در اين مورد نيز مي‌توان به يك کارايي‌ فراخطي دست يافت. اين موضوع زماني حاصل مي‌شود که با Scale کردن مسئله بتوانيم زمان بيشتري را روي روتين سريع‌تر صرف کنيم. براي اين بخش فقط به يک مثال از دنياي واقعي بسنده مي‌کنيم. فرض کنيد مي‌خواهيم پيانويي را از خانه حرکت داده و داخل کاميون بگذاريم. کار انجام شده نيز برابر با ميزان مسافت طي شده است. زمان ثابت در‌نظر‌گرفته شده نيز سي دقيقه است. حال اگر يک نفر را مسئول تکان دادن پيانو کنيم، شايد بيش از چند متر نتواند آن را تکان دهد و اين در حالي است که در تمام اين مدت کاميون بي‌استفاده مانده است. حال اگر دو نفر را براي کار بگماريم آن‌ها مي‌توانند در ده دقيقه پيانو را داخل کاميون گذاشته و سپس کاميون مي‌تواند بيست دقيقه حرکت کرده و پيانو را جابه جا کند. به اين ترتيب منابع ما دو برابر شده اما ميزان کار انجام شده تا صدها برابر زياد مي‌شود.

در پايان اين قسمت بايد به قانون Amdahl اشاره‌اي بكنيم. اين قانون ادعا مي‌کند که تسريع يک الگوريتم موازي در عمل به وسيله نسبت عمليات سري(نه موازي) موجود در آن محدود مي‌شود. براي مشاهده اين موضوع فرض کنيد الگوريتم مورد نظر براي يک پردازنده شامل S عمل سري و p عمل قابل موازي سازي است. پس داريم‌: . حال اگر از N پردازنده استفاده کنيم، خواهيم داشت: . حال با جاي‌گذاري داريم‌: . اكنون F را به عنوان فاکتوري براي نشان دادن ميزان نسبت عمليات سري به موازي به اين صورت تعريف مي‌کنيم‌: و به اين ترتيب . اگر F برابر 0 باشد (يعني نسبت هيچ عمليات سري‌اي نداشته باشيم)، و اگر F برابر 1 شود (يعني همه عمليات موازي باشد)، مي‌شود.اين قانون نشان مي‌دهد زياد کردن پردازنده‌ها در بسياري از موارد اقدام به صرفه‌اي نيست، بلکه بايد سعي شود تا الگوريتم طوري طراحي شود که نسبت عمليات سري آن کمتر و کمتر شود.

[Fahim 9563]

فرآيند طراحي

فرآيند طراحي الگوريتم هاي موازي به طور معمول به چهار مرحله تقسيم مي‌شود.

1- Partitioning: تقسيم مسئله به Task‌ يا وظايف کوچک‌تر

2- Communication‌: ساختار و الگوريتم ارتباطي بخش‌هاي مختلف با يکديگر

3- Agglomeration: ارزيابي ارتباطات و ساختارهاي تعريف شده در دو مرحله، نخست از نظر کارايي و سپس هزينه‌ها‌ي پياده سازي

4- Mapping: تخصيص وظايف به پردازنده‌ها

در ادامه سعي مي‌کنيم هر مرحله را به صورت خلاصه توضيح دهيم. شکل 3 اين مراحل را به صورت تصويري بيان مي‌کند.

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.

• ورود
• یا
• ثبت نام

شكل 3 - مراحل طراحي الگوريتم هاي موازي

يکي از قوانين اوليه در طراحي الگوريتم هاي موازي مي‌گويد‌: «‌يک الگوريتم موازي بايد طوري طراحي شده باشد که افزايش حجم مسئله به افزايش تعداد Task‌ها در آن منجر شود؛ نه افزايش حجم Task‌ها. اگر چنين قانوني در يک الگوريتم رعايت نشود، با افزايش تعداد پردازنده‌ها نمي‌توان کارايي بهتري را به دست آورد. پس بايد الگوريتم به‌طور دقيق دسته‌بندي شده و ارتباطات در آن به درستي مشخص شوند. به‌اين ترتيب، با بزرگ شدن مسئله، Task‌هاي جديدي نيز به مجموعه قبلي اضافه مي‌شوند که مي‌توانند به وسيله پردازنده‌ها‌ي جديد پردازش شوند.»

به طور کلي دو نوع تجزيه براي Partitioning وجود دارد: دامنه‌اي يا Domain Decomposition و وظيفه‌اي يا Functional Decomposition. در نوع دامنه‌اي، تجزيه بر‌اساس داده‌ها صورت مي‌گيرد. در مقابل، نوع وظيفه‌اي بر‌اساس واحد‌هاي محاسباتي تقسيم مي‌شود. به طور طبيعي در مدل دوم از محاسبات اضافه خبري نيست و منطق تقسيم بهتري را براي برنامه به همراه مي‌آورد. اما اين مدل از دو مشکل اساسي رنج مي‌برد. نخست اين‌که با تقسيم بر‌اساس محاسبات ممکن است مجبور به ذخيره‌سازي چندين باره داده‌ها شده يا ارتباطات بسيار زيادي را بين پردازنده‌ها برقرار سازيم که هر دوي اين موضوعات باعث کاهش کارايي مي‌شود. از طرف ديگر تجزيه مناسب مسئله بر‌اساس واحدهاي محاسباتي کاري دشوار و در مواردي غيرقابل انجام است. همچنين براي نسبت دادن ميزان کار برابر به هر پردازنده بايد بتوان Task‌هاي محاسباتي مختلف را از نظر حجم کار با يکديگر مقايسه كرد و اين نيز کاري بسيار مشکل است. به همين دليل، تجزيه دامنه‌اي به طور اصولي روش محبوب‌تري براي Partitioning است. ارتباطات ميان پردازنده‌ها را مي‌توان از جهات مختلف مورد بررسي قرار داد:

1- محلي(Local) در مقابل جهاني (Global)‌: در ارتباطات محلي هر Task تنها با مجموعه کوچکي از Task‌هاي ديگر ارتباط برقرار مي‌کند. در مقابل، در ارتباطات جهاني، هر Task با Task‌هاي بسيار ديگر ارتباط برقرار مي‌کند.

2- ساختاريافته (Structured)‌: يک Task و همسايه‌ها‌يش يک ساختار مشخص مانند درخت يا Grid را تشکيل مي‌دهند. در مقابل، ارتباطات ساختارنيافته مطرح مي‌شوند که شکل خاصي ندارند.

3- ايستا (Static) در مقابل پويا (Dynamic)‌: در ارتباطات ايستا ماهيت شرکاي ارتباطي در طول زمان تغيير نمي‌کند. در مقابل، در ارتباطات پويا آن‌ها به طور دائم در زمان اجرا تغيير مي‌کنند.

4- همگام (Synchronous) در مقابل ناهمگام(Asynchronous)‌: در ارتباطات همگام توليد‌کننده و مصرف‌کننده مشخص شده و تعاملي ارتباط برقرار کرده و عمليات انتقال داده را مديريت مي‌کنند. در مقابل، در مدل ناهمگام، مصرف‌کننده مي‌تواند داده‌ها را بدون مشارکت و همکاري توليد‌کننده دريافت کند.

در مرحله Agglomeration يا انباشتگي، به سراغ پياده سازي و مشخص ساختن الگوريتم براي يک پلتفرم خاص مي‌رويم. يکي از مواردي که در پياده‌سازي بايد مطرح شود بهينه ساختن ساختار براي اجرا روي ماشين مقصد است. به عنوان مثال، ممکن است الگوريتم ما Task‌هايي بسيار بيشتر از تعداد پردازنده‌ها‌ي ماشين توليد كند و در صورتي که ماشين قادر به اجراي بسيار سريع Task هاي کوچک نباشد، اين امر باعث کاهش بهره‌وري خواهد شد. در مرحله انباشتگي ما تصميمات اتخاد شده در دو مرحله نخست را مورد بازبيني دوباره قرار داده و براي بهبود اجراي آن‌ها تغييراتي را ايجاد مي‌كنيم. به عنوان مثال ممکن است چندين Task مشخص شده در مرحله Partitioning با يکديگر تلفيق شوند. به اين ترتيب، Task‌هاي کمتر با اندازه بيشتر را در اختيار خواهيم داشت. همچنين بايد مشخص كرد که در صورت لزوم، داده‌ها و محاسبات در مواقعي تکرار شوند.

در مرحله Mapping يا نگاشت، Task‌هاي مختلف به پردازنده‌ها نسبت داده مي‌شوند. متأسفانه تهيه مکانيزم نگاشت همه‌منظوره کاري بسيار مشکل و در بيشتر مواقع غيرقابل انجام است. براي همين بهتر است تا نگاشت در هنگام طراحي الگوريتم‌هاي موازي به صورت صريح مشخص شود. هدف اصلي اين مرحله کاهش زمان اجرا است و براي اين کار به دو قاعده توجه مي‌شود:

1- قراردادن Task هايي که قادر به کارکرد موازي هستند در پردازنده‌ها‌ي مختلف براي افزايش همزماني

2- قراردادن Task هايي که به ارتباطات فراوان نياز دارند روي يک پردازنده براي افزايش Locality.

به طور مشخص اين دو راهبرد در مواردي با يکديگر در تناقض قرار مي‌گيرند و در اين هنگام است که ما در شرايط انتخاب قرار مي‌گيريم از طرف ديگر، محدوديت منابع جلوي قرار دادن Task هاي زياد در يک پردازنده را مي‌گيرد. به طور کلي مسئله نگاشت به عنوان يک مسئله

NP-Complete محسوب مي‌شود و به اين ترتيب هيچ الگوريتم چند جمله‌اي با فاكتور زمان براي ارزيابي اين Trade-off‌ها در حالت کلي وجودندارد.

 

الگوريتم‌هاي موازي در عمل

مثال نخست: ضرب ماتريس‌ها

يکي از مثال‌هاي کلاسيک و ساده الگوريتم‌هاي موازي ضرب ماتريسي است. فرض کنيد دو ماتريس با نام‌هاي و در اختيار داريم و مي‌خواهيم ماتريس را که ضرب اين دو ماتريس است، محاسبه کنيم. براي به دست آوردن نحوه استفاده از روش تقسيم و حل به مثال ضرب ماتريس‌ها توجه مي‌كنيم:

 

با نگاه دقيق به اين مثال مي‌توان به اين نتيجه رسيد که هر ماتريس مي‌تواند با 8 عمل ضرب و 4 عمل جمع روي زير ماتريس‌هاي ساخته شود. به‌اين ترتيب، توانستيم مسئله ضرب را به زيرمسئله‌ها‌ي کوچک تر تقسيم كنيم. در ضمن براي راحتي کار فرض مي‌کنيم که تواني از 2 است.

الگوريتم موازي ضرب ماتريس

اين الگوريتم (فهرست1) ابتدا چهار زيرماتريس از وچهار زيرماتريس از تشکيل داده و سپس مشابه فرمول بالا آن‌ها را در يکديگر ضرب مي‌کند. به‌اين ترتيب ماتريس‌ها و به دست مي‌آيند. در نهايت نيز و با يکديگر جمع شده و نتيجه در ذخيره مي‌شود. براي بالا بردن کارايي الگوريتم مي‌توان عمل جمع را نيز به‌صورت موازي پياده سازي کرد.الگوريتم جمع موازي ماتريس(فهرست 2)

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.

• ورود
• یا
• ثبت نام

فهرست 1

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.

• ورود
• یا
• ثبت نام

فهرست 2

حال بايد به بررسي ميزان پيچيدگي الگوريتم پرداخته و آن را با الگوريتم هاي سريال موجود مقايسه کنيم. براي به دست آوردن Order الگوريتم‌هاي بازگشتي از قضيه Master استفاده مي‌کنيم(جدول1).

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.

• ورود
• یا
• ثبت نام

جدول 1

 

به‌اين ترتيب، مي‌توان تسريع الگوريتم را نيز محاسبه كرد:

 

اما اين پايان کار نيست. در طراحي الگوريتم‌هاي موازي ممکن است در مواردي تسريع را فداي حافظه كرد. به عنوان مثال، در مسئله ما ماتريس اضافه T در MULT فضاي قابل توجهي را به خود اختصاص مي‌دهد. اين موضوع به دليل وجود ساختار سلسله مراتبي براي حافظه در حالت کلي برنامه را کندتر خواهد كرد. حال مي‌توان نياز به اين ماتريس اضافه را از بين برد. هر چند که اين امر هزينه‌ها‌يي را نيز در بر خواهد داشت. براي اين‌کار کد ADD و MULT را ترکيب مي‌کنيم.

 

 

ادامه دارد

[سارا-افشار 36437]

مهم ترین مسئله تو حل مسایل به روش موازی شناسایی بخش های قابل موازی اجرا شدن هستن وخب برای هر مسئله ای باید معماری (سخت افزاری ) اونو طراحی کنیم

البته تو دنیای نرم افزار اینکار را با بکارگیری thread ها (رشته ها ) طوری که هر پردازنده یا واحد پرداش بتونه نخی رو اجرا کنه تاحدودی حل شده است

درضمن تو کامپیوترهای تک پردازنده هم میشود با استفاده از تکنیک thread ها یا agent ها مسئله ای رو به صورت موازی حل کرد

[Fahim 9563]

الگوريتم جمع و ضرب موازي ماتريس

حال به ارزيابي الگوريتم مي‌پردازيم. (فهرست3) به طور مشخص . از طرف ديگر:

در نتيجه تسريع برابر است با: . به‌اين ترتيب، مشخصاً الگوريتم موازي دوم عملکرد زماني بدتري نسبت به الگوريتم نخست دارد، اما در عوض با استفاده کمتر از حافظه مي‌تواند اين کمبود خود را جبران كرده و در مواردي حتي عملکرد بهتري از الگوريتم نخست داشته باشد.

 

مثال دوم: Merge Sort

در اين بخش يکي ديگر از مثال‌هاي مشهور روش تقسيم و حل براي الگوريتم‌هاي موازي را مورد بررسي قرار مي‌دهيم. الگوريتم مرتب سازي Merge Sort از فلسفه بسيار ساده‌اي استفاده مي‌کند: تقسيم مجموعه مورد نظر به دو بخش، مرتب سازي جداگانه هر بخش و سپس تلفيق دو مجموعه مرتب شده به صورت يک مجموعه. با توجه به ماهيت تقسيم و حل اين مسئله، موازي سازي آن کار به نسبت راحتي است. کار را با موازي سازي خود تابع Merge-Sort آغاز مي‌کنيم و تابع Merge را (که براي تلفيق دو زيرآرايه مرتب شده به کار مي‌رود) به همان صورت سنتي(خطي) باقي مي‌گذاريم(فهرست4).حال به ارزيابي الگوريتم مي‌پردازيم. توجه داشته باشيد که زمان اجراي Merge ازجنس است. پس داريم:

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.

• ورود
• یا
• ثبت نام

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.

• ورود
• یا
• ثبت نام

فهرست4

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.

• ورود
• یا
• ثبت نام

به‌اين ترتيب، ما به کارايي بهتري دست يافتيم، اما پيشرفت قابل توجهي نيست. دليل اصلي اين امر نيز الگوريتم خطي Merge است که گلوگاه کارايي ما محسوب مي‌شود. پس بهتر است اين الگوريتم را نيز به صورت موازي پياده سازي کنيم.درباره اين الگوريتم بايد چندين نکته ذکر شود. نخست ورودي اول به عنوان آرايه بزرگ‌تر و ورودي دوم آرايه کوچک‌تر محسوب مي‌شود. به همين دليل، در ابتداي کد اگر طول آرايه اول از آرايه دوم کمتر باشد، جاي اين دو آرايه عوض مي‌شود(if اول). در ضمن اگر طول آرايه نهايي يک باشد، يعني فقط يک عضو در A، (آرايه اول) وجودداشته باشد همان عضو به C منتقل مي‌شود(if دوم). حال اگر l=1 باشد (و مي‌دانيم که n=1 نيز نيست، زيرا اگر بود وارد if سوم نمي شد)، پس m نيز برابر يک است. در واقع اينجا فقط دو عنصر مورد مقايسه قرار مي‌گيرند. اگر A[1] از B[1] بزرگ‌تر باشد، ابتدا A[1] در C مي‌آيد و اگر هم نه، اين B[1] است که در C[1] قرار مي‌گيرد.

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.

• ورود
• یا
• ثبت نام

فهرست 5

در آخر نيز اگر هيچ‌کدام از اين حالات اتفاق نيفتاد، از ميانه آرايه بزرگ‌تر براي بخش بندي آرايه کوچک‌تر استفاده مي‌شود. سپس به صورت بازگشتي بخش‌هاي اول دو آرايه با هم و بخش‌هاي بزرگ‌تر آن‌ها نيز با يکديگر تلفيق مي‌شوند. با توضيح دقيق‌تر ابتدا j اي پيدا مي‌شود که B[j] و B[j+1] در دو طرف A[l/2] (ميانه A) قرار بگيرند(با استفاده از جست‌وجوي دودويي). سپس A[1…(l/2)] و B[1…j] يعني بخش‌هاي کوچک‌تر دو آرايه با يکديگر و A[(l/2+1)…l] و B[(j+1)…m] يعني بخش‌هاي بزرگ‌تر دو آرايه نيز با يکديگر تلفيق مي‌شوند. دليل اين نوع فراخواني نيز مشخص است. تمام عناصر دو بخش کوچک‌تر آرايه A و B از تمام عناصر دو بخش بزرگ‌تر آن‌ها کوچک‌تر هستند. بنابراين پس از تلفيق، اين دو بخش مي‌توانند به راحتي در کنار هم قرار گرفته و آرايه نهايي مرتب شده را تشکيل دهند. براي نشان دادن اين موضوع دقت کنيد که A[l/2] از تمام عناصر بخش کوچک‌تر A بزرگ‌تر است. همچنين A[l/2] از B[j] نيز بزرگ‌تر است پس مي‌توان نتيجه گرفت، A[l/2] از تمام عناصر تلفيق دو بخش کوچک‌تر A و B بزرگ‌تر است. از طرفي A[l/2+1] از تمام عناصر بخش بزرگتر A کوچک‌تر است. همچنين B[j+1] نيز از تمام عناصر بخش بزرگ‌تر B کوچک‌تر است. حال هر دوي آن‌ها از A[l/2] که بزرگ‌ترين تلفيق دو بخش کوچک‌تر بود، بزرگ‌ترهستند. پس مي‌توان نتيجه گرفت، تمام عناصر تلفيق دوم، از تمام عناصر تلفيق اول بزرگ‌ترهستند.(شكل3) ارزيابي كامل چنين روشي در اين مقاله نمي‌گنجد و مي‌توانيد آن را از منابع مختلف مطالعه كنيد. به هر ترتيب نتيجه کار اين است که تسريع الگوريتم کلي Merge Sort به مي‌رسد. اين عدد با استفاده از الگوريتمي بهينه‌تر حتي مي‌تواند به برسد.

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.

• ورود
• یا
• ثبت نام

شكل 4

منابع:

- دوره‌هاي آزاد MITا(MIT Open Courseware)

- الگوريتم‌هاي‌موازي (Parallel Algorithms‌)، ‌نوشته ‌گاي‌اي ‌بلوچ و بروس‌ام ماگز، دانشگا‌ه‌ كارنگي‌ملون

- طراحي الگوريتم‌هاي موازي (Designing Parallel Algorithms)، نوشته يان فاستر،Dr. Dobb’s Journal

 

پایان