Структуры аппаратного обеспечения
В данной главе дается обзор основных атрибутов архитектуры современных компьютеров. В следующем разделе описаны приложения параллельного программирования и использование архитектуры в них. Описание начинается с однопроцессорных систем и кэш-памяти. Затем рассматриваются мультипроцессоры с разделяемой памятью. В конце описываются машины с распределенной памятью, к которым относятся многомашинные системы с распределенной памятью и сети машин.
1.2.1. Процессоры и кэш-память
Современная однопроцессорная машина состоит из нескольких компонентов: центрального процессорного устройства (ЦПУ), первичной памяти, одного или нескольких уровней кэш-памяти (кэш), вторичной (дисковой) памяти и набора периферийных устройств (дисплей, клавиатура, мышь, модем, CD, принтер и т.д.). Основными компонентами для выполнения программ являются ЦПУ, кэш и память. Отношения между ними изображены на рис. 1.1.
Процессор выбирает инструкции из памяти, декодирует их и выполняет. Он содержит управляющее устройство (УУ), арифметико-логическое устройство (АЛУ) и регистры. УУ вырабатывает сигналы, управляющие действиями АЛУ, системой памяти и внешними устройствами. АЛУ выполняет арифметические и логические инструкции, определяемые набором инструкций процессора. В регистрах хранятся инструкции, данные и состояние машины (включая счетчик команд).
Кэш — это небольшой по объему, но скоростной модуль памяти, используемый для ускорения выполнения программы. В нем хранится содержимое областей памяти, часто используемых процессором. Причина использования кэш-памяти состоит в том, что в большинстве программ наблюдается временная локальность, означающая, что если произошло обращение к некоторой области памяти, то, скорее всего, в ближайшем будущем обращения к этой области повторятся. Например,
инструкции внутри циклов выбираются и выполняются многократно.
Когда программа обращается к адресу в памяти, процессор сначала ищет его в кэше. Если данные находятся там (происходит попадание в кэш), то они считываются из кэша.
Если данных в кэше нет (промах), то данные считываются из первичной памяти и в процессор, и в кэш-память. Аналогично, когда программа записывает данные, они помещаются в первичную память и, возможно, в локальный кэш. В сквозном кэше данные помещаются в память немедленно, в кэше с обратной записью — позже. Ключевой момент состоит в том, что после записи содержимое первичной памяти временно может не соответствовать содержимому кэша.
Чтобы ускорить передачу (увеличить пропускную способность) между кэшем и первичной памятью, в элемент кэш-памяти обычно включают непрерывную последовательность слов из памяти. Эти элементы называются блоками или строками кэша. При промахе из памяти в кэш
22 Глава 1. Обзор области параллельных вычислений
передается полная строка. Это эффективно, поскольку в большинстве программ наблюдается пространственная локальность, т.е. за обращением к одному слову памяти вскоре последуют обращения к другим близлежащим словам.
В современных процессорах обычно есть два типа кэша. Кэш уровня 1 находится ближе к процессору, а кэш уровня 2 — между кэшем уровня 1 и первичной памятью. Кэш уровня 1 меньше и быстрее, чем кэш уровня 2, и зачастую иначе организован. Например, кэшпамять уровня 1 обычно отображается непосредственно, а кэш уровня 2 является множественно-ассоциативным.2
Кроме того, кэш уровня 1 часто содержит отдельные области кэшпамяти для инструкций и данных, в то время как кэш уровня 2 обычно унифицирован, т.е. в нем хранятся и данные, и инструкции.
Проиллюстрируем различия в скорости работы уровней иерархии памяти. Доступ к регистрам происходит за один такт работы процессора, поскольку они невелики и находятся внутри ЦПУ. Данные кэш-памяти уровня 1 также доступны за один-два такта. Однако для доступа к кэш-памяти уровня 2 необходимо порядка 10 тактов, а к первичной памяти — от 50 до 100 тактов. Аналогичны и различия в размере типов памяти: ЦПУ содержит несколько десятков регистров, кэш уровня 1 — несколько десятков килобайт, кэш уровня 2 — порядка мегабайта, а первичная память — десятки и сотни мегабайт.
1.2.2. Мультипроцессоры с разделяемой памятью
В мультипроцессоре с разделяемой памятью процессоры и модули памяти связаны с помощью соединительной сети (рис. 1.2). Процессоры совместно используют первичную память, но каждый из них имеет собственный кэш.
В небольшом мультипроцессоре, имеющем от двух до (порядка) 30 процессоров, соединительная сеть реализована в виде шины памяти или, возможно, матричного коммутатора. Такой мультипроцессор называется однородным (UMA machine — от "uniform memory access"), поскольку время доступа каждого из процессоров к любому участку памяти одинаково. Однородные машины также называются симметричными мультипроцессорами.
В больших мультипроцессорах с разделяемой памятью, включающих десятки или сотни процессоров, память организована иерархически. Соединительная сеть имеет вид древообразного набора переключателей и областей памяти. Следовательно, одна часть памяти ближе к определенному процессору, другая — дальше от него. Такая организация памяти
В непосредственно отображаемом кэше каждый адрес памяти отображается в один элемент кэша, а в множественно-ассоциативном — во множество элементов (обычно два или четыре). Таким образом, если два адреса памяти отображаются в одну и ту же ячейку, в непосредственно отображаемом кэше может находиться только ячейка, к которой производилось самое последнее обращение, а в ассоциативном — обе ячейки. С другой стороны, непосредственно отображаемый кэш быстрее, поскольку проще выяснить, есть ли данное слово в кэше.
1.2. Структуры аппаратного обеспечения 23
позволяет избежать перегрузки, возникающей при использовании одной шины или коммутатора, и приводит к неравным временам доступа, поэтому такие мультипроцессоры называются неоднородными (NUMA machines).
В машинах обоих типов у каждого процессора есть собственный кэш. Если два процессора ссылаются на разные области памяти, их содержимое можно безопасно поместить в кэш каждого из них.
Проблема возникает, когда два процессора обращаются к одной области памяти примерно одновременно. Если оба процессора только считывают данные, в кэш каждого из них можно поместить копию данных. Но если один из процессоров записывает в память, возникает проблема согласованности кэша: в кэш-памяти другого процессора теперь содержатся неверные данные. Значит, необходимо либо обновить кэш другого процессора, либо признать содержимое кэша недействительным. В каждом мультипроцессоре протокол согласования кэшпамяти должен быть реализован аппаратно. Один из способов состоит в том, чтобы каждый кэш "следил" за адресной шиной, отлавливая ссылки на области памяти, находящиеся в нем.
Запись в память также приводит к проблеме согласованности памяти: когда в действительности обновляется первичная память? Например, если один процессор выполняет запись в область памяти, а другой позже считывает данные из этой области, будет ли считано обновленное значение? Существует несколько различных моделей согласованности памяти. Последовательная согласованность — это наиболее сильная модель. Она гарантирует, что обновления памяти будут происходить в некоторой последовательности, причем каждому процессору будет "видна" одна и та же последовательность. Согласованность процессоров — более слабая модель. Она обеспечивает, что записи в память, выполняемые каждым процессом, совершаются в том порядке, в котором их производит процессор, но записи, инициированные различными процессорами, для других процессоров могут выглядеть по-разному. Еще более слабая модель— согласование освобождения, при которой первичная память обновляется в указанных программистом точках синхронизации.
Проблема согласования памяти представляет противоречия между простотой программирования и расходами на реализацию. Программист интуитивно ожидает последовательного согласования, поскольку программа считывает и записывает переменные независимо от того, в какой части машины они хранятся в действительности.
Когда процесс присваивает переменной значение, программист ожидает, что результаты этого присваивания станут немедленно известными всем процессам программы. С другой стороны, последовательное согласование очень дорого в реализации и замедляет работу машины. Дело в том, что при каждой записи аппаратная часть должна проверить все кэши (и, возможно, обновить их или сделать недействительными) и модифицировать первичную память. Вдобавок, эти действия должны быть неделимыми. Вот почему в мультипроцессорах обычно реализуется более слабая модель согласования памяти, а программистам необходимо вставлять инструкции синхронизации памяти. Это часто обеспечивают компиляторы и библиотеки, так что прикладной программист этим может не заниматься.
Как было отмечено, строки кэш-памяти часто содержат последовательности слов, которые блоками передаются из памяти и обратно. Предположим, что переменные х и у занимают по одному слову и хранятся в соседних ячейках памяти, отображенных в одну и ту же строку кэш-памяти. Пусть некоторый процесс выполняется на процессоре 1 мультипроцессора и производит записи и чтения переменной х. Наконец, допустим, что еще один процесс, выполняемый на процессоре 2, считывает и записывает переменную у. Тогда при каждом обращении процессора 1 к переменной х строка кэш-памяти этого процессора будет содержать и копию переменной у. Аналогичная картина будет и в кэше процессора 2.
Ситуация, описанная выше, называется ложным разделением: процессы в действительности не разделяют переменные х и у, но аппаратная часть кэш-памяти интерпретирует обе переменные как один блок. Следовательно, когда процессор 1 обновляет переменную х, должна быть признана недействительной и обновиться строка кэша в процессоре 2, содержащая их, ну. Таким же образом, когда процессор 2 обновляет значение у, строка кэш-памяти, содержащая значения х и у, в процессоре 1 тоже должна быть обновлена или признана недействительной. Эти операции замедляют работу системы памяти, поэтому программа будет выполняться намного
24 Глава 1. Обзор области параллельных вычислений
медленнее, чем тогда, когда две переменные попадают в разные строки кэша. Главное здесь — чтобы программист ясно понимал, что процессы не разделяют переменные, когда фактически система памяти вынуждена обеспечивать их разделение и тратить время на управление им.
Чтобы избежать ложного разделения, программист должен гарантировать, что переменные, записываемые различными процессами, не будут находиться в смежных областях памяти. Одно из решений этой проблемы заключается в выравнивании, т.е. резервировании фиктивных переменных, которые просто занимают место и отделяют реальные переменные друг от друга. Это пример противоречия между временем и пространством: для сокращения времени выполнения приходится тратить пространство.
Итак, мультипроцессоры используют кэш-память для повышения производительности. Однако иерархичность памяти порождает проблемы согласованности кэша и памяти, а также возможность ложного разделения. Следовательно, для получения максимальной производительности на данной машине программист должен знать характеристики системы памяти и писать программы, учитывая их. К этим вопросам мы еще вернемся.
1.2.3. Мультикомпьютеры с распределенной памятью и сети
В мультипроцессоре с распределенной памятью тоже есть соединительная сеть, но каждый процессор имеет собственную память. Как показано на рис. 1.3, соединительная сеть и модули памяти меняются местами по сравнению с их положением в мультипроцессоре с разделяемой памятью. Соединительная сеть поддерживает передачу сообщений, а не чтение и запись в память. Следовательно, процессоры взаимодействуют, передавая и принимая сообщения. У каждого процессора есть свой кэш, но из-за отсутствия разделения памяти нет проблем согласованности кэша и памяти.
Мультикомпьютер (многомашинная система) — это мультипроцессор с распределенной памятью, в котором процессоры и сеть расположены физически близко (в одном помещении).
По этой причине такую многомашинную систему часто называют тесно связанной (спаренной) машиной. Она одновременно используется одним или небольшим количеством приложений; каждое приложение задействует выделенный набор процессоров. Соединительная сеть с большой пропускной способностью предоставляет высокоскоростной путь связи между процессорами. Обычно она организована в гиперкуб или матричную структуру. (Машины со структурой типа гиперкуб были одними из первых многомашинных систем.)
Сетевая система — это многомашинная система с распределенной памятью, узлы которой связаны с помощью локальной сети типа Ethernet или такой глобальной сети, как Internet. Сетевые системы называются слабо связанными мультикомпьютерами. Здесь процессоры взаимодействуют также с помощью передачи сообщений, но время их доставки больше, чем в многомашинных системах, и в сети больше конфликтов. С другой стороны, сетевая система строится на основе обычных рабочих станций и сетей, тогда как в многомашинной системе часто есть специализированные компоненты, особенно у связующей сети.
1 3 Приложения и стили программирования 25
Сетевая система, состоящая из набора рабочих станций, часто называется сетью рабочих станций (network of workstations — NOW) или кластером рабочих станций (cluster of workstations — COW). Все рабочие станции выполняют одно или несколько приложений, возможно, связанных между собой. Популярный сейчас способ построения недорогого мультипроцессора с распределенной памятью — собрать так называемую машину Беовулфа (Beowulf). Она состоит из базового аппаратного обеспечения и таких бесплатных программ, как чипы к процессорам Pentium, сетевые карты, диски и операционная система Linux. (Имя Беовулф взято из старинной английской поэмы, первого шедевра английской литературы.)
Существуют также гибридные сочетания мультипроцессоров с распределенной и разделяемой памятью. Узлами системы с распределенной памятью могут быть мультипроцессоры с разделяемой памятью, а не обычные процессоры.Возможен вариант, когда связующая сеть поддерживает и механизмы передачи сообщений, и механизмы прямого доступа к удаленной памяти (на сегодня это наиболее мощные машины). Наиболее общая комбинация — машина с поддержкой распределенной разделяемой памяти, т.е. распределенной реализации абстракции разделяемой памяти. Она облегчает программирование многих приложений, но ставит проблемы согласованности кэша и памяти. (В главе 10 описана распределенная разделяемая память и ее реализация в программном обеспечении.)
