## 16. Архитектуры компьютеров параллельного действия

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

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

### 16.1. Законы Амдала

Пусть пиковая производительность однопроцессорной системы равна T1, тогда пиковая производительность системы, состоящей из p таких процессоров увеличивается в p раз, T = pT1. Ускорением параллельной системы R назовем отношение ее производительности к производительности соответствующей однопроцессорной системы. Тогда пиковое ускорение R = T/T1 = p. Значит, пиковое ускорение p-процессорной системы равно p.

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

Первый закон Амдала. Производительность вычислительной системы, состоящей из нескольких связанных между собой устройств, определяется самым непроизводительным устройством. Общая эффективность всегда окажется связанной с самым неэффективным компонентом.

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

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

Второй закон Амдала. Пусть вычислительная система состоит из p процессоров. Предположим, что k из N операций алгоритма могут выполняться только последовательно. Пусть β = k/N – доля последовательных операций в алгоритме, 0 ≤ β ≤ 1. Тогда максимально возможное ускорение системы R = 1 / (β + (1- β)/p).

Очевидно, что предел выражения для ускорения R при неограниченном увеличении количества процессоров, то есть при p, стремящемся к бесконечности равен 1/ β. Пусть, например, доля операций, которые могут быть выполнены последовательно, равна β = 0,1, тогда реальное ускорение R не может быть больше 10 при любом количестве процессоров. Практический вывод из этих соображений состоит в том, что для общего повышения эффективности нужно не только наращивать количество процессоров в системе, но и улучшать свойства программы, в частности, уменьшать долю операций, выполняемых только последовательно.

### 16.2. Топология параллельных систем.

Из-за наличия в составе параллельной вычислительной системы более одного центрального процессора его уникальность в составе системы теряется. Процессор становится одним из многих аналогичных узлов. Поэтому в параллельных вычислительных системах термин «центральный процессор» заменяется термином процессорный элемент (ПЭ), процессорных модуль (ПМ) или процессорный узел (ПУ).

Вычислительные системы с параллельной архитектурой характеризуются:

1. Типом и мощностью процессорных элементов;

2. Масштабируемостью, то есть возможным количеством процессорных элементов;

3. Объемом и типом модулей памяти;

4. Возможными связями и способом взаимодействия между процессорными элементами, а также между процессорными элементами и модулями памяти.

В современных параллельных вычислительных системах используются высокопроизводительные, в основном 64-битные, процессоры PA-RISC (PA 8700, PA 8800), Alpha (Alpha 21264, Alpha 21364, Alpha 21464), Power PC (Power 3, Power 970, Power 4), MIPS (R14000, R16000), Sun (UltraSPARC III, UltraSPARC IV), AMD (Opteron, Athlon 64), Intel (Xeon EM64T, Itanium 2) и другие.

Различные системы допускают различную масштабируемость. Характерным является возможность включения в систему от 128 до 512 процессорных элементов. Вместе с тем существуют системы, содержащие десятки и сотни тысяч процессоров.

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

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

Способ соединения процессорных элементов и модулей памяти в параллельной вычислительной системе называется топологией системы.

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

### 16.3. Классификация параллельных систем по Флинну

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

Поток команд соответствует счетчику команд. Система с n процессорами имеет n счетчиков команд и, следовательно, n потоков команд.

Поток данных состоит из набора операндов. Потоки команд и данных в какой-то степени независимы, поэтому существует 4 комбинации:

На рис. 16.1 приведена расширенная классификация Флинна.

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

· SISD – это классический последовательный компьютер фон Неймана. Он содержит один поток команд и один поток данных и может выполнять только одно действие одномоментно (рис. 16.2).

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

Рис. 16.2

· SIMD – содержит один блок управления, выдающий по одной команде, но при этом имеется несколько АЛУ, которые могут обрабатывать несколько наборов данных одновременно. ILLIAC IV – прототип машин SIMD (рис. 16.3).

Рис. 16.3

В этот класс входят векторные и матричные вычислительные системы, которые находят применение при решении научно-технических задач, использующих векторные и матричные структуры данных.

Типичным представителем векторно-конвейерных систем является суперкомпьютер Cray-1, разработанный под руководством Сеймура Крея в компании Cray Research (в последствии – подразделение фирмы Silicon Graphics). В то время (1970-е гг.) это была самая мощная вычислительная система в мире. Ее тактовая частота составляла 80 МГц, объем оперативной памяти был равен 8 Мбайт, а пиковая производительность составляла 160 Мфлоп.

Примером более современных векторно-конвейерных вычислительных систем является разработанный в начале 1990-х годов в той же фирме суперкомпьютер Cray T90. Эта система может содержать до 16 процессорных элементов, использующих общую оперативную память. Тактовая частота процессоров равна 250 МГц, а пиковая производительность достигает 32 Гфлоп. Можно упомянуть еще и использующую векторные процессоры вычислительную систему Earth Simulator компании NEC. Система была пущена в эксплуатацию в 2002 г. В это время она состояла из 640 вычислительных узлов, в каждом из которых находилось по 8 процессоров. Пиковая производительность всей системы из 5120 процессоров составляла 40 Тфлоп.

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

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

Рис. 16.4

· MISD – несколько команд оперируют над одними данными (рис. 16.5). Некоторые считают машинами MISD машины с конвейерами.

Рис. 16.5

· MIMD – несколько независимых процессов работают как часть большой системы. В эту категорию попадает большинство параллельных процессоров и мультикомпьютеры и мультипроцессоры.

### 16.4. Классификация параллельных компьютерных систем класса MIMD

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

1. Совместимость с хорошо отлаженными механизмами доступа к оперативной памяти, используемыми в однопроцессорных системах;

2. Простота программирования приложений, простота разработки трансляторов и операционных систем;

3. Малое время доступа, более высокая производительность линий связи;

4. Возможность использования аппаратно управляемого кэширования.

5. К преимуществам систем с передачей сообщений относятся:

6. Более простое аппаратное устройство, не требующее согласованности кэш-памяти различных процессорных элементов;

7. Возможность построения хорошо масштабируемых систем.

16.4.1. Мультипроцессоры

Существует три типа мультипроцессоров. Они различаются по способу реализации памяти совместного использования.

UMA (Uniform Memory Access) – архитектура с однородным доступом к памяти. В машинах UMA каждый процессор имеет одно и тоже время доступа к памяти. Такая однородность делает производительность предсказуемой, а этот факт очень важен для написания эффективной программы.

Такие системы называют также симметричными мультипроцессорными системами и обозначают SMP (Symmetric Multi-Processing).

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

Все процессорные элементы обычно работают под управлением единственной общей для всех процессоров операционной системы.

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

Системы типа SMP просты в эксплуатации, не слишком дороги, но при этом отличаются относительно невысокой масштабируемостью. Характерным примером системы этого типа является компьютер Sun Enterprise 10000, состоящий из 64 процессорных элементов Ultra SPARC III.

NUMA (Non Uniform Memory Access) – архитектура с неоднородным доступом к памяти.

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

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

В архитектуре NUMA также существуют проблемы, связанные с доступом процессорных элементов к данным, модифицированным другим процессорным элементом и помещенным в его кэш-память. В связи с этим в класс NUMA входят системы без кэширования NC-NUMA (No Caching NUMA) и системы с согласованной кэш-памятью CC-NUMA (Coherent Cache NUMA), в которых проблемы когерентности решаются довольно эффективно. Характерным примером вычислительной системы класса NC-NUMA является машина Carnegie-Mellon Cm. Системами CC-NUMA являются: суперкомпьютеры Hewlett-Packard Superdome, SGI Origin 3000, Sun HPC 15000 и Sequent NUMA-Q 2000.

