محاسبات موازی
محاسبات موازی نوعی محاسبات است که در آن بسیاری از محاسبات یا فرآیندها به طور همزمان انجام می شود. [۱] مشکلات بزرگ را اغلب می توان به مسائل کوچکتر تقسیم کرد، که در همان زمان می توان آنها را حل کرد. چندین شکل مختلف از محاسبات موازی وجود دارد: سطح بیت، سطح دستورالعمل ، داده و موازی کاری . موازی‌سازی مدت‌هاست که در محاسبات با کارایی بالا استفاده می‌شود ، اما به دلیل محدودیت‌های فیزیکی که از مقیاس‌بندی فرکانس جلوگیری می‌کند، مورد توجه گسترده‌تری قرار گرفته است. [۲]از آنجایی که مصرف انرژی (و در نتیجه تولید گرما) توسط رایانه ها در سال های اخیر به یک نگرانی تبدیل شده است، [۳] محاسبات موازی به الگوی غالب در معماری کامپیوتر ، عمدتاً به شکل پردازنده های چند هسته ای تبدیل شده است. [۴]
محاسبات موازی ارتباط نزدیکی با محاسبات همزمان دارد – آنها اغلب با هم استفاده می‌شوند، و اغلب با هم ترکیب می‌شوند، اگرچه این دو متمایز هستند: می‌توان موازی‌سازی را بدون همزمانی و همزمانی را بدون موازی‌سازی (مانند چندوظیفه با اشتراک‌گذاری زمانی در یک واحد) داشت. پردازنده مرکزی). [۵] [۶] در محاسبات موازی، یک کار محاسباتی معمولاً به چند کار فرعی، اغلب بسیار، بسیار مشابه تقسیم می‌شود که می‌توانند به طور مستقل پردازش شوند و نتایج آنها پس از تکمیل، ترکیب می‌شوند. در مقابل، در محاسبات همزمان، فرآیندهای مختلف اغلب به وظایف مرتبط نمی پردازند. همانطور که در محاسبات توزیع شده معمول است، وظایف جداگانه ممکن است ماهیت متنوعی داشته باشند و اغلب در طول اجرا نیاز به ارتباطات بین فرآیندی دارند.
رایانه‌های موازی را می‌توان تقریباً بر اساس سطحی که سخت‌افزار از موازی‌سازی پشتیبانی می‌کند طبقه‌بندی کرد، رایانه‌های چند هسته‌ای و چند پردازنده‌ای دارای عناصر پردازشی متعدد در یک دستگاه واحد هستند، در حالی که خوشه‌ها ، MPP ها و شبکه‌ها از چندین رایانه برای کار بر روی یک دستگاه استفاده می‌کنند. وظیفه. معماری‌های موازی تخصصی کامپیوتر گاهی در کنار پردازنده‌های سنتی برای تسریع وظایف خاص مورد استفاده قرار می‌گیرند.
در برخی موارد موازی‌سازی برای برنامه‌نویس شفاف است، مانند موازی‌سازی سطح بیت یا سطح دستورالعمل، اما الگوریتم‌های موازی صریحا ، به‌ویژه آنهایی که از همزمانی استفاده می‌کنند، نوشتن دشوارتر از الگوریتم‌های متوالی است، [۷] زیرا همزمانی چندین الگوریتم جدید معرفی می‌کند. کلاس هایی از اشکالات نرم افزاری بالقوه ، که شرایط مسابقه رایج ترین آنهاست. ارتباط و همگام سازی بین وظایف فرعی مختلف معمولاً برخی از بزرگترین موانع برای دستیابی به عملکرد بهینه برنامه موازی است.
یک حد بالای نظری در مورد افزایش سرعت یک برنامه در نتیجه موازی سازی توسط قانون امدال ارائه شده است .
پس زمینه
به طور سنتی، نرم افزار کامپیوتری برای محاسبات سریال نوشته شده است . برای حل یک مسئله، یک الگوریتم به عنوان یک جریان سریالی از دستورالعمل ها ساخته و پیاده سازی می شود. این دستورالعمل ها بر روی یک واحد پردازش مرکزی در یک کامپیوتر اجرا می شوند. فقط یک دستور ممکن است در یک زمان اجرا شود – پس از اتمام آن دستورالعمل، دستور بعدی اجرا می شود. [۸]
از سوی دیگر، محاسبات موازی، از چندین عنصر پردازشی به طور همزمان برای حل یک مشکل استفاده می کند. این امر با تقسیم مسئله به بخش‌های مستقل انجام می‌شود تا هر عنصر پردازش بتواند بخشی از الگوریتم خود را به طور همزمان با سایرین اجرا کند. عناصر پردازشی می توانند متنوع باشند و شامل منابعی مانند یک کامپیوتر منفرد با چندین پردازنده، چندین کامپیوتر تحت شبکه، سخت افزار تخصصی یا هر ترکیبی از موارد فوق می باشند. [۸] محاسبات موازی تاریخی برای محاسبات علمی و شبیه‌سازی مسائل علمی، به‌ویژه در علوم طبیعی و مهندسی ، مانند هواشناسی ، استفاده می‌شد . این امر منجر به طراحی سخت افزار و نرم افزار موازی و همچنینمحاسبات با کارایی بالا [۹]
مقیاس فرکانس دلیل اصلی بهبود عملکرد کامپیوتر از اواسط دهه ۱۹۸۰ تا سال ۲۰۰۴ بود. زمان اجرا یک برنامه برابر است با تعداد دستورالعمل ضرب در میانگین زمان هر دستورالعمل. ثابت نگه داشتن سایر موارد، افزایش فرکانس ساعت، میانگین زمان لازم برای اجرای یک دستورالعمل را کاهش می دهد. بنابراین افزایش فرکانس زمان اجرا را برای همه برنامه های محاسباتی کاهش می دهد. [۱۰] با این حال، توان مصرفی P توسط یک تراشه با معادله P = C × V ۲ × F ارائه می شود ، که در آن C ظرفیت خازنی است.سوئیچ شدن در هر سیکل ساعت (متناسب با تعداد ترانزیستورهایی که ورودی آنها تغییر می کند)، V ولتاژ است و F فرکانس پردازنده (سیکل در ثانیه) است. [۱۱] افزایش فرکانس باعث افزایش توان مصرفی در یک پردازنده می شود. افزایش مصرف انرژی پردازنده در نهایت منجر به لغو پردازنده های Tejas و Jayhawk توسط اینتل در ۸ می ۲۰۰۴ شد ، که عموماً به عنوان پایان مقیاس فرکانس به عنوان الگوی معماری غالب رایانه ذکر می شود. [۱۲]
برای مقابله با مشکل مصرف برق و گرمای بیش از حد واحد پردازش مرکزی اصلی (CPU یا پردازنده) تولیدکنندگان شروع به تولید پردازنده های کم مصرف با چندین هسته کردند. هسته واحد محاسباتی پردازنده است و در پردازنده‌های چند هسته‌ای هر هسته مستقل است و می‌تواند به طور همزمان به حافظه مشابهی دسترسی داشته باشد. پردازنده های چند هسته ای محاسبات موازی را به رایانه های رومیزی آورده اند . بنابراین موازی سازی برنامه های سریال به یک وظیفه اصلی برنامه نویسی تبدیل شده است. در سال ۲۰۱۲، پردازنده‌های چهار هسته‌ای برای رایانه‌های رومیزی استاندارد شدند ، در حالی که سرورها دارای پردازنده‌های ۱۰ و ۱۲ هسته‌ای هستند. از قانون مورمی توان پیش بینی کرد که تعداد هسته های هر پردازنده هر ۱۸ تا ۲۴ ماه دو برابر می شود. این می تواند به این معنی باشد که بعد از سال ۲۰۲۰ یک پردازنده معمولی ده ها یا صدها هسته خواهد داشت. [۱۳]
یک سیستم عامل می تواند اطمینان حاصل کند که وظایف مختلف و برنامه های کاربر به صورت موازی بر روی هسته های موجود اجرا می شوند. با این حال، برای اینکه یک برنامه نرم‌افزار سریال از معماری چند هسته‌ای استفاده کامل کند، برنامه‌نویس باید کد را بازسازی و موازی‌سازی کند. افزایش سرعت اجرای نرم افزار کاربردی دیگر از طریق مقیاس فرکانس حاصل نمی شود، در عوض برنامه نویسان باید کد نرم افزار خود را موازی کنند تا از قدرت محاسباتی فزاینده معماری های چند هسته ای استفاده کنند. [۱۴]
قانون امدال و قانون گوستافسون
نمایش گرافیکی قانون امدال . سرعت یک برنامه از موازی سازی به مقداری از برنامه که می تواند موازی شود محدود می شود. به عنوان مثال، اگر بتوان ۹۰% برنامه را موازی کرد، حداکثر سرعت تئوری با استفاده از محاسبات موازی ۱۰ برابر خواهد بود بدون توجه به اینکه چند پردازنده استفاده می شود.
فرض کنید یک کار دارای دو بخش مستقل A و B است. بخش B تقریباً ۲۵٪ از زمان کل محاسبات را می گیرد. با کار بسیار سخت، ممکن است شخص بتواند این قسمت را ۵ برابر سریعتر بسازد، اما این تنها زمان کل محاسبات را اندکی کاهش می دهد. در مقابل، ممکن است نیاز باشد که کار کمتری انجام شود تا قسمت A دو برابر سریعتر باشد. این محاسبات را بسیار سریعتر از بهینه‌سازی بخش B می‌کند ، حتی اگر سرعت بخش B با نسبت بیشتر باشد (۵ برابر در مقابل ۲ برابر).
در حالت بهینه، افزایش سرعت حاصل از موازی سازی خطی خواهد بود – دوبرابر کردن تعداد عناصر پردازش باید زمان اجرا را به نصف کاهش دهد و دوبرابر کردن آن برای بار دوم باید دوباره زمان اجرا را به نصف کاهش دهد. با این حال، تعداد بسیار کمی از الگوریتم های موازی به سرعت بهینه دست می یابند. اکثر آنها برای تعداد کمی از عناصر پردازشی دارای یک سرعت تقریباً خطی هستند که برای تعداد زیادی از عناصر پردازشی به یک مقدار ثابت تبدیل می شود.
سرعت بالقوه یک الگوریتم در یک پلت فرم محاسباتی موازی توسط قانون آمدال ارائه شده است [۱۵]
- {\displaystyle S_{\text{latency}}(s)={\frac {1}{1-p+{\frac {p}{s}}}},}
جایی که
- تأخیر S سرعت بالقوه در تأخیر اجرای کل کار است.
- s سرعت تأخیر اجرای بخش قابل موازی سازی وظیفه است.
- p درصدی از زمان اجرای کل کار مربوط به بخش موازی پذیر کار قبل از موازی سازی است.
از آنجایی که تأخیر S < 1/(1 - p ) است، نشان می دهد که بخش کوچکی از برنامه که نمی تواند موازی شود، سرعت کلی موجود از موازی سازی را محدود می کند. برنامه ای که یک مسئله بزرگ ریاضی یا مهندسی را حل می کند معمولاً از چندین بخش موازی پذیر و چندین بخش غیرقابل موازی سازی (سریالی) تشکیل می شود. اگر بخش غیرقابل موازی سازی یک برنامه ۱۰ درصد از زمان اجرا را تشکیل می دهد ( ص= ۰٫۹)، ما نمی توانیم بیش از ۱۰ برابر افزایش سرعت داشته باشیم، صرف نظر از اینکه چند پردازنده اضافه شده است. این یک حد بالایی برای سودمندی افزودن واحدهای اجرایی موازی بیشتر قرار می دهد. “وقتی نمی توان یک کار را به دلیل محدودیت های متوالی تقسیم کرد، اعمال تلاش بیشتر تأثیری بر برنامه زمانی ندارد. بچه دار شدن نه ماه طول می کشد، مهم نیست که چند زن تعیین شوند.” [۱۶]
یک نمایش گرافیکی از قانون گوستافسون
قانون Amdahl فقط در مواردی اعمال می شود که اندازه مشکل ثابت شده باشد. در عمل، با در دسترس قرار گرفتن منابع محاسباتی بیشتر، آنها تمایل به استفاده از مسائل بزرگتر (مجموعه داده های بزرگتر) دارند، و زمان صرف شده در بخش قابل موازی سازی اغلب بسیار سریعتر از کار ذاتی سریال رشد می کند. [۱۷] در این مورد، قانون گوستافسون ارزیابی کمتر بدبینانه و واقع بینانه تری از عملکرد موازی ارائه می دهد: [۱۸]
- {\displaystyle S_{\text{latency}}(s)=1-p+sp.}
هم قانون Amdahl و هم قانون Gustafson فرض می کنند که زمان اجرای قسمت سریال برنامه مستقل از تعداد پردازنده ها است. قانون آمدال فرض می کند که کل مشکل اندازه ثابتی دارد به طوری که کل مقدار کاری که باید به صورت موازی انجام شود نیز مستقل از تعداد پردازنده ها است، در حالی که قانون گوستافسون فرض می کند که مقدار کل کاری که باید به صورت موازی انجام شود به صورت خطی با تعداد پردازنده ها
وابستگی ها
درک وابستگی داده ها در پیاده سازی الگوریتم های موازی اساسی است . هیچ برنامه ای نمی تواند سریعتر از طولانی ترین زنجیره محاسبات وابسته (معروف به مسیر بحرانی ) اجرا شود، زیرا محاسباتی که به محاسبات قبلی در زنجیره بستگی دارند باید به ترتیب اج%D
