چگونه ضرب ماتریس را در عمل تسریع می‌کند

واقعیت‌های عملی: سلسله‌مراتب حافظه در پردازنده‌های تجاری

پردازنده‌های واقعی مفاهیم کش و حافظه پوشش‌داده‌شده در سراسر این فصل را با پارامترهای مشخص و به‌دقت انتخاب‌شده پیاده‌سازی می‌کنند. هم ARM Cortex-A53 و هم Intel Core i7، که پیش‌تر در این مجموعه درباره طراحی پایپ‌لاین بحث شد، همچنین به‌طور معناداری در سلسله‌مراتب حافظه‌شان متفاوت‌اند: طرح‌های موبایل‌محور مانند Cortex-A53 معمولاً از اندازه‌های کش کوچک‌تر در هر سطح برای صرفه‌جویی در توان و مساحت die استفاده می‌کنند، در حالی که طرح‌های کارایی‌محور مانند Core i7 از کش‌های بزرگ‌تر و چندسطحی، اغلب سه سطح عمیق، استفاده می‌کنند تا میانگین زمان دسترسی حافظه را به قیمت توان و مساحت تراشه اضافه به حداقل برسانند.

به‌کارگیری مفاهیم کش: Cache Blocking برای ضرب ماتریس

ضرب ماتریس، که پیش‌تر در این مجموعه درباره موازی‌سازی زیرکلمه‌ای و موازی‌سازی سطح دستور بحث شد، همچنین می‌تواند به‌طور خاص برای سلسله‌مراتب حافظه با استفاده از تکنیکی به نام Cache Blocking (که Tiling نیز نامیده می‌شود) بهینه شود. به‌جای پردازش یک ماتریس بزرگ کامل ردیف‌به‌ردیف، که می‌تواند به‌طور مکرر داده کش‌شده مفید را به‌دلیل capacity miss هایی که پیش‌تر در این مجموعه بحث شد تخلیه کند، ماتریس به زیربلوک‌های کوچک‌تری تقسیم می‌شود که به‌طور خاص برای جا شدن درون کش اندازه‌گیری شده‌اند.

بدون blocking:
ماتریس بزرگ ردیف‌به‌ردیف دسترسی می‌شود،
داده‌ای که بعداً هنوز مورد نیاز است به‌طور مکرر تخلیه می‌شود،
که باعث بسیاری از capacity miss ها می‌شود

با blocking:
ماتریس به زیربلوک‌های کوچک‌تری تقسیم می‌شود
که کاملاً درون کش جا می‌شوند،
هر زیربلوک به‌طور کامل پردازش می‌شود
پیش از حرکت به بعدی

با اطمینان از اینکه داده هر زیربلوک در طول پردازش آن در کش باقی می‌ماند، cache blocking به‌طور قابل‌توجهی تعداد capacity miss ها را کاهش می‌دهد، و مستقیماً اصول محلیت معرفی‌شده پیش‌تر در این مجموعه را به یک بار کاری محاسباتی واقعی و به‌طور گسترده استفاده‌شده اعمال می‌کند.

مغالطات رایج درباره سلسله‌مراتب حافظه

• فرض اینکه کش بزرگ‌تر همیشه بهتر است — همان‌طور که پیش‌تر درباره مبادلات کارایی کش بحث شد، کش بزرگ‌تر زمان hit و هزینه را افزایش می‌دهد حتی در حالی که capacity miss را کاهش می‌دهد.
• فرض اینکه حافظه مجازی و کشینگ سیستم‌های نامرتبطی هستند — همان‌طور که پیش‌تر در چارچوب یکپارچه پوشش‌دهنده جای‌گذاری، شناسایی، جایگزینی، و سیاست نوشتن نشان داده شد، آن‌ها دقیقاً به همان پرسش‌های زیربنایی پاسخ می‌دهند.
• فرض اینکه یک cache miss همیشه همان مقدار زمان هزینه دارد — همان‌طور که پیش‌تر درباره سه نوع miss بحث شد، هزینه واقعی به‌شدت به این بستگی دارد که کدام سطح از سلسله‌مراتب حافظه باید در نهایت درخواست را برآورده کند.

دام‌های رایج در کد حساس به حافظه

• نوشتن کد با محلیت مکانی ضعیف، مانند دسترسی به عناصر آرایه در یک الگوی غیرپی‌درپی، که بهره کشینگ مبتنی‌بر‌بلوک که پیش‌تر در این مجموعه بحث شد را از بین می‌برد.
• نادیده گرفتن خطر load-use که پیش‌تر در این مجموعه بحث شد هنگام استدلال درباره اینکه چرا کد سنگین از نظر حافظه گاهی با وجود یک الگوریتم به‌ظاهر کارآمد، بدتر از انتظار عمل می‌کند.
• نادیده گرفتن سربار انسجام کش چندهسته‌ای، که پیش‌تر در این مجموعه بحث شد، هنگام نوشتن کد موازی که به‌طور مکرر داده مشترک را در سراسر هسته‌ها تغییر می‌دهد.

جمع‌بندی فصل: تصویر کامل سلسله‌مراتب حافظه

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