Computer Software Engineering

الگوریتم موازی

الگوریتم‌های موازی در علوم کامپیوتر، برخلاف الگوریتم‌های متوالی سنتی، الگوریتم‌هایی هستند که در آنها، هر بار قسمتی از برنامه روی پردازنده‌ای متفاوت اجرا می‌شود و در آخر برای کسب نتیجهٔ مطلوب، نتایج کنار هم قرار می‌گیرند.

بعضی از الگوریتم‌ها را می‌توان به آسانی به چنین قسمت‌هایی تقسیم کرد. بطور مثال، عمل بررسی اعداد از یک تا صدهزار برای تشخیص اعداد اول را، می‌توان با اختصاص دادن زیر مجموعه‌ای از اعداد به هر پردازنده موجود و سپس گردآوری لیست نتایج مطلوب، قسمت بندی کرد.

برخی از الگوریتم‌ها برای اجرای مراحل بعد، نیاز به نتایج مراحل قبل دارند. اینگونه مسائل را مسائل ذاتا متوالی می‌گویند. روش‌های عددی تکرار شونده، مانند روش نیوتون یا مسالهٔ سه تن، نمونه‌هایی از الگوریتم‌های متوالی هستند.

برخی از مسائل را خیلی دشوار می‌توان به صورت موازی در آورد حتی اگر بازگشتی باشند. یکی از این نمونه‌ها جستحوی عمقی درخت است.

الگوریتم‌های موازی ارزشمندند زیرا اجرای عملیات محاسباتی بزرگ از طریق الگوریتم‌های موازی، به دلیل کارکرد پردازنده‌های مدرن، بسیار سریع تر از اجرای آنها با الگوریتم‌های متوالی است. ساخت یک کامپیوتر با یک پردازندهٔ خیلی سریع بسیار سخت تر از ساختن یک کامپیوتر با تعداد زیادی پردازندهٔ کندتر با توان عملیاتی یکسان است.

با این حال، برای سرعت الگوریتم‌های موازی نیز محدودیت‌های خاص نظری وجود دارد. قسمتی از هر الگوریتم موازی، متوالی است، از این رو هر الگوریتم موازی یک نقطهٔ اشباع دارد. بعد از آن نقطهٔ اشباع اضافه کردن تعداد بیشتری پردازنده افزایش توان عملیاتی را در پی ندارد و تنها باعث بالا بردن هزینه و خسارات می‌شود.

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

الگوریتم‌های موازی باید از جهت ارتباط بین پردازنده‌های مختلف نیز بهینه شوند. الگوریتم‌های موازی از دو راه با پردازنده‌ها ارتباط برقرار می‌کنند، حافظهٔ مشترک، و رد و بدل کردن پیام.

پردازش حافظهٔ مشترک نیاز به قفل بندی اضافه برای اطلاعات دارد، از این رو هزینهٔ سیکل‌های گذرگاه و پردازنده‌های اضافی را تحمیل می‌کند و همچنین باعث غیر موازی شدن قسمت‌هایی از الگوریتم می‌شود.

پردازش از طریق انتقال پیام، از کانال‌ها و جعبه‌های پیام استفاده می‌کند اما این نوع ارتباط باعث افزایش هزینهٔ انتقال روی گذرگاه، حافظهٔ اضافی برای صف و جعبه‌های پیام و تاخیر در پیام‌ها می‌شود.

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

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

زیر مجموعه‌ای از الگوریتم‌های موازی، الگوریتم‌های توزیعی هستند که برای استفاده در محیط‌های محاسبات خوشه‌ای و محاسبات توزیعی طراحی شده‌اند، که در این حیطه باید ملاحظاتی افزون بر الگوریتم‌های موازی «سنتی»، اعمال شود.

طراحی الگوریتم های موازی

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

مشکلات موجود در طراحی الگوریتم های موازی

·         بازده

·         تناسب

·         جزء بندی محاسبات

o        تجزیهٔ

o        تکنیک های تجزیهٔ تابعی

·         موقعیت

·         ارتباطات همگام و غیر همگام

·         انباشتگی

طراحی های علمی

این روش طراحی را در چهار مرحله انجام می‌دهد.

·         جزء بندی

·         ارتباطات

·         انباشتگی

·         نقشه بندی

در دو مرحلهٔ اول، تمرکز ما روی تناسب و همزمانی است. در دو مرحلهٔ دیگر نیز تمرکز روی موقعیت، و دیگر مسائل مربوط به کارایی است.

جزء بندی

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

ارتباطات

ارتباطات لازم برای هماهنگ کردن اجرای امور مشخص می‌شوند. الگوریتم ها و ساختارهای مناسب ارتباطی نیز تعیین می‌گردند.

انباشتگی

امور و ساختار های ارتباطی تعریف شده در دو مرحلهٔ اول یک طرح با توجه به معیار های زیر ارزیابی می‌شوند.

·         نیاز های اجرایی

·         هزینه‌های پیاده سازی

در صورت لزوم ، کارها با هم ادغام می‌شوند برای:

·         بهبود بخشیدن به کارآیی

·         کاهش هزینه‌های توسعه

نقشه بندی

برای هر پردازنده یک کار تعریف شده است تا اهداف:

·         افزایش بهره برداری از پردازنده ها

·         کاهش هزینه‌های ارتباطی

را محقق سازد.

نقشه برداری را می‌توان بصورت ثابت یا در زمان اجرا توسط الگوریتم های توازن بارگذاری انجام داد.