Исследование и анализ архитектуры компьютеров параллельного действия

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

При пакетной коммутации не нужно посылать пробный пакет в пункт назначения заранее, но все равно требуется некоторое время установки, Т_а, на компоновку пакета. Здесь время передачи в одну сторону составляет Т_а+р/Ь, но за этот период пакет доходит только до первого коммутатора. При прохождении через сам коммутатор получается некоторая задержка, Td, а затем происходит переход к следующему коммутатору и т. д. Время Та состоит из времени обработки и задержки в очереди (когда нужно ждать, пока не освободится выходной порт). Если имеется п коммутаторов, то общее время ожидания в одну сторону составляет T_a+n(p/b+Td)+p/b, где последнее слагаемое отражает копирование пакета из последнего коммутатора в пункт назначения.

Время ожидания в одну сторону для коммутации без буферизации пакетов и «червоточины» в лучшем случае будет приближаться к Т_а+р/Ь, поскольку здесь нет пробных пакетов для установки схемы и нет задержки, обусловленной промежуточным хранением. По существу, это время начальной установки для компоновки пакета плюс время на передачу битов. Следовало бы еще прибавить задержку на распространение сигнала, но она обычно незначительна. Следующая характеристика аппаратного обеспечения -- пропускная способность. Многие программы параллельной обработки, особенно в естественных науках, перемещают огромное количество данных, поэтому число байтов, которое система способна перемещать в секунду, имеет очень большое значение для производительности. Существует несколько показателей пропускной способности. Один из них -- пропускная способность между двумя секциями -- мы уже рассмотрели. Другой показатель -- суммарная пропускная способность -- вычисляется путем суммирования пропускной способности всех каналов связи. Это число показывает максимальное число битов, которое можно передать сразу. Еще один важный показатель -- средняя пропускная способность каждого процессора. Если каждый процессор способен выдавать только 1 Мбайт/с, то от сети с пропускной способностью между секциями в 100 Гбайт/с не будет толку. Скорость взаимодействия будет ограничена тем, сколько данных может выдавать каждый процессор.

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

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

Метрика аппаратного обеспечения показывает, на что способно аппаратное обеспечение. Но пользователей интересует совсем другое. Они хотят знать, насколько быстрее будут работать их программы на компьютере параллельного действия по сравнению с однопроцессорным компьютером. Для них ключевым показателем является коэффициент ускорения: насколько быстрее работает программа в п-процессорной системе по сравнению с 1-процессорной системой. Результаты обычно иллюстрируются графиком (рис. 8.). Здесь мы видим несколько разных параллельных программ, которые работают на мультикомпьютере, состоящем из 64 процессоров Pentium Pro. Каждая кривая показывает повышение скорости работы одной программы с к процессорами как функцию от к. Идеальное повышение скорости показано пунктирной линией, где использование к процессоров заставляет программу работать в к раз быстрее для любого к. Лишь немногие программы достигают совершенного повышения скорости, но есть достаточное число программ, которые приближаются к идеалу. Скорость работы N-объектной задачи с добавлением новых процессоров увеличивается очень стремительно; авари (африканская игра) ускоряется вполне сносно; но инвертирование матрицы нельзя ускорить более чем в пять раз, сколько бы процессоров мы не использовали.

Рис. 8. На практике программы не могут достичь идеального повышения скорости. Идеальный коэффициент ускорения показан пунктирной линией

Есть ряд причин, по которым практически невозможно достичь идеального повышения скорости: все программы содержат последовательную часть, они часто имеют фазу инициализации, они обычно должны считывать данные и собирать результаты. Большое количество процессоров здесь не поможет. Предположим, что на однопроцессорном компьютере программа работает Т секунд, причем доля (f) от этого времени является последовательным кодом, а доля (1-f) потенциально параллелизуется, как показано на рис. 9, а. Если второй код можно запустить на процессорах без издержек, то время выполнения программы в лучшем случае сократится с (l-f)T до (l-f)T/n, как показано на рис. 9, б. В результате общее время выполнения программы (и последовательной и параллельной частей) будет f T+(l-f )T/n. Коэффициент ускорения -- это время выполнения изначальной программы (Т), разделенное на это новое время выполнения:

Speedup= n /d+(n-l)f)

Для f=0 мы можем получить линейное повышение скорости, но для f>0 идеальное повышение скорости невозможно, поскольку в программе имеется последовательная часть. Это явление носит название закона Амдала.

Рис. 8.9. Программа содержит последовательную часть и параллелизуемую часть (а); результат параллельной обработки части программы (б)

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

