Реклама:

Мультипроцессоры, подобные тому, который изображен на рис. 8.26, плохо поддаются масштабированию, поскольку в них нет кэш-памяти. Каждый раз обращаться к удаленной памяти, чтобы получить доступ к слову, которого нет в локальной памяти, очень расточительно - это весьма негативно сказывается на производительности. Однако с добавлением кэш-памяти возникает проблема согласованности кэшей. Один из способов поддержания согласованности кэшей - обеспечить слежение за системной шиной. Технически это сделать несложно, но когда количество процессоров переваливает за некоторый предел, подобное решение становится нереализуемым. Для создания действительно больших мультипроцессоров нужен совершенно другой подход.

Самый популярный на сегодня подход к построению больших мультипроцессоров, относящихся к системам СС-МиМА, реализован в мультипроцессоре на основе каталога. Основная идея состоит в хранении базы данных с информацией о том, где именно находится каждая строка кэша и каково ее состояние. При обращении к строке кэша в базу данных направляется запрос о том, где эта строка находится и является она "чистой" или "грязной" (модифицированной). Поскольку запрашивать базу данных приходится при выполнении любой команды обращения к памяти, база данных должна поддерживаться высокоскоростным специализированным аппаратным обеспечением, способным обработать запрос за доли шинного цикла.

Чтобы лучше понять, что собой представляет мультипроцессор на основе каталога, рассмотрим в качестве примера систему из 256 узлов, в которой каждый узел состоит из одного процессора и 16-мегабайтного ОЗУ, связанного с процессором локальной шиной. Общий объем памяти составляет 232 байт. Она разделена на 226 строк кэша по 64 байт каждая. Память статически распределена по узлам: адреса 0-16 М располагаются в узле 0, адреса 16-32 М - в узле 1 и т. д. Узлы связаны коммуникационной сетью (рис. 8.27, а). Сеть может быть реализована в виде решетки, гиперкуба или иметь другую топологию. Каждый узел содержит элементы каталога для 218 64-байтных строк кэша, образующих 224 байт памяти. На данный момент мы предполагаем, что строка может содержаться не более чем в одном кэше.

СОМА-мультипроцессоры

Рис. 8.27. Мультипроцессор на основе каталога, содержащий 256 узлов (а); разбиение 32-разрядного адреса памяти на поля (б); каталог в узле 36 (в)

Чтобы понять, как работает каталог, проследим путь команды LOAD из процессора 20, который обращается к кэшированной строке. Сначала процессор, выдавший команду, передает ее диспетчеру памяти, который транслирует ее, чтобы получить физический адрес, например, 0x24000108. Диспетчер памяти разделяет этот адрес на три части, как показано на рис. 8.27, б. В десятичной системе счисления эти три части представляют собой узел 36, строку 4 и смещение 8. Диспетчер памяти видит, что слово памяти, к которому производится обращение, находится в узле 36, а не в узле 20, поэтому посылает запрос через сеть в узел 36, где находится нужная строка, узнает, есть ли строка 4 в кэше, и если да, то где именно.

Когда запрос приходит в узел 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, то контролировать изменения в строках кэша нет никакого смысла, поскольку любой новый запрос требует передачи сообщения существующей копии, чтобы объявить ее недействительной.

Естественно, для хранения информации о состоянии каждой строки кэша ("чистая" или "грязная") требуется информировать исходный узел о каждом изменении строки кэша, даже если существует только одна копия этой строки. Если же таких копий несколько, изменение одной из них означает необходимость объявления всех остальных недействительными, поэтому нужен какой-то протокол, позволяющий избежать ситуации гонок. Например, чтобы изменить совместно используемую строку кэша, один из держателей этой строки перед ее изменением мог бы запросить монопольный доступ к ней. Такой запрос означал бы объявление всех остальных копий недействительными. Другие возможные оптимизации CC-NUMA-машин обсуждаются в [195].

NUMA-мультипроцессор Sun Fire Е25К

В качестве примера NUMA-машин с общей памятью рассмотрим семейство мультипроцессоров Sun Fire компании Sun Microsystems. В этом семействе имеется много различных моделей, из которых мы рассмотрим мультипроцессор Е25К, содержащий 74 процессора UltraSPARC IV. По своей сути, каждый из этих процессоров представляет собой пару процессоров UltraSPARC III Си с общими кэшем и памятью. Система Е15К отличается только тем, что вместо сдвоенных в ней используются одиночные процессоры. В семействе есть и более простые модели, но нам интересно выяснить, как работают модели с максимальным числом процессоров.

