موضوع مقاله: الگوریتم موازی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم موازی | مقدمه: الگوریتم‌های موازی در علوم کامپیوتر، برخلاف الگوریتم‌های متوالی سنتی، الگوریتم‌هایی هستند که در آنها، هر بار قسمتی از برنامه روی پردازنده‌ای متفاوت اجرا می‌شود و در آخر برای کسب نتیجهٔ مطلوب، نتایج کنار هم قرار می‌گیرند. | ## بخش 1: الگوریتم موازی | به‌طور مثال، عمل بررسی اعداد از یک تا صدهزار برای تشخیص اعداد اول را، می‌توان با اختصاص دادن زیر مجموعه‌ای از اعداد به هر پردازنده موجود و سپس گردآوری فهرست نتایج مطلوب، قسمت بندی کرد. روش‌های عددی تکرار شونده، مانند روش نیوتون یا مسئلهٔ سه تن، نمونه‌هایی از الگوریتم‌های متوالی هستند. الگوریتم‌های موازی ارزشمندند زیرا اجرای عملیات محاسباتی بزرگ از طریق الگوریتم‌های موازی، به دلیل کارکرد پردازنده‌های مدرن، بسیار سریع تر از اجرای آن‌ها با الگوریتم‌های متوالی است. ساخت یک کامپیوتر با یک پردازندهٔ خیلی سریع بسیار سخت‌تر از ساختن یک کامپیوتر با تعداد زیادی پردازندهٔ کندتر با توان عملیاتی یکسان است. قسمتی از هر الگوریتم موازی، متوالی است، از این رو هر الگوریتم موازی یک نقطهٔ اشباع دارد. بعد از آن نقطهٔ اشباع اضافه کردن تعداد بیشتری پردازنده افزایش توان عملیاتی را در پی ندارد و تنها باعث بالا بردن هزینه و خسارات می‌شود. هزینه و پیچیدگی الگوریتم‌های موازی بر اساس حافظه و زمانی (تعداد سیکل‌های پردازنده) که مصرف می‌کنند تخمین زده می‌شود. | ## بخش 2: الگوریتم موازی | الگوریتم‌های موازی از دو راه با پردازنده‌ها ارتباط برقرار می‌کنند، حافظهٔ مشترک، و رد و بدل کردن پیام. پردازش حافظهٔ مشترک نیاز به قفل بندی اضافه برای اطلاعات دارد، از این رو هزینهٔ سیکل‌های گذرگاه و پردازنده‌های اضافی را تحمیل می‌کند و همچنین باعث غیر موازی شدن قسمت‌هایی از الگوریتم می‌شود. پردازش از طریق انتقال پیام، از کانال‌ها و جعبه‌های پیام استفاده می‌کند اما این نوع ارتباط باعث افزایش هزینهٔ انتقال روی گذرگاه، حافظهٔ اضافی برای صف و جعبه‌های پیام و تأخیر در پیام‌ها می‌شود. در طراحی‌های چند پردازنده‌ای از گذرگاه‌های خاصی استفاده می‌شود تا بدین گونه از هزینه‌های تعاملات کاسته شود اما این پردازنده‌است که حجم ترافیک را تعیین می‌کند. برای مثال، بررسی تمام اعداد از یک تا صدهزار برای یافتن اعداد اول را می‌توان به راحتی بین پردازنده‌ها تقسیم کرد. اما در این روش ممکن است بعضی از پردازنده‌ها مجبور شوند بیشتر از بعضی دیگر کار کنند، در این صورت پردازنده‌هایی که کارشان به پایان رسیده‌است تا پایان کار دیگر پردازنده‌ها بی‌کار می‌مانند. زیر مجموعه‌ای از الگوریتم‌های موازی، الگوریتم‌های توزیعی هستند که برای استفاده در محیط‌های محاسبات خوشه‌ای و محاسبات توزیعی طراحی شده‌اند، که در این حیطه باید ملاحظاتی افزون بر الگوریتم‌های موازی «سنتی»، اعمال شود. | ## بخش 3: الگوریتم موازی | طراحی الگوریتم‌های موازی طراحی الگوریتم‌ها به راحتی و به دستورهای مشخص محدود نمی‌شود. در این فرایند سعی بر ایجاد درکی شهودی است از آنچه که یک الگوریتم موازی خوب را تشکیل می‌دهد. کاملاً همینه مشکلات موجود در طراحی الگوریتم‌های موازی بازده تناسب جزء بندی محاسبات تجزیهٔ تکنیک‌های تجزیهٔ تابعی موقعیت ارتباطات همگام و غیر همگام انباشتگی طراحی‌های علمی این روش طراحی را در چهار مرحله انجام می‌دهد. جزء بندی ارتباطات انباشتگی نقشه بندی در دو مرحلهٔ اول، تمرکز ما روی تناسب و همزمانی است. جزء بندی کارهای مربوط به محاسبات و داده‌هایی که روی آن‌ها پردازش انجام می‌گیرد را به بخش‌های کوچک تقسیم کنید. انباشتگی امور و ساختارهای ارتباطی تعریف شده در دو مرحلهٔ اول یک طرح با توجه به معیارهای زیر ارزیابی می‌شوند. | ## جمع‌بندی | نیازهای اجرایی هزینه‌های پیاده‌سازی در صورت لزوم، کارها با هم ادغام می‌شوند برای: بهبود بخشیدن به کارایی کاهش هزینه‌های توسعه نگاشت (تطابق - mapping) - جزءجزء کردن کارها و تخصیص کارها به پردازنده‌ها) برای هر پردازنده یک سری کار تعریف می‌شود و در این نگاشت موارد زیر رعایت می‌شود: افزایش بهره‌برداری پردازنده‌ها -طوری‌که کارها به صورت متوازن بر روی آن‌ها تقسیم شود کاهش هزینه‌های ارتباطی بین پردازنده‌ها نگاشت را می‌توان به صورت ثابت یا در زمان اجرا توسط الگوریتم‌های توازن بارگذاری انجام داد.