COMA (Cache Only Memory Access) – архитектура с доступом только к кэш-памяти. В этой архитектуре локальная память каждого процессорного элемента используется только как кэш-память. При этом общая для всех процессорных элементов оперативная память в системе отсутствует. Отличительной особенностью этой архитектуры является отсутствие постоянной привязки строк кэша к адресам локальных блоков оперативной памяти. Строки помещаются в локальную память (кэш) любого из процессорных элементов по мере необходимости. Это избавляет от проблем согласования, но появляются сложности с удалением элементов, а также с определением наличия строк кэша в оперативной памяти. Эти системы пока не очень распространены, и еще не накоплен достаточный опыт их эксплуатации.

16.4.2. Мультикомпьютеры

Во вторую категорию MIMD попадают мультикомпьютеры. Они не имеют памяти совместного использования на архитектурном уровне. Поскольку мультикомпьютеры не имеют доступа к отдаленным модулям памяти, то они иногда называются машинами NORMA (NO Remote Memory Access – без доступа к отдаленным модулям памяти).

Мультикомпьютеры можно разделить на две категории.

1. MPP (Massively Parallel Processor) – процессоры с массовым параллелизмом, дорогостоящие компьютеры, которые состоят из большого количества процессоров, связанных высокоскоростной коммуникационной сетью.

2. NOW (Network of Workstations), COW (Cluster of Workstations) – сети рабочих станций и кластеры рабочих станций, которые связываются при помощи уже имеющихся соединений.

### 16.5. Семантика памяти

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

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

16.5.1. Строгая согласованность

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

16.5.2. Согласованность по последовательности (секвенциальная состоятельность)

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

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

Однако есть модели согласованности, которые не гарантируют такого порядка.

16.5.3. Процессорная согласованность

Процессорная согласованность – более проигрышная модель, но зато ее легче реализовать на больших мультипроцессорах. Она имеет два свойства:

1. Все процессоры воспринимают записи любого процессора в том порядке, в котором они начинаются;

2. Все процессоры видят записи в слово памяти в том порядке, в котором они происходят.

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

При таких ограничениях возможна ситуация, что процессор 2 начнет записи 2А, 2В, 2С одновременно с записями процессора 1. Другие процессоры, считывающие слова из памяти, увидят последовательность из шести записей, например 1А, 2А, 1В, 2В, 1С, 2С или 1А, 1В, 1С, 2А, 2В, 2С и т.п. При процессорной согласованности не гарантируется, что каждый процессор видит одну и ту же последовательность. Единственное, что гарантируется совершенно точно, что никто не увидит последовательность 1В, 1А, … .

16.5.4. Слабая согласованность

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

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

16.5.5. Свободная согласованность

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

В такой модели операция синхронизации разделяется на две разные операции. Чтобы считать или записать общую переменную, процессор (т.е. его ПО) сначала должно выполнить операцию acquire над переменной синхронизации, чтобы получить монопольный доступ к общим разделяемым данным. Затем процессор может использовать эти данные по своему усмотрению, а затем процессор выполняет операцию release над переменной синхронизации, чтобы показать, что он завершил работу. Операция release не требует завершения незаконченных записей, однако она сама не может быть завершена, пока не закончатся все начатые записи. Новые операции памяти могут начаться сразу же.

Когда начинается новая операция acquire, производится проверка, все ли начатые операции release завершены. Если нет, то операции acquire будут задержаны. Это гарантирует, что все переменные в критической области будут обновлены. Такая схема сложнее, чем слабая согласованность, но она имеет преимущество: здесь не надо задерживать выполнение команд без необходимости.

### 16.6. Архитектуры UMA SMP (симметричная архитектура)

#### 16.6.1. UMA-мультипроцессоры с шинной организацией

В основе самых простых мультипроцессоров лежит одна шина (рис. 16.6 а). Если процессору нужно считать информацию из памяти, он проверяет, свободна ли шина.

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

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

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

#### 16.6.2.Отслеживание изменений данных в кэш-памяти

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

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

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

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

Самый простой протокол когерентности кэширования называется сквозным кэшированием. Возможны 4 варианта, которые приведены в таблице 1.

Таблица 1

Действие | Локальный запрос | Удаленный запрос
Промах при чтении | Вызов данных из памяти |
Попадание при чтении | Использование данных из локальной кэш-памяти |
Промах при записи | Обновление данных в основной памяти |
Попадание при записи | Обновление данных в кэш-памяти и основной памяти | Объявление элемента кэш-памяти недействительным

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

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

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

#### 16.6.3. Протокол MESI

Один из популярных протоколов с обратной записью, использующий стратегию признания данных недействительными, называется MESI (по первым буквам четырех состояний). В его основе лежит протокол однократной записи. Этот протокол используется в Pentium II и других процессорах для отслеживания шины. Каждый элемент кэш-памяти может находится в одном из четырех состояний:

1. Invalid – элемент кэш-памяти содержит недействительные данные.

2. Shared – несколько кэшей могут содержать данную строку, основная память обновлена.

3. Exclusive – никакой другой кэш не содержит эту строку, основная память обновлена.

4. Modified – элемент действителен, основная память недействительна, копий элемента не существует.

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

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

Варианты:

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

2. Если процессор 1 собрался записать слово в этой строке, то процессор 2 видит это и передает сигнал о том, что нужно подождать, пока строка не будет записана в основную память. Когда строка записана, процессор помечает собственную строку как недействительную.

#### 16.6.4. UMA-мультипроцессоры с перекрестной коммутацией

Даже при всех возможных оптимизациях использование только одной шины ограничивает размер мультипроцессора UMA до 16 или 32 процессоров.

Самая простая схема соединения процессоров с k блоками памяти – координатный коммутатор (рис 16.7). Координатный коммутатор представляет собой неблокируемую сеть. Это значит, что процессор всегда будет связан с нужным модулем памяти. Никакого предварительного планирования не требуется. Недостатком координатного коммутатора является то, что число узлов растет как n2. Поэтому координатные коммутаторы приемлемы для систем средних размеров.

Sun Enterprise 10000

Эта система состоит из одного корпуса с 64 процессорами. Координатный коммутатор Gigaplahe-XP запакован в плату, содержащую 8 гнезд на каждой стороне. Каждое гнездо вмещает плату (400 х 500 мм), содержащую 4 процессора UltraSPARC II на 333 МГц и ОЗУ на 4 Гбайт. Благодаря жестким требованиям к синхронизации и малому времени ожидания доступ к памяти вне платы занимает столько же времени, что и доступ к памяти на плате.

Иметь только одну шину для взаимодействия всех процессоров и всех блоков памяти неудобно, поэтому в системе Enterprise 10000 применяется другая стратегия. Здесь используется координатный коммутатор 16 х 16 для перемещения данных между основной памятью и блоками кэш-памяти. Длина строки кэш-памяти составляет 64 байта, а ширина канала связи – 16 байт, строка кэш-памяти перемещается за 4 цикла. Координатный коммутатор работает от точки к точке, поэтому его нельзя использовать для сохранения когерентности кэш-памяти.