Система Е25К содержит 18 наборов плат, каждый набор состоит из платы процессор-память, платы ввода-вывода с четырьмя PCI-слотами и платы расширения. Плата расширения попарно объединяет платы процессор-память и ввода-вывода, связывая эти пары с центральной панелью, которая несет остальные платы и обеспечивает их коммутацию. На каждой плате процессор-память находится 4 процессора и 4 модуля ОЗУ по 8 Гбайт. Таким образом, на каждой плате процессор-память имеется 8 процессоров и 32-гигабайтное ОЗУ (для Е15К - 4 процессора и столько же 32-гигабайтных ОЗУ). В целом в системе Е25К имеются 144 процессора, 576 Гбайт памяти и 72 PCI-слота, как показано на рис. 8.28. Любопытно, что число 18 было выбрано исключительно из соображений габаритов: система из 18 наборов плат - это самая большая система, которую можно внести в дверной проем, не разбирая на части. В то время как программисты думают только о нулях и единицах, разработчикам приходится задумываться, в том числе, и о том, как покупатель будет вносить их творение в дом.

Для соединения 18 наборов плат на центральной панели имеются три схемы перекрестной коммутации размером 18 х 18 - по одной схеме для адресных линий, ответов и данных. В дополнение к 18 наборам плат, в центральную панель вставляется плата управления системой, содержащая, помимо процессора, интерфейсы для подключения дисковода, ленточного накопителя, последовательных линий и прочей периферии, необходимой для загрузки системы, ее поддержки и управления.

СОМА-мультипроцессоры

Рис, 8,28. Мультипроцессор Е25К компании Sun Microsystems

Подсистема памяти - сердце любого мультипроцессора. Как же распределенная память соединяется со 144 процессорами? Прямолинейные подходы, то есть большая общая шина слежения или схема перекрестной коммутации размером 144 х 72, в данном случае малопригодны. Первый вариант плох тем, что общая шина становится узким местом всей системы, а второй не годится потому, что разрабатывать такой коммутатор сложно и дорого. Поэтому большим мультипроцессорам, таким как Е25К, неизбежно приходится использовать нетривиальные подсистемы памяти.

На уровне наборов плат логика слежения обеспечивает каждому процессору возможность сверять поступающие запросы со списком блоков в его локальном кэше. Когда процессор обращается к слову памяти, он сначала преобразует виртуальный адрес в физический и проверяет, есть ли нужный блок в кэше. (Физические адреса 43-разрядные, но из-за габаритных требований объем памяти ограничен значением 576 Гбайт.) Если нужный блок обнаруживается в собственном кэше, затребованное слово возвращается. В противном случае логика слежения проверяет, есть ли нужный блок в пределах того же набора плат. Если есть, то запрос выполняется. Иначе, как показано далее, запрос посылается через схему перекрестной коммутации адресных линий. Логика слежения способна обслуживать по одному запросу за такт. Так как тактовая частота системы составляет 150 МГц, можно обработать 150 миллионов запросов в секунду, или 2,7 миллиардов запросов для всех 18 наборов плат.

Хотя на рис. 8.28 логика слежения показана в виде шины, физически она представляет собой древовидную структуру устройств, вверх и вниз по которой передаются команды. Когда с шины РСІ или процессора поступает адрес, он через двухточечное соединение попадает в адресный повторитель, как показано на рис. 8.29. С любого из двух повторителей адрес попадает в плату расширения, откуда передается обратно вниз по дереву к устройствам. Благодаря этой схеме удается избавиться от шины, соединяющей три платы.

СОМА-мультипроцессоры

Рис, 8,29, Четырехуровневое соединение блоков в Sun Fire Е25К. Пунктирные линии означают передачу адресов, сплошные - передачу данных

Для обмена данными применяется четырехуровневое соединение (рис. 8.29). Такой подход обеспечивает высокую производительность. На уровне 0 пары процессоров и блоков памяти соединяются небольшими схемами перекрестной коммутации, которые к тому же соединяются с уровнем 1. Две группы пар процессор-память соединяются второй схемой перекрестной коммутации на уровне 1. Эти коммутаторы выполнены в виде специализированных интегральных схем. У них есть входы для каждой строки и каждого столбца коммутирующей сетки, хотя не все сочетания строк и столбцов используются (или даже имеют смысл). Вся логика коммутации плат построена на схемах перекрестной коммутации размером 3x3.

