انسجام مبتنی بر دایرکتوری

انسجام مبتنی بر دایرکتوری مکانیزمی برای رسیدگی به مشکل انسجام کش در حافظه مشترک توزیع شده (DSM) است.

معرفی

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

در زیر چند تا از مزایا و معایب پروتکل انسجام کش مبتنی بر دایرکتوری آورده شده‌است:

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

با توجه به بحث فوق، واضح است که استفاده از سیستم‌های مبتنی بر گذرگاه برای سیستم‌های نسبتاً کوچک جذاب تر به نظر می‌رسد. با این حال، سیستم‌های مبتنی بر دایرکتوری زمانی حیاتی می‌شوند که مقیاس سیستم افزایش یابد و تعداد گره‌ها افزایش یابد؛ بنابراین هنگام مقایسه بین طرح‌های انسجام حافظه کش مبتنی بر دایرکتوری و مبتنی بر گذرگاه یک نوع تجارت کردن وجود دارد.

تاریخ

ایده سیستم‌های انسجام کش مبتنی بر دایرکتوری مدت‌ها پیش آغاز شد.

ایده DASH (معماری دایرکتوری برای حافظه مشترک) اولین بار توسط C.K. Tang^[۱] در اواسط دهه ۱۹۷۰ ارائه شد. با این حال، استفاده از آن برای انسجام حافظه کش چند سال بعد، به ویژه در سال ۱۹۷۸، زمانی که محققان دانشگاه استنفورد اولین نسخه از این سیستم‌های انسجام را به نام Stanford DASH پیشنهاد کردند، در مقاله ای^[۲] که این سیستم را با مشکلات و پیشرفت‌ها با چنین طرح‌هایی توصیف می‌کرد، پیشنهاد شد. در کنار این رویکرد، چندین تلاش برای ارائه یک سیستم مقیاس پذیر انجام شد. به عنوان مثال، BBN Butterfly^[۳] که در سال ۱۹۸۵ معرفی شد، و IBM PR3^[۴] که در سال ۱۹۸۷ معرفی شد، نمونه‌هایی از سیستم‌های چند پردازنده ای مقیاس پذیر هستند. با این حال، هر دوی این سیستم‌ها دارای یک اشکال هستند. برای مثال، BBN Butterfly حافظه کش ندارد. به‌طور مشابه، IBM PR3 انسجام کش سخت‌افزاری را ارائه نمی‌کند، که عملکرد هر دوی این طرح‌ها را محدود می‌کند، به‌ویژه زمانی که از پردازنده‌های با کارایی بالا استفاده می‌شود.^[۵]

محدودیت‌های سایر رقبا انتخاب سیستم‌های مبتنی بر DASH را هنگام طراحی سیستم‌های انسجام حافظه کش و سایر سیستم‌هایی که نیاز به مقیاس پذیری در گره‌های مبتنی بر حافظه کش دارند، آسان‌تر کرده‌است. در سال ۱۹۸۵، جیمز آرچیبالد^[۶] و ژان لوپ بائر از دانشگاه واشینگتن مقاله^[۷] ای منتشر کردند که یک تنوع اقتصادی تر، قابل گسترش و مدولارتر از رویکرد «دایرکتوری جهانی» از نظر استفاده از سخت‌افزار در طرح را پیشنهاد می‌کردند.

در سال ۱۹۹۲، دانیل لنوسکی از دانشگاه استنفورد مقاله ای^[۸] منتشر کرد که در آن پیشرفت‌هایی در پروتکل‌های انسجام کش برای سیستم‌های مبتنی بر دایرکتوری پیشنهاد شد. در مقاله ای در سال ۱۹۹۶، او طراحی SGI Origin 2000 را معرفی کرد، خانواده ای از رایانه‌های سرور که از انسجام کش مبتنی بر دایرکتوری استفاده می‌کنند. Origin 3000^[۹] در ژوئیه ۲۰۰۰ معرفی شد.

پروتکل‌ها

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

نمودار کلی طرح انسجام مبتنی بر دایرکتوری که عملگرها و پیام‌های مختلف را نشان می‌دهد.

همان‌طور که در نمودار جریان داده نشان داده شده‌است، عملگرهایی که در یک سیستم حافظه مشترک توزیع شده که پروتکل انسجام مبتنی بر دایرکتوری را پیاده‌سازی می‌کند، درگیر هستند عبارتند از:

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

تصویر ۱: نمودار انتقال حالت برای پروتکل مبتنی بر دایرکتوری

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

گره دایرکتوری به عنوان یک نقطه سریال عمل می‌کند و تمام ارتباطات از طریق این گره جهت حفظ صحت و درستی هدایت می‌شوند.

گره دایرکتوری

یک گره دایرکتوری وضعیت کلی یک بلوک کش را در کل سیستم کش برای همه پردازنده‌ها پیگیری می‌کند. می‌تواند در سه حالت باشد:

جستارهای وابسته

• پروتکل انسجام
• پروتکل MSI
• آرایه بیتی
• حافظه مشترک توزیع شده
• کش اسنوپی

منابع

1. Tang, C.K. "Cache system design in the tightly coupled multiprocessor system". AFIPS '76 Proceedings of the June 7–10, 1976, National Computer Conference and Exposition.
2. "The Directory-Based Cache Coherence Protocol for the DASH Multiprocessor" (PDF). Computer Systems Laboratory.
3. Schmidt, G.E. "The Butterfly Parallel Processor". In Proc. Of ICS.
4. "The IBM research parallel processor prototype PR3: Introduction and architicture". In Proceeding of the 1985 International Conference of Parallel Processing.
5. "Design of Scalable Shared-Memory Multiprocessors: The DASH approach". Computer System Laboratory, Stanford University.
6. "James Archibald". ece.byu.edu. Archived from the original on 2 August 2017. Retrieved 2016-11-15.
7. "An economical solution to the cache coherence problem". ISCA '84 Proceedings of the 11th Annual International Symposium on Computer Architecture.
8. Lenoski, Daniel; Laudon, James; Gharachorloo, Kourosh; Weber, Wolf-Dietrich; Gupta, Anoop; Hennessy, John; Horowitz, Mark; Lam, Monica S. (1992-03-01). "The Stanford Dash Multiprocessor". Computer. 25 (3): 63–79. doi:10.1109/2.121510. ISSN 0018-9162.
9. Corp., Silicon Graphics International. "Support Home Page". support1-sgi.custhelp.com. Archived from the original on 13 April 2018. Retrieved 2016-11-16.