موازی‌سازی خودکار

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

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

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

تجزیه‌کننده

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

تجزیه

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

برنامه‌ریزی

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

تولید کد

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

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

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

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

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

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

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

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

مثال

یک حلقه 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 را از آنتن تلویزیون بفرستد.

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

امروزه تحقیقات بر استفاده از قدرت 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" بایگانی‌شده در ۲۷ مه ۲۰۱۵ توسط Wayback Machine. 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" بایگانی‌شده در ۲۷ مه ۲۰۱۵ توسط Wayback Machine. 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.

[۱]

[۲]

[۳]

[۴]

[۵]