محاسبات موازی

سرعت بالقوه یک الگوریتم در یک پلت فرم محاسباتی موازی توسط قانون Amdahl ارائه شده است[15]

جایی که

تأخیر سرعت بالقوه در تأخیر اجرای کل کار است.

s سرعت تأخیر اجرای بخش قابل موازی سازی وظیفه است.

p درصدی از زمان اجرای کل کار مربوط به قسمت موازی پذیر کار قبل از موازی سازی است.

از آنجایی که Slatency < 1/(1 – p)، نشان می دهد که بخش کوچکی از برنامه که نمی تواند موازی شود، سرعت کلی موجود از موازی سازی را محدود می کند. برنامه ای که یک مسئله بزرگ ریاضی یا مهندسی را حل می کند معمولاً از چندین بخش موازی پذیر و چندین بخش غیرقابل موازی سازی (سریالی) تشکیل می شود. اگر بخش غیرقابل موازی سازی یک برنامه 10 درصد از زمان اجرا را به خود اختصاص دهد (9/0=p)، بدون در نظر گرفتن تعداد پردازنده اضافه شده، نمی توانیم بیش از 10 برابر افزایش سرعت داشته باشیم. این یک حد بالایی برای سودمندی افزودن واحدهای اجرایی موازی بیشتر قرار می دهد. «وقتی به دلیل محدودیت‌های متوالی نمی‌توان یک کار را تقسیم کرد، اعمال تلاش بیشتر تأثیری در برنامه ندارد. بچه‌دار شدن نه ماه طول می‌کشد، مهم نیست که چند زن تعیین شوند».[16]

یک نمایش گرافیکی از قانون گوستافسون

قانون Amdahl فقط در مواردی اعمال می شود که اندازه مشکل ثابت شده باشد. در عمل، با در دسترس قرار گرفتن منابع محاسباتی بیشتر، آنها تمایل دارند در مسائل بزرگتر (مجموعه داده های بزرگتر) استفاده شوند و زمان صرف شده در بخش قابل موازی سازی اغلب بسیار سریعتر از کار ذاتی سریال رشد می کند.[17] در این مورد، قانون گوستافسون ارزیابی کمتر بدبینانه و واقع بینانه تری از عملکرد موازی ارائه می دهد:[18]

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

وابستگی ها

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

اجازه دهید Pi و Pj دو بخش برنامه باشند. شرایط برنشتاین[19] زمانی را توصیف می‌کند که این دو مستقل هستند و می‌توانند به صورت موازی اجرا شوند. برای Pi، بگذارید Ii همه متغیرهای ورودی و Oi متغیرهای خروجی باشد و به همین ترتیب برای Pj. Pi و Pj در صورت رضایت، مستقل هستند

نقض شرط اول یک وابستگی به جریان را ایجاد می کند که مربوط به بخش اول است که نتیجه ای را ایجاد می کند که توسط بخش دوم استفاده می شود. شرط دوم نشان دهنده یک ضد وابستگی است، زمانی که بخش دوم یک متغیر مورد نیاز بخش اول را تولید می کند. شرط سوم و نهایی نشان دهنده یک وابستگی خروجی است: وقتی دو بخش در یک مکان می نویسند، نتیجه از آخرین بخش اجرا شده منطقاً می آید.[20]

شرایط مسابقه، طرد متقابل، همگام سازی و کاهش سرعت موازی

وظایف فرعی در یک برنامه موازی اغلب رشته نامیده می شود. برخی از معماری‌های موازی کامپیوتر از نسخه‌های کوچک‌تر و سبک‌تر رشته‌ها به نام فیبر استفاده می‌کنند، در حالی که برخی دیگر از نسخه‌های بزرگ‌تر به نام فرآیندها استفاده می‌کنند. با این حال، “رشته ها” به طور کلی به عنوان یک اصطلاح عمومی برای وظایف فرعی پذیرفته شده است.[21] موضوعات اغلب نیاز به دسترسی همگام به یک شی یا منابع دیگر دارند، برای مثال زمانی که باید متغیری را که بین آنها به اشتراک گذاشته شده است به روز کنند. بدون همگام سازی، دستورالعمل های بین دو رشته ممکن است به هر ترتیبی در هم آمیخته شوند.

اگر دستور 1B بین 1A و 3A اجرا شود، یا اگر دستور 1A بین 1B و 3B اجرا شود، برنامه داده های نادرستی تولید می کند. این به عنوان شرایط مسابقه شناخته می شود. برنامه نویس باید از یک قفل برای ارائه انحراف متقابل استفاده کند. قفل یک ساختار زبان برنامه نویسی است که به یک رشته اجازه می دهد تا کنترل یک متغیر را در دست بگیرد و از خواندن یا نوشتن آن توسط رشته های دیگر جلوگیری کند، تا زمانی که آن متغیر باز شود. رشته ای که قفل را نگه می دارد برای اجرای بخش حیاتی خود (بخشی از یک برنامه که نیاز به دسترسی انحصاری به برخی متغیرها دارد) و باز کردن قفل داده ها پس از اتمام آزاد است.

