موازی سازی خودکار
موازی‌سازی خودکار، همچنین اتوماتیک‌سازی، که آخرین مورد دلالت بر اتوماسیون در هنگام استفاده در متن دارد، به تبدیل کد دنباله‌ای به کد چند ریسه یا بردار (یا حتی هر دو) اشاره دارد تا بتوان از چندین پردازنده به طور همزمان در دستگاه چندپردازشی حافظه مشترک (SMP) استفاده کرد. هدف موازی‌سازی اتوماتیک، رهایی برنامه‌نویسان از روند موازی‌سازی دستی است.[۱] اگرچه کیفیت موازی‌سازی اتوماتیک در چند دهه گذشته بهبود یافته است، موازی سازی کاملاً خودکار برنامه های پی در پی توسط کامپایلرها به دلیل نیاز به تجزیه و تحلیل برنامه‌های پیچیده و عوامل ناشناخته (مانند دامنه داده ورودی) در حین کامپایل، یک چالش بزرگ است.[۲]
ساختارهای کنترل برنامه‌نویسی بیشتر متمرکز روی حلقه‌ها هستند، زیرا به طور کلی بیشتر زمان اجرای یک برنامه در داخل برخی از حلقه‌ها اتفاق می افتد. دو روش اصلی برای موازی سازی حلقه ها وجود دارد: چند ریسه‌ای خط لوله‌ای و چند ریسه‌ای حلقوی.[۳]
به عنوان مثال ، یک حلقه را در نظر بگیرید که در هر تکرار صد عملیات انجام می‌دهد و برای هزار بار تکرار می‌شود. این را می‌توان به عنوان یک شبکه از 100 ستون و 1000 ردیف، در کل 100000 عملیات تصور کرد. چند ریسه‌ای حلقوی هر ردیف را به یک ریسه متفاوت اختصاص می‌دهد. چند ریسه‌ای خط لوله‌ای ، هر ستون را به ریسه متفاوتی اختصاص می دهد.
تکنیک موازی سازی خودکار[ویرایش]
تجزیه[ویرایش]
این اولین مرحله است که اسکنر فایل‌های ورودی را برای شناسایی کلیه موارد استفاده ایستا و خارجی می‌خواند. هر خط در فایل در برابر الگوهای از پیش تعریف شده بررسی می‌شود تا به نشانه‌ها تفکیک شود. این نشانه‌ها در فایلی ذخیره می‌شوند که بعدا توسط موتور گرامر مورد استفاده قرار می‌گیرد. موتور گرامر الگوهای مشخصی را که با قوانین از پیش تعریف شده مطابقت دارد بررسی می‌کند تا متغیرها، حلقه ها، دستورات کنترل، عملکردها و غیره را در کد شناسایی کند.
آنالیز[ویرایش]
از آنالیز کننده برای شناسایی بخش هایی از کدی استفاده می‌شود که به طور همزمان قابل اجرا هستند. آنالیز کننده از داده‌های ایستا ارائه شده توسط تجزیه‌کننده استفاده می‌کند. آنالیز کننده ابتدا تمام عملکردهای کاملاً مستقل را پیدا می‌کند و آنها را به عنوان کارهای مجزا علامت‌گذاری می‌کند. سپس آنالایز کننده کارهایی وابستگی دارند را پیدا می‌کند.
زمانبندی[ویرایش]
برنامه‌ریز تمام وظایف و وابستگی آنها به یکدیگر را از نظر اجرا و زمان شروع ذکر می‌کند. برنامه‌ریز، زمانبندی بهینه از نظر تعداد پردازنده‌های مورد استفاده یا کل زمان اجرای برنامه را تولید می‌کند.
کد سازی[ویرایش]
برنامه‌ریز لیستی از کلیه وظایف و جزئیات هسته‌هایی را که در آن اجرا می‌شود، به همراه زمانی که در آن اجرا می‌شود، ایجاد می کند. کدسازها سازه‌های ویژه ای را در کد وارد می‌کند که در هنگام اجرا توسط برنامه‌ریز خوانده می‌شود. این سازه‌ها، برای برنامه‌ریز مشخص می‌کند كه یک وظیفه خاص در آن هسته با چه زمان‌های شروع و پایانی انجام خواهد شد.
چند ریسه‌ای حلقوی[ویرایش]
روش چند ریسه‌ای حلقوی سعی در بخش کردن حلقه را دارد تا در هر تکرار هر بخش به طور موازی بر روی یک پردازنده جداگانه اجرا شود.
آنالیز موازی کامپایلر[ویرایش]
کامپایلر معمولاً برای تعیین موارد زیر دو گذر از آنالیز را انجام می دهد:
آیا موازی‌سازی حلقه ایمن است؟ پاسخ به این سؤال به تحلیل دقیق وابستگی و آنالیز نام مستعار نیاز دارد.
آیا این گونه موازی‌سازی ارزش دارد؟ این پاسخ نیاز به یک ارزیابی معتبر(مدل سازی) از حجم کار برنامه و ظرفیت سیستم موازی دارد.
در اولین مرحله کامپایلر، آنالیز وابستگی به داده از حلقه را انجام می‌شود تا مشخص شود که آیا هر تکرار حلقه می‌تواند به طور مستقل از دیگران اجرا شود. وابستگی به داده‌ها گاهی اوقات قابل دستیابی است. اما ممکن است فرستادن پیام در هماهنگ سازی حافظه مشترک یا روش دیگر ارتباط پردازنده، بهینه نباشد.
در مرحله دوم کامپایلر سعی دارد با مقایسه زمان اجرای نظری کد پس از موازی‌سازی با زمان اجرای متوالی کد، موازی‌سازی را توجیه کند. کد همیشه از اجرای موازی سود نمی برد. سربار اضافی که می‌تواند در استفاده از چندین پردازنده بوجود آید، سرعت بالقوه کد موازی را کم می‌کند.
مثال[ویرایش]
به یک حلقه DOALL گفته می‌شود اگر بتوان در هر تکرار آن، دستورات را به صورت موازی اجرا کرد. کد Fortran زیر یک DOALL است و می توان آن را با کامپایلر به صورت خودکار موازی اجرا کرد زیرا هر تکرار مستقل از دیگران است و نتیجه‌نهایی آرایه z صرف نظر از دستور اجرای سایر تکرارها صحیح خواهد بود.
do i = 1, n
z(i) = x(i) + y(i)
enddo
بسیاری از مشکلات خوشایند موازی که چنین حلقه‌های DOALL دارند، وجود دارد. به عنوان مثال ، هنگام پخش فیلم با اشعه ایکس، هر فریم فیلم بطور مستقل رندر می‌شود و ممکن است هر پیکسل از یک فریم به صورت مستقل ارائه شود. از طرف دیگر ، کد زیر نمی تواند به طور خودکار موازی شود، زیرا مقدار به نتیجه تکرار قبلی یعنی بستگی دارد.
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 عملیات را به یک پردازنده متفاوت، که شاید در یک آرایه systolic قرار گرفته باشد، با وارد کردن کد مناسب برای انتقال خروجی یک پردازنده به پردازنده بعدی اختصاص دهد.
تحقیقات اخیر روی استفاده از قدرت GPU[۴] و سیستم های چند هسته‌ای[۵] برای محاسبه چنین بلوک‌های کد مستقل در زمان اجرا تمرکز دارد. برای دسترسی به حافظه (چه مستقیم و چه غیرمستقیم) می‌توان به سادگی برای تکرارهای مختلف یک حلقه مشخص کرد و این روش برای مقایسه تشخیص وابستگی مفید است. با استفاده از این اطلاعات، تکرارها به صورت سطحی دسته‌بندی می شوند که تکرارهای متعلق به همان سطح مستقل از یکدیگر باشند و به صورت موازی قابل اجرا باشند.
مشکلات[ویرایش]
موازی‌سازی خودکار توسط کامپایلرها یا ابزارها به دلایل زیر بسیار دشوار است:[۶]
- تجزیه و تحلیل وابستگی برای کدی که از آدرس‌دهی‌های غیرمستقیم، اشاره‌گرها، بازگشتی یا تماس‌های غیرمستقیم استفاده می‌کند سخت است زیرا تشخیص چنین وابستگی‌ها در زمان کامپایل دشوار است.
- حلقه‌ها تعداد ناشناخته‌ای از تکرار دارند.
- هماهنگی دسترسی به منابع جهانی از نظر تخصیص حافظه، I/O و متغیرهای مشترک دشوار است.
- الگوریتم‌های نامنظم که از indirection وابسته به ورودی استفاده می‌کنند، در تجزیه و تحلیل زمان بهینه و بهینه‌سازی دخالت می‌کنند.[۷]
راه حل[ویرایش]
با توجه به مشکلات ذاتی در موازی‌سازی کاملا خودکار، چندین روش ساده‌تر برای دستیابی به یک برنامه موازی با کیفیت بالاتر وجود دارد. آنها به شرح زیر هستند:
- به برنامه‌نویسان اجازه داده شود که برای موازی‌سازی کامپایلر راهنما قرار دهند. مانند HPF برای سیستم‌های حافظه توزیع شده و OpenMP یا OpenHMPP برای سیستم‌های حافظه مشترک.
- یک سیستم تعاملی بین برنامه‌نویسان و ابزارها و کامپایلرهای موازی ایجاد شود. نمونه‌های قابل توجه عبارتند از: پارچه‌برداری بردار، سارو اکسپلورر (کامپایلر با فرمت دانشگاه استنفورد) ، کامپایلر Polaris و ParaWise (رسما CAPTools).
- استفاده از چندریسه‌ای سودگرانه که توسط سخت‌افزار حمایت شود.
کامپایلرها و ابزارهای موازی[ویرایش]
بیشتر کامپایلرهای تحقیقاتی برای موازی‌سازی خودکار، برنامه‌های Fortran را در نظر می‌گیرند. زیرا استناد به Fortran تضمین‌های قوی‌تر را نسبت به زبان‌هایی نظیر C می‌دهد. چند نمونه از آن به شرح زیر هستند:
- کامپایلر Paradigm
- کامپایلر Polaris
- کامپایلر Rice Fortran D
- کامپایلر SUIF
- کامپایلر Vienna Fortran
منابع[ویرایش]
- ↑ "Yehezkael, Rafael (2000). "Experiments in Separating Computational Algorithm from Program Distribution and Communication". Lecture Notes in Computer Science of Springer Verlag. Lecture Notes in Computer Science. 1947: 268–278. doi:10.1007/3-540-70734-4_32. ISBN 978-3-540-41729-3.
- ↑ Fox, Geoffrey; Roy Williams; Paul Messina (1994). Parallel Computing Works!. Morgan Kaufmann. pp. 575, 593. ISBN 978-1-55860-253-3.
- ↑ 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.CS1 maint: archived copy as title (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.
همچنین ببینید[ویرایش]
This article "موازی سازی خودکار" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:موازی سازی خودکار. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