6. Методы достижения высокой производительности

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

Рассмотрим 4 процессора, которые соединены шиной (рис. 8.10, а). А теперь представим, что мы расширили систему до 16 процессоров, добавив еще 12 (рис.10, б). Если пропускная способность шины составляет b Мбайт/с, то увеличив в 4 раза число процессоров, мы сократим имеющуюся пропускную способность каждого процессора с Ь/4 Мбайт/с до Ь/16 Мбайт/с. Такая система не является расширяемой.

А теперь проделаем то же действие с сеткой (решеткой) межсоединений (рис. 10, в, г). В такой топологии при добавлении новых процессоров мы добавляем новые каналы, поэтому при расширении системы суммарная пропускная способность на каждый процессор не снизится, как это было в случае с шиной. Отношение числа каналов к числу процессоров увеличивается от 1,0 при наличии 4 процессоров (4 процессора, 4 канала) до 1,5 при наличии 16 процессоров (16 процессоров, 24 канала), поэтому с добавлением новых процессоров суммарная пропускная способность на каждый процессор увеличивается.

Рис.10. Система из 4 процессоров, соединенных шиной (а); система из 16 процессоров, соединенных шиной (б); сетка межсоединений из 4 процессоров (в); сетка межсоединений из 16 процессоров (г)

Естественно, пропускная способность -- это не единственный параметр. Добавление процессоров к шине не увеличивает диаметр сети или время ожидания при отсутствии трафика, а добавление процессоров к решетке, напротив, увеличивает. Диаметр решетки пхп равен 2(п-1), поэтому в худшем случае время ожидания растет примерно как квадратный корень от числа процессоров. Для 400 процессоров диаметр равен 38, а для 1600 процессоров -- 78, поэтому если увеличить число процессоров в 4 раза, то диаметр, а следовательно, и среднее время ожидания вырастут приблизительно вдвое.

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

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

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

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

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

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

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

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

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

7. Программное обеспечение

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

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

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

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

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

1. Модели управления.

2. Степень распараллеливания процессов.

3. Вычислительные парадигмы.

4. Методы коммуникации.

5. Базисные элементы синхронизации.

8. Классификация компьютеров параллельного действия

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

Таблица 1. Классификация компьютеров параллельного действия, разработанная Флинном

В основе классификации лежат два понятия: потоки команд и потоки данных. Поток команд соответствует счетчику команд. Система с п процессорами имеет п счетчиков команд и, следовательно, п потоков команд.

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

Потоки команд и данных в какой-то степени независимы, поэтому существует 4 комбинации (см. табл. 1). SISD (Single Instruction stream Single Data stream -- один поток команд, один поток данных) -- это классический последовательный компьютер фон Неймана. Он содержит один поток команд и один поток данных и может выполнять только одно действие одномоментно. Машины SIMD (Single Instruction stream Multiple Data stream -- один поток команд, несколько потоков данных) содержат один блок управления, выдающий по одной команде, но при этом есть несколько АЛУ, которые могут обрабатывать несколько наборов данных одновременно. ILLIAC IV -- прототип машин SIMD. Существуют и современные машины SIMD. Они применяются для научных вычислений.

Машины MISD (Multiple Instruction stream Single Data stream -- несколько потоков команд, один поток данных) -- несколько странная категория. Здесь несколько команд оперируют одним набором данных. Трудно сказать, существуют ли такие машины. Однако некоторые считают машинами MISD машины с конвейерами.

Последняя категория -- машины MIMD (Multiple Instruction stream Multiple Data stream -- несколько потоков команд, несколько потоков данных). Здесь несколько независимых процессоров работают как часть большой системы. В эту категорию попадает большинство параллельных процессоров. И мультипроцессоры, и мультикомпьютеры -- это машины MIMD.

Мы расширили классификацию Флинна (схема на рис.11). Машины SIMD распались на две подгруппы. В первую подгруппу попадают многочисленные суперкомпьютеры и другие машины, которые оперируют векторами, выполняя одну и ту же операцию над каждым элементом вектора. Во вторую подгруппу попадают машины типа ILLIAC IV, в которых главный блок управления посылает команды нескольким независимым АЛУ.

Рис. 11. Классификация компьютеров параллельного действия

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

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

