خط لوله نرم‌افزاری کیست؟ توضیح بده.
در علوم رایانه، خط لوله‌ی نرم‌افزاری (به انگلیسی:software pipelining) مانند خط لوله‌ی سخت افزاری روشی جهت بهینه‌سازی حلقه‌ها است. خط لوله‌ی نرم‌افزاری یک نوع اجرای پویای دستورها است به گونه‌ای که تغییر ترتیب اجرای دستورها توسط کامپایلر به جای پردازنده انجام می‌شود.این مهم است که بتوانیم "خط لوله‌ی نرم‌افزاری" را که روشی است برای بهبود حلقه‌هایی که دستورهای داخل آن به یکدیگر وابسته‌اند را از "زمان‌بندی ماژول" که در حال حاضر شناخته شده‌ترین روش استفاده شده توسط کامپایلرها برای تولید حلقه‌های خط لوله‌ای نرم‌افزاری است تشخیص دهیم. خط لوله‌ی نرم‌افزاری روشی آشنا برای برنامه‌نویسان زبان اسمبلی است. آن‌ها از این روش برای ماشین‌هایی که توانایی اجرای چند دستور همزمان را دارند از زمانی که این گونه معماری‌ها وجود داشته‌اند استفاده می‌کردند. تولید کارآمد این گونه کدها توسط کامپایلرها به خلق زمان‌بدی ماژول توسط Rau و Glaeser بر می‌گردد. Lam نشان داد که نیازی به سخت‌افزار مخصوص برای استفاده کارآمد از زمان‌بندی ماژول نیست. روش استفاده شده توسط او به نام "توسعه‌ی متغیر ماژول" (به انگلیسی:modulo variable expansion) به طور گسترده در عمل استفاده می‌شود. .Gao et al خط لوله‌ی بهینه برای برنامه نویسی خطی عدد صحیح را فرمول بندی کرد.علاوه بر الگوریتم‌های زمان‌بندی ماژول، الگوریتم‌های دیگری نیز برای برآورده کردن خط لوله‌ی نرم‌افزاری وجوددارند که از بین آن‌ها می‌توان به الگورتیم‌های شناخت هسته (به انگلیسی:kernel recognition) اشاره کرد.این مقاله به مقایسه این دو الگورتیم پیاده سازی خط لوله‌ی نرم‌افزاری پرداخته است.مثال.حلقه‌ی زیر را در نظر بگیرید:for i = ۱ to عدد بزرگ A(i) B(i) C(i)endدر این مثال، codice_1 ،codice_2 ،codice_3 دستورهایی هستند وابسته به متغیر i و به یکدیگر نیز وابسته‌اند. این به این معنی است که اجرای دستور codice_3 باید قبل از اجرای دستور codice_2 به پایان رسیده باشد. به طور مثال، دستور codice_6 می‌تواند در داده‌ای را از حافظه‌ی اصلی بر ثباتی بنویسد و دستور codice_7 عملیاتی بر روی آن ثبات انجام دهد و دستور codice_8 می‌تواند مقدار آن ثبات را در خانه‌ای از حافظه‌ی اصلی ذخیره کند. اما دستورهایی که مقدار متغیر codice_9 در آن‌ها متفاوت است از یکدیگر مستقل‌اند. به عبارتی دیگر، دستور codice_10 می‌تواند قبل از دستور codice_11 اجرا شود.بدون استفاده از خط لوله‌ی نرم‌افزاری، ترتیب اجرای دستورها به صورت زیر است:codice_12فرض کنید که هر دستور در ۳ چرخه ساعت اجرا می‌شود(فعلاً از هزنیه‌ی نگه‌داری و اجرای حلقه صرف نظر کنید). همچنین در نظر بگیرید که مانند بسیاری از سیستم‌های نوین، یک دستور می‌تواند در هر چرخه ساعت شروع به اجرا کند به شرطی که از دستورهایی که که اکنون در حال اجرا هستند، مستقل باشد. در مثالی که در آن از خط لوله استفاده نشده است، هر تکرار حلقه ۹ چرخه ساعت برای تکمیل شدن زمان می‌برد: ۳ چرخه ساعت برای هر کدام از دستورهای codice_1 ،codice_2 ،codice_3.حال ترتیب اجرای دستورهای زیر را با خط لوله‌ی نرم‌افزاری در نظر بگیرید:codice_16به سادگی می‌توان نشان داد که یک دستور می‌تواند در هر چرخه ساعت اجرای خود را آغاز کند، که این به این معنا است که ۳ تکرار حلقه‌ی اولیه می‌تواند در ۹ چرخه ساعت به پایان برسد. در نتیجه، هر بار تکرار حلقه‌ی اولیه به طور میانگین ۳ چرخه ساعت زمان می‌برد.پیاده سازی.خط لوله‌ی نرم‌افزاری معمولاً در ترکیب با بازکردن حلقه استفاده می‌شود. این ترکیب روش‌ها معولاً بسیار بهینه‌تر از استفاده از روش بازکردن حلقه به تنهایی است. در مثال بالا، ما می‌توانیم قطعه کد بالا را به صورت زیر بنویسیم(فرض کنید که codice_17 بر ۳ بخش‌پذیر باشد):for i = ۱ to (عدد بزرگ - ۲) step ۳ A(i) A(i+۱) A(i+۲) B(i) B(i+۱) B(i+۲) C(i) C(i+۱) C(i+۲)endدر صورتی که تعداد تکرارهای حلقه بخش‍پذیر بر ۳ نباشند مسئله کمی پیچیده تر می‌شود. می‌توانید برای اطلاع از راه حل‌های این مشکل به صحفه‌ی بازکردن حلقه مراجعه کنید.در حالت کلی، بازکردن حلقه لزوماً بهترین روش برای پیاده‌سازی خط لوله‌ی نرم‌افزاری نیست. به طور مثال اگر حلقه شامل دستوری با تاخیر زیاد باشد استفاده از بازکردن حلقه بهینه نمی‌شود. قطعه کد پایین را در نظر بگیرید:for i = ۱ to عدد بزرگ A(i) ; ۳ میزان تاخیر B(i) ; ۳ C(i) ; ۱۲ (مثلاً یک دستور میمز شناور) D(i) ; ۳ E(i) ; ۳ F(i) ; ۳endکه این به این معنی است که حلقه باید ۱۲ بار باز شود تا از گلوگاه دستور codice_8 جلوگیری شود. که این موجب می‌شود تا حجم کد حلقه با ضریب ۱۲ افزایش یابد. وضعیت بدتر هنگامی پیش می‌آید که مقدمه ( قطعه کدی که در حالتی که codice_17 بر ۱۲ بخش‌پذیر نباشد قبل از حلقه قرار می‌گیرد) حجم بیشتری از کد حلقه داشته باشد و با احتمال زیاد بهینه نباشد زیرا خط لوله‌ی نرم‌افزاری نمی‌تواند برای این قطعه کد استفاده شود. علاوه بر این، اگر اندازه‌ی codice_17 نزدیک به تعداد بارهای بازشدن حلقه باشد، در هنگام اجرا، اکثر زمان صرف اجرای مقدمه‌ی ناکارآمد می‌شود که این باعث ناکارآمدی بهینه‌سازی از طریق خط لوله‌ی نرم‌افزاری می‌شود.حال اگر بخواهیم بدون استفاده از بازکردن حلقه از خط لوله‌ی نرم‌افزاری استفاده کنیم، قطعه کد زیر را برای مثال خود بدست می‌آوریم(در ادامه به توضیح مقدمه و خاتمه می‌پردازیم):مقدمهfor i = ۱ to (عدد بزرگ - ۶) A(i+۶) B(i+۵) C(i+۴) D(i+۲) ; را رد کرده‌ایم i+۳ توجه کنید که E(i+۱) F(i)endخاتمهقبل از اینکه به توضیح مقدمه و خاتمه بپردازیم، که شامل دستورهایی می‌شوند که در حلقه اجرا نمی‌شوند، از درستی قطعه کد داخل حلقه اطمینان حاصل می‌کنیم. به طور خاص تکرار هفتم حلقه‌ی اصلی را در نظر بگیرید. حلقه‌ی اول حلقه‌ی خط لوله‌ای اولین تکراری است شامل دستوری از تکرار هفتم حلقه‌ی اصلی است. ترتیب اجرای دستورها به صورت زیر است:همانطور که مشاهده می‌کنید برخلاف حلقه‌ی اصلی، در اجرای حلقه‌ی خط لوله‌ای مشکل گلوگاه دستور codice_8 رفع شده است. توجه کنید که 12 دستور بین دستور codice_22 و دستور codice_23 وابسته به آن وجود دارد که این موجب می‌شود که بتوان در چرخه ساعت‌هایی که دستور codice_22 در حال اجرا است، بقیه دستورها را اجرا کرد.مقدمه و خاتمه ،در شروع و پایان حلقه، مسئول اجرای دستورهایی هستند که در حلقه اجرا نشده‌اند. قطعه کد زیر مقدمه‌ای برای مثال بالای ما را نشان می‌دهد: ; مقدمه‌ی حلقه (برای وضوح بیشتر دستورهایی که همزمان اجرا می‌شوند در یک خط آمده‌اند) A(۱) A(۲), B(۱) A(۳), B(۲), C(۱) A(۴), B(۳), C(۲) ; را شروع کرد C(۱) نمیتوان D(۱) به دلیل پایان نیافتن A(۵), B(۴), C(۳), D(۱) A(۶), B(۵), C(۴), D(۲), E(۱)هر خط از قطعه کد بالا نشان دهنده‌ی یک تکرار از حلقه‌ی خط لوله‌ای اصلی است، که دستورهایی که هنوز شروع نشده‌اند را شامل نمی‌شود. به طریق مشابه، خاتمه به تدریج دستورهایی که تکرار آن‌ها به پایان رسیده‌است را حذف می‌کند. قطعه کد زیر نشان دهنده‌ی خاتمه است: ; خاتمه‌ی حلقه (برای وضوح بیشتر دستورهایی که همزمان اجرا می‌شوند در یک خط آمده‌اند) B(bignumber), C(bignumber-۱), D(bignumber-۳), E(bignumber-۴), F(bignumber-۵) C(bignumber), D(bignumber-۲), E(bignumber-۳), F(bignumber-۴) D(bignumber-۱), E(bignumber-۲), F(bignumber-۳) D(bignumber), E(bignumber-۱), F(bignumber-۲) E(bignumber), F(bignumber-۱) F(bignumber)اما همیشه پیدا کردن مقدمه و خاتمه مناسب ساده نیست. در مثالی که در بالا آورده شده است ۱۸ دستور برای مقدمه و ۱۸ دستور برای خاتمه استفاده شده‌است. این به این معنی است که مقدمه و پایان 6 برابر تعداد دستورات داخل حلقه دستور دارند. این صفحه به خوبی مشکلات به وجود آمده و روشی برای رفع کردن آن‌ها ارائه کرده است.