کلید افزایش کارایی در پردازنده‌ها؛ بافر مقصد انشعاب یا BTB
برنامه‌های کاربردی دنیای واقعی دربرگیرندهٔ برنامه‌های مرکز داده‌هاData center applications شامل حجم عظیمی از دستوراتInstructions هستند. این حجم زیاد از دستورات، شامل تعداد قابل‌توجهی دستورات انشعابBranch instruction هستند که موجب میشود عدم برخوردMiss در حافظۀ نهان دستوراتI-Cache بالا برود.
حافظۀ نهان یا Cache چیست؟
حافظۀ نهان یک حافظۀ موقتی است که داده‌های پرکاربردی که در یک بازهٔ زمانی (به این نزدیکی زمانی دسترسی‌ها، محلیت زمانی یا Temporal locality می‌گویند) یا در یک بازهٔ مکانی (از حیث قرارگیری در حافظه، به این نزدیکی، Spatial locality می‌گویند) را در خود نگه می‌دارد تا نیاز به دسترسی کندتر و طولانی‌تر به حافظهٔ اصلی (RAM) را کمتر کند و سرعت اجرای دستورات بالاتر برود.
برای غلبه بر این میزان بالای عدم برخورد در حافظۀ نهان دستورات، راه‌حل‌های متنوعی ارائه شده‌است که یکی از این راه‌ها FDIPFetch Directed Instruction Prefetching است. این واحد در پردازنده‌ها، با پیش‌واکشیPrefetching دستورهای آينده، آن‌ها را به حافظۀ نهان دستورات برده تا در زمان اجرای واقعی آماده باشند. نکتهٔ حائز اهمیت در پیش‌واکشی دستورات، توجه به دستورات انشعاب شرطیConditional Branch و غیرشرطیUnconditional Branch است.
برای دستورات شرطی، طبعاً بخشی تحت‌عنوان پیش‌بینی‌کنندهٔ انشعابBranch Predictor نیاز داریم که بتواند رخ‌دادنTaken یا ندادنNot Taken دستور انشعاب شرطی را پیش‌بینی کند. این پیش‌بینی می‌تواند به انتخاب دستورات و آدرس‌های درست در پیش‌واکشی کمک کند، به گونه‌ای که پیش‌بینی اشتباه می‌تواند مجموعهٔ دستورات اشتباهی را وارد حافظۀ نهان دستورات کند و موجب آلودگی حافظۀ نهان شود.
همچنین در هر دو نوع دستورات انشعاب شرطی و غیرشرطی، نیاز است مقصد انشعاب برای پیش‌واکشی مشخص باشد تا بدانیم که پس از این دستور پرش، به چه آدرسی می‌رویم. به واحدی که مقصد (احتمالی) دستورات انشعاب را در خود نگهداری می‌کند، بافر مقصد انشعابBranch Target Buffer (BTB) می‌گویند.
همان‌طور که مشخص است، توانایی پیش‌واکشی FDIP کاملاً وابسته به دقت BTB است. از آن‌جا که ظرفیت BTB محدود است و نمی‌توان مقصد تمام دستورات انشعاب را در آن ذخیره کرد، شاهد عدم برخورد در BTB خواهیم بود. افزودن حجم BTB یک پردازنده، در هنگام طراحی پردازنده‌ها دچار محدودیت است، زیرا میزان حافظهٔ ایستاStatic Random-Access Memory روی تراشه محدود است؛ که این حافظه به‌عنوان حافظهٔ نهان دستورات و داده‌ها و همچنین BTB استفاده میشود.
در زمانی که این متن نوشته میشود، پردازنده با بیشترین اندازهٔ BTB در بازار، IBM z15 است که دارای یک BTB دولایه، شامل لایهٔ اولL1 (Level 1) و لایهٔ دومL2 (Level 2) است. شاید در نگاه اول 144K مدخل برای BTB پردازنده کافی به نظر برسد که شاید این‌طور هم هست! اما باید توجه شود که قیمت این بزرگ‌رایانهMainframe شرکت IBM هم بسیار چشم‌گیر است!
در سیستم‌های رایج و ارزان‌تر اندازهٔ BTB در حدود زیر ۱۰k مدخل است که شاید برای برنامه‌های چند مگابایتی (یا گیگابایتی) حال حاضر، کافی نباشد. پیش از بیان روش‌هایی برای عملکرد بهتر BTB و برخوردHit بیشتر، به ساختار کلی BTB و FDIP اشاره می‌کنم.
همان‌طور که در تصویر ۱ مشخص است، تاریخچۀ دستوراتHistory و PCProgram Counter وارد واحد پیش‌بینی انشعابBranch Prediction Unit (BPU) میشود که BTB در این واحد قرار دارد.
برای دستوراتی نظیر call و return ها از پشتهٔ آدرس بازگشتReturn Address Stack استفاده میشود و همچنین برای پرش‌هایی که مقصد آن‌ها از ثبات‌هاRegister یا حافظه خوانده میشود (که اصطلاحاً به آن‌ها پرش غیرمستقیم می‌گوییم)، از IJPIndirect Jump Predictor استفاده میشود که خود این بخش، برای پیش‌بینی مقصد از حافظۀ نهان مقصدTarget Cache یا تاریخچۀ مسیرPath History بهره می‌برد.
این اطلاعات به همراه اطلاعات BTB و نتیجهٔ پیش‌بینی دستور انشعاب به یک مالتی‌پلکسرMultiplexer وارد شده و نتیجهٔ نهایی به‌عنوان آدرس بعدی برای پیش‌واکشی وارد صف مقصد واکشیFetch Target Queue (FTQ) میشود.
در نهایت این آدرس به واحد واکشی دستورInstruction Fetch Unit (IFU) وارد شده تا واکشی/پیش‌واکشی صورت گیرد.
ساختار کلی BTB؛ بافر مقصد انشعاب چه چیزهایی را نگه می‌دارد؟
BTB اطلاعاتی دربارهٔ دستورات انشعابی که حداقل یک‌بار واکشی شده‌اند نگه می‌دارد که شامل نوع دستور انشعاب (پرش مستقیمDirect jump، پرش غیر مستقیمIndirect jump، call، return و …)، مقصد دستور انشعابBranch Target Instruction، بیت‌های برچسبTag که نقشی مشابه بیت‌های برچسب در حافظه‌های نهان را ایفا می‌کنند و برخی اطلاعات دیگر مانند سیاست جایگزینیReplacement Policy است. دسترسی به BTB درست مانند حافظهٔ نهان است. بنابراین پیش‌بینی میشود که مانند حافظه‌های نهان، از سیاست‌های جایگزینی برای قراردادن دستور انشعاب جدید، در صورت پر بودن جایگاه‌های مناسب برای ذخیره‌سازی آن دستور انشعاب در BTB استفاده کنیم.
در زمینهٔ بهبود عملکرد BTB چه کار‌هایی انجام شده‌است؟
یکی از مواردی که برای بهبود نرخ برخورد در BTBها انجام شده‌است، ابداع الگوریتم‌هاAlgorithms و سیاست‌های جایگزینی است. برخی از این سیاست‌های جایگزینی با استفاده از تاریخچۀ دستورات گذشته، میزان اهمیت دستورات انشعاب را با روابطی که ارائه می‌دهند، محاسبه کرده و در هنگام جایگزینی، دستورات انشعاب با اهمیت کمتر (آن‌هایی که کمتر دسترسی می‌خورند) را از BTB خارج کرده و دستور جدید را جایگزین می‌کنند.
همچنین عده‌ای با پیاده‌سازی الگوریتم بهینهٔ BeladyBelady's anomaly algorithm بر روی تاریخچهٔ دستورات گذشته، قصد دارند عملکردی نیمه‌بهینهSub-optimal داشته باشند. برای مطالعهٔ بیشتر دربارۀ جزئیات این روش، به مقالهٔ Thermometer مراجعه کنید.
علاوه بر ارائۀ سیاست‌های جایگزینی نوین، روش‌های دیگری نظیر تغییر ساختار کلی BTBها می‌تواند مؤثر باشد. برای مثال، یکی از اقدامات انجام‌شده در این زمینه، چندلایه کردن BTBهاست. همانند حافظۀ نهان چندلایه (شامل L1L1 (Level 1) و L2L2 (Level 2)) یا صفحه‌بندی چندسطحیmulti-level paging، امکان پیاده‌سازی BTB چندلایه نیز وجود دارد.
در این روش، یک BTB اولیهMain BTB داریم که offset آدرس مقصد دستور انشعاب را مشخص می‌کند و شمارۀ صفحۀ آدرس مقصد، توسط یک Page BTB تعیین میشود. بدین صورت که یک اشاره‌گر از مدخل مربوطه در BTB اولیه به یک سطر در Page BTB وجود دارد که شمارۀ صفحهٔ مربوط به آدرس مقصد را نگهداری می‌کند. حتی امکان پیاده‌سازی این ساختار با بیش از دو لایه نیز وجود دارد. اما از آن‌جا که دسترسی چندلایه احتمالاً زمان بیشتری نسبت به دسترسی به یک لایه صرف می‌کند، این روش باید با در نظر گرفتن سربارOverhead ناشی از افزایش زمان دسترسی و همچنین قابلیت استفادۀ بهینه از حافظۀ on-chip SRAM برای BTB پردازنده و ذخیره‌سازی تعداد بیشتری دستور انشعاب، به‌عنوان یک مبادلهTrade-Off انتخاب شود.
(یادآوری: SRAM که عمدتاً برای حافظۀ نهان سیستم‌ها استفاده میشود، از DRAMDRAM (Dynamic Random-Access Memory) مورد استفاده در حافظۀ اصلی سریع‌تر است، اما هزینهٔ بالاتری نیز دارد.)
روش دیگر برای تغییر ساختار BTB، استفاده از BTBهای مجموعه-انجمنیSet-Associative است. پیش از پرداختن به این موضوع، به تصویر ۳ توجه کنید.
همان‌طور که مشاهده میشود، فرض کردیم که یک سیستم با آدرس‌دهی بایت‌به‌بایتByte-Addressable داریم که فضای آدرس‌دهی آن، شامل آدرس‌های ۴۸ بیتی است. دستورات این سیستم، مضرب ۴ بایت4-Byte-Aligned هستند و این یعنی دو بیت سمت راست آدرس آن‌ها صفر است.
همان‌طور که در این مثال مشاهده میشود، آدرس مقصد دستور انشعاب در بیت‌های ۶ تا ۴۸ با آدرس خود دستور انشعاب یکسان است و این یعنی در صورت داشتن Branch PC نیازی به نگهداری ۴۳ بیت پرارزش نیست. همچنین دو بیت کم‌ارزش نیز همیشه صفر هستند. بنابراین شاید صرفاً نگه‌داشتن بیت‌های ۳ تا ۵ برای مقصد دستور انشعاب کافی باشد.
این ایده ناشی از یک قاعدهٔ کلی در مهندسی نرم‌افزار امروزی است: توابع کوچک محبوب‌تراند! و این موجب میشود که آدرس مقاصد دستور انشعاب، عموماً به آدرس خود دستور انشعاب نزدیک باشد و صرفاً در تعدادی بیت کم‌ارزش متفاوت باشد. بنابراین نیازی به نگهداری کل آدرس مقصد نیست.
طبق این موضوع، می‌توان از BTBهای مجموعه-انجمی با اندازهٔ راه‌هایWay متفاوت استفاده کرد، که هر دستور انشعاب را در راه با اندازهٔ مناسب قرار می‌دهیم. برای مثال ممکن است فاصلهٔ مقصد یک دستور انشعاب از خود دستور، به اندازه‌ای باشد که صرفاً ۱۸ بیت offset (به جز دو بیت کم‌ارزش که همیشه برابر صفر هستند) کافی باشد، در این صورت این دستور انشعاب می‌تواند در راه‌های با شمارهٔ ۶ و ۷ قرار گیرد.
برای اطلاع بیشتر از روش ارائه‌شده در مقالهٔ مربوطه، به مقالهٔ BTB-X مراجعه کنید!
ادامه راه
شاید به نظر برسد که میزان ایده‌ها و نوآوری‌های انجام‌شده بر روی BTBها به اندازه‌ای بوده که نیاز فعلی پردازنده‌ها و بارکاری‌هاWorkloads را برطرف کند، اما با توجه به رشد روزافزون برنامه‌های کاربردی اجراشده بر روی مرکزهای داده، توجه به استفاده از تکنیک‌های جدید برای بهبود عملکرد BTB همچنان ضروری به نظر می‌رسد. بنابراین پژوهشگران همچنان به دنبال راهکارهای جدید برای بهبود عملکرد BTB خواهند بود و این موضوع، می‌تواند زمینهٔ پژوهشی خوبی برای علاقه‌مندان به معماری کامپیوتر باشد!
منابع
-
Thermometer: Profile-Guided BTB Replacement for Data CenterApplications
-
A Storage-Effective BTB Organization for Servers