Во вторую подкатегорию машин MIMD попадают мультикомпьютеры, которые в отличие от мультипроцессоров не имеют памяти совместного использования на архитектурном уровне. Другими словами, операционная система в процессоре мультикомпьютера не может получить доступ к памяти, относящейся к другому процессору, просто путем выполнения команды LOAD. Ему приходится отправлять сообщение и ждать ответа. Именно способность операционной системы считывать слово из отдаленного модуля памяти с помощью команды LOAD отличает мультипроцессоры от мультикомпьютеров. Как мы уже говорили, даже в мультикомпью-тере пользовательские программы могут обращаться к другим модулям памяти с помощью команд LOAD и STORE, но эту иллюзию создает операционная система, а не аппаратное обеспечение. Разница незначительна, но очень важна. Так как мультикомпьютеры не имеют прямого доступа к отдаленным модулям памяти, они иногда называются машинами NORMA (NO Remote Memory Access -- без доступа к отдаленным модулям памяти).

Мультикомпьютеры можно разделить на две категории. Первая категория содержит процессоры МРР (Massively Parallel Processors -- процессоры с массовым параллелизмом) -- дорогостоящие суперкомпьютеры, которые состоят из большого количества процессоров, связанных высокоскоростной коммуникационной сетью. В качестве примеров можно назвать Cray T3E и IBM SP/2.

Вторая категория мультикомпьютеров включает рабочие станции, которые связываются с помощью уже имеющейся технологии соединения. Эти примитивные машины называются NOW (Network of Workstations -- сеть рабочих станций) и COW (Cluster of Workstattions -- кластер рабочих станций). В следующих разделах мы подробно рассмотрим машины SIMD, мультипроцессоры MIMD и мультикомпьютеры MIMD. Цель -- показать, что собой представляет каждый из этих типов, что собой представляют подкатегории и каковы ключевые принципы разработки. В качестве иллюстраций мы рассмотрим несколько конкретных примеров.

9. Компьютеры SIMD

Компьютеры SIMD (Single Instruction Stream Multiple Data Stream -- один поток команд, несколько потоков данных) используются для решения научных и технических задач с векторами и массивами. Такая машина содержит один блок управления, который выполняет команды по одной, но каждая команда оперирует несколькими элементами данных. Два основных типа компьютеров SIMD -- это массивно-параллельные процессоры (array processors) и векторные процессоры (vector processors). Рассмотрим каждый из этих типов по отдельности.

9.1. Массивно-параллельные процессоры

Идея массивно-параллельных процессоров была впервые предложена более 40 лет назад. Однако прошло еще около 10 лет, прежде чем такой процессор (ILLIACIV) был построен для NASA. С тех пор другие компании создали несколько коммерческих массивно-параллельных процессоров, в том числе СМ-2 и Maspar MP-2, но ни один из них не пользовался популярностью на компьютерном рынке.

Рис.12. Массивно-параллельный процессор 1ШАС IV

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

Хотя все массивно-параллельные процессоры соответствуют этой общей модели, они могут отличаться друг от друга в некоторых моментах. Первый вопрос -- это структура обрабатывающего элемента. Она может быть различной -- от чрезвычайно простой до чрезвычайно сложной. Самые простые обрабатывающие элементы -- 1-битные АЛУ (как в СМ-2). В такой машине каждый АЛУ получает два 1-битных операнда из своей локальной памяти плюс бит из слова состояния программы (например, бит переноса). Результат операции -- 1 бит данных и несколько флаговых битов. Чтобы совершить сложение двух целых 32-битных чисел, блоку управления нужно транслировать команду 1-битного сложения 32 раза. Если на одну команду затрачивается 600 не, то для сложения целых чисел потребуется 19,2 мке, то есть получается медленнее, чем в первоначальной IBM PC. Но при наличии 65 536 обрабатывающих элементов можно получить более трех миллиардов сложений в секунду при времени сложения 300 пикосекунд.

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

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

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

9.2 Мультипроцессоры с памятью совместного использования

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

Мультипроцессор, как и все компьютеры, должен содержать устройства ввода-вывода (диски, сетевые адаптеры и т. п.). В одних мультипроцессорных системах только определенные процессоры имеют доступ к устройствам ввода-вывода и, следовательно, имеют специальную функцию ввода-вывода. В других мультипроцессорных системах каждый процессор имеет доступ к любому устройству ввода-вывода. Если все процессоры имеют равный доступ ко всем модулям памяти и всем устройствам ввода-вывода и каждый процессор взаимозаменим с другими процессорами, то такая система называется SMP (Symmetric Multiprocessor -- симметричный мультипроцессор). Ниже мы будем говорить именно о таком типе систем.

9.3 Мультипроцессор Stanford DASH

