Реклама

Наш канал:

Таненбаум Э.- Архитектура компьютера. стр.470

Когда запрос приходит в узел 36, он направляется в устройство каталога. Устройство проверяет таблицу из 218 элементов (один элемент на каждую строку кэша) и извлекает элемент 4. На рис. 8.27, в видно, что строка отсутствует в кэше, поэтому устройство вызывает строку 4 из локального ОЗУ, отправляет ее узлу 20 и обновляет элемент каталога 4, показывая, что эта строка находится в кэше узла 20.

А теперь рассмотрим второй запрос, на этот раз для строки 2 из узла 36. На рис. 8.27, в видно, что эта строка находится в кэше узла 82. В этот момент устройство может обновить элемент 2 каталога, показывая, что строка находится теперь в узле 20, затем послать сообщение в узел 82, чтобы строка из него была передана в узел 20, и объявить кэш узла 82 недействительным. Отметим, что передавать многочисленные сообщения приходится в любом мультипроцессоре с общей памятью.

Давайте вычислим, сколько памяти занимают каталоги. Каждый узел содержит 16-мегабайтное ОЗУ и 218 9-разрядных элементов для трассировки этого ОЗУ. Таким образом каталог отнимает примерно 9 х 218 бит от 16 Мбайт, или около 1,76 %, что вполне допустимо. Даже если длина строки кэша составляет 32 байта, потери памяти составят всего 4 %. Если длина строки кэша равна 128 байт, потери окажутся еще ниже — 1 %.

Очевидным недостатком этой схемы является то, что строка может быть кэши-рована только одним узлом. Чтобы строки можно было кэшировать в нескольких узлах, требуется какой-то способ их поиска (например, чтобы объявлять недействительными или обновлять при записи). Возможны различные варианты.

Один из вариантов — предоставить каждому элементу каталога k полей для идентификации других узлов, что позволит кэшировать каждую строку на нескольких узлах (до k узлов). Второй вариант — заменить поле номера узла битовой картой, по одному биту на узел. Здесь нет ограничений на количество копий, но существенно растут непроизводительные затраты. Каталог, содержащий 256 бит для каждой 64-байтной (512-разрядной) строки кэша, требует более 50 % памяти. Третий вариант — хранить в каждом элементе каталога 8-разрядное поле и использовать это поле в качестве заголовка связного списка, объединяющего вместе все копии строки кэша. При такой стратегии требуется дополнительное пространство на каждом узле для указателей связного списка. Кроме того, требуется просматривать список, чтобы в случае необходимости найти все копии. Каждая из трех стратегий имеет свои достоинства и недостатки. На практике используются все три стратегии.

Еще одна проблема данной схемы — как проверять, обновлена исходная память или нет. Если нужно считать строку кэша, которая не изменялась, запрос может быть удовлетворен из основной памяти, и при этом не нужно направлять запрос в кэш. Если же требуется считать измененную строку кэша, запрос должен быть направлен в тот узел, в котором находится эта строка кэша, поскольку только здесь имеется ее действительная копия. Если же разрешается иметь только одну копию строки кэша, как показано на рис. 8.27, то контролировать изменения в строках кэша нет никакого смысла, поскольку любой новый запрос требует передачи сообщения существующей копии, чтобы объявить ее недействительной.