По этой причине помимо координатного коммутатора имеются 4 адресные шины, которые используются для отслеживания строк в кэш-памяти (рис. 16.8). Каждая шина использует ¼ часть физического адресного пространства. Для выбора шины используется 2 адресных бита. В случае промаха кэш-памяти при считывании процессор должен считать данные из основной памяти и тогда он обращается к соответствующей адресной шине, чтобы узнать, нет ли нужной строки в других блоках кэш-памяти. Все 16 плат отслеживают все 4 адресные шины одновременно, поэтому, если ответа нет, это означает, что требуемая строка отсутствует в кэш-памяти и следует обратиться в основную память.

Вызов из памяти происходит от точки к точке по координатному коммутатору по 16 байт. Цикл шины составляет 12 нс (83,3 МГц), и каждая адресная шина может отслеживаться в каждом цикле любой другой шины, т.е. возможно 167 млн отслеживаний/с. Каждое отслеживание может потребовать передачи строки кэш-памяти в 64 байта, поэтому узел должен обеспечить передачу со скоростью 9.93 Гбайт/с. Строку кэш-памяти в 64 байта можно передать за 4 цикла (48 нс) при пропускной способности в 1.24 Гбайта/с за одну передачу. Поскольку узел может обрабатывать 16 передач одновременно, его максимальная пропускная способность – 19.87 Гбайт/с, а этого достаточно для поддержания скорости отслеживания, даже если учесть возможность возникновения конфликтной ситуации, при которой практическая пропускная способность снижается до 60% от теоретической.

Enterprise 10000 использует 4 отслеживающие шины параллельно и очень широкий коммутатор для передачи данных. Такая система преодолевает предел в 64 процессора. Но для существенного увеличения числа процессоров требуется иной подход.

#### 16.6.5. UMA-мультипроцессоры с многоступенчатой коммутацией

В основе другого подхода лежит коммутатор 2 х 2. Коммутатор содержит два входа и два выхода. Сообщения, приходящие на один из входов могут переключаться на любой выход. Коммутаторы 2 х 2 можно компоновать различными способами и получать многоступенчатые сети. Один из возможных вариантов – сеть omega (рис. 16.9). В этой сети соединены 8 процессоров и 8 модулей памяти, используя 12 коммутаторов. Для n процессоров и n модулей памяти потребуется log2n ступеней, n/2 коммутаторов на каждой ступени. Всего (nlog2n)/2 коммутаторов, что значительно лучше, чем n2.

Рис. 16.9

Рисунок разводки сети omega называют полным тасованием. По мере прохождения сообщения по сети последовательно используются биты адреса получателя. Эти биты замещаются битами адреса отправителя, т.о. получатель знает, откуда пришел запрос.

Рассмотрим, что произойдет, если процессору 001 нужно записать обратиться в модуль памяти 001, одновременно процессор 000 обращается в модуль 000. Запрос может вступить в конфликт с запросом процессора 001 на коммутаторе 3А. Одному из запросов придется подождать. В отличии от координатного коммутатора, сеть omega – блокируемая сеть.

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

### 16.7. Мультипроцессоры NUMA

Для дальнейшего увеличения количества процессоров в системе необходимо находить дополнительные технические решения.

Мультипроцессоры NUMA (NonUniform Memory Access – с неоднородным доступом к памяти). Как и мультипроцессоры UMA, они обеспечивают единое адресное пространство для всех процессоров, но в отличие от машин UMA, доступ к локальным модулям памяти происходит быстрее, чем к удаленным. Следовательно, все программы UMA будут работать без изменений на машинах NUMA, но производительность будет хуже, чем на машинах UMA с той же тактовой частотой.

Машины NUMA три ключевые характеристики, которыми все они обладают и которые в совокупности отличают их от других мультипроцессоров.

1. Существует одно адресное пространство, видимое для всех процессоров.

2. Доступ к удаленной памяти осуществляется с использованием команд load и store.

3. Доступ к удаленной памяти происходит медленнее, чем доступ к локальной памяти.