Первый мультипроцессор CC-NUMA на основе каталога -- DASH (Directory Architecture for SHared memory -- архитектура на основе каталога для памяти совместного использования) -- был создан в Стенфордском университете как исследовательский проект. Данная разработка проста для понимания. Она повлияла на ряд промышленных изделий, например SGI Origin 2000. Мы рассмотрим 64-процессорный прототип данной разработки, который был реально сконструирован. Он подходит и для машин большего размера.

Схема машины DASH в немного упрощенном виде представлена на рис.13, а. Она состоит из 16 кластеров, каждый из которых содержит шину, 4 процессора MIPS R3000, 16 Мбайт глобальной памяти, а также некоторые устройства ввода-вывода (диски и т. д.), которые на схеме не показаны. Каждый процессор отслеживает только свою локальную шину. Локальная совместимость поддерживается с помощью отслеживания; для глобальной согласованности нужен другой механизм, поскольку глобального отслеживания не существует.

Рис. 13. Архитектура DASH (а); каталог DASH (б)

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

Глобальная память кластера 0 включает адреса с 0 по 16 М. Глобальная память кластера 1 включает адреса с 16 М по 32 М и т. д. Размер строки кэш-памяти составляет 16 байтов. Передача данных также осуществляется по строкам в 16 байтов. Каждый кластер содержит 1 М строк.

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

1 М элементов по 18 битов каждый означает, что общий размер каждого каталога превышает 2 Мбайт. При наличии 16 кластеров вся память каталога будет немного превышать 36 Мбайт, что составляет около 14% от 256 Мбайт. Если число процессоров на кластер возрастает, объем памяти каталога не меняется. Большое число процессоров на каждый кластер позволяет погашать стоимость памяти каталога, а также контроллера шины при наличии большого числа процессоров, сокращая стоимость на каждый процессор. Именно поэтому каждый кластер имеет несколько процессоров.

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

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

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

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

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

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

Протоколы DASH основаны на обладании и признании недействительности. В каждый момент у каждой строки имеется уникальный владелец. Для строк в состоянии UNCHANGED или SHARED владельцем является собственный кластер данной строки. Для строк в состоянии MODIFIED владельцем является тот кластер, в котором содержится единственная копия этой строки. Прежде чем записать что-либо в строку в состоянии SHARED, нужно найти и объявить недействительными все существующие копии. .

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

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

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

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

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

Если строка находится где-либо еще, пакет посылается в исходный кластер. Здесь может быть три варианта. Если строка находится в состоянии UNCACHED, она помечается как MODIFIED и отправляется к запрашивающему процессору. Если строка находится в состоянии SHARED, все копии объявляются недействительными, и после этого над строкой совершается та же процедура, что и над UNCASHED строкой. Если строка находится в состоянии MODIFIED (изменена), то запрос направляется в тот кластер, в котором строка содержится в данный момент. Этот кластер удовлетворяет запрос, а затем объявляет недействительной свою собственную копию.

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

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

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

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

Рис.14. Мультипроцессор NUMA-Q

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

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

В качестве связи между платами quad board используется интерфейс SCI. Этот интерфейс был разработан для того, чтобы заменить шину в больших мультипроцессорах и мультикомпьютерах (например, NUMA-Q). SCI поддерживает непротиворечивость кэшей, которая необходима в мультипроцессорах, а также позволяет быстро передавать блоки, что необходимо в мультикомпьютерах. SCI выдерживает нагрузку до 64 К узлов, адресное пространство каждого из которых может быть до 2⁴⁸ байтов. Самая большая система NUMA-Q состоит из 63 плат quad board, которые содержат 252 процессора и почти 2³⁸байтов физической памяти. Как видим, возможности SCI гораздо выше.

Кольцо, которое соединяет платы IQ-Link, соответствует протоколу SCI. В действительности это вообще не кольцо, а отдельные двухточечные кабели. Ширина кабеля составляет 18 битов: 1 бит синхронизации, 1 флаговый бит и 16 битов данных. Все они передаются параллельно. Каналы синхронизируются с тактовой частотой 500 МГц, при этом скорость передачи данных составляет 1 Гбайт/с. По каналам передаются пакеты. Каждый пакет содержит заголовок из 14 байтов, 0, 16, 64 или 256 байтов данных и контрольную сумму на 2 байта. Трафик состоит из запросов и ответов.

