الگوریتم موازی
الگوریتم‌های موازی در علوم کامپیوتر، برخلاف الگوریتم‌های متوالی سنتی، الگوریتم‌هایی هستند که در آنها، هر بار قسمتی از برنامه روی پردازنده‌ای متفاوت اجرا می‌شود و در آخر برای کسب نتیجهٔ مطلوب، نتایج کنار هم قرار می‌گیرند.
بعضی از الگوریتم‌ها را می‌توان به آسانی به چنین قسمت‌هایی تقسیم کرد. به‌طور مثال، عمل بررسی اعداد از یک تا صدهزار برای تشخیص اعداد اول را، می‌توان با اختصاص دادن زیر مجموعه‌ای از اعداد به هر پردازنده موجود و سپس گردآوری فهرست نتایج مطلوب، قسمت بندی کرد.
برخی از الگوریتم‌ها برای اجرای مراحل بعد، نیاز به نتایج مراحل قبل دارند. این‌گونه مسائل را مسائل ذاتاً متوالی می‌گویند. روش‌های عددی تکرار شونده، مانند روش نیوتون یا مسئلهٔ سه تن، نمونه‌هایی از الگوریتم‌های متوالی هستند.
برخی از مسائل را خیلی دشوار می‌توان به صورت موازی درآورد حتی اگر بازگشتی باشند. یکی از این نمونه‌ها جستحوی عمقی درخت است.
الگوریتم‌های موازی ارزشمندند زیرا اجرای عملیات محاسباتی بزرگ از طریق الگوریتم‌های موازی، به دلیل کارکرد پردازنده‌های مدرن، بسیار سریع تر از اجرای آنها با الگوریتم‌های متوالی است. ساخت یک کامپیوتر با یک پردازندهٔ خیلی سریع بسیار سخت‌تر از ساختن یک کامپیوتر با تعداد زیادی پردازندهٔ کندتر با توان عملیاتی یکسان است.
با این حال، برای سرعت الگوریتم‌های موازی نیز محدودیت‌های خاص نظری وجود دارد. قسمتی از هر الگوریتم موازی، متوالی است، از این رو هر الگوریتم موازی یک نقطهٔ اشباع دارد. بعد از آن نقطهٔ اشباع اضافه کردن تعداد بیشتری پردازنده افزایش توان عملیاتی را در پی ندارد و تنها باعث بالا بردن هزینه و خسارات می‌شود.
هزینه و پیچیدگی الگوریتم‌های موازی بر اساس حافظه و زمانی (تعداد سیکل‌های پردازنده) که مصرف می‌کنند تخمین زده می‌شود.
الگوریتم‌های موازی باید از جهت ارتباط بین پردازنده‌های مختلف نیز بهینه شوند. الگوریتم‌های موازی از دو راه با پردازنده‌ها ارتباط برقرار می‌کنند، حافظهٔ مشترک، و رد و بدل کردن پیام.
پردازش حافظهٔ مشترک نیاز به قفل بندی اضافه برای اطلاعات دارد، از این رو هزینهٔ سیکل‌های گذرگاه و پردازنده‌های اضافی را تحمیل می‌کند و همچنین باعث غیر موازی شدن قسمت‌هایی از الگوریتم می‌شود.
پردازش از طریق انتقال پیام، از کانال‌ها و جعبه‌های پیام استفاده می‌کند اما این نوع ارتباط باعث افزایش هزینهٔ انتقال روی گذرگاه، حافظهٔ اضافی برای صف و جعبه‌های پیام و تأخیر در پیام‌ها می‌شود.
در طراحی‌های چند پردازنده‌ای از گذرگاه‌های خاصی استفاده می‌شود تا بدین گونه از هزینه‌های تعاملات کاسته شود اما این پردازنده‌است که حجم ترافیک را تعیین می‌کند.
مشکل دیگر الگوریتم‌های موازی تضمین توازن درخور آنها است. برای مثال، بررسی تمام اعداد از یک تا صدهزار برای یافتن اعداد اول را می‌توان به راحتی بین پردازنده‌ها تقسیم کرد. اما در این روش ممکن است بعضی از پردازنده‌ها مجبور شوند بیشتر از بعضی دیگر کار کنند، در این صورت پردازنده‌هایی که کارشان به پایان رسیده‌است تا پایان کار دیگر پردازنده‌ها بی‌کار می‌مانند.
زیر مجموعه‌ای از الگوریتم‌های موازی، الگوریتم‌های توزیعی هستند که برای استفاده در محیط‌های محاسبات خوشه‌ای و محاسبات توزیعی طراحی شده‌اند، که در این حیطه باید ملاحظاتی افزون بر الگوریتم‌های موازی «سنتی»، اعمال شود.
طراحی الگوریتم‌های موازی
[ویرایش]طراحی الگوریتم‌ها به راحتی و به دستورهای مشخص محدود نمی‌شود. هدف ارائهٔ چهارچوبی است که طی آن طراحی الگوریتم‌های موازی امکان‌پذیر شود. در این فرایند سعی بر ایجاد درکی شهودی است از آنچه که یک الگوریتم موازی خوب را تشکیل می‌دهد.
کاملاً همینه
مشکلات موجود در طراحی الگوریتم‌های موازی
[ویرایش]- بازده
- تناسب
- جزء بندی محاسبات
- تجزیهٔ
- تکنیک‌های تجزیهٔ تابعی
- موقعیت
- ارتباطات همگام و غیر همگام
- انباشتگی
طراحی‌های علمی
[ویرایش]این روش طراحی را در چهار مرحله انجام می‌دهد.
- جزء بندی
- ارتباطات
- انباشتگی
- نقشه بندی
در دو مرحلهٔ اول، تمرکز ما روی تناسب و همزمانی است. در دو مرحلهٔ دیگر نیز تمرکز روی موقعیت، و دیگر مسائل مربوط به کارایی است.
جزء بندی
[ویرایش]کارهای مربوط به محاسبات و داده‌هایی که روی آنها پردازش انجام می‌گیرد را به بخش‌های کوچک تقسیم کنید. مشکلات عملی مانند تعداد پردازنده‌ها در کامپیوتر مرکز در محاسبات نمی‌آید.
ارتباطات
[ویرایش]ارتباطات لازم برای هماهنگ کردن اجرای امور مشخص می‌شوند. الگوریتم‌ها و ساختارهای مناسب ارتباطی نیز تعیین می‌گردند.
انباشتگی
[ویرایش]امور و ساختارهای ارتباطی تعریف شده در دو مرحلهٔ اول یک طرح با توجه به معیارهای زیر ارزیابی می‌شوند.
- نیازهای اجرایی
- هزینه‌های پیاده‌سازی
در صورت لزوم، کارها با هم ادغام می‌شوند برای:
- بهبود بخشیدن به کارایی
- کاهش هزینه‌های توسعه
نگاشت (تطابق - mapping) - جزءجزء کردن کارها و تخصیص کارها به پردازنده‌ها)
برای هر پردازنده یک سری کار تعریف می‌شود و در این نگاشت موارد زیر رعایت می‌شود:
- افزایش بهره‌برداری پردازنده‌ها -طوری‌که کارها به صورت متوازن بر روی آنها تقسیم شود
- کاهش هزینه‌های ارتباطی بین پردازنده‌ها
نگاشت را می‌توان به صورت ثابت یا در زمان اجرا توسط الگوریتم‌های توازن بارگذاری انجام داد.
پیوندها
[ویرایش]- multiple-agent system (MAS)، شبکه عصبی
- رایانش موازی
- English wikipedia
پیوند به بیرون
[ویرایش]- Parallel Algorithm Design
- Designing and Building Parallel Programs page at the US Argonne National Laboratories
- cauchy.math.colostate.edu/... /Oct2/oct2.htm