Каждый набор плат состоит из трех плат: платы процессор-память, платы ввода-вывода и платы расширения, соединяющей две предыдущие платы. Коммутатор уровня 2 расположен на плате расширения, он соединяет саму память и порты ввода-вывода (которые во всех процессорах UltraSPARC отображаются на память). Все данные, поступающие в набор плат или из него, проходят через коммутатор уровня 2. Наконец, обмен данными между разными платами на уровне 3 происходит через схему перекрестной коммутации размером 18 х 18. Данные передаются блоками по 32 байта, таким образом, на передачу стандартного блока в 64 байта требуется два такта.

Теперь, выяснив, как расположены компоненты, обратимся к общей памяти. На самом нижнем уровне адресное пространство объемом 576 Гбайт разбивается на 229 блоков по 64 байта. Это - неделимые элементы памяти. У каждого из них есть своя "родная" плата, где блок "живет", пока он не потребуется где-то еще. Большинство блоков большую часть времени находятся на своих платах. Когда процессору требуется блок, будь то с собственной платы или с любой другой из 17 оставшихся, он сначала запрашивает копию в собственном кэше, после чего работает с кэшированной копией. Хотя на каждой микросхеме в системе Е25К находятся два процессора, у них общее адресное пространство, а, значит, и общий кэш блоков.

Каждый блок памяти (и каждая строка кэша всех микросхем) может находиться в одном из трех состояний:

♦ эксклюзивный доступ (для записи);

♦ совместный доступ (для чтения); 4* недействителен (то есть пуст).

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

Если логике слежения не удается найти строку кэша или найденная строка находится в совместном доступе, через центральную панель к родной плате искомого блока передается запрос, чтобы узнать, где находится блок. Состояние каждого из блоков хранится в его ЕСС-битах, поэтому плата может немедленно выяснить это состояние. Если блок не находится в совместном доступе или находится в совместном доступе одной или нескольких удаленных плат, память на родной плате будет обновлена, поэтому родная плата сможет выполнить запрос. В этом случае копия строки кэша за два такта передается через схему перекрестной коммутации данных запросившему ее процессору.

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

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

Так как каждая плата содержит 229 блоков памяти, в худшем случае каталог должен иметь 229 записей. Поскольку в действительности его объем гораздо меньше, может оказаться, что в каталоге (поиск в котором осуществляется ассоциативно) нет места для некоторых записей. В этом случае родному набору плат придется посылать широковещательный запрос всем остальным 17 наборам плат, чтобы определить местоположение блока. Обязанности по поддержанию согласованности каталогов и выполнению протокола обновления возлагаются на схему перекрестной коммутации ответов, которая обрабатывает большую часть трафика, направленного обратно отправителю. Благодаря разделению протокольного трафика по двум шинам (адресов и ответов) и передаче данных по третьей общую пропускную способность системы удается поддерживать на высоком уровне.

За счет распределения нагрузки между разными устройствами на разных платах Sun Fire Е25К может работать с очень высокой производительностью. Ранее уже упоминалось значение 2,7 миллиардов запросов в секунду. Центральная панель способна поддерживать девять одновременных обменов данными с девятью платами-отправителями и девятью платами-получателями. Так как схема перекрестной коммутации данных имеет ширину 32 байта, за каждый такт может передаваться 288 байт данных. На тактовой частоте 150 МГц это дает пиковую пропускную способность 40 Гбайт/сек, когда все обращения направлены удаленным платам. Если же есть возможность программно расположить страницы памяти так, чтобы большая часть обращений были бы локальными, пиковая пропускная способность системы будет заметно превышать это значение.

Более подробную техническую информацию о Sun Fire Е25К смотрите в [38, 39].

СОМА-мультипроцессоры

NUMA- и CC-NUMA-машины обладают одним серьезным недостатком: обращения к удаленной памяти выполняются гораздо медленнее, чем к локальной. В CC-NUMA-машине эта разница в производительности в какой-то степени нивелируется за счет кэш-памяти. Однако если объем запрашиваемых удаленных данных значительно превышает вместимость кэш-памяти, постоянно будут происходить кэш-промахи, что негативно скажется на производительности.