Если время доступа к удаленной памяти не скрыто (кэш-память отсутствует), то такая система называется NC-NUMA (No Caching NUMA – NUMA без кэширования. Если присутствуют согласованные кэши, то система называется CC-NUMA (Coherenet Cache NUMA – NUMA с согласованной кэш-памятью).

Упрощенная структурная схема системы NC-NUMA приведена на рис. 16.10. Запрос памяти приходит в блок управления памятью. Определяется, находятся ли требуемые данные в локальной памяти. Если да, то запрос отправляется по локальной шине. Если данных в локальной памяти нет, то запрос отправляется по системной шине к системе, в которой присутствуют данные. В первых таких системах (70-е годы) обращение к системной шине требовало времени в 10 раз большее, чем обращение к локальной памяти.

Согласованность памяти гарантировало отсутствие кэш-памяти, т.к. каждое слово имеется в единственном экземпляре. Машина NC-NUMA использует сложное программное обеспечение для перемещения страниц, чтобы максимально увеличить производительность.

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

#### 16.7.1. CC-NUMA мультипроцессоры

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

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

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

Проследим путь команды из процессора 20, который обращается к кэшированной строке. Процессор передает ее на блок управления памятью, который переводит ее в физический адрес, например 0х24000108. Блок управления разделяет этот адрес на три части. Получили: узел 36, строка 4, смещение 8. Слово находится в 36 узле, поэтому необходимо делать запрос через сеть, узнать есть ли строка 4 в кэш-памяти и где именно. Когда запрос прибывает в узел 36, он направляется в аппаратное обеспечение каталога. Аппаратное обеспечение индексирует таблицу в 218 элементов (один элемент на строку) и извлекает элемент 4. Если строка отсутствует в кэш-памяти, то аппаратное обеспечение вызывает строку из локального ОЗУ, отправляет в узел 20 и обновляет элемент каталога 4, показывая, что эта строка размещена в кэш-памяти узла 20. Если строка присутствует в кэш-памяти, то аппаратное обеспечение обновляет элемент каталога, и объявляет элемент кэш-памяти в узле 36 недействительным.

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

Недостаток разработки в том, что строка может быть кэширована только в одном узле. Существуют различные варианты преодоления этого недостатка и все они связаны с дополнительными непроизводственными затратами памяти.

#### 16.7.2. Мультипроцессор Stanford DASH

Первый мультипроцессор CC-NUMA на основе каталога DASH (Directory Architecture for Shared memory – архитектуры на основе каталога для памяти совместного использования) был разработан в Стэндфордском университете как исследовательский проект. В ней применялся ряд промышленных компонент. Схема машины DASH в упрощенном варианте представлена на рис. 16.12. Она состоит из 16 кластеров, каждый из которых содержит шину, 4 процессора, 16 Мбайт глобальной памяти, а также некоторые устройства ввода/вывода (диски и т.п.), которые на схеме не показаны. Каждый процессор отслеживает только свою локальную шину. Локальная совместимость поддерживается с помощью отслеживания, для глобальной совместимости нужны иные механизмы, т.к. глобального отслеживания не существует.

Полный объем адресного пространства в данной системе равен 256 Мбайт. Адресное пространство разделено на 16 областей по 16 Мбайт каждая.

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

Получается, что объем каждого каталога превышает 2 Мбайта. При наличии 16 кластеров непроизводственные затраты составляют 14 % от 256 Мбайт.

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

Каждый кластер в DASH связан с интерфейсом, который дает возможность кластеру обмениваться информацией с другими кластерами. Интерфейсы связаны через межкластерные каналы в прямоугольную решетку. В системе использована маршрутизация «червоточина», поэтому первая часть пакета может быть направлена дальше еще до того, как получен весь пакет, что сокращает задержку на каждом транзитном участке. Существует два набора межкластерных пакетов: один для запрашиваемых, другой – для ответных. Межкластерные каналы не отслеживаются.

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

1. UNCACHED (некэшированная) – строка находится в памяти.

2. SHARED (совместно используемая) – память содержит новейшие данные, строка может находится в нескольких блоках кэш-памяти.

3. MODIFIED (измененная) – строка, содержащаяся в памяти неправильная; данная строка находится только в одной кэш-памяти.

Состояние каждой строки кэш-памяти содержится в поле Состояние в соответствующем элементе каталога, как показано на рис. 16.12.

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

#### 16.7.3. Мультипроцессор Sequent NUMA-Q

Машина DASH никогда не была коммерческим продуктом. Одно из коммерческих изделий машин этого класса – Sequent NUMA-Q 2000. В ней используется интересный протокол когерентности кэширования SCI (Scalable Coherent Interface – масштабируемый когерентный интерфейс). Этот протокол стандартизирован (стандарт IEEE 1569) и используется в ряде других машин CC-NUMA.

В основе машины Sequent NUMA-Q лежит стандартная плата quard board производства Intel. Плата содержит 4 процессора Pentium-Pro и до 4 Гбайт ОЗУ. Каждый процессор содержит кэш-память первого и второго уровней. Непротиворечивость кэшей сохраняется благодаря отслеживанию локальной шины платы с использованием протокола MESI. Скорость передачи данных в локальной шине составляет 534 Мбайт/с. Размер строки кэш-памяти равен 64 байтам. Схема мультипроцессора Sequent NUMA-Q изображена на рис. 16.13.

Чтобы расширить систему надо вставить плату сетевого контроллера в гнездо сетевого контроллера на плате. Сетевой контроллер (плата IQ-Link) соединяет все платы в один мультипроцессор. Задача контроллера – реализовать протокол SCI. Каждая плата IQ-Link содержит 32 Мбайт кэш-памяти, каталог, который следит за там, что находится кэше, интерфейс с локальной шиной платы quard board и микросхему, называемую информационным ядром, соединяющим плату IQ-Link с другими платами IQ-Link. Эта микросхема подкачивает данные от входа к выходу, сохраняя те данные, которые направляются в ее узел и передавая прочие данные без изменений.

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

Рассмотрим интерфейс SCI. Этот интерфейс был разработан для того, чтобы заменить шину в больших мультипроцессорах и мультикомпьютерах.

SCI поддерживает непротиворечивость кэшей, что важно для мультипроцессоров; и позволяет быстро передавать блоки, что актуально для мультикомпьютеров. SCI выдерживает нагрузку до 64 К узлов, адресное пространство каждого из которых может быть до 248 байтов. Самая большая система NUMA-Q состоит из 63 плат, которые содержат 252 процессора и почти 236 физической памяти.

Кольцо, соединяющее платы IQ-Link соответствует протоколу SCI и представляет собой не кольцо, а двухточечные кабели (от платы к плате). Ширина кабеля – 18 бит (1 синхронизация, 1 флаг, 16 информационных). Тактовая частота – 500 Мгц, скорость передачи данных – 1 Гбайт/с. Передача осуществляется пакетами. Состав пакета:

· заголовок 14 байт;

· 0, 16, 64 или 256 байт данных;

· контрольная сумма 2 байта.

Физическая память в машине распределена по узлам, так что каждая страница памяти имеет свою собственную машину. Каждая плата quard board может иметь до 4 Гбайт ОЗУ. Размер строки кэш-памяти – 64 байта. Таким образом каждая плата содержит 236 строк. Если строка не используется, она находится только в одном месте – в собственной памяти.

Для каждого узла существует таблица локальной памяти из 236 элементов, по которой можно определить местоположение строк.

Все копии строки кэш-памяти собираются в дважды связанный список. Элемент в таблице локальной памяти показывает, в каком узле находится головная часть списка. В машине NUMA-Q 2000 достаточно 6-битного номера, поскольку может быть максимум 32 узла. Для системы SCI максимального размера достаточно 16-битного номера. Такая схема для больших систем лучше, чем битовое отображение. Поэтому SCI более расширяема, чем DASH.

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

Каждый элемент каталога состоит из 36 бит. Шесть бит указывают на узел, который содержит предыдущую строчку цепочки. Следующие шесть – на узел, содержащий следующую строчку цепочки. 0 – конец цепочки, поэтому максимальный размер системы – 63 узла, а не 64. 7 бит предназначены для записи состояния строки. Последние 13 бит – тэг, который используется для идентификации строки. (Замечание. Объем ОЗУ системы – 63 х 232≈238, что соответствует 232 строк кэш-памяти. 232строк отображаются на 219 элементов кэш-памяти. Существует 213 строк, отображаемые на каждый элемент. Следовательно, 13-битный тэг требуется для идентификации строки).

Каждая строка имеет фиксированную позицию только в одном блоке памяти. Строки могут находится в одном из трех состояний:

· UNCACHED (некэшированная) – строка находится в памяти.

· SHARED (совместно используемая) – память содержит новейшие данные, строка может находится в нескольких блоках кэш-памяти.

· MODIFIED (измененная) – строка, содержащаяся в памяти неправильная; данная строка находится только в одной кэш-памяти.

В протоколе SCI определены 3 операции со списком: добавление узла к списку, удаление узла из списка, очистка всех узлов, кроме одного. Последняя операция нужна, если разделяемая строка изменена и становится единственной.

Протокол SCI имеет три варианта сложности. Протокол минимальной степени сложности разрешает иметь только одну копию каждой кэш-строки в памяти. В соответствии с протоколом средней степени сложности каждая строка может кэшироваться в неограниченном количестве узлов. Полный протокол различает особенности для увеличения производительности. Полностью протокол изложен в стандарте IEEE 1596.

#### 16.7.4. NUMA-мультипроцессор Sun Fire E25K

Система содержит 74 процессора UltraSPARC IV. UltraSPARC IV – сдвоенный процессор с общими кэшем и памятью. В семействе Sun Fire имеется и более простые модели, но интересно рассмотреть модель с максимальным числом процессоров.

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

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

Подсистема памяти не тривиальна.

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

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

Если нет, то запрос посылается через схему перекрестной коммутации адресных линий. Логика слежения позволяет обслуживать по одному запросу на такт. Тактовая частота 150 МГц, в секунду обрабатывается 150 миллионов запросов, или 2,7 млрд. запросов на все 18 плат.

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

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

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

· Совместный доступ (для чтения);

· Недействительный (пустой).

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

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

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

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

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

### 16.7.5. Мультипроцессоры COMA

Машины NUMA и СС-NUMA имеют недостаток: обращения к удаленной памяти происходят гораздо медленнее, чем обращения к локальной памяти.

Машины UМА, например, Sun Enterprise 10000 имеют очень высокую производительность, но ограничены в размерах и дорого стоят. Машины NUMA могут расширятся до больших размеров, но в таких системах трудно распределить страницы и предсказать, какие страницы понадобятся и страницы трудно перемещать из-за их значительных размеров. Это может привести к существенному сокращению производительности машины.

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

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

В результате появляются две новые проблемы:

1. как разместить строки кэш-памяти;

2. если строка удаляется из памяти, что произойдет, если это последняя копия.

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

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

Машина COMA обещает существенно увеличить производительности системы, но в настоящее время известно очень мало машин COMA (2 машины: KSR-1 и Data Diffusion Machine), и для объективной оценки недостаточно информации.

### 16.8. Мультикомпьютеры

Обобщенная схема мультикомпьютера приведена на рис. 16.15.

#### 16.8.1. Коммуникационные сети

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

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

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

Пропускная способность сети межсоединений – количество данных, которое она может передать в секунду.

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

Сети межсоединений можно характеризовать по их размерности. Размерность определяется по числу возможных вариантов перехода. Если выбора нет (один путь) – сеть нульмерная (рис. 16.16 а-в); два варианта (направо/налево) – одномерная (рис. 16.16 г); четыре варианта (направо/налево/вверх/вниз) – двумерная и (рис. 16.16 д, е) т. д. Трехмерная размерность – куб – приведена на рис. 16.16 ж, черырехмерный куб – рис. 16.16 з. N-мерный куб называют гиперкубом.

##### 16.8.1.1. Коммутация

На рис. 16.17 приведена сеть межсоединений с четырьмя коммутаторами. На рисунке каждый коммутатор имеет 4 входных и 4 выходных порта. Задача коммутатора – принимать пакеты, которые приходят на любой входной порт и отправлять пакеты из соответствующих выходных портов. Каждый выходной порт связан с входным портом другого коммутатора через последовательный или параллельный канал (пунктирная линия). Существуют специальные сигналы для управления каналами. Параллельные каналы характеризуются более высокой производительностью, но в них возникает проблема расфазировки данных (нужно быть уверенным, что все биты прибывают одновременно) и они стоят гораздо дороже.

Существует несколько стратегий переключений.

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

Коммутация с промежуточным хранением – здесь не требуется предварительного резервирования. Из исходного пункта посылается целый пакет к первому коммутатору, где он хранится целиком. Затем он передается следующему коммутатору и так до тех пор, пока не прибудет к месту назначения. Процесс перемещения пакета приведен на рис. 16.18. Никакого предварительного резервирования ресурсов не требуется.

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

При буферизации на входе один или несколько буферов связываются с каждым входным портом в форме очереди типа FIFO. Если пакет нельзя передать, то он просто ждет своей очереди. Но если пакет ожидает, то следующий пакет также ожидает очереди, даже если требуемый ему порт свободен. Такая ситуация называется блокировкой начала очереди.

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

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

Существует идея разработки гибридной сети межсоединений, объединяющей в себе коммутацию каналов и коммутацию пакетов. Например, каждый пакет можно разделить на части и как только первая часть пакета поступила в коммутатор, ее можно передавать дальше, даже если оставшиеся части пакета еще не прибыли.

Такой подход отличается от коммутации каналов тем, что ресурсы не резервируются заранее. Следовательно, возможна конфликтная ситуация в соревновании за право обладания ресурсами. При коммутации без буферизации пакетов, если первый блок пакета не может двигаться дальше, оставшаяся часть пакета продолжает поступать в коммутатор. В худшем случае эта схема превращается в коммутацию с промежуточным хранением. При другом типе маршрутизации, т.н. «wormhole routing» (червоточина), если первый блок не может двигаться дальше, то в исходный пункт подается сигнал остановить передачу и пакет может растянуться на несколько коммутаторов. После освобождения ресурсов продвижение пакета продолжается. Это схоже с конвейерным выполнением команд в центральном процессоре: в любой момент времени каждый коммутатор выполняет часть работы.

##### 16.8.1.2. Алгоритмы выбора маршрута

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

Алгоритмы выбора маршрута можно разделить на две категории: маршрутизация от источника и распределенная маршрутизация. При маршрутизации от источника источник определяет весь путь по сети заранее. Этот путь выражается списком из номеров портов, которые нужно будет использовать в каждом коммутаторе по пути к пункту назначения. Если путь лежит через k коммутаторов, то первые k байтов в каждом пакете будут содержать k номеров выходных портов, по 1 байту на каждый порт. Когда пакет доходит до коммутатора, первый байт отсекается и используется для определения выходного порта. Оставшаяся часть пакета используется для направления в соответствующий порт.

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

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

#### 16.8.2. MPP – процессоры с массовым параллелизмом

MPP (Massively Parallel Processor – процессоры с массовым параллелизмом) – это огромные компьютеры, стоимостью несколько миллионов долларов. Они используются в научных исследованиях и промышленности для выполнения сложных вычислений, для обработки большого числа транзакций, для хранения больших баз данных и управления ими.

В большинстве таких машин используются стандартные процессоры (Pentium, UltraSPARC, DEC Alpha и др.).

Особенности MPP-мультикомпьютеров:

· наличие высокопроизводительной сети передачи сообщений;

· высокая производительность процессов ввода-вывода (связана с необходимостью обработки огромных объемов данных);

· отказоустойчивость – система сохраняет работоспособность при отказе части процессоров;

· наличие специального аппаратного и программного обеспечения для контроля и диагностики системы, обнаружения и устранения неисправностей.

##### 16.8.2.1. BlueGene

Система BlueGene была задумана IBM в 1999 году как суперкомпьютер для решения задач большой сложности в биологии. IBM вложила в разработку и постройку этого компьютера $100 млн. Заказ на такую машину поступил в 2001 году от Департамента энергетики.

Целью проекта было построение не только самой быстрой, но и самой эффективной в показателях терафлоп/с, терафлоп/ватт, терафлоп/м3. По этой причине IBM отказалась от принципа использования самых быстрых компонентов независимо от цены. Вместо этого был выпущен собственный однокристальный компонент, работающий с умеренным быстродействием, обладающий низким энергопотреблением. Первая микросхема появилась в 2003 году, первая четверть машины – 2004 г. Тогда же она была сертифицирована как самый производительный компьютер с производительностью 71 терафлоп/с.

В основе системы лежит узел, образованный из специализированной микросхемы PowerPC 440 (рис. 16.19)

Рис. 16.19

Узел состоит из двух ядер PowerPC 440, работающих с частотой 700 МГц. PowerPC 440 – конвейеризированный сдвоенный суперскалярный процессор. Два процесса идентичны, но программируются отдельно. Один используется для вычислений, второй – для взаимодействия с остальными 65535 узлами.

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

Для сравнения: промах кэш памяти на первом уровне обходится в 11 тактов, промах на втором – 28, промах на третьем уровне – 75 тактов.

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

Для более высокого уровня была разработана плата, на которую устанавливается две микросхемы и оперативная память на 1 Гбайт. В дальнейшем планируется 4 Гбайт (рис. 16.20). Платы монтируются на панели, по 16 на каждой. На панели получается 32 процессора и 16 Гбайт памяти. 32 панелей вставляются в стойку размером 60 х 90 см. Т.о. на стойке – 1024 процессора. Система состоит из 64 стоек. Всего 65336 вычислительных процессоров, 65536 коммуникационных процессоров. Производительность 4,6∙1014 команд в секунду.

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

Система проста и в ней не используется никаких особенных технологий, за исключением плотного размещения узлов.

Для подключения микросхем требуется масштабируемая и высокопроизводительная коммуникационная сеть. В качестве топологии выбран трехмерный тор 64 х32 х 32. Конструктивно каждая стойка на 1024 узла образует тор 8 х 8 х16.

Взаимодействие в трехмерном торе поддерживается в форме виртуальной сквозной маршрутизации.

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

Третья сеть используется для глобальных приостановок и прерываний.

Четвертая и пятая сети построены на основе технологии Gigabit Ethernet. Одна используется для обмена информацией с внешними источниками, вторая для отладки.

На каждом вычислительном и коммуникационном узле имеется специализированная малая операционная система, поддерживающая одного пользователя и один процесс. Эта система производительна, проста и надежна.

##### 16.8.2.2. RedStorm

RedStorm (Thor’s Hammer) разработана в лаборатории Sandia по заданию министерства энергетики США. Предыдущая разработка Sandia базировалась на узлах Intel, возникли проблемы. В 2002 году Sandia решила заменить предыдущую систему и решила использовать продукцию компании Cray Research. К 2004 году система была уже поставлена, что объясняется тем, что RedStorm состоит из обычных компонентов (за исключением микросхемы маршрутизации).

Используется процессор AMD Opteron. Он поддерживает три режима работы:

· унаследованный, совместим с Pentium;

· совместимости – 64-разрядная адресация при 32-ых программах;

· 64-разрядный для адресов и данных.

Еще одно преимущество – наличие контроллера памяти, работающего на частоте процессора, а не на частоте шины, что существенно повышает производительность памяти. Контроллер позволяет работать с восемью модулями DIMM памяти по 4 Гбайт каждый (всего – 32 Гбайт). В системе Red Storm устанавливается 2-4 Гбайт, предусмотрена возможность расширения.

Каждому процессору Opteron выделяется собственный специализированный сетевой процессор Seastar (IBM). Это критически важный элемент, так как практические весь обмен информацией в системе происходит через сеть Seastar.

Процессоры Opteron – обычные процессоры, но установлены на специальную плату. На каждой плате 4 процессора, память на 4 Гбайт, 4 процессора Seastar, процессор RAS, микросхема Ethernet на 100 Мбит/с. (рис. 16.21).

Набор 8 плат вставляется в кассету, 3 кассеты образуют стойку (96 процессоров). Система содержит 108 стоек. Всего 10368 процессоров, память 10 Тбайт, общей памяти нет. Теоретическая вычислительная мощность – 41 терафлоп/с.

Маршрутиризаторы Seastar соединены друг с другом в трехмерный тор. Еще одна сеть построена на основе Ethernet со скоростью 100 Мбит/с и служит для обслуживания и поддержки системы. В дополнение к 108 вычислительным стойкам имеется 16 стоек ввода/вывода и обслуживания. В каждой из них установлено 32 процессора Opteron. Из них 256 – ввод/вывод, 256 – обслуживание. Общий объем дискового пространства – 240 Тбайт, общая производительность дисковой системы – 50 Гбайт/с.

Система при помощи механических переключателей разбивается на две части – секретную и несекретную (рис. 16.22). Из общего числа процессоров 2688 всегда секретны, 2688 – всегда несекретны, остальные 4992 можно переключать между секциями.

Вся система располагается в отдельном здании 2000 м2, спроектированном таким образом, чтобы система могла расширятся до 30000 процессоров.

Общая стоимость проекта (включая разработку около $100 млн. Cray рассчитывает продавать уменьшенные копии под названием Х3Т.

Вычислительные узлы работают под управлением облегченного ядра Catamount (дикая кошка). Узлы ввода/вывода под Linux с поддержкой интерфейса MPI. На Red Storm можно запускать имеющиеся программы предыдущей Red.

В такой системе вопросы надежности выходят на первый план. У аппаратного обеспечения предыдущей Red среднее время наработки на отказ составляло 900 часов, но операционная система обеспечивала только 40 часов.

##### 16.8.2.3. Сравнение систем BlueGene и RedStorm

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

Система BluеGene c самого начала была спроектирована как коммерческая машина, ориентированная на продажу крупным компаниям. Система RedStorm была построена по индивидуальному заказу, к тому же компания Cray планирует выставлять на продажу уменьшенные версии системы.

Подход IBM прост: из существующих ядер построить пусть специализированную, но низкоскоростную и дешевую в массовом производстве микросхему, затем очень большое количество микросхем объединить не слишком дорогой сетью.

Подход Sandia – взять один из мощнейших имеющихся в продаже 64-разрядный процессор, объединить высокоскоростным маршрутизатором и получить высокопроизводительный вычислительный узел. Таких узлов потребуется меньше, общий поток информации будет проходить быстрее.

В BlueGene удалось добиться более высокой плотности размещения микросхем, система занимает меньше места и потребляет меньше энергии.

По производительности BluGene выигрывает, т.к. ее производительность 71 терафлоп/с, в то время как у RedStorm 41. Но конструкция RedStorm расширяема и используя, например, двухъядерные процессоры Opteron можно поднять производительность до 82 терафлоп/с. С другой стороны, IBM может еще увеличить тактовую частоту. Таким образом, пути развития архитектур МРР – суперкомпьютера еще не подошли к своему пределу.

#### 16.8.3. Кластерные вычисления

Следующий тип мультикомпьютеров – кластерные компьютеры (системы COW или NOW Network of Workstation – сеть рабочих станций). Обычно он состоит из нескольких сотен персональных компьютеров или рабочих станций, соединенных посредством сетевых плат. Различие между MPP и COW аналогично разнице между большой вычислительной машиной и персональным компьютером. Компоненты одинаковы, но различное быстродействие. Но они управляются и применяются по-разному.

Процессоры в МРР – это обычные процессоры, которые можно купить. Используются обычные динамические ОЗУ и ОС UNIX.

Исторически системы МРР отличались высокоскоростной сетью. Но с появлением коммерческих высокоскоростных сетей это различие начало сглаживаться. Основной нишей для МРР останутся дорогостоящие суперкомпьютеры для которых главное – производительность, а цена принципиального значения не имеет.

Преимущество систем COW над МРР в том, что COW полностью состоит из компонентов, которые можно купить и цены на которые постоянно падают.

Существует множество различных видов COW, но доминируют два из них: централизованные и децентрализованные. Централизованные системы COW представляют собой кластер рабочих станций или персональных компьютеров, смонтированных в один блок в одном помещении. Иногда в таких системах применяется компоновка высокой плотности для сокращения длины кабелей. Как правило, такие машины не имеют развитой периферии за исключением сетевых карт. Такие системы еще называют автономными рабочими станциями, а Гордон Белл, разработчик PDP-11 и VAX назвал их безголовыми рабочими станциями

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

Кластеры зачастую невелики, тем не менее можно построить очень большой кластер из обычных ПК. Один из вариантов предложила и реализовала компания Google.

##### 16.8.3.1. Google

С точки зрения поисковой системы задача состоит в том, чтобы проиндексировать и сохранить весь Интернет (более 8 млрд. страниц и 1 млрд. изображений), а затем находить информацию за 0,5 с при интенсивности 100 запросов/с. Система никогда не должна отключаться.

Функционирование Google обеспечивает множество периферийных центров по всему миру. При обращении анализируется IP-адрес отправителя запроса и обращение производится к ближайшим информационным центрам.

Каждый информационный центр подключается к Интернету как минимум одной оптоволоконной линией ОС-48 (2,488 Гбит/с), по которой поступают запросы и отправляются ответы. Имеется дополнительная линия ОС-12 (622 Мбит/с) к резервному поставщику услуг на случай перерыва в работе основного. Имеются бесперебойные источники питания, дизельные генераторы на случай природных и других катаклизмов.

Схема обработки запросов в Google иллюстрируется рис. 16.23.

Рис. 16.23.

Прибыв в центр (1) запрос перенаправляется выравнивателем нагрузки к одному из многочисленных обработчиков запросов (2), и, параллельно, в систему проверки правописания (3) и сервер контекстной рекламы (4). Параллельно выполняется поиск запрошенного слова на индексных серверах (5), на которых хранятся записи о каждом слове в Сети.

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

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

Индексные серверы возвращают наборы идентификаторов документов (6), которые затем комбинируются в соответствии с логикой запроса.

На этом этапе происходит обращение к самим документам (7), извлекая из них названия, ссылки, а также фрагменты текста, окружающие запрошенные слова. Копии многих документов Сети хранятся на серверах документов всех информационных центров, в настоящее время их объем достигает сотен терабайтов. Для ускорения параллельного поиска документы также разделены на фрагменты. В итоге для обработки запроса приходится проверить не менее 100 Мегабайт данных.

После того, как результаты возвращаются обработчику запросов (8), они объединяются в соответствии с индексом страниц. Добавляется информация о возможных ошибках (если они есть, 9) и контекстная реклама (10). Результаты оформляются в формате HTML и передаются пользователю.

Для работы Google использует дешевые персональные компьютеры средней производительности. Объединив эти компьютеры они создали самый большой в мире кластер. Главный принцип – оптимизация отношения цена/производительность.

Дешевый персональный компьютер менее надежен, но абсолютно надежной техники не бывает. Поэтому, программное обеспечение Google написано так, чтобы работать на ненадежном оборудовании. Опыт Google показывает, что в год ломается 2% всех компьютеров. При этом, более половины отказов – жесткие диски, затем – блоки питания, потом – микросхемы памяти. Процессоры, если привыкли работать, совсем не ломаются.

В типичном компьютере Google установлен процессор Pentium с частотой 2 ГГц, 512 Мбайт оперативной памяти, 80 Гбайт диска и микросхема Ethernet, которая очень дешево стоит. Конструктивно, компьютеры размещаются в корпусах высотой 1u (5 см), компьютеры устанавливаются в стойки по 80 в каждую. Компьютеры подключаются к Ethernet через коммутатор, установленный внутри стойки. Все стойки в центре подключены к Ethernet также при помощи коммутатора. Для живучести имеется 2 дополнительных коммутатора. Структура типичного информационного центра приведена на рис. 16.24.

В Google использованы три правила создания крупных веб-серверов.

1.Любые компоненты ломаются и это надо учитывать.

2.Для повышения пропускной способности и доступности все должно дублироваться.

3.Необходимо оптимизировать отношение цена/производительность.

Таким образом, программное обеспечение должно быть отказоустойчивым. Самое лучшее оборудование ломается, если его достаточно много и ПО должно это учитывать. И программное и аппаратное обеспечение должно обладать избыточностью. Третий пункт вытекает из первых двух. Если система должным образом реагирует на сбои оборудования, нет смысла тратить лишние деньги на дорогостоящие компоненты. Лучше эти деньги потратить на дополнительное оборудование и повысить производительность.

Google в рамках проекта Caffeine, включающего в себя оптимизацию инфраструктуры поисковика, переделал файловую систему Google File System (GFS).

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

В спецификации GFS прямо написано, что время отклика на запрос менее важно, чем обеспечение высокой пропускной способности. Современные приложения Google, такие как Gmail и YouTube, напротив, требуют быстрого отклика на действия пользователя.

GFS состоит из главного узла и блочных серверов (master node и chunkservers соответственно). Главный узел раздает запросы к серверам, а те возвращают блоки данных. Одним из недостатков такой системы является наличие только одного главного узла. При отказе узла сервис может оказаться недоступным на долгое время. Дорабатывая GFS, разработчикам удалось сократить это время с нескольких часов до 10 секунд.

#### 16.8.4. Коммуникационное программное обеспечение для мультикомпьютеров

При программирования мультикомпьютера требуется специальное программное обеспечение для организации связей между процессорами и синхронизации.

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

1. Синхронная передача сообщений.

2. Буферная передача сообщений.

3. Неблокируемая передача сообщений.

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

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

Неблокируемая передача сообщений. Отправитель может продолжать работу сразу после вызова. Библиотека сообщает ОС, что она сделает вызов позднее, когда у нее будет время. Отправитель вообще не блокируется. Недостаток: отправитель после выполнения операции send не может снова использовать буфер сообщений, т.к. не исключена возможность, что сообщение еще не отправлено. Отправитель должен каким-то образом определять, когда он может использовать буфер. Все это усложняет ПО.

#### 16.8.5. Планирование

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

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

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | время |  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | Время |  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
время |  | 1 |  |  |  |  |  |  | 1 | 4 | 7 |  | 1 | 4 | 7
| 2 |  |  | 3 |  | 3
| 3 |  |  |  | 5 | 9 |  |  |  | 6
|  |  |  |  |  |  |  |  | 8 | 5
| 4 | 5 |  |  |  | 2 |  |
|  |  |  |  |  | 9 | 2
|  |  |  |  |  |  | 6 |  |  |
| 6 |  |  |  | 8 |  |  |  |  |  |  |  |  |  |  |  |
| 7 | 8 | 9 |  |  |  |  |  |  |  |  |  |  |  |  |
а |  | б |  | в
|  | Рис. 16.25 |  |

В более сложном алгоритме, задачи, которые не могут быть приняты к выполнению пропускаются, и берется первая задача, для выполнения которой достаточно ресурсов. Всякий раз, когда задача завершается очередь просматривается с первой задачи (рис. 16.25 б).

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

#### 16.8.5. Совместно используемая память на прикладном уровне

Из рассмотренных ранее вариантов построения больших систем можно сделать вывод, что мультикомпьютеры можно расширять до гораздо больших размеров, чем мультипроцессоры. Однако, мультикомпьютеры не имеют совместно используемой памяти на архитектурном уровне. Это привело к появлению таких систем с передачей сообщений как PVM и MPI. Большинство программистов предпочитают иллюзию совместно используемой памяти, даже если ее не существует.

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

##### 16.5.5.1. Распределенная совместно используемая память

Один из классов систем с общей памятью на прикладном уровне – это системы со страничной организацией памяти. Такая система называется DSM (Distributed Shared Memory – распределенная совместно используемая память).

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

Впервые идея была реализована в машине IVY. В результате в мультикомпьютере появилась память совместного использования, согласованная по последовательности. В целях улучшения производительности возможны оптимизации. Первая оптимизация, появившаяся в IVY, -- страницы, предназначенные только для чтения, могли присутствовать в разных ОЗУ.

Но даже при такой оптимизации трудно достичь высокой производительности, т.к. в случае записи информации в одну и ту же страницу разными процессорами, страница должна постоянно перемещаться от процессору к процессору. Такая ситуация называется ложным совместным использованием.

Проблему ложного совместного использования можно разрешить различными способами.

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

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

При возникновении ошибки из-за отсутствия страницы, необходимо определить ее местонахождение. Используются различные способы, в том числе и каталоги, как в машинах NUMA и COMA.

Фактически, система DSM представляет собой программную реализацию машин NUMA или COMA, в которой каждая страница трактуется как строка кэш-памяти.

#### 16.8.6. Производительность

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

##### 16.8.6.1. Метрика аппаратного обеспечения

В аппаратном обеспечении наибольший интерес представляет скорость работы процессоров, устройств ввода/вывода и сети. Поскольку скорость работы процессоров и устройств ввода/ вывода такая же как и в однопроцессорных системах, то особый интерес представляют те параметры, которые связаны с межсоединениями. Здесь два основных момента: время ожидания и пропускная способность.

Полное время ожидания – это время, которое требуется на то, чтобы процессор отправил пакет и получил ответ. Обычно интерес представляет время ожидания для пакетов минимального размера (одно слово или небольшая строка кэш-памяти). Для различных схем коммутации это время различно.

Для сетей с коммутацией каналов время ожидания складывается из времени установки соединения и времени передачи. Для установки нужно выслать пробный пакет для резервации ресурсов, а затем передать сообщение об этом. Когда пакет готов, его можно передавать на полной скорости. Тогда для передачи пакета размером в p бит в одну сторону потребуется время Ts+p/b секунд (Ts – общее время установки, b – пропускная способность). Если схема дуплексная, т.е. время установки на ответ не требуется, то для получения ответа потребуется Ts+2p/b секунд.

При пакетной коммутации не нужно посылать пробный пакет заранее, но все равно требуется некоторое время установки Ta. Здесь время передачи равно Tа+p/b, но за этот период пакет доходит только до первого коммутатора. При прохождении через коммутатор возникает задержка Td, которое состоит из времени обработки и задержки в очереди. Для n коммутаторов общее время ожидания в одну сторону составляет Ta+n(p/b+Td)+p/b, где последнее слагаемое – копирование пакета из последнего коммутатора в пункт назначения.

Время ожидания в одну сторону для коммутации без буферизации пакетов и «червоточины» в лучшем случае будет приближаться к Tа+p/b, поскольку здесь нет пробных пакетов и нет задержки, обусловленной промежуточным хранением.

Следующая характеристика аппаратного обеспечения – пропускная способность. Существует несколько показателей пропускной способности. Бисекционную пропускную способность уже рассматривали.

Суммарная пропускная способность – вычисляется путем суммирования пропускной способности всех каналов связи. Это число показывает максимальное число битов, которые можно передать сразу.

Средняя пропускная способность каждого процессора. Пропускная способность сети должна быть согласована с пропускной способностью процессоров.

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

##### 16.8.6.3. Способы достижения высокой производительности

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

Пусть у нас имеется 4 процессора, соединенные шиной (рис. 16.26 а). Шина имеет некоторую пропускную способность, например, b Мбайт/с. Расширим систему до 16 процессоров (рис. 16.26 б). Тогда пропускная способность каждого процессора сократится в 4 раза. Такая система не является расширяемой.

Рассмотрим другую топологию межсоединений (рис. 16.27 а, б). В такой топологии при добавлении новых процессоров добавляются новые каналы, поэтому при расширении системы пропускная способность на каждый процессор не снижается.

Пропускная способность – не единственный параметр. Добавления процессора к шине не увеличивает диаметр сети или время ожидания при отсутствии трафика, а добавление процессора к решетке – увеличивает. В такой конфигурации увеличение числа процессоров в 4 раза влечет увеличение диаметра сети, а, следовательно, и среднее время ожидания в 2 раза.

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

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

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

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

Некоторые машины автоматически переключаются от процесса к процессу после каждой команды, чтобы скрыть длительное время ожидания. Такая идея была реализована в одном из первых суперкомпьютеров CDC 6600. Было объявлено, что он содержит 10 периферийных процессоров, которые работают параллельно. А на самом деле он содержал только один периферийный процессор, который моделировал работу 10 процессоров.

Четвертая технология – использование неблокирующих записей. Обычно при выполнении команды записи в память процессор ждет, пока она не закончится и только потом продолжает работать. При наличии неблокирующих записей процессор продолжает работать, пока отрабатывается команда записи в память. Продолжать работы при выполнении операции считывания из памяти сложнее, однако реализуемо, если применить исполнение с изменением последовательности.

#### 16.8.7. Распределенные вычисления

Многие сегодняшние задачи очень масштабны и многоплановы. Для их решения требуется объединение ресурсов (интеллектуальных и материальных) многих организаций, зачастую разбросанных по всему миру. Рост потребностей в крупномасштабном сотрудничестве между организациями привел к развитию систем и технологий объединения разрозненных компьютеров в то, что получило название распределенных вычислений (grid computing). Систему распределенных вычислений можно рассматривать как очень большой, интернациональный слабо связанный гетерогенный кластер.

Целью системы распределенных вычислений является создание технической инфраструктуры, которая позволила бы из нескольких организаций, решающих общую задачу создать единую виртуальную организацию. Для реализации этой цели разрабатываются службы, инструменты и протоколы, что позволяет отдельным членам функционировать в рамках виртуальной организации. Система распределенных вычислений многомерна, с большим количеством участников – одноранговых узлов. Отличие от модели «клиент-сервер» состоит в том, что соединение не двухточечное, а многомерное. В системе распределенных вычислений необходимо обеспечить доступ к разным ресурсам, которыми обладает та или иная организация. Эта организация и решает, какие ресурсы доступны, а какие нет. Суть системы распределенных вычислений – управление доступом к ресурсам.

Один из вариантов представления системы распределенных вычислений – это представление ее в виде многоуровневой иерархической структуры.

Таблица 2

Уровень | Описание
Уровень приложений | Приложения, которые совместно и согласовано используют ресурсы.
Уровень коллективов | Исследования, посредничество, мониторинг, управление группами ресурсов.
Уровень ресурсов | Безопасность и управление доступом к отдельным ресурсам
Уровень инфраструктуры | Физические ресурсы, включая компьютеры, диски, сети, программы, данные

Нижний уровень – уровень инфраструктуры, объединяющий компоненты, из которых построена система распределенных вычислений.

Уровень ресурсов – отвечает за управление отдельными ресурсами. Назначение этого уровня состоит в том, чтобы обеспечить более высоким уровням однообразный интерфейс, при помощи которого они могли бы выяснять характеристики отдельных ресурсов, выполнять их мониторинг и безопасно использовать.

Уровень коллективов – оперирует группами ресурсов. Одна из функций заключается в исследовании системы распределенных вычислений, выявляя места размещения ресурсов. Уровень коллективов отвечает за размножение данных, включение в систему новых участников и ресурсов, политику использования ресурсов.

Уровень приложений – вершина иерархии. На этом уровне работают пользовательские приложения.

Одна из проблем распределенных вычислений – безопасность. С одной стороны, владелец ресурса желает иметь полный информацию о его использовании, с другой стороны излишний контроль может сделать совместное использование ресурсов слишком обременительным. Следует выбрать некоторую компромиссную модель.

Для поддержания взаимодействия между различными организациями и машинами необходимы стандарты как на предоставляемые услуги, так и на протоколы доступа к ним. Для управления процессом стандартизации сообщество распределенных вычислений создало организацию Global Grid Forum. Результатом ее работы стал шаблон для разработки стандартов OGSA (Open Grid Services Architecture – открытая архитектура служб распределенных вычислений). Разрабатываемые стандарты опираются на уже существующие, например для описания служб OGSA применяется язык WSDL (Web Services Definition Language – язык описания веб-служб) Стандартизированные на настоящий момент службы попадают под одну из следующих восьми категорий.

1. Службы инфраструктуры.

2. Службы управления ресурсами.

3. Службы данных.

4. Контекстные службы (описание требуемых ресурсов и политики их использования).

5. Информационные службы (получение информации о доступности ресурса)

6. Службы самоконтроля (поддержание заявленного качества услуг).

7. Службы защиты (применение политик безопасности).

8. Службы управления выполнением (управление потоком задач).