پیش‌نویس:اجرای خارج از ترتیب

"این مقاله در حال ترجمه از ویکی انگلیسی است

لطفا حذف نشود. "

 تاریخچه 
اجرای خارج از ترتیب (Out-of-order execution) گونه‌ای محدود از معماری جریان داده (Dataflow Architecture) است که در دههٔ ۱۹۷۰ و اوایل دههٔ ۱۹۸۰ یکی از مهم‌ترین حوزه‌های پژوهشی در معماری رایانه به‌شمار می‌رفت.مشارکت کنندگان ویکیپدیا. "CSFstudent1404Alm".دانشنامه ویکیپدیای انگلیسی

 کاربردهای اولیه در ابررایانه‌ها 
احتمالاً نخستین ماشینی که از اجرای خارج از ترتیب استفاده کرد، CDC 6600 بود که در سال ۱۹۶۴ معرفی شد و برای رفع تعارض‌ها از سازوکاری به نام اسکوربورد (Scoreboard) استفاده می‌کرد. با این حال، CDC 6600 توانایی مدیریت تعارض‌های WAW (نوشتن پس از نوشتن) را نداشت و در مواجهه با چنین تعارضی، اجرای پردازنده متوقف می‌شد. تورنتون این وضعیت را «تعارض مرتبهٔ اول» (First Order Conflict) نامید. این سامانه هرچند از رفع تعارض‌های RAW (خواندن پس از نوشتن) که «تعارض مرتبهٔ دوم» نامیده می‌شد و همچنین رفع تعارض‌های WAR (نوشتن پس از خواندن) که «تعارض مرتبهٔ سوم» نامیده می‌شد پشتیبانی می‌کرد، و این قابلیت‌ها برای برخورداری از اجرای کامل خارج از ترتیب کافی بودند، اما فاقد سازوکار مدیریت دقیق استثناها (Precise Exception Handling) بود. همچنین شکل ابتدایی و محدودی از پیش‌بینی انشعاب (Branch Prediction) در این سامانه وجود داشت، مشروط بر آن‌که مقصد انشعاب در ساختاری موسوم به «پشتهٔ دستورالعمل» (Instruction Stack) قرار داشته باشد. این پشته تنها تا عمق هفت واژه نسبت به شمارندهٔ برنامه (Program Counter) را پوشش می‌داد.

حدود دو سال بعد، IBM System/360 Model 91 (۱۹۶۶) با بهره‌گیری از الگوریتم توماسولو، سازوکار تغییرنام ثبات‌ها (Register Renaming) را معرفی کرد. این روش وابستگی‌های کاذب (WAW و WAR) را از میان برمی‌برد و در نتیجه اجرای کامل خارج از ترتیب را امکان‌پذیر می‌سازد. در این سازوکار، دستوری که باید مقداری را در ثبات rn بنویسد، می‌تواند پیش از اجرای دستور قدیمی‌تری که از همان ثبات استفاده می‌کند اجرا شود. این کار با نوشتن نتیجه در یک ثبات جایگزینِ تغییرنام‌یافته، مانند alt-rn، انجام می‌شود. تنها زمانی که همهٔ دستورهای پیشینِ مرتبط با ثبات rn اجرا شده باشند، ثبات جایگزین به عنوان ثبات اصلی در نظر گرفته می‌شود. تا آن زمان، دستورهای قدیمی‌تر همچنان به ثبات rn و دستورهای جدیدتر به ثبات alt-rn ارجاع داده می‌شوند.