Мы уже знаем, что достаточно высокую производительность имеют UMA-ма-шины, но число процессоров в них невелико, к тому же они довольно дороги. NC-NUMA-машины хорошо масштабируются, но в них требуется ручное или полуавтоматическое размещение страниц памяти, результаты которого часто плачевны. Дело в том, что очень непросто предсказать, где и какие страницы могут понадобиться, кроме того, страницы трудно перемещать из-за их больших размеров. CC-NUMA-машины, такие как мультипроцессор Sun Fire Е25К, начинают работать очень медленно, если большому числу процессоров требуются большие объемы удаленных данных. Так или иначе, каждая из этих схем имеет существенные недостатки.

Однако существует мультипроцессор, в котором все эти проблемы решаются за счет использования основной памяти каждого процессора в качестве кэш-памяти. Такая система называется СОМА (Cache Only Memory Access - доступ только к кэш-памяти). В ней страницы не имеют собственных "домашних" машин, как в системах NUMA и CC-NUMA, фактически, страницы в этой системе вообще не имеют "прописки".

Вместо этого физическое адресное пространство делится на строки кэша, которые по запросу свободно перемещаются в системе. Блоки памяти не имеют собственных машин. У них, как у кочевников в некоторых странах третьего мира, дом там, где они оказались. Память, которая привлекает строки по мере необходимости, называется притягивающей. Использование основной памяти в качестве большого кэша увеличивает процент кэш-попаданий, а, следовательно, и производительность.

К сожалению, ничего идеального не бывает. С системой СОМА связаны две новые проблемы:

♦ Как размещаются строки кэша?

♦ Что делать, когда удаляемая из памяти строка является последней копией?

Первая проблема связана со следующим фактом. Как известно, диспетчер памяти выполняет трансляцию виртуального адреса в физический. Если после трансляции оказывается, что строки нет в "настоящем" аппаратном кэше, очень трудно сказать, есть вообще искомая строка в основной памяти или ее там нет. Аппаратная поддержка механизма разбиения памяти на страницы здесь не поможет, поскольку каждая страница состоит из большого количества отдельных строк кэша, которые располагаются в системе независимо друг от друга. Даже если известно, что строки в основной памяти нет, как выяснить, где она есть? В данном случае нельзя спросить об этом "домашнюю" машину потерявшейся страницы, поскольку таковой машины в системе просто нет.

Было предложено несколько решений этой проблемы. Чтобы знать, находится строка кэша в основной памяти или нет, для каждой строки кэша можно аппа-ратно поддерживать специальный тег. Тогда диспетчер памяти сможет сравнивать тег нужной строки с тегами всех строк кэша, пока не обнаружится совпадение.

Другое решение - отображать страницы целиком, но при этом не требовать наличия всех строк кэша. Тогда для каждой страницы потребуется аппаратно построить битовую карту, где каждой строке соответствует 1 бит, который и укажет на присутствие или отсутствие этой строки. В этой схеме, которая называется простой схемой СОМА, если строка присутствует, она должна находиться в правильной позиции на своей странице. Если она отсутствует, то любая попытка использовать ее должна вызывать исключение, которое позволит программно найти и задействовать нужную строку.

Таким образом, система будет искать только те строки, которые действительно находятся в удаленной памяти. Еще одно решение - предоставить каждой странице "домашнюю" машину (домашнюю в том смысле, что в каталоге для нее выделяется запись, а не в том, что на этой машине хранятся данные). Тогда чтобы выяснить, где искать строку, можно отправить сообщение ее домашней машине. Другое решение - организовать память в виде древовидной структуры и искать, двигаясь вверх, пока строка не будет найдена.

Вторая проблема связана с удалением последней копии. Как и в CC-NUMA-машине, строка кэша может одновременно находиться в нескольких узлах. Если происходит кэш-промах, строку нужно прочитать, а это обычно означает ее удаление. А что произойдет, если выбранная строка окажется последней копией? В этом случае ее нельзя удалять.

Одно из возможных решений - вернуться к каталогу и проверить, существуют ли другие копии. Если да, то строку можно смело удалять. Если нет, ее нужно где-то разместить. Другое решение - пометить одну из копий каждой строки кэша как главную и никогда ее не удалять. При таком подходе проверять каталог не потребуется. В любом случае СОМА-машина потенциально должна иметь более высокую производительность, чем CC-NUMA, но пока было создано всего несколько СОМА-машин, а для реализации всего их потенциала нужно накопить некоторый опыт. Первыми С ОМА-машинами были KSR-1 [34] и Data Diffusion Machine [83]. В качестве более свежего примера можно привести SDAARC [62].

NUMA-мультипроцессоры || Оглавление || Мультикомпьютеры8