موازی‌سازی خودکار: تفاوت میان نسخه‌ها

محتوای حذف‌شده محتوای افزوده‌شده

درخط

نسخهٔ ‏۱۱ دسامبر ۲۰۲۰، ساعت ۱۹:۰۲

موازی سازی خودکار، موازی خودکار، یا autoparallelization به تبدیل یک رشته کد متوالی کد به چند رشته ای و / یا بردار مستقل از هم، کد به منظور حل در پردازنده های هسته ای به طور همزمان در یک حافظه مشترک چند پردازشی هستند( SMP دستگاه). موازی سازی کاملاً خودکار برنامه های ترتیبی چالش برانگیز است زیرا به تجزیه و تحلیل برنامه پیچیده ای نیاز دارد و از آنجا که بهترین روش به مقادیر پارامتر ها بستگی دارد که در زمان کامپایل مشخص نیستند.

برنامه نویسی ساختارهای کنترل که بیشترین تمرکز خودکار آنها بر روی حلقه ها هستند ، زیرا به طور کلی ، بیشتر زمان اجرای برنامه در داخل نوعی از حلقه سپری می شود. دو روش اصلی برای موازی سازی حلقه ها وجود دارد: رایانش چند ریسمانی و حلقوی چند ریسمانی. ^[۱] به عنوان مثال ، یک حلقه را در نظر بگیرید که در هر تکرار صد عملیات انجام می دهد ، و برای هزاربار اجرا می شود. این را می توان به عنوان شبکه ای از 100 ستون در 1000 ردیف ، در مجموع 100000 عملیات در نظر گرفت. حلقوی چند ریسمانی نسبت می دهد هر ردیف را به یک ریسمان اختصاص می دهد. رایانش چند ریسمانی هر ستون را به یک موضوع ریسمان اختصاص می دهد. که این ریسمان ها به صورت موازی اجرا می شوند.

تکنیک موازی سازی خودکار

تجزیه‌کننده

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

تجزیه

از تجزیه گر برای شناسایی بخشهایی از کد استفاده می شود که می توانند همزمان اجرا شوند. آنالیز کننده از اطلاعات داده های استاتیک ارائه شده توسط تجزیه کننده استفاده می کند. تجزیه گر ابتدا تمام توابع کاملاً مستقل را پیدا کرده و آنها را به عنوان وظایف جداگانه علامت گذاری می کند. سپس تجزیه گر می یابد که کدام وظایف وابسته به دیگری هستند.

برنامه ریزی

برنامه ریز کلیه وظایف و وابستگی آنها به یکدیگر از نظر زمان اجرا و شروع را لیست می کند. برنامه ریز زمان بهینه را با توجه به تعداد پردازنده های مورد استفاده، کل زمان اجرای برنامه و... پیدا می کند.

تولید کد

برنامه ریز لیستی از تمام وظایف و جزئیات هسته ها همراه با زمان و قسمتی که باید روی آنها اجرا شود را تولید می کند. تولید کننده کد، سازه های خاصی را در کد وارد می کند که در هنگام اجرا توسط برنامه ریز خوانده می شود. این سازه ها به برنامه ریز دستور می دهند که یک کار خاص همراه با زمان شروع و پایان بر روی کدام هسته انجام شود.

حلقوی چند ریسمانی

یک کامپایلر با موازی سازی حلقوی چند ریسمانی سعی می کند یک حلقه را تقسیم کند تا هر تکرار بتواند همزمان بر روی یک پردازنده جداگانه اجرا شود.

تجزیه و تحلیل موازی سازی کامپایلر

کامپایلر برای تعیین موارد زیر معمولاً قبل از موازی سازی ، دو بار تجزیه و تحلیل انجام می دهد:

آیا حلقه موازی سازی ایمن است؟ پاسخ به این سوال از این لحاظ ضروری است که به تحلیل دقیق وابستگی تجزیه و تحلیل مستعار نیاز دارد
آیا ارزش آن را دارد که موازی شود؟ این پاسخ نیاز به تخمینی (مدل سازی) قابل اعتماد از میزان بار برنامه و ظرفیت سیستم موازی دارد.

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

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

