انسجام حافظه نهان بر مبنای دایرکتوری
در مهندسی کامپیوتر، انسجام حافظه نهان بر مبنای دایرکتوری (انگلیسی: Directory-based cache coherence) نوعی مکانیسم انسجام حافظه نهان است که در آن از دایرکتوری‌ها به جای استفاده در جاسوسی گذرگاه، در مدیریت حافظه پنهان استفاده می‌شود. منظور از گذرگاه، مجموعه سیم‌هایی است که داده‌ها و دستورها را با سرعت از میان واحد پردازشگر مرکزی، حافظه و دستگاه‌های جانبی رایانه عبور می‌دهند. روش‌های جاسوسی گذرگاه به دلیل استفاده از پخش کردن، مقیاس غیرقابل قبولی دارند. از این روش‌ها می‌توان برای بررسی عملکرد کامپیوتر و مقیاس‌پذیری سیستم‌های دایرکتوری استفاده کرد.[۱]
قالب برداری تمام‌بیت ویرایش
در قالبِ بُرداری تمام‌بیت،[الف] برای هر خط حافظه نهان در دسترس در حافظه، یک بیت تعبیه می‌شود. برای بررسی این که یک خط حافظه نهان توسط هر پردازنده منفرد ذخیره شده است یا خیر، آن بیت مورد استفاده قرار می‌گیرد.[۲] قالب برداری تمام‌بیت ساده‌ترین ساختار برای پیاده‌سازی است، اما کمترین مقیاس پذیری را دارد.[۱] سرور اس‌جی‌آی اوریجین ۲۰۰۰[ب] ترکیبی از بردارهای تمام‌بیت و بیت‌درشت[پ] را بسته به تعداد پردازنده‌ها مورد استفاده قرار می‌دهد.[۳]
هر ورودی دایرکتوری باید شامل ۱ بیت ذخیره‌شده به‌ازای هر پردازنده و هر خطِ کَش باشد. همچین علاوه بر آن بیت، بیت‌های دیگری برای بررسی وضعیت دایرکتوری در هر ورودی وجود دارد. این نوع طراحی نیازمند تمام پردازنده‌ها به ازای تعداد خطوط حافظه نهان است. همچنین برای محاسبه نسبت سربار ذخیره‌سازی داریم:
(اندازه بلوک کش × ۸) / (تعداد پردازنده)
می‌توان مشاهده کرد که سربار دایرکتوری با استفاده از تعداد پردازنده‌ها به صورت خطی ارزیابی می‌شود. این نوع ارزیابی برای سیستم‌هایی با تعداد پردازنده‌های کم به‌صرفه است. در حالی که برای سیستم‌های سنگین با پردازنده‌های زیاد منجر به هزینهٔ زیادی می‌شود.
برای مثال در سیستمی با بلوک‌های ۳۲ بایتی و ۱۰۲۴ پردازنده نسبت سربار ذخیره‌سازی برابر با ۴۰۰٪ می‌شود.[۲]
قالب برداری بیت‌درشت ویرایش
قالب برداری بیت‌درشت[ت] مشابه قالب برداری تمام‌بیت است، با این تفاوت که دایرکتوری به‌جای ردیابی یک بیت به ازای هر پردازنده برای هر خط حافظه پنهان، چندین پردازنده را در گره‌های مختلف دسته‌بندی می‌کند.
همچنین در دایرکتوری اطلاعات دیگری نیز وجود دارد. مانند این که آیا یک خط حافظه پنهان در یک گره ذخیره می‌شود یا خیر. این امر باعث صرفه‌جویی در هزینه‌ها می‌شود و همچنین میزان تردد در مجموعه سیم‌هایی که داده‌ها و دستورها را با سرعت از میان واحد پردازشگر مرکزی، حافظه و دستگاه‌های جانبی رایانه عبور می‌دهند، بهبود می‌یابد؛[۳] بنابراین نسبت سربار یکسان است، فقط تعداد پردازنده‌ها با تعداد گروه‌های پردازنده جایگزین می‌شود. هنگامی که یک درخواست گذرگاه برای یک خط حافظه پنهان ارسال می‌شود، دایرکتوری سیگنال را به جای حافظه پنهانی (که آن را شامل می‌شود)، به هر پردازنده در گره ارسال می‌کند و منجر به ایجاد شلوغی بیش از حد لازم در گره‌هایی فاقد آن اطلاعات می‌شود.[۲]
در این حالت، ورودی دایرکتوری از ۱ بیت برای گروهی از پردازنده‌ها و برای هر خط حافظه پنهان استفاده می‌کند. مشابه مثال برای قالب برداری تمام‌بیت، اگر ۱ بیت را برای ۸ پردازنده به‌عنوان یک دسته در نظر بگیریم، سربار ذخیره‌سازی ۵۰٪ خواهد بود ((۳۲x۸)/۱۲۸). این یک پیشرفت قابل توجه در مقایسه با قالب برداری تمام‌بیت است.
قالب دایرکتوری پراکنده ویرایش
حافظه نهان در یک زمان خاص فقط بخش کمی از بلوک‌ها را در حافظهٔ اصلی ذخیره می‌کند. از این رو بیشتر ورودی‌های دایرکتوری متعلق به بلوک‌هایی است که در حافظهٔ نهان ذخیره نشده‌اند. در قالب دایرکتوری پراکنده،[ث] میزان هدر رفت تنها از طریق ذخیره کردن بلوک‌های حافظهٔ نهان در دایرکتوری کاهش می‌یابد.[۲] پردازنده‌ای با ۶۴ کیلوبایت حافظهٔ پنهان، بلوک‌های ۳۲ بایتی و ۴ مگابایت حافظهٔ اصلی را در نظر داشته باشید. حداکثر تعداد ورودی‌هایی که دایرکتوری می‌تواند در قالب دایرکتوری پراکنده داشته باشد ۲۰۴۸ است. اگر دایرکتوری یک ورودی را به تمام بلوک‌های حافظه اختصاص دهد، تعداد ورودی‌های دایرکتوری ۱۳۱٬۰۷۲ خواهد شد. در نتیجه فرمت دایرکتوری از لحاظ ذخیره‌سازی به‌صرفه نیست و بهینه‌سازی آن امری بسیار قابل توجه است.
قالب درخت دودویی با اعداد متعادل ویرایش
در قالب درخت دودویی با اعداد متعادل،[ج] دایرکتوری غیرمتمرکز است و بین حافظه‌های نهانی که حداقل در یک بلوک حافظه مشترک هستند، توزیع می‌شود. حافظه‌های نهان متفاوت که در یک بلوک حافظه اشتراک دارند به شکل یک درخت دودویی مرتب شده‌اند. اولین حافظهٔ نهانی که به یک بلوک حافظه دسترسی پیدا می‌کند، گره ریشه نام می‌گیرد. هر بلوک حافظه دربرگیرندهٔ اطلاعات گره ریشه (HEAD) و شمارشگر بخش‌های مشترک (SC) است. بخش SC دارای حافظه‌های پنهانی است که بلوک را به اشتراک می‌گذارند. هر ورودی حافظهٔ نهان دارای تعدادی نشانگر به حافظه‌های نهانی بعدی است که از طریق هسته‌های دیگر قابل دسترسی هستند و به نام‌های L-CHD و R-CHD شناخته می‌شوند. این دایرکتوری شامل یک شرط اساسی می‌شود و آن شرط این است که درخت دودویی باید از لحاظ عددی دارای تعادل باشد؛ یعنی تعداد گره‌های زیردرخت سمت چپ باید مساوی با یا بیشتر از تعداد گره‌های زیردرخت سمت راست باشد. تمام زیردرخت‌ها نیز باید از شرط تعادل پیروی کنند.[۴]
قالب دایرکتوری زنجیره‌ای ویرایش
حافظه قالب دایرکتوری زنجیره‌ای،[چ] اشاره‌گر دایرکتوری را روی آخرین حافظهٔ نهانی قرار می‌دهد که به بلوک دسترسی داشته‌است. همچنین هر حافظهٔ نهان نشانگر حافظهٔ نهان قبلی که به بلوک دسترسی داشته است را در بر می‌گیرد. در نتیجه زمانی که پردازنده درخواست افرودن داده را به یک بلوک در حافظه ارسال می‌کند، پردازنده مواردی را باطل می‌کند. در این دایرکتوری وقتی که یک بلوک حافظهٔ نهان با بلوک دیگری جایگزین می‌شود، باید لیست پیوندی را پیمایش کنیم تا دایرکتوری را تغییر دهیم که این مورد باعث افزایش تأخیر می‌شود. به منظور جلوگیری از این امر، فهرست‌های پیوندی دوطرفه در حال حاضر به‌طور گسترده استفاده می‌شوند که در آن هر کپی حافظهٔ نهان دارای اشاره‌گرهایی به حافظهٔ نهان قبلی و بعدی است که به بلوک دسترسی دارد.[۵]
قالب اشاره‌گر دارای محدودیت ویرایش
قالب اشاره‌گر دارای محدودیت[ح] تعدادی اشاره‌گر را برای مسیریابی پردازنده‌هایی که اطلاعات را در حافظهٔ نهان ذخیره می‌کنند، به‌کار می‌گیرد. زمانی که یک پردازندهٔ جدید بلوک را در حافظهٔ نهان ذخیره می‌کند، یک اشاره‌گر آزاد به آن پردازنده اختصاص داده می‌شود. اگر تعداد اشتراک‌گذاران از تعداد اشاره‌گرهای آزاد بیشر باشد، مشکلاتی به‌وجود می‌آید. چند روش برای رسیدگی به این مشکلات وجود خواهد داشت. یکی از این روش‌ها باطل کردن یکی از اشتراک‌گذارها با استفاده از اشاره‌گر آن برای درخواست‌کنندهٔ جدید است. اما در حالت‌هایی که برای یک بلوک تعداد زیادی خواننده وجود دارد، مانند قفل، این روش می‌تواند پرهزینه باشد. روش دیگر این است که یک استخر جداگانه از اشاره‌گرهای آزاد برای تمامی بلوک‌ها در دسترس باشد. این روش معمولاً مؤثر است، زیرا تعداد بلوک‌های مشترک توسط تعداد زیادی پردازنده معمولاً زیاد نیست.[۲]
یادداشت‌ها ویرایش
منابع ویرایش
- ↑ ۱٫۰ ۱٫۱ Reihnhart, Steven; Basu, Arkaprava; Beckmann, Bradford; Hill, Mark (2013-07-11). "CMP Directory Coherence: One Granularity Does Not Fit All" (PDF).
{{cite journal}}: Cite journal requires|journal=(help) - ↑ ۲٫۰ ۲٫۱ ۲٫۲ ۲٫۳ ۲٫۴ Solihin, Yan (2015-10-09). Fundamentals of Parallel Multicore Architecture. Raleigh, North Carolina: Solihin Publishing and Consulting, LLC. pp. 331–335. ISBN 978-1-4822-1118-4.
- ↑ ۳٫۰ ۳٫۱ Laudon, James; Lenoski, Daniel (1997-06-01). The SGI Origin: a ccNUMA highly scalable serve. Proceedings of the 24th annual international symposium on Computer architecture.
- ↑ Seo, Dae-Wha; Cho, Jung Wan (1993-01-01). "Directory-based cache coherence scheme using number-balanced binary tree". Microprocessing and Microprogramming. 37 (1): 37–40. doi:10.1016/0165-6074(93)90011-9.
- ↑ Chaiken, D.; Fields, C.; Kurihara, K.; Agarwal, A. (1990-06-01). "Directory-based cache coherence in large-scale multiprocessors". Computer. 23 (6): 49–58. CiteSeerX 10.1.1.461.8404. doi:10.1109/2.55500. ISSN 0018-9162.