DOPIPE - ویکی‌پدیا، دانشنامهٔ آزاد

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

پیشینه[ویرایش]

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

انواع مختلفی از تکنیک‌های موازی‌سازی وجود دارد که بر اساس میزان هزینه‌های اضافی حاصل از ذخیره داده‌ها، میزان موازی سازی و وابستگی داده ها استفاده می‌شود . برخی از تکنیک‌های شناخته شده عبارتند از: DOALLDOACROSS و DOPIPE .

DOALL: وقتی می‌توانیم هر تکرار از حلقه را بدون هیچ گونه تعاملی بین تکرار‌ها، موازی کنیم از این تکنیک استفاده می‌کنیم. بنابراین، زمان کلی مورد نیاز برای اجرا از N * T (برای یک فرِآیند سری، که در آن T زمان اجرای هر تکرار است) به T کاهش می‌یابد (زیرا تمامی N تکرار به صورت موازی اجرا می‌شوند).

DOACROSS: هرگاه احتمال وابستگی داده‌‌ها وجود داشته باشد از این تکنیک استفاده می‌شود. بنابراین، کار‌ها را به نحوی موازی می‌کنیم که کار‌هایی با داده‌های مستقل به صورت موازی اجرا شوند، اما کار‌هایی که داده‌های وابسته دارند به صورت متوالی اجرا شوند. در پردازنده‌های موازی برای همزمانی کار‌های وابسته، درجه‌ای از همزمان‌سازی استفاده می‌شود.

شرح[ویرایش]

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

مثال[ویرایش]

برنامه زیر شبه کد مربوط به موازی‌سازی DOPIPE را نشان می‌دهد.

در این کد، در حلقه‌ای که با j از 1 تا N تکرار می‌شود سه کار (F1، F0 و F2) وجود دارند. در زیر فهرست وابستگی‌های موجود در کد را مشاهده می‌کنید:

F1[j] → ^T F1[j+1]، نشان می‌دهد که دستورالعمل F1 در تکرار j+1 باید پس از دستورالعمل F1 در تکرار j اجرا شود. به این حالت وابستگی حقیقی نیز گفته می‌شود.

F1[j] → ^T F2[j]، نشان می‌دهد که دستورالعمل F2 در تکرار j باید پس از دستورالعمل F1 در تکرار j اجرا شود.

}for (j=1; j<=N; j++)      ;F0: o[j] = x[j] - a[j]     ;F1: z[j] = z[j-1] * 5     ;F2: y[j] = z[j] * w[j] { 

اگر این کد به صورت متوالی اجرا شود، آنگاه کل زمان مصرف شده برابر با N * (T _F0 + T _F1 + T _F2 ) خواهد بود، که T _F1 ، T _F0 و T _F2 به ترتیب نشان‌دهنده زمان اجرای توابع F1، F0 و F2 در هر تکرار هستند. حال اگر این حلقه را با ایجاد خط لوله در دستورالعمل‌های درون حلقه به روش زیر موازی‌سازی کنیم:

}for (j=1; j<=N; j++)     موازی سازی F0: o[j] = x[j] - a[j];             // DOALL  {  }for (j=1; j<=N; j++)    موازی سازی  F1: z[j] = z[j-1] * 5;              // DOPIPE    نتیجه F1 ارسال شده و برای استفاده در دسترس است   ;post(j)                              {  }for (j=1; j<=N; j++)       منتظر می ماند تا F1 کامل شود و مقدار z[j] را تولید می کند تا توسط F2 استفاده شود //   ;wait(j)        ;F2: y[j] = z[j] * w[j] { 

از آنجایی که F0 یک تابع مستقل است، یعنی هیچ وابستگی درون-حلقه‌ای ندارد (بدون وابستگی به تکرارهای j+1 یا j-1 )، هیچ نوع وابستگی هم به سایر دستورالعمل‌های درون حلقه ندارد.بنابراین، می‌توانیم این تابع را کاملا جدا کنیم و با استفاده از موازی‌سازی DOALL آن را به صورت موازی اجرا کنیم. از طرف دیگر، دستورالعمل‌های F1 و F2 وابسته هستند (در بالا توضیح داده شد)، بنابراین آنها را به دو حلقه مختلف جدا می‌کنیم و با خط لوله ایجاد شده اجرا می‌کنیم. برای ایجاد همزمانی بین حلقه‌های F1 و F2 از post (j) و wait (j) استفاده می‌کنیم.

با شروع از اولین تکرار j ، دستورالعمل F1 در زمان T _F1 اجرا می‌شود. در همین حین، F2 اجرا نمی‌شود زیرا منتظر است تا مقدار z[j] توسط F1 تولید شود. وقتی اجرای F1 برای تکرار j کامل شد، با استفاده از post(j) این مقدار را پست می‌کند. پس از انتظار برای اجرای F1، با استفاده ازF2 ، wait(j) اجرای خود را آغاز می کند زیرا مقدار z[j] را برای استفاده در دسترس دارد. همچنین، از آنجایی که اجرای F1 با F2 محدود نمی‌شود، F1 همزمان تکرار j+1 را اجرا می‌کند. تصویر زیر جدول زمانی اجرای تمامی دستوالعمل‌ها را نشان می‌دهد.

از روی تصویر می‌بینیم که کل زمان لازم برای اجرای F0 برابر با T_F0 است ، زیرا تمامی تکرارهای F0 به صورت موازی اجرا می‌شوند. در حالیکه برای F1 و F2، کل زمان اجرا برابر است با مقدار N * T _F1 + T _F2 (اگر زمان مربوط به همزمان‌سازی را ناچیز در نظر بگیریم).

این مقدار به میزان قابل توجهی کمتر از زمان به دست آمده در هنگام اجرای متوالی است.

در مقایسه با سایر مدل ها[ویرایش]

موازی‌سازی DOALL عمدتاً بر اساس اصل << تقسیم کن و موفق شو >> کار می‌کند. در اینجا همه کارها با تکرارهای متفاوتی اجرا می‌شوند که از مجموعه داده‌های منحصربفردی استفاده می‌کنند. بنابراین مشکل این پیاده‌سازی این است که وقتی حجم زیادی از داده‌ها با هم محاسبه می‌شوند، فضای کش بزرگی برای کار کردن با رشته‌های مختلف مورد نیاز است. از آنجایی که در این رشته‌ها هیچ نوع وابستگی وجود ندارد، هیچ انرژی اضافه‌ای برای ارتباط بین رشته‌ای هزینه نمی‌شود.

در حالی که در DOPIPE، انرژی اضافه‌ای برای همزمان‌سازی بین رشته‌ها مورد نیاز است. اما به دلیل ساختار خط لوله ایجاد شده در آن، به فضای کش کمتری نیاز دارد زیرا داده‌های تولید شده بلافاصله توسط مصرف کننده مصرف می‌شود.

و نیز مراجعه کنید به[ویرایش]

• رایانش موازی
• موازی سازس سطح حلقه
• موازی کاری
• وابستگی داده
• OpenMP
• موازی سازی خودکار
• ریسمان (رایانش)
• حافظه نهان (رایانش)

منابع[ویرایش]