مثال

یک حلقه DOALL نامیده می شود اگر تمام تکرارهای آن ، در هر فراخوانی مشخص ، بتواند همزمان اجرا شود. کد Fortran زیر DOALL است ، و توسط یک کامپایلر می تواند بصورت خودکار موازی شود زیرا هر تکرار مستقل از موارد دیگر است ، و نتیجه نهایی آرایه z صرف نظر از ترتیب اجرای سایر تکرارها صحیح خواهد بود.

  do i = 1, n
   z(i) = x(i) + y(i)
  enddo

بسیاری از مسائل وجود دارند که دارای چنین حلقه های DOALL است. به عنوان مثال ، هنگام رندرینگ یک فیلم ، هر فریم از فیلم می تواند به طور مستقل پردازش شود و هر پیکسل از یک فریم ممکن است به طور مستقل رندر شود. از طرف دیگر ، کد زیر نمی تواند به صورت خودکار موازی شود ، زیرا مقدار (z(i به نتیجه تکرار قبلی ، (z(i - 1 بستگی دارد.

  do i = 2, n
   z(i) = z(i - 1)*2
  enddo

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

  do i = 2, n
   z(i) = z(1)*2**(i - 1)
  enddo

با این حال ، کامپایلرهای موازی ساز معمولاً قادر به تشخیس خودکار این موازی سازی ها نیستند و اینکه آیا این کد در وهله اول از موازی سازی سود می برد جای سوال است.

رایانش چند ریسمانی

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

بسیاری از کد ها وجود دارند که با این روش قابل تقسیم به بلوک های کد نسبتاً مستقل هستند ، به ویژه سیستم هایی که از خط لوله ها و فیلترها استفاده می کند وجود دارند. به عنوان مثال ، هنگام تولید برنامه تلویزیونی پخش زنده ، کارهای زیر باید چندین بار در ثانیه انجام شوند:

یک فریم داده پیکسل خام را از سنسور تصویری بخواند.
انجام MPEG روی سطر داده های خام انجام داده شود.
آنتروپی بردارهای حرکت و سایر داده ها فشرده شود.
داده های فشرده شده را به بسته تقسیم کند.
تصحیح خطای مناسب را انجام دهد و FFT را به بسته های داده از سیگنال های COFDM تبدیل کند.
سیگنال های COFDM را از آنتن تلویزیون بفرستد.

یک کامپایلر موازی ساز به روش رایانش چند ریسمانی می تواند هر یک از این 6 عملیات را به یک پردازنده اختصاص دهد، که احتمالا در یک آرایه سیستولیک و کد مناسب را برای انتقال خروجی یک پردازنده به پردازنده بعدی درج کند.

امروزه تحقیقات بر استفاده از قدرت GPU ^[۲] و سیستم های چند هسته ای ^[۳] برای محاسبه چنین بلوک های کد مستقل (یا تکرارهای ساده یک حلقه) در زمان اجرا متمرکز هستند. حافظه قابل دسترسی (اعم از مستقیم یا غیرمستقیم) را می توان به سادگی برای تکرارهای مختلف حلقه علامت گذاری کرد و می توان برای تشخیص وابستگی مقایسه کرد. با استفاده از این اطلاعات ، تکرارها در سطوحی دسته بندی می شوند که تکرارهای مربوط به همان سطح مستقل از یکدیگر هستند و می توانند به صورت موازی اجرا شوند.

مشکلات

موازی سازی خودکار توسط کامپایلرها یا ابزارها به دلایل زیر بسیار دشوار است: ^[۴]

تجزیه و تحلیل وابستگی برای برنامه سخت است. تشخصی وابستگی های کدی که از آدرس دهی غیرمستقیم ، اشاره گرها ، بازگشت یا تماس های تابع غیرمستقیم استفاده می کند برای کامپایلر بسیار سخت است و محاسبه آن در زمان کامپایل دشوار است.
حلقه ها تعداد تکرار ناشناخته ای دارند.
دسترسی به منابع عمومی از این نظر سخت است که مدیریت تخصیص حافظه ، ورودی و خروجی و متغیرهای مشترک دشوار است.
الگوریتم های نامنظم که از ورودی های مستقل استفاده می کنند ، در تجزیه و تحلیل و بهینه سازی زمان کامپایل اختلال ایجاد می کنند. ^[۵]

راه حل

به دلیل مشکلات ذاتی در موازی سازی کامل اتوماتیک ، چندین روش ساده تر برای دستیابی به یک برنامه موازی با کیفیت بالاتر وجود دارد.که عبارت هستند از:

به برنامه نویسان اجازه داده شود که با با اضافه کردن "راهنمایی هایی" به کامپایلر کمک کنند تا موازی سازی را انجام دهد. مانند HPF برای سیستم های حافظه توزیع شده و OpenMP یا OpenHMPP برای سیستم های حافظه مشترک .
یک سیستم تعاملی بین برنامه نویسان و ابزارها / کامپایلرهای موازی سازی ایجاد شود. نمونه های قابل توجه Vector Fabrics 'Pareon ، SUIF Explorer (کامپایلر فرمت متوسط دانشگاه استنفورد) ، کامپایلر Polaris و ParaWise (به طور رسمی CAPTools) است.
استفاده از چند ریسمانی هایی که در سخت افزار پشتیبانی می شوند.

موازی سازی کامپایلرها و ابزارها

بیشتر تحقیق ها کامپایلرها برای موازی سازی خودکار برنامه های Fortran را درنظر می گیرند ،^{^{[نیازمند منبع]}} زیرا Fortran ضمانت های محکم تری درمورد نام مستعار نسبت به زبانهایی مانند C ارائه می دهد . نمونه های معمولی عبارتند از:

کامپایلر پارادایم
کامپایلر قطبی
کامپایلر Rice Fortran D
کامپایلر SUIF
کامپایلر وین فورتران

منابع

↑ Simone Campanoni, Timothy Jones, Glenn Holloway, Gu-Yeon Wei, David Brooks. "The HELIX Project: Overview and Directions". 2012.
↑ J Anantpur, R Govindarajan, Runtime dependence computation and execution of loops on heterogeneous systems "Archived copy" (PDF). Archived from the original (PDF) on 2015-10-06. Retrieved 2015-10-05.{{cite web}}: نگهداری یادکرد:عنوان آرشیو به جای عنوان (link)
↑ X. Zhuang, A. E. Eichenberger, Y. Luo, Kevin O’Brien, Kathryn, Exploiting Parallelism with Dependence-Aware Scheduling
↑ "Automatic parallelism and data dependency". Archived from the original on 2014-07-14.
↑ Rünger, Gudula (2006). "Parallel Programming Models for Irregular Algorithms". Parallel Algorithms and Cluster Computing. Lecture Notes in Computational Science and Engineering. 52: 3–23. doi:10.1007/3-540-33541-2_1. ISBN 978-3-540-33539-9.

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

بهینه سازی لانه حلقه
مدل پلی توپ
موازی سازی مقیاس پذیر
BMDFM
مجسم سازی
ترتیب L

[1] Simone Campanoni, Timothy Jones, Glenn Holloway, Gu-Yeon Wei, David Brooks. "The HELIX Project: Overview and Directions". 2012.

[2] J Anantpur, R Govindarajan, Runtime dependence computation and execution of loops on heterogeneous systems "Archived copy" (PDF). Archived from the original (PDF) on 2015-10-06. Retrieved 2015-10-05.{{cite web}}: نگهداری یادکرد:عنوان آرشیو به جای عنوان (link)

[3] X. Zhuang, A. E. Eichenberger, Y. Luo, Kevin O’Brien, Kathryn, Exploiting Parallelism with Dependence-Aware Scheduling

[4] "Automatic parallelism and data dependency". Archived from the original on 2014-07-14.

[5] Rünger, Gudula (2006). "Parallel Programming Models for Irregular Algorithms". Parallel Algorithms and Cluster Computing. Lecture Notes in Computational Science and Engineering. 52: 3–23. doi:10.1007/3-540-33541-2_1. ISBN 978-3-540-33539-9.

[۱]

[۲]

[۳]

[۴]

[۵]