یک رشته با موفقیت متغیر V را قفل می کند، در حالی که رشته دیگر قفل می شود – تا زمانی که قفل V دوباره باز نشود ادامه پیدا نمی کند. این امر اجرای صحیح برنامه را تضمین می کند. قفل ها ممکن است برای اطمینان از اجرای صحیح برنامه زمانی که رشته ها باید دسترسی به منابع را سریالی کنند، ضروری باشد، اما استفاده از آنها می تواند تا حد زیادی یک برنامه را کند کند و ممکن است بر قابلیت اطمینان آن تأثیر بگذارد.[22]

قفل کردن چندین متغیر با استفاده از قفل های غیر اتمی امکان بن بست برنامه را معرفی می کند. یک قفل اتمی چندین متغیر را به طور همزمان قفل می کند. اگر نتواند همه آنها را قفل کند، هیچ کدام را قفل نمی کند. اگر دو thread هر کدام نیاز به قفل کردن همان دو متغیر با استفاده از قفل های غیر اتمی داشته باشند، ممکن است یک رشته یکی از آنها را قفل کند و رشته دوم متغیر دوم را قفل کند. در چنین حالتی، هیچ یک از رشته ها نمی توانند کامل شوند و بن بست نتیجه می گیرد.[23]

بسیاری از برنامه های موازی نیاز دارند که وظایف فرعی آنها همزمان عمل کنند. این مستلزم استفاده از یک مانع است. موانع معمولاً با استفاده از قفل یا سمافور اجرا می‌شوند.[24] یک دسته از الگوریتم ها که به نام الگوریتم های بدون قفل و بدون انتظار شناخته می شوند، به طور کلی از استفاده از قفل ها و موانع جلوگیری می کنند. با این حال، اجرای این رویکرد به طور کلی دشوار است و به ساختارهای داده ای به درستی طراحی شده نیاز دارد.[25]

همه موازی سازی ها منجر به افزایش سرعت نمی شود. به طور کلی، از آنجایی که یک کار به رشته‌های بیشتر و بیشتری تقسیم می‌شود، آن رشته‌ها بخش فزاینده‌ای از زمان خود را صرف برقراری ارتباط با یکدیگر یا انتظار یکدیگر برای دسترسی به منابع می‌کنند.[26][27] هنگامی که سربار ناشی از اختلاف منابع یا ارتباطات بر زمان صرف شده برای محاسبات دیگر غالب شود، موازی سازی بیشتر (یعنی تقسیم حجم کار بر روی رشته های بیشتر) به جای کاهش مدت زمان مورد نیاز برای اتمام، افزایش می یابد. این مشکل که به عنوان کاهش سرعت موازی شناخته می شود، [28] می تواند در برخی موارد با تجزیه و تحلیل نرم افزار و طراحی مجدد بهبود یابد.[29]

موازی سازی ریزدانه، درشت دانه و شرم آور

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

طبقه بندی فلین

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

طبقه بندی فلین

جریان داده واحد

SISDMISD

جریان های داده های متعدد

SIMDMIMD

زیرمجموعه های SIMD[30]

پردازش آرایه (SIMT) پردازش خطی (SIMD بسته بندی شده) پردازش انجمنی (SIMD پیش فرض/ماسک شده)

همچنین ببینید

SPMDMPMD

طبقه بندی تک دستورالعمل-تک داده (SISD) معادل یک برنامه کاملاً متوالی است. طبقه بندی تک دستور العمل-چند داده (SIMD) مشابه انجام عملیات مشابه به طور مکرر بر روی یک مجموعه داده بزرگ است. این معمولا در برنامه های پردازش سیگنال انجام می شود. چند دستور العمل تک داده (MISD) یک طبقه بندی به ندرت استفاده می شود. در حالی که معماری‌های کامپیوتری برای مقابله با این ابداع شد (مانند آرایه‌های سیستولیک)، تعداد کمی از برنامه‌های کاربردی که متناسب با این کلاس بودند، تحقق یافت. برنامه های چند دستور العمل چندگانه (MIMD) تا حد زیادی رایج ترین نوع برنامه های موازی هستند.

به گفته دیوید ا. شاید به دلیل قابل درک بودن آن – پرکاربردترین طرح.»[31]

← اجاره ابر رایانه   →

اینجا کلیک کنید