نها هدفی که موازی سازی الگوریتم ها دنبال میکنه بالا بردن سرعت هست . هدف ما اینه که یک الگوریتم رو که قبلا به صورت سریال انجام میشده حالا روی چند پردازنده تقسیم اش کنیم و با سرعت بیشتری اون رو انجام بدیم .

نکته ای که این وسط به ذهنم میرسه بگم اینه که بعضی ها Thread ها رو همون موازی نویسی در نظر میگیرن . اما این غلط هست . بعضی ها فکر میکنن که Thread ها به صورت موازی اجرا میشن . جالبه بدونید که اصلا Thread ها زمانی مطرح شدن که هنوز دستگاه های چند پردازنده فراگیر نشده بود . اصلا و ابدا اینطوری نیست که Thread ها همزمان اجرا بشن . فرض کنید شما یک CPU دارید . آیا CPU شما میتونه در آن واحد دو تا پردازش انجام بده ؟! خیر . شاید بشه گفت شما با Thread این شانس رو میدین که اجرا شما موازی به نظر بیاد. مثلا یک بازی رو در نظر بگیرید . من قرار هست که هواپیمایی رو تکون بدم و شلیک کنم. حالا من از Thread استفاده نمیکنم و معمولی برنامه نویسی میکنم . اگر من دستم رو روی شلیک نگه دارم هواپیما از جاش تکون نمیخوره چون CPU در حال پردازش شلیک هست . ولی اگر به صورت Thread بنویسم این شانس رو به هواپیما میدم که حرکت کنه .

الگوریتم های موازی بر روی چند پردازنده اجرا میشن . حالا از معماری های مختلف برای اجرا دستور العمل ها که بگذریم الگوریتم های موازی معمولا روی معماری SIMD مطرح میشن . یعنی یک دستور رو چند داده

خوب حالا این سوال پیش میاد که آیا هر الگوریتمی رو به صورت موازی در بیاریم به درد میخوره ؟‌ خیر

معیار هایی وجود داره برای اینکه ببینیم اگر یک الگوریتم رو به صورت موازی در بیاریم با صرفه هست یا نه .

اولین معیار سرعت هست . اینکه چه مقدار موازی سازی باعث افزایش سرعت شده بسیار اهمیت داره . این معیار رو بهش SpeedUp میگن . Speedup در واقع نسبت سرعت اجرا الگوریتم در حالت سریال به حالت موازی هست . یعنی مثلا اگر یک الگوریتم در حالت سریال با پیچیدگی زمانی ( O ( NLOGN اجرا بشه و در حالت موازی با پیچیدگی ( O ( LogN افزایش سرعت ما N خواهد بود .

اما آیا SpeedUp معیاری کاملی است ؟ مثلا اگر برای رسیدن به این مقدار ما N پردازنده استفاده کرده باشیم آیا موازیسازی کار عاقلانه ایست ؟؟

برای اینکه معیار کاملتری داشته باشیم باید هزینه ها را نیز در نظر بگیریم . برای محاسبه هزینه تعداد پردازنده های استفاده شده را در زمان محاسبه ضرب میکنیم . مثلا الگوریتمی در حالت موازی از ( O ( N اجرا میشود و M پردازنده نیز استفاده کرده . پس هزینه ما N * M خواهد بود .

حال به جایی میرسیم که باید در نظر بگیریم آیا موازی سازی به نفع ما بوده یا نه . برای این کار روش باید Cost Optimal باشد . یعنی از نظر هزینه به صرفه باشد یعنی هزینه اجرای الگوریتم در حالت موازی از هزینه آن در حالت سریال پایین تر باشد .

حدس میزنید هزینه در حالت سریال چگونه محاسبه میشود ؟‌ پیچیدگی زمانی الگوریتم * ۱ چون یک CPU بیشتر نداریم

پس علاوه بر اینکه الگوریتم ما باید سرعت بیشتری داشته باشد باید هزینه کمتری نیز داشته باشد .
حال به نحوه نوشتن الگوریتم های موازی می پردازیم معمولا نحوه نمایش الگوریتم موازی به صورت Pseudocode به صورت زیر است .

ّFor ( i = 1 To N ) Do In Parallel
{
Pi :
Some Action
}

یا به صورت

ّFor ( i in S ) Do in Parallel
{
Pi:
Some Action
}

فرق حالت اول و دوم در این است که شما در حالت اول پردازنده مشخصی را برای اجرای الگوریتم خود انتخاب میکنید و بر اساس شماره های تعیین شده عملیات مورد نظر را انجام میدهند . اما در حالت دوم از بین مجموعه ای از پردازنده ها شما تعدادی را انتخاب میکنید که عملیات مورد نظر شما را انجام دهند .

حال به یک نمونه موازی سازی میپردازیم .

فرض کنید N پردازنده داریم و هر پردازنده n داده در اختیار دارد . میخواهیم ببینیم آیا داده X در بین کل داده موجود در پردازنده ها وجود دارد یا خیر ؟

ّFor ( i = To N ) Do In Parallel
Pi : For ( J = 0 To n )
If A[j] = X Return True

حال به نظر شما این الگوریتم برای پیدا کردن عدد X در بین N*n عدد بهینه است ؟؟