Физическая память в машине NUMA-Q 2000 распределена по узлам, так что каждая страница памяти имеет свою собственную машину. Каждая плата quad board может вмещать до 4 Гбайт ОЗУ. Размер строки кэш-памяти равен 64 байтам, поэтому каждая плата quad board содержит 2²⁶ строк кэш-памяти. Когда строка не используется, она находится только в одном месте -- в собственной памяти.

Однако строки могут находиться в нескольких разных кэшах, поэтому для каждого узла должна существовать таблица локальной памяти из 2²⁶ элементов, по которой можно находить местоположение строк. Один из возможных вариантов -- иметь на каждый элемент таблицы битовое отображение, которое показывает, какие платы IQ-Link содержат эту строку. Но в SCI не используется такое битовое отображение, поскольку оно плохо расширяется. (Напомним, что SCI может выдерживать нагрузку до 64 К узлов, и иметь 2²⁶ элементов по 64 К битов каждый было бы слишком накладно.)

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

Кроме таблицы локальной памяти, каждая плата IQ-Link содержит каталог с одним элементом для каждой строки кэш-памяти, которую плата в данный момент содержит. Поскольку размер кэш-памяти составляет 32 Мбайт, а строка кэш-памяти включает 64 байта, каждая плата IQ-Link может содержать до 2¹⁹ строк кэш-памяти. Поэтому каждый каталог содержит 2¹⁹ элементов, по одному элементу на каждую строку кэш-памяти.

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

Рис. 15. Протокол SCI соединяет всех держателей данной строки в дважды связанный список. В данном примере строка находится одновременно в трех узлах

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

Последние 13 битов -- это тег (нужен для идентификации строки). Напомним, что самая большая система NUMA-Q 2000 содержит 63х2³²=2³⁸ байтов ОЗУ, поэтому имеется почти 2³² строк кэш-памяти. Все кэши прямого отображения, поэтому 2³² строк отображаются на 2¹⁹ элементов кэш-памяти, существует 2¹³ строк, которые отображаются на каждый элемент. Следовательно, 13-битный тег нужен для того, чтобы показывать, какая именно строка находится там в данный момент.

Каждая строка имеет фиксированную позицию только в одном блоке памяти (исходном). Эти строки могут находиться в одном из трех состояний: UNCACHED (некэшированном), SHARED (совместного использования) и MODIFIED (измененном). В протоколе SCI эти состояния называются HOME,

FRESH и GONE соответственно, но мы во избежание путаницы будем использовать прежнюю терминологию. Состояние UNCACHED означает, что строка не содержится ни в одном из кэшей на плате IQ-Link, хотя она может находиться в локальной кэш-памяти на той же самой плате quad board. Состояние SHARED означает, что строка находится по крайней мере в одной кэш-памяти платы IQ-Link, а память содержит обновленные данные. Состояние MODIFIED означает, что строка находится в кэш-памяти на какой-то плате IQ-Link, но, возможно, эта строка была изменена, поэтому память может содержать устаревшие данные.

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

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

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

Разберемся, как обрабатывается команда READ. Если процессор, выполняющий эту команду, не может найти нужную строку на своей плате, то плата IQ-Link посылает пакет исходной плате IQ-Link, которая затем смотрит на состояние этой строки. Если состояние UNCACHED, оно превращается в SHARED, и нужная строка берется из основной памяти. Затем таблица локальной памяти в исходном узле обновляется. После этого таблица содержит одноэлементный список, указывающий на узел, в кэш-памяти которого в данный момент находится строка.

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

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

10 Мультикомпьютеры с передачей сообщений

Как видно из схемы на рис. 11, существует два типа параллельных процессоров MIMD: мультипроцессоры и мультикомпьютеры. В предыдущем разделе мы рассматривали мультипроцессоры. Мы увидели, что мультипроцессоры могут иметь разделенную память, доступ к которой можно получить с помощью обычных команд LOAD и STORE. Такая память реализуется разными способами, включая отслеживающие шины, многоступенчатые сети, а также различные схемы на основе каталога. Программы, написанные для мультипроцессора, могут получать доступ к любому месту в памяти, не имея никакой информации о внутренней топологии или схеме реализации. Именно благодаря такой иллюзии мультипроцессоры весьма популярны.

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

В Sequent NUMA-Q дошли до 256 процессоров, но ценой неодинакового времени доступа к памяти. Ниже мы рассмотрим два мультикомпьютера, которые содержат 2048 и 9152 процессора соответственно. Через много лет кто-нибудь сконструирует мультипроцессор, содержащий 9000 узлов, но к тому времени мультикомпьютеры будут содержать уже 100 000 узлов.

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