در Model 91، تغییرنام ثبات‌ها از طریق یک مسیر میان‌بُر موسوم به گذرگاه مشترک داده (Common Data Bus یا CDB) و نیز بافرهای عملوند مبدأ حافظه پیاده‌سازی شده بود. این طراحی موجب می‌شد ثبات‌های معماری فیزیکی برای چندین چرخه بلااستفاده بمانند، زیرا جدیدترین وضعیت موردنیاز برای دستورهای اجرا‌نشده روی CDB نگهداری می‌شد. یکی دیگر از مزیت‌های Model 91 نسبت به CDC 6600، توانایی اجرای خارج از ترتیب دستورها در درون یک واحد اجرایی واحد بود؛ قابلیتی که در CDC 6600 عمدتاً به اجرای خارج از ترتیب میان واحدهای مختلف محدود می‌شد. این ویژگی با استفاده از ایستگاه‌های رزرو (Reservation Stations) فراهم شده بود؛ به‌گونه‌ای که دستورها پس از آماده شدن از ایستگاه رزرو به واحد اجرایی ارسال می‌شدند، در حالی که در CDC 6600 هر واحد اجرایی از یک صف FIFO استفاده می‌کرد. Model 91 همچنین می‌توانست عملیات بارگذاری و ذخیره‌سازی را بازآرایی کند و برخی از آن‌ها را پیش از عملیات بارگذاری و ذخیره‌سازیِ پیشین اجرا نماید. این در حالی بود که CDC 6600 تنها توانایی محدودی در جابه‌جایی بارگذاری‌ها نسبت به بارگذاری‌های دیگر و ذخیره‌سازی‌ها نسبت به ذخیره‌سازی‌های دیگر داشت و نمی‌توانست بارگذاری‌ها را از ذخیره‌سازی‌های قبلی یا ذخیره‌سازی‌ها را از بارگذاری‌های قبلی عبور دهد. با این حال، در Model 91 تنها ثبات‌های ممیز شناور تغییرنام می‌شدند؛ بنابراین هنگام اجرای محاسبات عدد صحیح همچنان با همان محدودیت‌های WAW و WAR موجود در CDC 6600 مواجه بود. افزون بر این، هر دو سامانه از مشکل استثناهای غیردقیق (Imprecise Exceptions) رنج می‌بردند؛ مشکلی که پیش از فراگیر شدن اجرای خارج از ترتیب و استفادهٔ عملی از آن در سامانه‌هایی غیر از ابررایانه‌ها باید برطرف می‌شد.

 استثناهای دقیق 
برای آن‌که یک سامانه بتواند از استثناهای دقیق (Precise Exceptions) پشتیبانی کند، باید در هنگام وقوع استثنا، وضعیت صحیح و ترتیبیِ اجرای برنامه در دسترس باشد. تا سال ۱۹۸۵، روش‌های گوناگونی برای دستیابی به این هدف توسعه یافته بود که توسط جیمز ئی. اسمیت و اندرو آر. پلشکون توصیف شده‌اند. رایانهٔ CDC Cyber 205 را می‌توان یکی از پیشگامان این حوزه دانست؛ زیرا هنگام وقوع وقفهٔ حافظهٔ مجازی، کل وضعیت پردازنده ــ از جمله اطلاعات مربوط به دستورهایی که اجرای آن‌ها به‌طور کامل پایان نیافته بود ــ در یک بستهٔ تبادل نامرئی ذخیره می‌شد تا پردازنده بتواند اجرای برنامه را دقیقاً از همان وضعیت از سر بگیرد.

با این حال، برای آن‌که تمامی استثناها دقیق باشند، لازم است روشی برای خنثی‌کردن آثار دستورهای اجراشده وجود داشته باشد. CDC Cyber 990 که در سال ۱۹۸۴ معرفی شد، با استفاده از یک بافر تاریخچه (History Buffer) وقفه‌های دقیق را پیاده‌سازی می‌کرد. این بافر مقادیر قدیمیِ ثبات‌ها را که در اثر اجرای دستورها بازنویسی شده بودند نگهداری می‌کرد و در صورت وقوع استثنا و نیاز به بازگرداندن اجرای برنامه، این مقادیر دوباره بازیابی می‌شدند. اسمیت از طریق شبیه‌سازی نشان داد که افزودن یک بافر بازآرایی (Reorder Buffer)، یا سازوکاری معادل آن، به رایانهٔ Cray-1S تنها حدود ۳ درصد از کارایی اجرای چهارده حلقهٔ نخست مجموعه‌آزمون Livermore (در حالت غیر برداری) می‌کاهد. بخش مهمی از پژوهش‌های دانشگاهی در این زمینه نیز توسط ییل پَت (Yale Patt) و با استفاده از شبیه‌ساز HPSm انجام شد.

در دههٔ ۱۹۸۰ بسیاری از ریزپردازنده‌های اولیهٔ RISC نتایج اجرای دستورها را به‌صورت خارج از ترتیب در ثبات‌ها ثبت می‌کردند؛ رویکردی که معمولاً به بروز استثناهای غیردقیق (Imprecise Exceptions) منجر می‌شد. Motorola 88100 از معدود ریزپردازنده‌های آن دوره بود که با وجود نوشتن نتایج به‌صورت خارج از ترتیب، از مشکل استثناهای غیردقیق رنج نمی‌برد؛ هرچند این پردازنده هر دو نوع استثنای دقیق و غیردقیقِ ممیز شناور را مجاز می‌دانست. در این پردازنده، اجرای دستورها به‌ترتیب آغاز می‌شد، اما برخی از آن‌ها ــ به‌ویژه دستورهای ممیز شناور ــ برای تکمیل اجرا به چرخه‌های بیشتری نیاز داشتند. با این وجود، اجرای تک‌چرخه‌ایِ ساده‌ترین دستورها باعث می‌شد دامنهٔ این مشکل در مقایسه با CDC 6600 به‌مراتب محدودتر باشد.

 جداسازی (Decoupling) 
اسمیت همچنین دربارهٔ روش‌هایی پژوهش کرد که به کمک آن‌ها واحدهای اجرایی مختلف بتوانند با استقلال بیشتری از یکدیگر و نیز از حافظه، بخش واکشی و رمزگشایی دستورها (Front-End) و واحد انشعاب عمل کنند. او این ایده‌ها را در سامانهٔ Astronautics ZS-1 (۱۹۸۸) به کار گرفت. در این معماری، خط لولهٔ مربوط به عملیات عدد صحیح، بارگذاری و ذخیره‌سازی از خط لولهٔ ممیز شناور جدا شده بود و این جداسازی امکان بازآرایی دستورها میان خط لوله‌های مختلف را فراهم می‌کرد. ZS-1 همچنین قادر بود برخی عملیات بارگذاری را پیش از عملیات ذخیره‌سازیِ پیشین اجرا کند.

اسمیت در مقاله‌ای که در سال ۱۹۸۴ منتشر کرد، استدلال نمود که اعمال سازوکار استثناهای دقیق تنها بر خط لولهٔ عدد صحیح و حافظه برای بسیاری از کاربردها کافی است؛ زیرا چنین رویکردی همچنان امکان استفاده از حافظهٔ مجازی را فراهم می‌کند. هر خط لوله دارای یک بافر دستور بود که آن را از واحد رمزگشایی دستورها جدا می‌کرد و بدین ترتیب از توقف بخش جلویی پردازنده جلوگیری می‌شد. همچنین برای مستقل‌تر کردن دسترسی به حافظه از فرایند اجرا، هر یک از دو خط لوله به دو صف آدرس‌پذیر مجهز شده بود که در عمل نوعی تغییرنام محدود ثبات‌ها را پیاده‌سازی می‌کردند.

معماری مشابهی که بر پایهٔ جداسازی اجزا طراحی شده بود، اندکی پیش‌تر در سامانهٔ Culler 7 نیز مورد استفاده قرار گرفته بود. افزون بر این، مجموعه‌دستورهای (ISA) پردازندهٔ ZS-1، همانند معماری POWER که بعدها توسط IBM معرفی شد، اجرای زودهنگام دستورهای انشعاب را تسهیل می‌کرد.

 به ثمر رسیدن پژوهش‌ها 
با معرفی POWER1 در سال ۱۹۹۰، شرکت IBM بار دیگر به استفاده از اجرای خارج از ترتیب روی آورد. این پردازنده نخستین پردازنده‌ای بود که تغییرنام ثبات‌ها را ــ هرچند تنها برای ثبات‌های ممیز شناور ــ با سازوکار استثناهای دقیق ترکیب می‌کرد. POWER1 به جای استفاده از بافر بازآرایی (Reorder Buffer)، از یک فایل ثبات فیزیکی (Physical Register File) بهره می‌برد؛ یعنی مجموعه‌ای از ثبات‌ها که به‌صورت پویا بازنگاشت می‌شد و هم مقادیر تأییدنشده (Uncommitted) و هم مقادیر تأییدشده (Committed) را در خود نگه می‌داشت. با این حال، قابلیت لغو اثر دستورها تنها در واحد انشعاب مورد نیاز بود. این واحد از یک بافر تاریخچه استفاده می‌کرد که IBM آن را «پشتهٔ شمارندهٔ برنامه» (Program Counter Stack) می‌نامید و برای بازگرداندن تغییرات اعمال‌شده بر ثبات‌های شمارنده، پیوند (Link) و وضعیت (Condition) به کار می‌رفت.

با وجود این پیشرفت‌ها، توانایی بازآرایی دستورها در POWER1 همچنان محدود بود؛ حتی در مورد دستورهای ممیز شناور. از آنجا که این پردازنده قادر به بازآرایی عملیات حسابی ممیز شناور نبود و نتایج این عملیات همچنان به ترتیب در دسترس قرار می‌گرفتند، ثبات‌های مقصد آن‌ها نیز تغییرنام نمی‌شدند. همچنین POWER1 فاقد ایستگاه‌های رزرو (Reservation Stations) مورد نیاز برای اجرای خارج از ترتیب چند دستور در یک واحد اجرایی مشترک بود.

یک سال بعد، در مدل ES/9000 Model 900 شرکت IBM، قابلیت تغییرنام برای ثبات‌های همه‌منظوره نیز افزوده شد. این سامانه برای واحد عدد صحیح دوگانه دارای ایستگاه‌های رزرو شش‌ورودی بود؛ به‌گونه‌ای که در هر چرخه، از میان شش دستور آماده، حداکثر دو دستور می‌توانستند انتخاب و اجرا شوند. واحد ممیز شناور نیز از شش ورودی مشابه بهره می‌برد. سایر واحدها از صف‌های سادهٔ FIFO استفاده می‌کردند. حداکثر فاصلهٔ بازآرایی در این سامانه به ۳۲ دستور می‌رسید.

در سال ۱۹۹۱، پردازندهٔ A19 از خانوادهٔ رایانه‌های بزرگ (Mainframe) سری A شرکت Unisys نیز عرضه شد. ادعا می‌شد که این سامانه از اجرای خارج از ترتیب پشتیبانی می‌کند و یکی از تحلیلگران صنعت رایانه فناوری به‌کاررفته در A19 را سه تا پنج سال جلوتر از رقبای آن زمان توصیف کرده است.

 رواج گسترده 
نخستین پردازنده‌های سوپراسکالر تک‌تراشه‌ای، از جمله Intel i960CA در سال ۱۹۸۹، از روش زمان‌بندی ساده‌ای مبتنی بر اسکوربورد (Scoreboarding) استفاده می‌کردند؛ روشی که پیش‌تر حدود یک‌چهارم قرن قبل در CDC 6600 به کار گرفته شده بود. در فاصلهٔ سال‌های ۱۹۹۲ تا ۱۹۹۶، با افزایش تعداد ترانزیستورهای قابل استفاده در پردازنده‌ها، پیشرفت سریعی در فناوری‌های اجرای خارج از ترتیب رخ داد و این فناوری از سامانه‌های پیشرفته به رایانه‌های شخصی نیز راه یافت.

پردازندهٔ Motorola 88110 که در سال ۱۹۹۲ معرفی شد، از یک بافر تاریخچه برای بازگرداندن وضعیت دستورها استفاده می‌کرد. در این پردازنده، عملیات بارگذاری (Load) می‌توانست پیش از عملیات ذخیره‌سازی (Store) قبلی اجرا شود. همچنین هنگامی که دستورهای ذخیره‌سازی یا انشعاب در انتظار آغاز اجرا بودند، دستورهای بعدی از انواع دیگر می‌توانستند بدون توقف از تمامی مراحل خط لوله، از جمله مرحلهٔ بازنوشت (Writeback)، عبور کنند. ظرفیت ۱۲ ورودی بافر تاریخچه، حداکثر فاصلهٔ بازآرایی دستورها را محدود می‌کرد.

پردازندهٔ PowerPC 601 که در سال ۱۹۹۳ عرضه شد، نسخه‌ای تکامل‌یافته از معماری RISC Single Chip بود که خود ساده‌شده‌ای از POWER1 به شمار می‌رفت. این پردازنده اجازه می‌داد دستورهای انشعاب و ممیز شناور از دستورهای عدد صحیحی که قبلاً در صف دستورهای واکشی‌شده قرار گرفته بودند پیشی بگیرند. چهار ورودی پایینی این صف به‌طور مداوم برای بررسی امکان ارسال دستورها به واحدهای اجرایی (Dispatch) پایش می‌شد. همچنین در صورت وقوع خطای نهانگاه (Cache Miss)، عملیات بارگذاری و ذخیره‌سازی می‌توانستند بازآرایی شوند. در این معماری تنها ثبات‌های پیوند (Link Register) و شمارنده (Count Register) قابلیت تغییرنام داشتند.

در پاییز ۱۹۹۴، شرکت NexGen و همچنین IBM با همکاری موتورولا، قابلیت تغییرنام ثبات‌های همه‌منظوره را به پردازنده‌های تک‌تراشه‌ای آوردند. پردازندهٔ Nx586 شرکت NexGen نخستین پردازندهٔ خانوادهٔ x86 بود که از اجرای خارج از ترتیب پشتیبانی می‌کرد و می‌توانست تا ۱۴ ریزعملیات (Micro-operations) را در بازآرایی نگه دارد. پردازندهٔ PowerPC 603 نیز هم ثبات‌های همه‌منظوره و هم ثبات‌های ممیز شناور را تغییرنام می‌کرد. در این طراحی، هر یک از چهار واحد اجرایی غیرانشعابی می‌توانست یک دستور را در انتظار اجرای خود نگه دارد، بدون آنکه جریان دستورها در سایر واحدها متوقف شود. یک بافر بازآرایی پنج‌ورودی نیز اجازه می‌داد حداکثر چهار دستور از یک دستورِ هنوز اجرا نشده پیشی بگیرند. همچنین به کمک یک بافر ذخیره‌سازی (Store Buffer)، عملیات بارگذاری می‌توانست پیش از یک عملیات ذخیره‌سازیِ قبلی به نهانگاه دسترسی پیدا کند.

پردازندهٔ PowerPC 604 که در سال ۱۹۹۵ معرفی شد، نخستین پردازندهٔ تک‌تراشه‌ای بود که از بازآرایی در سطح واحدهای اجرایی بهره می‌برد. سه واحد از شش واحد اجرایی آن دارای ایستگاه‌های رزرو دوورودی بودند که اجازه می‌دادند دستور جدیدتر پیش از دستور قدیمی‌تر اجرا شود. ظرفیت بافر بازآرایی این پردازنده ۱۶ دستور بود. همچنین یک صف بارگذاری چهارورودی و یک صف ذخیره‌سازی شش‌ورودی برای مدیریت بازآرایی عملیات بارگذاری و ذخیره‌سازی در هنگام وقوع خطای نهانگاه در نظر گرفته شده بود.

پردازندهٔ HAL SPARC64 که در سال ۱۹۹۵ عرضه شد، از نظر ظرفیت بازآرایی از ES/9000 Model 900 فراتر رفت. این پردازنده دارای سه ایستگاه رزرو هشت‌ورودی برای واحدهای عدد صحیح، ممیز شناور و تولید آدرس بود و علاوه بر آن، یک ایستگاه رزرو دوازده‌ورودی برای عملیات بارگذاری و ذخیره‌سازی داشت. این ساختار امکان بازآرایی گسترده‌تری را برای دسترسی به حافظه و نهانگاه نسبت به پردازنده‌های پیشین فراهم می‌کرد. در هر لحظه تا ۶۴ دستور می‌توانستند در وضعیت بازآرایی‌شده قرار داشته باشند.

پردازندهٔ Pentium Pro نیز در سال ۱۹۹۵ یک ایستگاه رزرو یکپارچه (Unified Reservation Station) معرفی کرد. ظرفیت ۲۰ ریزعملیاتی این ایستگاه امکان بازآرایی بسیار انعطاف‌پذیری را فراهم می‌ساخت و یک بافر بازآرایی ۴۰ ورودی از آن پشتیبانی می‌کرد. در این پردازنده، عملیات بارگذاری می‌توانستند هم از عملیات بارگذاری قبلی و هم از عملیات ذخیره‌سازی قبلی پیشی بگیرند و زودتر اجرا شوند.

