خط لوله نرم‌افزاری

در علوم رایانه، خط لوله‌ی نرم‌افزاری (به انگلیسی:software pipelining) مانند خط لوله‌ی سخت افزاری روشی جهت بهینه‌سازی حلقه‌ها است. خط لوله‌ی نرم‌افزاری یک نوع اجرای پویای دستورها است به گونه‌ای که تغییر ترتیب اجرای دستورها توسط کامپایلر به جای پردازنده انجام می‌شود.
این مهم است که بتوانیم خط لوله‌ی نرم‌افزاری را که روشی است برای بهبود حلقه‌هایی که دستورهای داخل آن به یکدیگر وابسته‌اند را از زمان‌بندی ماژول که در حال حاضر شناخته شده‌ترین روش استفاده شده توسط کامپایلرها برای تولید حلقه‌های خط لوله‌ای نرم‌افزاری است تشخیص دهیم. خط لوله‌ی نرم‌افزاری روشی آشنا برای برنامه‌نویسان زبان اسمبلی است. آن‌ها از این روش برای ماشین‌هایی که توانایی اجرای چند دستور همزمان را دارند از زمانی که این گونه معماری‌ها وجود داشته‌اند استفاده می‌کردند. تولید کارآمد این گونه کدها توسط کامپایلرها به خلق زمان‌بدی ماژول توسط Rau و Glaeser بر می‌گردد.^[۱] Lam نشان داد که نیازی به سخت‌افزار مخصوص برای استفاده کارآمد از زمان‌بندی ماژول نیست. روش استفاده شده توسط او به نام توسعه‌ی متغیر ماژول (به انگلیسی:modulo variable expansion) به طور گسترده در عمل استفاده می‌شود.^[۲] .Gao et al خط لوله‌ی بهینه برای برنامه نویسی خطی عدد صحیح را فرمول بندی کرد.^[۳] علاوه بر الگوریتم‌های زمان‌بندی ماژول، الگوریتم‌های دیگری نیز برای برآورده کردن خط لوله‌ی نرم‌افزاری وجوددارند که از بین آن‌ها می‌توان به الگورتیم‌های شناخت هسته (به انگلیسی:kernel recognition) اشاره کرد.^[۴]این مقاله به مقایسه این دو الگورتیم پیاده سازی خط لوله‌ی نرم‌افزاری پرداخته است.

مثال

حلقه‌ی زیر را در نظر بگیرید:

for i = ۱ to عدد بزرگ
 A(i)
 B(i)
 C(i)
end

در این مثال، C(i) ،B(i) ،A(i) دستورهایی هستند وابسته به متغیر i و به یکدیگر نیز وابسته‌اند. این به این معنی است که اجرای دستور A(i) باید قبل از اجرای دستور B(i) به پایان رسیده باشد. به طور مثال، دستور A می‌تواند در داده‌ای را از حافظه‌ی اصلی بر ثباتی بنویسد و دستور B عملیاتی بر روی آن ثبات انجام دهد و دستور C می‌تواند مقدار آن ثبات را در خانه‌ای از حافظه‌ی اصلی ذخیره کند. اما دستورهایی که مقدار متغیر i در آن‌ها متفاوت است از یکدیگر مستقل‌اند. به عبارتی دیگر، دستور A(۲) می‌تواند قبل از دستور A(۱) اجرا شود.
بدون استفاده از خط لوله‌ی نرم‌افزاری، ترتیب اجرای دستورها به صورت زیر است:

A(۱) B(۱) C(۱) A(۲) B(۲) c(۲) A(۳) B(۳) C(۳) ...

فرض کنید که هر دستور در ۳ چرخه ساعت اجرا می‌شود(فعلاً از هزنیه‌ی نگه‌داری و اجرای حلقه صرف نظر کنید). همچنین در نظر بگیرید که مانند بسیاری از سیستم‌های نوین، یک دستور می‌تواند در هر چرخه ساعت شروع به اجرا کند به شرطی که از دستورهایی که که اکنون در حال اجرا هستند، مستقل باشد. در مثالی که در آن از خط لوله استفاده نشده است، هر تکرار حلقه ۹ چرخه ساعت برای تکمیل شدن زمان می‌برد: ۳ چرخه ساعت برای هر کدام از دستورهای C(i) ،B(i) ،A(i).
حال ترتیب اجرای دستورهای زیر را با خط لوله‌ی نرم‌افزاری در نظر بگیرید:

A(۱) A(۲) A(۳) B(۱) B(۲) B(۳) C(۱) C(۲) C(۳) ...

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

پیاده سازی

خط لوله‌ی نرم‌افزاری معمولاً در ترکیب با بازکردن حلقه استفاده می‌شود. این ترکیب روش‌ها معولاً بسیار بهینه‌تر از استفاده از روش بازکردن حلقه به تنهایی است. در مثال بالا، ما می‌توانیم قطعه کد بالا را به صورت زیر بنویسیم(فرض کنید که عدد بزرگ بر ۳ بخش‌پذیر باشد):

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

