الگوریتم توماسولو
الگوریتم توماسولو یک الگوریتم سخت‌افزاری معماری کامپیوتر برای زمان‌بندی پویا دستورالعمل‌ها است که امکان اجرای خارج از نظم را می‌دهد و استفاده کارآمدتر از واحدهای اجرایی متعدد را ممکن می‌سازد. این الگوریتم توسط رابرت توماسولو در IBM در سال 1967 توسعه یافت و برای اولین بار در واحد ممیز شناور IBM System/360 Model 91 پیاده سازی شد.
نوآوری‌های اصلی الگوریتم توماسولو شامل تغییر نام رجیستر در سخت‌افزار، ایستگاه‌های رزرو برای همه واحدهای اجرایی، و یک گذرگاه داده مشترک (CDB) است که مقادیر محاسبه‌شده بر روی آن به تمام ایستگاه‌های رزروی که ممکن است به آنها نیاز داشته باشند، پخش می‌شود. این پیشرفت‌ها امکان اجرای موازی بهتر دستورالعمل‌ها را فراهم می‌آورد که در غیر این صورت در الگوریتم اسکوربوردینگ یا الگوریتم های قدیمی تر باعث متوقف شدن خط لوله پردازنده می شدند.
رابرت توماسولو در سال 1997 جایزه اکرت-ماچلی را برای کارش بر روی این الگوریتم دریافت کرد.
مفاهیم پیاده سازی
در این قسمت مفاهیم لازم برای اجرای الگوریتم توماسولو آمده است:
گذرگاه مشترک داده
گذرگاه مشترک داده (CDB) ایستگاه های رزرو را مستقیماً به واحدهای عملکردی متصل می کند. به گفته توماسولو این گذرگاه "اولویت را حفظ می کند در حالی که همزمانی را تشویق می کند". این دو اثر مهم دارد:
- واحدهای عملکردی می‌توانند به نتیجه هر عملیاتی بدون درگیر کردن یک ثبات ممیز شناور دسترسی داشته باشند، و به واحدهای متعددی که در انتظار نتیجه هستند اجازه می‌دهند بدون انتظار برای حل اختلاف برای دسترسی به پورت‌های خواندن فایل ثبات، ادامه دهند.
- تشخیص هازارد و کنترل اجرا توزیع شده است. ایستگاه های رزرو زمان اجرای یک دستورالعمل را به جای یک واحد تشخیص هازارد اختصاصی کنترل می کنند.
دستور دستورالعمل
دستورالعمل‌ها به‌طور متوالی صادر می‌شوند تا تأثیرات دنباله‌ای از دستورالعمل‌ها، مانند استثنائات مطرح‌شده توسط این دستورالعمل‌ها، به همان ترتیبی که بر روی یک پردازنده به ترتیب رخ می‌دهد، بدون توجه به این واقعیت که آنها خارج از نظم اجرا می‌شوند، رخ می‌دهند.
تغییر نام ثبات ها
الگوریتم توماسولو از تغییر نام ثبات برای اجرای صحیح اجرای خارج از نظم استفاده می کند. همه ثبات های ایستگاه‌های رزرو و ثبات های همه منظوره دارای یک مقدار واقعی یا یک مقدار جانشین هستند. اگر در مرحله صدور، مقدار واقعی برای ثبات مقصد در دسترس نباشد، در ابتدا از مقدار جانشین استفاده می شود. مقدار جانشین برچسبی است که نشان می دهد کدام ایستگاه رزرو مقدار واقعی را تولید می کند. هنگامی که کار واحد به پایان رسید و نتیجه را در CDB پخش کرد، مکان جانشین با مقدار واقعی جایگزین می شود.
هر واحد کاربردی دارای یک ایستگاه رزرو واحد است. ایستگاه های رزرو اطلاعات مورد نیاز برای اجرای یک تک دستور، از جمله عملیات و عملوندها را در خود نگهداری می کنند. واحد عملکردی زمانی که آزاد باشد و زمانی که تمام عملوندهای منبع مورد نیاز برای یک دستورالعمل واقعی هستند، پردازش را آغاز می کند.
استثناها
از نظر عملی، ممکن است استثناهایی وجود داشته باشد که اطلاعات وضعیت کافی در مورد یک استثنا در دسترس نباشد، در این صورت پردازنده ممکن است استثنای خاصی را مطرح کند که به آن استثنا "غیر دقیق" می‌گویند. استثناهای نادقیق نمی توانند در پیاده سازی های به ترتیب رخ دهند، زیرا وضعیت پردازنده فقط به ترتیب برنامه تغییر می کند (به استثناهای خط لوله RISC مراجعه کنید).
برنامه‌هایی که استثناهای «دقیق» را تجربه می‌کنند، زمانی که دستورالعمل خاصی که استثنا را می‌توان تعیین کرد، می‌توانند در نقطه ای که استثنا صادر شده است دوباره راه‌اندازی یا دوباره اجرا شوند. با این حال، مواردی که استثناهای «غیر دقیق» را تجربه می‌کنند، معمولاً نمی‌توانند مجدداً راه‌اندازی یا اجرا شوند، زیرا سیستم نمی‌تواند دستورالعمل خاصی را که استثنا را به وجود آورده است، تعیین کند.
همچنین ببینید
- بافر سفارش مجدد (ROB)
- موازی سازی در سطح دستورالعمل (ILP)
منابع
- ↑ Tomasulo, Robert Marco (Jan 1967). "An Efficient Algorithm for Exploiting Multiple Arithmetic Units". IBM Journal of Research and Development. IBM. 11 (1): 25–33. doi:10.1147/rd.111.0025. ISSN 0018-8646.
- ↑ "Robert Tomasulo – Award Winner". ACM Awards. ACM. Retrieved 8 December 2014.
مطالعه بیشتر
- Savard, John J. G. (2018) [2014]. "Pipelined and Out-of-Order Execution". quadibloc. Archived from the original on 2018-07-03. Retrieved 2018-07-16.
پیوند به بیرون
- Dynamic Scheduling - Tomasulo's Algorithm توسط Wayback Machine (بایگانی‌شده دسامبر ۲۵, ۲۰۱۷) راه برگشت
- شبیه سازی اپلت جاوا HASE از الگوریتم توماسولو