با گسترش به‌کارگیری کامل اجرای خارج از ترتیب در پردازنده‌های R10000 شرکت SGI/MIPS و PA-8000 از معماری HP PA-RISC در سال ۱۹۹۶، نرخ عملیِ اجرای دستورها در هر چرخه (Instructions Per Cycle) بیش از پیش افزایش یافت. در همان سال، پردازنده‌های Cyrix 6x86 و AMD K5 نیز فناوری‌های پیشرفتهٔ بازآرایی دستورها را به رایانه‌های شخصی رایج وارد کردند.

از زمانی که معماری DEC Alpha در سال ۱۹۹۸ و با پردازندهٔ Alpha 21264 به اجرای خارج از ترتیب مجهز شد، هسته‌های پردازشی خارج از ترتیبِ با کارایی بالا عملاً از نظر عملکرد توسط هسته‌های درون‌ترتیب (In-order) قابل رقابت نبودند. تنها استثناهای قابل توجه، Itanium 2 حاصل همکاری HP و Intel و همچنین IBM POWER6 بودند؛ هرچند POWER6 نیز دارای یک واحد ممیز شناور خارج از ترتیب بود. سایر پردازنده‌های قدرتمند مبتنی بر اجرای درون‌ترتیب، از جمله UltraSPARC III و UltraSPARC IV شرکت Sun و نیز رایانه‌های بزرگ IBM، به تدریج از رقبای خارج از ترتیب خود عقب ماندند. سامانه‌های اصلی IBM حتی برای دومین بار قابلیت اجرای خارج از ترتیب را کنار گذاشتند و تا نسل z10 همچنان از معماری درون‌ترتیب استفاده می‌کردند.

در سال‌های بعد، برخی پردازنده‌های بزرگ مبتنی بر اجرای درون‌ترتیب تمرکز خود را بر افزایش کارایی از طریق چندریسمانی (Multithreading) قرار دادند. با این حال، در نهایت خانوادهٔ SPARC T و پردازنده‌های Xeon Phi نیز به ترتیب در سال‌های ۲۰۱۱ و ۲۰۱۶ به سمت اجرای خارج از ترتیب حرکت کردند.

تقریباً تمامی پردازنده‌های مورد استفاده در تلفن‌های همراه و سایر کاربردهای کم‌هزینه و کم‌مصرف تا حدود سال ۲۰۱۰ همچنان مبتنی بر اجرای درون‌ترتیب بودند. نخستین تغییر مهم در این روند با معرفی هستهٔ Scorpion شرکت Qualcomm در خانوادهٔ Snapdragon رخ داد که از فاصلهٔ بازآرایی ۳۲ دستور پشتیبانی می‌کرد. اندکی بعد نیز هستهٔ Arm Cortex-A9 جایگزین Cortex-A8 شد.

در رایانه‌های شخصی ارزان‌قیمت مبتنی بر معماری x86، ریزمعماری درون‌ترتیب Bonnell که در نسل‌های اولیهٔ Intel Atom به کار رفته بود، ابتدا با ریزمعماری Bobcat شرکت AMD به چالش کشیده شد و سپس در سال ۲۰۱۳ جای خود را به ریزمعماری خارج از ترتیب Silvermont داد.

با وجود مزایای عملکردی اجرای خارج از ترتیب، پیچیدگی زیاد این روش دستیابی هم‌زمان به کمترین مصرف انرژی، کمترین هزینه و کوچک‌ترین اندازهٔ تراشه را دشوار می‌کند. به همین دلیل، اجرای درون‌ترتیب همچنان در بسیاری از ریزکنترل‌گرها (Microcontrollers)، سامانه‌های تعبیه‌شده (Embedded Systems) و همچنین هسته‌های کم‌مصرف مورد استفاده در تلفن‌های همراه ــ مانند Arm Cortex-A55 و Cortex-A510 در پیکربندی big.LITTLE ــ کاربرد گسترده‌ای دارد.