موازی‌سازی خودکار
موازی سازی خودکار، موازی خودکار، یا autoparallelization به تبدیل یک سری کد متوالی به کد مبدا با چند ریسمانی و یا برداری سازی خودکار مستقل از هم گفته می شود. کد به منظور حل در پردازنده‌های هسته ای به‌طور همزمان در یک حافظه مشترک چند پردازشی هستند(SMP دستگاه). موازی سازی کاملاً خودکار برنامه‌های ترتیبی چالش‌برانگیز است زیرا به تجزیه و تحلیل برنامه پیچیده‌ای نیاز دارد و همچنین بهترین روش به مقادیر پارامترها بستگی دارد که در زمان کامپایل مشخص نیستند.
برنامه‌نویسی ساختارهای کنترل که بیشترین تمرکز خودکار آنها بر روی حلقه‌ها هستند، زیرا به‌طور کلی، بیشتر زمان اجرای برنامه در داخل نوعی از حلقه سپری می‌شود. دو روش اصلی برای موازی سازی حلقه‌ها وجود دارد: رایانش چند ریسمانی و حلقوی چند ریسمانی. به عنوان مثال، یک حلقه را در نظر بگیرید که در هر تکرار صد عملیات انجام می‌دهد، و برای هزاربار اجرا می‌شود. این را می‌توان به عنوان شبکه ای از ۱۰۰ ستون در ۱۰۰۰ ردیف، در مجموع ۱۰۰۰۰۰ عملیات در نظر گرفت. حلقوی چند ریسمانی نسبت می‌دهد هر ردیف را به یک ریسمان اختصاص می‌دهد. رایانش چند ریسمانی هر ستون را به یک موضوع ریسمان اختصاص می‌دهد؛ که این ریسمان‌ها به صورت موازی اجرا می‌شوند.
اولین مرحله خواندن فایل‌های ورودی است تا همه منابع خارجی که از آن در برنامه استفاده شده را شناسایی کنیم. هر سطر در فایل چک خواهد شد تا به الگوهای از پیش تعریف شده افراض شود. این نشانه‌ها در فایلی ذخیره می‌شوند که بعداً توسط قسمتی دیگر پردازش خواهند شد. این قسمت زبان مجموعه توکن‌ها را با قوانین از پیش تعریف شده چک می‌کند تا ببیند آیا با متغیرها، حلقه‌ها، دستورات کنترل، توابع و… تطابق دارند یا نه.
از تجزیه گر برای شناسایی بخشهایی از کد استفاده می‌شود که می‌توانند همزمان اجرا شوند. آنالیز کننده از اطلاعات داده‌های استاتیک ارائه شده توسط تجزیه کننده استفاده می‌کند. تجزیه گر ابتدا تمام توابع کاملاً مستقل را پیدا کرده و آنها را به عنوان وظایف جداگانه علامت گذاری می‌کند. سپس تجزیه گر می‌یابد که کدام وظایف وابسته به دیگری هستند.
برنامه‌ریز کلیه وظایف و وابستگی آنها به یکدیگر از نظر زمان اجرا و شروع را لیست می‌کند. برنامه‌ریز زمان بهینه را با توجه به تعداد پردازنده‌های مورد استفاده، کل زمان اجرای برنامه و… پیدا می‌کند.
برنامه‌ریز لیستی از تمام وظایف و جزئیات هسته‌ها همراه با زمان و قسمتی که باید روی آنها اجرا شود را تولید می‌کند. تولیدکننده کد، سازه‌های خاصی را در کد وارد می‌کند که در هنگام اجرا توسط برنامه‌ریز خوانده می‌شود. این سازه‌ها به برنامه‌ریز دستور می‌دهند که یک کار خاص همراه با زمان شروع و پایان بر روی کدام هسته انجام شود.
یک کامپایلر با موازی سازی حلقوی چند ریسمانی سعی می‌کند یک حلقه را تقسیم کند تا هر تکرار بتواند همزمان بر روی یک پردازنده جداگانه اجرا شود.
"کامپایلر" برای تعیین موارد زیر معمولاً قبل از موازی سازی، دو بار تجزیه و تحلیل انجام می‌دهد:
در اولین بار کامپایلر تجزیه و تحلیل وابستگی به داده‌ها از حلقه را انجام می‌دهد تا تعیین کند آیا هر تکرار حلقه می‌تواند به‌طور مستقل از دیگران اجرا شود. بعضی مواقع داده‌ها به هم وابستگی ندارند، اما ممکن است هزینه اضافی برای ارسال پیام، همگام سازی حافظه مشترک یا مشکلات دیگری در حین ارتباط ایجاد کنند.
در دفعه دوم با مقایسه زمان اجرای نظری کد پس از موازی سازی با زمان اجرای ترتیبی کد، می‌بینیم که آیا موازی سازی توجیه کند پذیر است یا خیر. در بعضی مواقع، اجرای کد به طوز موازی سودمند نیست. هزینه اضافی که برای استفاده و تنظیم کار و ارتباط بین چندین پردازنده لازم است می‌تواند باعث شود که اجرای برنامه از اجرا روی یک پردازنده آرامتر باشد.
یک حلقه DOALL نامیده می‌شود اگر تمام تکرارهای آن، در هر فراخوانی مشخص، بتواند همزمان اجرا شود. کد Fortran زیر DOALL است، و توسط یک کامپایلر می‌تواند بصورت خودکار موازی شود زیرا هر تکرار مستقل از موارد دیگر است، و نتیجه نهایی آرایه codice_1 صرف نظر از ترتیب اجرای سایر تکرارها صحیح خواهد بود. بسیاری از مسائل وجود دارند که دارای چنین حلقه‌های DOALL است. به عنوان مثال، هنگام رندرینگ یک فیلم، هر فریم از فیلم می‌تواند به‌طور مستقل پردازش شود و هر پیکسل از یک فریم ممکن است به‌طور مستقل رندر شود.
از طرف دیگر، کد زیر نمی‌تواند به صورت خودکار موازی شود، زیرا مقدار (codice_2 به نتیجه تکرار قبلی، (codice_3 بستگی دارد. این بدان معنا نیست که کد نمی‌تواند موازی شود. در واقع، معادل است با با این حال، کامپایلرهای موازی ساز معمولاً قادر به تشخیس خودکار این موازی سازی‌ها نیستند و اینکه آیا این کد در وهله اول از موازی سازی سود می‌برد جای سؤال است.
یک کامپایلر موازی ساز به روش رایانش چند ریسمانی سعی می‌کند توالی عملیات درون یک حلقه را به مجموعه ای از بلوک‌های کد تقسیم کند، به طوری که هر بلوک کد بتواند همزمان بر روی پردازنده‌های جداگانه اجرا شود.
بسیاری از کدها وجود دارند که با این روش قابل تقسیم به بلوک‌های کد نسبتاً مستقل هستند، به ویژه سیستم‌هایی که از خط لوله‌ها و فیلترها استفاده می‌کند وجود دارند. به عنوان مثال، هنگام تولید برنامه تلویزیونی پخش زنده، کارهای زیر باید چندین بار در ثانیه انجام شوند:
یک کامپایلر موازی ساز به روش رایانش چند ریسمانی می‌تواند هر یک از این ۶ عملیات را به یک پردازنده اختصاص دهد، که احتمالاً در یک آرایه سیستولیک و کد مناسب را برای انتقال خروجی یک پردازنده به پردازنده بعدی درج کند.
امروزه تحقیقات بر استفاده از قدرت GPU و سیستم‌های چند هسته ای برای محاسبه چنین بلوک‌های کد مستقل (یا تکرارهای ساده یک حلقه) در زمان اجرا متمرکز هستند. حافظه قابل دسترسی (اعم از مستقیم یا غیرمستقیم) را می‌توان به سادگی برای تکرارهای مختلف حلقه علامت گذاری کرد و می‌توان برای تشخیص وابستگی مقایسه کرد. با استفاده از این اطلاعات، تکرارها در سطوحی دسته‌بندی می‌شوند که تکرارهای مربوط به همان سطح مستقل از یکدیگر هستند و می‌توانند به صورت موازی اجرا شوند.
موازی سازی خودکار توسط کامپایلرها یا ابزارها به دلایل زیر بسیار دشوار است:
به دلیل مشکلات ذاتی در موازی سازی کامل اتوماتیک، چندین روش ساده‌تر برای دستیابی به یک برنامه موازی با کیفیت بالاتر وجود دارد؛ که عبارت هستند از:
بیشتر تحقیق‌ها کامپایلرها برای موازی سازی خودکار برنامه‌های Fortran را درنظر می‌گیرند ، زیرا Fortran ضمانت‌های محکم تری درمورد نام مستعار نسبت به زبانهایی مانند C ارائه می‌دهد. نمونه‌های معمولی عبارتند از: