ابهام‌زدایی حافظه

**ابهام‌زدایی حافظه** مجموعه‌ای از تکنیک‌هایی است که توسط ریزپردازنده‌هایی با کارایی بالا با اجرای خارج از نظم استفاده می‌شود که دستورالعمل‌های دسترسی به حافظه (بارگیری و ذخیره‌سازی) را خارج از نظم برنامه اجرا می‌کنند. مکانیسم‌های انجام ابهام‌زدایی حافظه، که با استفاده از منطق دیجیتال در هسته ریزپردازنده پیاده‌سازی می‌شوند، وابستگی‌های واقعی بین عملیات حافظه را در زمان اجرا شناسایی می‌کنند و به پردازنده اجازه می‌دهند زمانی که وابستگی نقض شده است، بازیابی شود. آن‌ها همچنین وابستگی‌های حافظه جعلی را حذف می‌کنند و با امکان اجرای بی‌نظم بارها و ذخیره‌ها ، موازی‌سازی بیشتر در سطح دستورالعمل را امکان‌پذیر می‌سازند.

## پیش زمینه

### وابستگی ها
هنگام تلاش برای اجرای دستورات بدون نظم، یک ریزپردازنده باید وابستگی های واقعی بین دستورالعمل ها را رعایت کند. به عنوان مثال، یک وابستگی واقعی ساده را در نظر بگیرید:
 1: $1، $2، $3 # R1 add در خط 2 به دستور `add` در خط 1 وابسته است زیرا ثبات R1 یک عملوند منبع عملیات جمع در خط 2 است. `add` در خط 2 نمی تواند اجرا شود تا زمانی که `add` در خط 1 کامل شود. در این حالت، وابستگی **ثابت** است و به راحتی توسط یک ریزپردازنده تعیین می شود، زیرا منابع و مقصدها ثبت هستند. ثبت مقصد دستور `add` در خط 1 ( `R1` ) بخشی از رمزگذاری دستورالعمل است، و بنابراین می تواند توسط ریزپردازنده در اوایل مرحله رمزگشایی خط لوله تعیین شود. به طور مشابه، رجیسترهای منبع دستور `add` در خط 2 ( `R1` و `R4` ) نیز در خود دستورالعمل کدگذاری می شوند و در رمزگشایی تعیین می شوند. برای احترام به این وابستگی واقعی، منطق زمان‌بندی ریزپردازنده، این دستورالعمل‌ها را به ترتیب صحیح صادر می‌کند (اول دستورالعمل 1، سپس دستورالعمل 2) تا زمانی که دستورالعمل 2 به آنها نیاز دارد، نتایج 1 در دسترس باشد.

عوارض زمانی ایجاد می شود که وابستگی به طور ایستا قابل تعیین نباشد. چنین وابستگی‌های غیراستاتیکی با دستورالعمل‌های حافظه (بارگیری‌ها و ذخیره‌سازی‌ها) به وجود می‌آیند، زیرا مکان عملوند ممکن است به‌طور غیرمستقیم به‌عنوان یک عملوند رجیستر مشخص شود، نه اینکه مستقیماً در خود دستورالعمل مشخص شود.
 1: ذخیره $1، 2 ($2) # Mem[R2+2] $30 و `$31` آماده هستند: مقادیر `$30` و `$31` مدت‌ها پیش محاسبه شده‌اند و تغییر نکرده‌اند. با این حال، فرض کنید `$27` آماده نیست: ارزش آن هنوز در حال محاسبه با دستور `div` (تقسیم عدد صحیح) است. در نهایت، فرض کنید که رجیسترهای `$30` و `$31` دارای مقدار یکسانی هستند و بنابراین همه بارها و ذخیره‌های قطعه به کلمه حافظه یکسانی دسترسی دارند.

در این شرایط، دستور `sw $27, 0($30)` در خط 2 آماده اجرا نیست، اما دستور `lw $08, 0($31)` در خط 3 آماده است. اگر پردازنده اجازه دهد دستور `lw` قبل از `sw` اجرا شود، بار یک مقدار قدیمی را از سیستم حافظه می خواند. با این حال، باید مقداری را که توسط `sw` نوشته شده بود، می خواند. بارگذاری و ذخیره خارج از نظم برنامه اجرا شد، اما یک وابستگی حافظه بین آنها وجود داشت که نقض شد.

به طور مشابه، فرض کنید که ثبت نام `$26` آماده *است* . دستور `sw $26, 0($30)` در خط 4 نیز آماده اجرا است و ممکن است قبل از `lw $08, 0($31)` در خط 3 اجرا شود. اگر این اتفاق بیفتد، دستور `lw $08, 0($31)` مقدار *اشتباهی* را از سیستم حافظه می‌خواند، زیرا دستورالعمل ذخیره‌سازی بعدی مقدار آن را قبل از اجرای بار در آنجا نوشته است.

### مشخص کردن وابستگی های حافظه
وابستگی به حافظه در سه نوع ظاهر می شود:

* وابستگی **های Read-After-Write** (RAW): وابستگی های RAW که به عنوان وابستگی های واقعی نیز شناخته می شوند، زمانی ایجاد می شوند که یک عملیات بارگذاری مقداری را از حافظه می خواند که توسط آخرین عملیات ذخیره سازی قبلی در همان آدرس تولید شده است.
* وابستگی‌های **Write-After-Read** (WAR): وابستگی‌های WAR زمانی به وجود می‌آیند که یک عملیات ذخیره مقداری را در حافظه می‌نویسد که بار قبلی آن را می‌خواند.
* وابستگی‌های WAW **بعد از نوشتن** : که به عنوان وابستگی‌های خروجی نیز شناخته می‌شوند، وابستگی‌های WAW زمانی ایجاد می‌شوند که دو عملیات ذخیره مقادیر را در یک آدرس حافظه بنویسند.

سه وابستگی در بخش کد قبلی نشان داده شده است (برای وضوح بازتولید شده است):
 1: div $27, $20
 2: sw  $27, 0($30)
 3: lw  $08, 0($31)
 4: sw  $26, 0($30)
 5: lw  $09, 0($31)

* دستورالعمل `lw $08, 0($31)` در خط 3 دارای وابستگی RAW به دستورالعمل `sw $27, 0($30)` در خط 2 است و `lw $09, 0($31)` در خط 5 دارای وابستگی RAW به `sw $26, 0($30)` است. `sw $26, 0($30)` دستورالعمل در خط 4. هر دو دستورالعمل بارگیری آدرس حافظه را که فروشگاه های قبلی نوشته بودند می خواند. فروشگاه‌ها جدیدترین تولیدکنندگان آن آدرس حافظه بودند و بارها مقدار آن آدرس حافظه را می‌خوانند.
* دستورالعمل `sw $26, 0($30)` در خط 4 دارای وابستگی به WAR به `lw $08, 0($31)` در خط 3 است زیرا آدرس حافظه را می نویسد که بار قبلی از آن خوانده می شود.
* دستورالعمل `sw $26, 0($30)` در خط 4 دارای وابستگی WAW به دستورالعمل `sw $27, 0($30)` در خط 2 است زیرا هر دو فروشگاه در یک آدرس حافظه می نویسند.

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

### اجتناب از وابستگی به WAR و WAW
مقادیر دستورالعمل‌های ذخیره‌سازی هنگام اجرا به سیستم حافظه (در ریزپردازنده‌های مدرن، حافظه پنهان CPU ) متعهد نمی‌شوند. درعوض، دستورالعمل‌های موجودی، از جمله آدرس حافظه و داده‌های ذخیره، در **[[صف (نوع داده انتزاعی)|صف]] موجودی** بافر می‌شوند تا به نقطه بازنشستگی برسند. هنگامی که یک موجودی تنها می شود، *سپس* ارزش خود را در سیستم حافظه می نویسد. با این کار از مشکلات وابستگی WAR و WAW که در قطعه کد بالا نشان داده شده است، جلوگیری می شود، جایی که یک بار قبلی مقدار نادرستی را از سیستم حافظه دریافت می کند، زیرا ذخیره بعدی اجازه داشت قبل از بارگذاری قبلی اجرا شود.

علاوه بر این، بافر کردن موجودی تا زمان تنها شدن، به پردازنده‌ها این امکان را می‌دهد تا دستورالعمل‌های ذخیره را که از دستورالعملی پیروی می‌کنند که ممکن است استثنایی ایجاد کند (مانند بار آدرس نامناسب، تقسیم بر صفر و غیره) یا یک دستورالعمل شاخه مشروط که جهت آن (گرفته شده یا نشده است) را اجرا کنند. گرفته شده) هنوز مشخص نیست. اگر دستور تولید استثنا اجرا نشده باشد یا جهت شاخه به اشتباه پیش‌بینی شده باشد، پردازنده دستورالعمل‌ها را در یک «مسیر اشتباه» واکشی و اجرا کرده است. این دستورات اصلا نباید اجرا می شد. شرط استثنا باید قبل از اجرای هر یک از دستورالعمل‌های گمانه‌زنی رخ می‌داد، یا اینکه شاخه باید جهت دیگری را طی می‌کرد و باعث می‌شد دستورالعمل‌های مختلف واکشی و اجرا شوند. پردازشگر هنگام کشف استثنا یا پیش‌بینی نادرست شاخه، باید هر نتیجه‌ای را که از دستورالعمل‌های بد مسیر و به‌طور فرضی اجرا شده است، «دور» کند. مشکل ذخیره ها این است که هر ذخیره ای که در مسیر بد یا اشتباه پیش‌بینی شده است، نباید مقادیر خود را به سیستم حافظه متعهد می‌کرد. اگر ذخیره ها مقادیر خود را متعهد می‌کردند، «دور انداختن» commit غیرممکن بود و وضعیت حافظه دستگاه توسط داده‌های یک دستورالعمل فروشگاهی که نباید اجرا می‌شد خراب می‌شد.

بنابراین، بدون ذخیره بافر، ذخیره‌ها نمی‌توانند اجرا شوند تا زمانی که تمام دستورالعمل‌های احتمالی ایجاد استثنا قبلی اجرا شوند (و استثنایی ایجاد نکرده باشند) و تمام جهت‌های شاخه قبلی شناخته شده باشند. وادار کردن فروشگاه‌ها به صبر کردن تا زمانی که دستورالعمل‌ها و استثناهای شعبه شناخته شوند، به طور قابل توجهی تهاجمی خارج از دستور را کاهش می‌دهد و ILP ( موازی سطح دستورالعمل ) و عملکرد را محدود می‌کند. با استفاده از بافر فروشگاه، فروشگاه‌ها می‌توانند قبل از دستورالعمل‌های شعبه‌ای که باعث استثنا هستند یا حل نشده اجرا کنند، داده‌های خود را در صف ذخیره بافر کنند، اما مقادیر خود را تا زمان تنها شدن تحویل ندهند. این از ذخیره‌سازی در مسیرهای پیش‌بینی نادرست یا بد از تخصیص مقادیر خود به سیستم حافظه جلوگیری می‌کند و در عین حال افزایش ILP و عملکرد را از اجرای کامل ذخیره های خارج از نظم ارائه می‌دهد.

### ذخیره برای بارگیری حمل و نقل
بافر کردن فروشگاه‌ها تا زمان جدا شدن از وابستگی‌های WAW و WAR جلوگیری می‌کند، اما مسئله جدیدی را معرفی می‌کند. سناریوی زیر را در نظر بگیرید: یک انبار آدرس و داده های خود را در صف انبار اجرا و بافر می کند. چند دستورالعمل بعد، یک بار اجرا می شود که از همان آدرس حافظه ای که فروشگاه به تازگی برای آن نوشته است خوانده می شود. اگر بار داده های خود را از سیستم حافظه بخواند، مقدار قدیمی را می خواند که توسط ذخیره قبلی بازنویسی شده بود. داده های به دست آمده توسط بار نادرست خواهد بود.

برای حل این مشکل، پردازنده ها از تکنیکی به نام **حمل و نقل ذخیره به بار** با استفاده از صف ذخیره استفاده می کنند. علاوه بر بافر کردن فروشگاه‌ها تا زمان بازنشستگی، صف فروشگاه هدف دوم را نیز دنبال می‌کند: ارسال داده‌ها از فروشگاه‌های تکمیل‌شده اما هنوز بازنشسته ("در پرواز") به بارهای بعدی. به جای یک صف ساده FIFO ، صف فروشگاه در واقع یک حافظه آدرس پذیر محتوا (CAM) است که با استفاده از آدرس حافظه جستجو می شود. هنگامی که یک بار اجرا می شود، صف فروشگاه را برای فروشگاه های درون پرواز به همان آدرسی که به طور منطقی به ترتیب برنامه زودتر هستند، جستجو می کند. اگر یک ذخیره منطبق وجود داشته باشد، بار به جای سیستم حافظه، مقدار داده خود را از آن ذخیره می‌گیرد. اگر هیچ ذخیره مطابقی وجود نداشته باشد، بار به طور معمول به سیستم حافظه دسترسی پیدا می کند. هر فروشگاه مشابه قبلی باید قبلاً بازنشسته شده باشد و ارزش های خود را متعهد شده باشد. این تکنیک به بارها اجازه می دهد تا در صورتی که انبار تولیدکننده آنها تکمیل شده باشد اما هنوز تنها نشده باشد، داده های صحیح را به دست آورند.

ممکن است چندین ذخیره در آدرس حافظه بارگذاری در صف انبار وجود داشته باشد. برای رسیدگی به این مورد، صف انبار با اولویت کدگذاری می شود تا *آخرین* ذخیره ای را انتخاب کند که منطقاً زودتر از بارگذاری به ترتیب برنامه باشد. تعیین اینکه کدام ذخیره «جدیدترین» است، می‌تواند با چسباندن نوعی مُهر زمانی به دستورالعمل‌ها در حین واکشی و رمزگشایی، یا به طور متناوب با دانستن موقعیت نسبی (شیار) بار با توجه به قدیمی‌ترین و جدیدترین ذخیره های موجود در داخل به دست آید.

### نقض وابستگی RAW

#### تشخیص نقض وابستگی RAW
CPUهای خارج از نظم مدرن می توانند از تعدادی تکنیک برای تشخیص نقض وابستگی RAW استفاده کنند، اما همه تکنیک ها نیاز به ردیابی بارهای حین پرواز از زمان اجرا تا زمان تنها شدن دارند. هنگامی که یک بار اجرا می شود، به سیستم حافظه و/یا صف ذخیره برای بدست آوردن مقدار داده آن دسترسی پیدا می کند و سپس آدرس و داده های آن تا زمان بازنشستگی در **صف بارگذاری** بافر می شوند. صف بارگذاری از نظر ساختار و عملکرد مشابه صف فروشگاه است و در واقع در برخی از پردازنده ها ممکن است با صف فروشگاه در یک ساختار واحد به نام **صف ذخیره بار** یا **LSQ ترکیب** شود. تکنیک های زیر برای تشخیص نقض وابستگی RAW استفاده می شود یا پیشنهاد شده است:

#### بارگیری صف جستجوی CAM
با استفاده از این تکنیک، صف بارگذاری، مانند صف فروشگاه، یک CAM است که با استفاده از آدرس دسترسی حافظه جستجو می‌شود و همه بارهای حین پرواز را ردیابی می‌کند. هنگامی که یک فروشگاه اجرا می شود، صف بارگذاری را برای بارهای تکمیل شده از همان آدرسی که به طور منطقی به ترتیب برنامه بعدی هستند، جستجو می کند. اگر چنین بار تطبیقی وجود داشته باشد، باید قبل از ذخیره اجرا شده باشد و بنابراین یک مقدار نادرست و قدیمی را از سیستم حافظه/صف فروشگاه خوانده باشد. هر دستورالعملی که از مقدار بار استفاده کرده باشد، از داده های بد نیز استفاده کرده است. برای بازیابی در صورت تشخیص چنین تخلفی، بار به عنوان "نقض" در بافر بازنشستگی علامت گذاری می شود. فروشگاه در صف فروشگاه و بافر بازنشستگی باقی می ماند و به طور معمول بازنشسته می شود و در هنگام بازنشستگی ارزش خود را به سیستم حافظه متعهد می کند. با این حال، هنگامی که بار نقض شده به نقطه بازنشستگی می رسد، پردازنده خط لوله را شستشو می دهد و اجرا را از دستورالعمل بارگذاری مجدد شروع می کند. در این مرحله، تمام فروشگاه های قبلی مقادیر خود را به سیستم حافظه متعهد کرده اند. اکنون دستور بارگذاری مقدار صحیح را از سیستم حافظه می خواند و هر دستورالعمل وابسته با استفاده از مقدار صحیح دوباره اجرا می شود.

این تکنیک نیاز به جستجوی انجمنی صف بار در هر اجرای فروشگاه دارد، که انرژی مدار را مصرف می‌کند و می‌تواند ثابت کند که مسیر زمان‌بندی دشواری برای صف‌های بار بزرگ است. با این حال، به هیچ درگاه حافظه اضافی ( کش ) یا ایجاد تضاد منابع با بارگذاری‌ها یا ذخیره‌های دیگری که در حال اجرا هستند نیاز ندارد.

#### ابهام زدایی در دوران بازنشستگی
با این تکنیک، دستورالعمل های بارگذاری که خارج از دستور اجرا شده اند، دوباره اجرا می شوند (آنها به سیستم حافظه دسترسی پیدا می کنند و برای بار دوم مقدار را از آدرس خود می خوانند) زمانی که به نقطه بازنشستگی می رسند. از آنجایی که بار اکنون دستورالعمل بازنشستگی است، هیچ وابستگی به هیچ دستورالعملی که هنوز در حال پرواز است ندارد. تمام فروشگاه های پیش از آن مقادیر خود را به سیستم حافظه متعهد کرده اند، بنابراین هر مقداری که از سیستم حافظه خوانده می شود، تضمین می شود که درست باشد. مقدار خوانده شده از حافظه در زمان اجرای مجدد با مقدار بدست آمده در هنگام اجرای بار برای اولین بار مقایسه می شود. اگر مقادیر یکسان باشد، مقدار اولیه صحیح بوده و تخلفی رخ نداده است. اگر مقدار اجرای مجدد با مقدار اصلی متفاوت باشد، نقض RAW رخ داده است و خط لوله باید شسته شود زیرا دستورالعمل های وابسته به بار از مقدار نادرستی استفاده کرده اند.

این تکنیک از نظر مفهومی ساده‌تر از جستجوی صف بارگذاری است، و CAM دوم و جستجوی پرقدرت آن را حذف می‌کند (صف بار اکنون می‌تواند یک صف ساده FIFO باشد). از آنجایی که بار باید درست قبل از بازنشستگی مجدداً به سیستم حافظه دسترسی پیدا کند، دسترسی باید بسیار سریع باشد، بنابراین این طرح بر یک کش سریع متکی است. مهم نیست که حافظه نهان چقدر سریع باشد، اما دومین دسترسی به سیستم حافظه برای هر دستور بار خارج از دستور، تأخیر بازنشستگی دستورالعمل را افزایش می دهد و تعداد کل دسترسی های کش را که باید توسط پردازنده انجام شود، افزایش می دهد. با استفاده مجدد از یک درگاه کش موجود می‌توان دسترسی حافظه پنهان بازنشستگی اضافی را برآورده کرد. با این حال، این باعث ایجاد اختلاف منبع پورت با بارگذاری‌ها و ذخیره‌های دیگر در پردازنده می‌شود که در تلاش برای اجرا هستند، و در نتیجه ممکن است باعث کاهش عملکرد شود. از طرف دیگر، یک پورت کش اضافی را می توان فقط برای رفع ابهام بار اضافه کرد، اما این باعث افزایش پیچیدگی، قدرت و مساحت کش می شود. برخی از کارهای اخیر (Roth 2005) راه‌هایی را برای فیلتر کردن بسیاری از بارها از اجرای مجدد نشان داده‌اند، اگر مشخص باشد که هیچ نقض وابستگی RAW ممکن است رخ نداده باشد. چنین تکنیکی به چنین تأخیر و اختلاف منابع کمک می کند یا از بین می برد.

یک مزیت جزئی این طرح (در مقایسه با جستجوی صف بارگذاری) این است که نقض وابستگی RAW را علامت‌گذاری نمی‌کند و در صورتی که فروشگاهی که باعث نقض وابستگی RAW شده باشد (آدرس فروشگاه با یک پرواز در حین پرواز مطابقت داشته باشد، نقض وابستگی RAW را علامت‌گذاری نمی‌کند و خط لوله را شروع نمی‌کند. load's address) دارای یک مقدار داده است که با مقدار داده موجود در حافظه پنهان مطابقت دارد. در طرح جستجوی load-queue، یک مقایسه داده اضافی باید به سخت افزار جستجوی صف بار اضافه شود تا از چنین هموار شدن خط لوله جلوگیری شود.

#### اجتناب از نقض وابستگی RAW
CPUهایی که به طور کامل از اجرای بی‌نظم بارها و ذخیره‌سازی‌ها پشتیبانی می‌کنند، باید بتوانند نقض وابستگی RAW را در صورت وقوع شناسایی کنند. با این حال، بسیاری از CPUها با اجبار همه بارها و ذخیره‌ها به اجرای منظم، یا با پشتیبانی از فرم محدودی از اجرای بار/ذخیره خارج از نظم، از این مشکل جلوگیری می‌کنند. این رویکرد عملکرد کمتری را در مقایسه با پشتیبانی از اجرای کامل بار/ذخیره خارج از سفارش ارائه می‌کند، اما می‌تواند پیچیدگی هسته اجرایی و حافظه‌های پنهان را به میزان قابل توجهی کاهش دهد.

گزینه اول، مرتب کردن بارها و ذخیره‌ها، از وابستگی‌های RAW اجتناب می‌کند، زیرا امکان اجرای بار قبل از ذخیره‌سازی تولیدکننده و به دست آوردن داده‌های نادرست وجود ندارد. امکان دیگر این است که بارها و ذخیره سازی ها را به طور موثر به دو عملیات تقسیم کنید: تولید آدرس و دسترسی به حافظه پنهان. با این دو عملیات مجزا اما مرتبط، CPU می‌تواند به بارها و ذخیره‌ها اجازه دسترسی به سیستم حافظه را تنها زمانی بدهد که همه بارها و ذخیره‌های قبلی آدرس خود را در LSQ تولید و بافر کرده باشند. پس از تولید آدرس، دیگر هیچ وابستگی مبهمی وجود ندارد زیرا همه آدرس‌ها شناخته شده‌اند، و بنابراین بارهای وابسته تا زمانی که ذخیره‌های مربوطه آنها تکمیل نشود، اجرا نمی‌شوند. این طرح هنوز هم اجازه می دهد تا برخی از "خارج از نظم" - عملیات تولید آدرس برای هر بارگذاری در پرواز و فروشگاه می تواند بدون ترتیب اجرا شود، و هنگامی که آدرس ها تولید شدند، دسترسی های حافظه پنهان برای هر بار یا فروشگاه می تواند انجام شود. به هر ترتیبی که به وابستگی های واقعی (اکنون شناخته شده) احترام می گذارد، اتفاق می افتد.

## مسائل اضافی

### پیش بینی وابستگی به حافظه
پردازنده‌هایی که به‌طور کامل از اجرای بار/ذخیره خارج از دستور پشتیبانی می‌کنند، می‌توانند از یک تکنیک مرتبط دیگر، به نام پیش‌بینی وابستگی حافظه ، برای پیش‌بینی وابستگی‌های واقعی بین بارها و ذخیره‌ها *قبل از* مشخص شدن آدرس‌هایشان استفاده کنند. با استفاده از این تکنیک، پردازنده می‌تواند از اجرای بارهایی که پیش‌بینی می‌شود به یک فروشگاه در حین پرواز وابسته هستند، قبل از تکمیل آن فروشگاه جلوگیری کند، از نقض وابستگی RAW جلوگیری کند و در نتیجه از فلاش خط لوله و جریمه عملکردی که متحمل می‌شود جلوگیری کند. برای جزئیات بیشتر به مقاله پیش بینی وابستگی حافظه مراجعه کنید.

## جستارهای وابسته
* خط لوله دستورالعمل
* اجرای خارج از دستور
* حافظه پنهان CPU
* پیش‌بینی وابستگی به حافظه

## منابع
رده:معماری رایانه