tomboy
یک شنبه 20 فروردین 1391, 20:02 عصر
درآمدي بــر الگوريتم‌هاي مـــوازي (قسمت اول)
آشنايي با نحوه طراحي و پياده‌سازي الگوريتم‌هاي موازي
ماهنامه شبکه - مهر 1389 شماره 115
http://www.shabakeh-mag.com/Data/Articles/Items/2011/9/1005453.jpg
كيومرث سلطاني
استفان هاوکينگ، فيزيکدان مشهور، در مقدمه کتاب «تاريخچه زمان» درباره به کارگيري فرمول‌هاي رياضي در يک کتاب مي‌گويد: «... و در اين رهگذر گفته مي‌شد که هر معادله رياضي‌اي که در اين کتاب گنجانده شود، ميزان فروش را به نصف کاهش خواهد داد.» و اين دقيقاً همان تذكري بود كه از سوي پرهام‌ايزدپناه به من يادآوري شد! با اين حال، نوشتن از الگوريتم‌هاي موازي بدون اشاره هر چند مختصر به آناليز الگوريتم‌ها امکان‌پذير نيست. در نتيجه، اين مقاله از تکنيک‌هاي آناليز الگوريتم‌ها بهره برده است. با اين حال سعي شده تا کليت مطلب را به صورت معرفي نگه داشته و بي‌دليل به عمق بعضي مطالب وارد نشويم. پس از بيان مدل‌سازي اوليه، مراحل طراحي يک الگوريتم موازي را بيان‌کرده و سپس چهار مثال عملي درباره الگوريتم‌هاي موازي ارائه كنيم. البته، مثال‌هاي جالب و قابل بررسي در اين زمينه فراوان است و هر کدام مي‌توانند تکنيک جديدي را در زمينه طراحي الگوريتم‌هاي موازي به ما آموزش دهند. در اين مقاله چهار مثال بسيار مشهور و کلاسيک و در عين حال ساده را معرفي کرده‌ايم كه مي‌توانند نقطه شروع بسيار خوبي براي آشنايي با نحوه طراحي و پياده‌سازي الگوريتم هاي موازي محسوب شوند.اين مطلب يكي از مقالات بخش ويژه نشريه ماهنامه شبكه در شماره 115 با عنوان محاسبات موازي (http://www.shabakeh-mag.com/Item.aspx?id=1000058) مي‌باشد. جهت دريافت اين بخش ويژه به بخش پرونده‌هاي ويژه سايت مراجعه نمائيد.
Cilk
کدهاي نوشته شده در اين بخش با استفاده از Cilk نوشته شده‌اند. کيلک نسخه‌اي از زبان C است که در محيط پردازش موازي مورد استفاده قرار مي‌گيرد. سينتکس اين زبان مشابه زبان C بوده که از چندين دستور اضافه مانند Spawn و Sync نيز سود مي‌برد.
Spawn: اين دستور بيان مي‌کند، فراخواني رويه‌اي که پس از کلمه کليدي Spawn مي‌آيد مي‌تواند به صورت موازي با بقيه کد اجرا شود. البته Scheduler ، اجباري براي اجراي رويه به صورت موازي ندارد، بلکه اين دستور تنها به Scheduler مي‌گويد که مي‌تواند اين کار را انجام دهد.
Sync: اين دستور اجراي رويه فعلي را تا زماني که کار اجراي رويه‌هاي قبلي‌اي که به وسيله spawn فراخواني شده بودند تمام شود، متوقف مي‌سازد. به‌اين ترتيب، زماني که تمام رويه‌هاي موازي در حال اجرا کارشان به پايان رسيده و به فريم والد خود بازگشتند، اجراي رويه فعلي از سر گرفته مي‌شود.در ادامه مقاله مثال‌هاي گوناگوني از نحوه به کارگيري کيلک براي نوشتن برنامه‌هاي موازي ارائه مي‌شود.
مدل سازي اوليه
براي معرفي برخي از مفاهيم اوليه مورد نياز در بررسي الگوريتم‌هاي موازي به مثال مشهور فيبوناچي مراجعه مي‌کنيم.
محاسبه عدد nام سري فيبوناچي
fib(n)
if n < 2
then return n
x <- spawn fib(n-1)
y <- spawn fib(n-2)
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 دست يافت.
http://www.shabakeh-mag.com/data/gallery/2011/9/parallelalgurithms1_s.jpg (http://www.shabakeh-mag.com/Data/Gallery/2011/9/parallelAlgurithms1.jpg)
شكل 1- جريان دستورات براي Fib(4). هر دايره نشان دهنده يک Thread است. هر فلش کامل نشان دهنده توالي دستور بعدي است. هر فلش خط چين نشان دهنده يک عمل Spawn و هر فلش نقطه چين نشان دهنده يک Return از رويه Spawn شده است.
براي اثبات اين نتيجه بايد از برهان خلف استفاده کنيم. فرض کنيد که Tp<T1/P باشد. در بهترين حالت P پردازنده مي‌تواند حداکثر P کار را در يک مرحله انجام دهد. با ضرب کردن دو طرف نامساوي در P خواهيم داشت: که بيان مي‌کند تعداد کل عمليات(طرف چپ نامساوي) کمتر از است و اين تناقض مي‌باشد. پس حکم اثبات مي‌شود.
در ادامه با كمي توجه بيشتر به کران پايين مي‌توان به نتيجه جالبي رسيد. با مفروضات مطرح شده در بالا، با استفاده از 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 برابر کرد؟
http://www.shabakeh-mag.com/data/gallery/2011/9/parallelalgurithms2_s.jpg
شكل 2- تسريع الگوريتم با اضافه کردن پردازنده
جواب اين سؤال مثبت است. با اين‌که تسريع فراخطي در موارد بسيار نادري اتفاق مي‌افتد، اما به هر صورت کاملاً امکان پذير است. براي اين امر مي‌توان به دلايل بسياري اشاره كرد که بارز ترين آن مسئله اضافه‌شدن حافظه Cache است. با زياد شدن تعداد پردازنده‌ها حافظه Cache در دسترس نيز افزايش پيدا مي‌کند. به اين ترتيب، در حالي که ممکن است مسئله اوليه در Cache يک پردازنده جا نشود، زيرمسئله‌ها مي‌توانند در Cache پردازندههاي مربوط به خود جاي گرفته و به اين ترتيب استفاده سريع‌تري را از حافظه به ارمغان بياورند. تسريع فراخطي هنگام اجراي الگوريتمي به روش عقب‌گرد(Backtracking) نيز مي‌تواند رخ دهد. زيرا ممکن است يک Thread شاخه‌اي از درخت Thread ديگر را هرس کرده و به اين ترتيب ميزان عمليات مورد انجام کمتر شود. در مسئله‌ها‌ي جست‌وجو نيز در موارد خاصي جست‌وجوي موازي مي‌تواند نتيجه‌اي بسيار سريع‌تر از جست‌وجوي خطي داشته باشد. به خصوص اگر فضاي جست‌وجو توزيع خاصي داشته باشد. تسريع تعريف شده در بالا تنها معيار قابل توجه براي ارزيابي يک الگوريتم موازي نيست. به عنوان مثال، مي‌توان زمان را ثابت فرض کرد و تعداد عملياتي را که الگوريتم موازي انجام داده با تعداد عمليات الگوريتم سري مقايسه كرد. در اين مورد نيز مي‌توان به يك کارايي فراخطي دست يافت. اين موضوع زماني حاصل مي‌شود که با Scale کردن مسئله بتوانيم زمان بيشتري را روي روتين سريع‌تر صرف کنيم. براي اين بخش فقط به يک مثال از دنياي واقعي بسنده مي‌کنيم. فرض کنيد مي‌خواهيم پيانويي را از خانه حرکت داده و داخل کاميون بگذاريم. کار انجام شده نيز برابر با ميزان مسافت طي شده است. زمان ثابت در‌نظر‌گرفته شده نيز سي دقيقه است. حال اگر يک نفر را مسئول تکان دادن پيانو کنيم، شايد بيش از چند متر نتواند آن را تکان دهد و اين در حالي است که در تمام اين مدت کاميون بي‌استفاده مانده است. حال اگر دو نفر را براي کار بگماريم آن‌ها مي‌توانند در ده دقيقه پيانو را داخل کاميون گذاشته و سپس کاميون مي‌تواند بيست دقيقه حرکت کرده و پيانو را جابه جا کند. به اين ترتيب منابع ما دو برابر شده اما ميزان کار انجام شده تا صدها برابر زياد مي‌شود.
در پايان اين قسمت بايد به قانون Amdahl اشاره‌اي بكنيم. اين قانون ادعا مي‌کند که تسريع يک الگوريتم موازي در عمل به وسيله نسبت عمليات سري(نه موازي) موجود در آن محدود مي‌شود. براي مشاهده اين موضوع فرض کنيد الگوريتم مورد نظر براي يک پردازنده شامل S عمل سري و p عمل قابل موازي سازي است. پس داريم: . حال اگر از N پردازنده استفاده کنيم، خواهيم داشت: . حال با جاي‌گذاري داريم: . اكنون F را به عنوان فاکتوري براي نشان دادن ميزان نسبت عمليات سري به موازي به اين صورت تعريف مي‌کنيم: و به اين ترتيب . اگر F برابر 0 باشد (يعني نسبت هيچ عمليات سري‌اي نداشته باشيم)، و اگر F برابر 1 شود (يعني همه عمليات موازي باشد)، مي‌شود.اين قانون نشان مي‌دهد زياد کردن پردازنده‌ها در بسياري از موارد اقدام به صرفه‌اي نيست، بلکه بايد سعي شود تا الگوريتم طوري طراحي شود که نسبت عمليات سري آن کمتر و کمتر شود.
آشنايي با نحوه طراحي و پياده‌سازي الگوريتم‌هاي موازي
ماهنامه شبکه - مهر 1389 شماره 115
http://www.shabakeh-mag.com/Data/Articles/Items/2011/9/1005453.jpg
كيومرث سلطاني
استفان هاوکينگ، فيزيکدان مشهور، در مقدمه کتاب «تاريخچه زمان» درباره به کارگيري فرمول‌هاي رياضي در يک کتاب مي‌گويد: «... و در اين رهگذر گفته مي‌شد که هر معادله رياضي‌اي که در اين کتاب گنجانده شود، ميزان فروش را به نصف کاهش خواهد داد.» و اين دقيقاً همان تذكري بود كه از سوي پرهام‌ايزدپناه به من يادآوري شد! با اين حال، نوشتن از الگوريتم‌هاي موازي بدون اشاره هر چند مختصر به آناليز الگوريتم‌ها امکان‌پذير نيست. در نتيجه، اين مقاله از تکنيک‌هاي آناليز الگوريتم‌ها بهره برده است. با اين حال سعي شده تا کليت مطلب را به صورت معرفي نگه داشته و بي‌دليل به عمق بعضي مطالب وارد نشويم. پس از بيان مدل‌سازي اوليه، مراحل طراحي يک الگوريتم موازي را بيان‌کرده و سپس چهار مثال عملي درباره الگوريتم‌هاي موازي ارائه كنيم. البته، مثال‌هاي جالب و قابل بررسي در اين زمينه فراوان است و هر کدام مي‌توانند تکنيک جديدي را در زمينه طراحي الگوريتم‌هاي موازي به ما آموزش دهند. در اين مقاله چهار مثال بسيار مشهور و کلاسيک و در عين حال ساده را معرفي کرده‌ايم كه مي‌توانند نقطه شروع بسيار خوبي براي آشنايي با نحوه طراحي و پياده‌سازي الگوريتم هاي موازي محسوب شوند.اين مطلب يكي از مقالات بخش ويژه نشريه ماهنامه شبكه در شماره 115 با عنوان محاسبات موازي (http://www.shabakeh-mag.com/Item.aspx?id=1000058) مي‌باشد. جهت دريافت اين بخش ويژه به بخش پرونده‌هاي ويژه سايت مراجعه نمائيد.
Cilk
کدهاي نوشته شده در اين بخش با استفاده از Cilk نوشته شده‌اند. کيلک نسخه‌اي از زبان C است که در محيط پردازش موازي مورد استفاده قرار مي‌گيرد. سينتکس اين زبان مشابه زبان C بوده که از چندين دستور اضافه مانند Spawn و Sync نيز سود مي‌برد.
Spawn: اين دستور بيان مي‌کند، فراخواني رويه‌اي که پس از کلمه کليدي Spawn مي‌آيد مي‌تواند به صورت موازي با بقيه کد اجرا شود. البته Scheduler ، اجباري براي اجراي رويه به صورت موازي ندارد، بلکه اين دستور تنها به Scheduler مي‌گويد که مي‌تواند اين کار را انجام دهد.
Sync: اين دستور اجراي رويه فعلي را تا زماني که کار اجراي رويه‌هاي قبلي‌اي که به وسيله spawn فراخواني شده بودند تمام شود، متوقف مي‌سازد. به‌اين ترتيب، زماني که تمام رويه‌هاي موازي در حال اجرا کارشان به پايان رسيده و به فريم والد خود بازگشتند، اجراي رويه فعلي از سر گرفته مي‌شود.در ادامه مقاله مثال‌هاي گوناگوني از نحوه به کارگيري کيلک براي نوشتن برنامه‌هاي موازي ارائه مي‌شود.
مدل سازي اوليه
براي معرفي برخي از مفاهيم اوليه مورد نياز در بررسي الگوريتم‌هاي موازي به مثال مشهور فيبوناچي مراجعه مي‌کنيم.
محاسبه عدد nام سري فيبوناچي
fib(n)
if n < 2
then return n
x <- spawn fib(n-1)
y <- spawn fib(n-2)
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 دست يافت.
http://www.shabakeh-mag.com/data/gallery/2011/9/parallelalgurithms1_s.jpg (http://www.shabakeh-mag.com/Data/Gallery/2011/9/parallelAlgurithms1.jpg)
شكل 1- جريان دستورات براي Fib(4). هر دايره نشان دهنده يک Thread است. هر فلش کامل نشان دهنده توالي دستور بعدي است. هر فلش خط چين نشان دهنده يک عمل Spawn و هر فلش نقطه چين نشان دهنده يک Return از رويه Spawn شده است.
براي اثبات اين نتيجه بايد از برهان خلف استفاده کنيم. فرض کنيد که Tp<T1/P باشد. در بهترين حالت P پردازنده مي‌تواند حداکثر P کار را در يک مرحله انجام دهد. با ضرب کردن دو طرف نامساوي در P خواهيم داشت: که بيان مي‌کند تعداد کل عمليات(طرف چپ نامساوي) کمتر از است و اين تناقض مي‌باشد. پس حکم اثبات مي‌شود.
در ادامه با كمي توجه بيشتر به کران پايين مي‌توان به نتيجه جالبي رسيد. با مفروضات مطرح شده در بالا، با استفاده از 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 برابر کرد؟
http://www.shabakeh-mag.com/data/gallery/2011/9/parallelalgurithms2_s.jpg
شكل 2- تسريع الگوريتم با اضافه کردن پردازنده
جواب اين سؤال مثبت است. با اين‌که تسريع فراخطي در موارد بسيار نادري اتفاق مي‌افتد، اما به هر صورت کاملاً امکان پذير است. براي اين امر مي‌توان به دلايل بسياري اشاره كرد که بارز ترين آن مسئله اضافه‌شدن حافظه Cache است. با زياد شدن تعداد پردازنده‌ها حافظه Cache در دسترس نيز افزايش پيدا مي‌کند. به اين ترتيب، در حالي که ممکن است مسئله اوليه در Cache يک پردازنده جا نشود، زيرمسئله‌ها مي‌توانند در Cache پردازندههاي مربوط به خود جاي گرفته و به اين ترتيب استفاده سريع‌تري را از حافظه به ارمغان بياورند. تسريع فراخطي هنگام اجراي الگوريتمي به روش عقب‌گرد(Backtracking) نيز مي‌تواند رخ دهد. زيرا ممکن است يک Thread شاخه‌اي از درخت Thread ديگر را هرس کرده و به اين ترتيب ميزان عمليات مورد انجام کمتر شود. در مسئله‌ها‌ي جست‌وجو نيز در موارد خاصي جست‌وجوي موازي مي‌تواند نتيجه‌اي بسيار سريع‌تر از جست‌وجوي خطي داشته باشد. به خصوص اگر فضاي جست‌وجو توزيع خاصي داشته باشد. تسريع تعريف شده در بالا تنها معيار قابل توجه براي ارزيابي يک الگوريتم موازي نيست. به عنوان مثال، مي‌توان زمان را ثابت فرض کرد و تعداد عملياتي را که الگوريتم موازي انجام داده با تعداد عمليات الگوريتم سري مقايسه كرد. در اين مورد نيز مي‌توان به يك کارايي فراخطي دست يافت. اين موضوع زماني حاصل مي‌شود که با Scale کردن مسئله بتوانيم زمان بيشتري را روي روتين سريع‌تر صرف کنيم. براي اين بخش فقط به يک مثال از دنياي واقعي بسنده مي‌کنيم. فرض کنيد مي‌خواهيم پيانويي را از خانه حرکت داده و داخل کاميون بگذاريم. کار انجام شده نيز برابر با ميزان مسافت طي شده است. زمان ثابت در‌نظر‌گرفته شده نيز سي دقيقه است. حال اگر يک نفر را مسئول تکان دادن پيانو کنيم، شايد بيش از چند متر نتواند آن را تکان دهد و اين در حالي است که در تمام اين مدت کاميون بي‌استفاده مانده است. حال اگر دو نفر را براي کار بگماريم آن‌ها مي‌توانند در ده دقيقه پيانو را داخل کاميون گذاشته و سپس کاميون مي‌تواند بيست دقيقه حرکت کرده و پيانو را جابه جا کند. به اين ترتيب منابع ما دو برابر شده اما ميزان کار انجام شده تا صدها برابر زياد مي‌شود.
در پايان اين قسمت بايد به قانون Amdahl اشاره‌اي بكنيم. اين قانون ادعا مي‌کند که تسريع يک الگوريتم موازي در عمل به وسيله نسبت عمليات سري(نه موازي) موجود در آن محدود مي‌شود. براي مشاهده اين موضوع فرض کنيد الگوريتم مورد نظر براي يک پردازنده شامل S عمل سري و p عمل قابل موازي سازي است. پس داريم: . حال اگر از N پردازنده استفاده کنيم، خواهيم داشت: . حال با جاي‌گذاري داريم: . اكنون F را به عنوان فاکتوري براي نشان دادن ميزان نسبت عمليات سري به موازي به اين صورت تعريف مي‌کنيم: و به اين ترتيب . اگر F برابر 0 باشد (يعني نسبت هيچ عمليات سري‌اي نداشته باشيم)، و اگر F برابر 1 شود (يعني همه عمليات موازي باشد)، مي‌شود.اين قانون نشان مي‌دهد زياد کردن پردازنده‌ها در بسياري از موارد اقدام به صرفه‌اي نيست، بلکه بايد سعي شود تا الگوريتم طوري طراحي شود که نسبت عمليات سري آن کمتر و کمتر شود.