که این به این معنی است که حلقه باید ۱۲ بار باز شود تا از گلوگاه دستور C جلوگیری شود. که این موجب می‌شود تا حجم کد حلقه با ضریب ۱۲ افزایش یابد. وضعیت بدتر هنگامی پیش می‌آید که مقدمه ( قطعه کدی که در حالتی که عدد بزرگ بر ۱۲ بخش‌پذیر نباشد قبل از حلقه قرار می‌گیرد) حجم بیشتری از کد حلقه داشته باشد و با احتمال زیاد بهینه نباشد زیرا خط لوله‌ی نرم‌افزاری نمی‌تواند برای این قطعه کد استفاده شود. علاوه بر این، اگر اندازه‌ی عدد بزرگ نزدیک به تعداد بارهای بازشدن حلقه باشد، در هنگام اجرا، اکثر زمان صرف اجرای مقدمه‌ی ناکارآمد می‌شود که این باعث ناکارآمدی بهینه‌سازی از طریق خط لوله‌ی نرم‌افزاری می‌شود. حال اگر بخواهیم بدون استفاده از بازکردن حلقه از خط لوله‌ی نرم‌افزاری استفاده کنیم، قطعه کد زیر را برای مثال خود بدست می‌آوریم(در ادامه به توضیح مقدمه و خاتمه می‌پردازیم):

مقدمه
for i = ۱ to (عدد بزرگ - ۶)
 A(i+۶)
 B(i+۵)
 C(i+۴)
 D(i+۲) ; را رد کرده‌ایم i+۳ توجه کنید که 
 E(i+۱)
 F(i)
end
خاتمه

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

تکرار ۱ : A(۷) B(۶) C(۵) D(۳) E(۲) F(۱)

تکرار ۲: A(۸) B(۷) C(۶) D(۴) E(۳) F(۲)

تکرار ۳: A(۹) B(۸) C(۷) D(۵) E(۴) F(۳)

تکرار ۴: A(۱۰) B(۹) C(۸) D(۶) E(۵) F(۴)

تکرار ۵: A(۱۱) B(۱۰) C(۹) D(۷) E(۶) F(۵)

تکرار ۶: A(۱۲) B(۱۱) C(۱۰) D(۸) E(۷) F(۶)

تکرار ۷: A(۱۳) B(۱۲) C(۱۱) D(۹) E(۸) F(۷)

همانطور که مشاهده می‌کنید برخلاف حلقه‌ی اصلی، در اجرای حلقه‌ی خط لوله‌ای مشکل گلوگاه دستور C رفع شده است. توجه کنید که 12 دستور بین دستور C(7) و دستور D(7) وابسته به آن وجود دارد که این موجب می‌شود که بتوان در چرخه ساعت‌هایی که دستور C(7) در حال اجرا است، بقیه دستورها را اجرا کرد. مقدمه و خاتمه ،در شروع و پایان حلقه، مسئول اجرای دستورهایی هستند که در حلقه اجرا نشده‌اند. قطعه کد زیر مقدمه‌ای برای مثال بالای ما را نشان می‌دهد:

 ; مقدمه‌ی حلقه (برای وضوح بیشتر دستورهایی که همزمان اجرا می‌شوند در یک خط آمده‌اند) 
 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 برابر تعداد دستورات داخل حلقه دستور دارند.^[۵] این صفحه به خوبی مشکلات به وجود آمده و روشی برای رفع کردن آن‌ها ارائه کرده است.

جستارهای وابسته

• بهینه‌سازی کامپایلر
• خط لوله
• بهینه سازی حلقه

منابع

1. B.R. Rau and C.D. Glaeser, "Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing", In Proceedings of the Fourteenth Annual Workshop on Microprogramming (MICRO-14), December 1981, pages 183-198
2. M. Lam, "Software pipelining: An effective scheduling technique for VLIW machines", In Proceedings of the ACM SIGPLAN 88 Conference on Programming Language Design and Implementation (PLDI 88), July 1988 pages 318-328. Also published as ACM SIGPLAN Notices 23(7).
3. J. Ruttenberg, G.R. Gao, A. Stoutchinin, and W. Lichtenstein, "Software pipelining showdown: optimal vs. heuristic methods in a production compiler", In Proceedings of the ACM SIGPLAN 1996 Conference on Programming Language Design and Implementation, June 1996, pages 1-11. Also published as ACM SIGPLAN Notices 31(5).
4. V. Allan, R.B. Jones, R.M. Lee, S.J. Allan, "Software Pipelining", In ACM Computing Surveys, (1998). 27. 10.1145/212094.212131.
5. Wikipedia contributors (۱۶ اکتبر ۲۰۱۹). «Software pipelining». Wikipedia, The Free Encyclopedia. دریافت‌شده در ۱ فوریه ۲۰۲۰.