Реклама:

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

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

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

Мультипроцессоры и мультикомпьютеры

Рис. 8.15. Мультипроцессор из 16 процессоров, имеющих общую память (а); изображение, разделенное на 16 секций, каждую из которых анализирует отдельный процессор (б)

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

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

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

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

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

Поскольку процессоры в мультикомпьютере не могут взаимодействовать друг с другом простыми обращениями к общей памяти, процессоры обмениваются сообщениями через связывающую их коммуникационную сеть. В качестве примеров мультикомпьютеров можно назвать IBM BlueGene/L, Red Storm и кластер Google.

При отсутствии общей памяти, реализованной аппаратно, предполагается определенная программная структура. В мультикомпьютере невозможно иметь единое для всех процессоров виртуальное адресное пространство, позволяющее считывать и записывать информацию командами LOAD и STORE. Например, если процессор в верхнем левом углу рис. 8.15, б (присвоим этому процессору номер 0) обнаружит, что часть его объекта попадает в другую секцию, относящуюся к следующему процессору (пусть это будет процессор 1), он может просто продолжать считывать информацию из памяти, чтобы получить изображение хвоста самолета. Однако если то же самое обнаружит процессор 0 на рис. 8.16, б,

Мультипроцессоры и мультикомпьютеры

он не сможет просто считать информацию из памяти процессора 1. В данном случае алгоритм получения данных должен быть другим.

Рис. 8.16. Мультикомпьютер из 16 процессоров, каждый из которых имеет собственную память (а); битовая карта изображения с рис. 8.15, разделенная между 16 модулями памяти (б)

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

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

Возникает вопрос: зачем вообще создавать мультикомпьютеры, если мультипроцессоры гораздо проще программировать? Ответ прост: создать большой мультикомпьютер проще и дешевле, чем мультипроцессор с таким же количеством процессоров. Реализация общей памяти, совместно используемой несколькими сотнями процессоров, - это весьма сложная задача, а разработать мультикомпьютер, содержащий 10 ООО процессоров и более, довольно легко. Далее в этой главе мы рассмотрим мультикомпьютер с более чем 50 ООО процессорами.

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

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

Второй подход - использовать аппаратное обеспечение мультикомпыотера и операционную систему, которая будет моделировать общую память, предоставляя единое виртуальное адресное пространство, разбитое на страницы. При таком подходе получается распределенная общая память (Distributed Shared Memory, DSM), в которой каждая страница расположена в одном из модулей памяти (см. рис. 8.16, я), а каждая машина содержит собственную виртуальную память и собственные таблицы страниц [127]. Если процессор выполняет команду LOAD или STORE, обращаясь к странице, которой у него нет, происходит системное исключение. После этого операционная система находит нужную страницу и обращается к соответствующему процессору, чтобы тот выгрузил страницу из памяти и послал ее через внутреннюю коммуникационную сеть, по которой процессоры обмениваются сообщениями. Когда страница попадает процессу-получателю, она отображается на память, и выполнение прерванной команды возобновляется. По существу, операционная система просто получает недостающие страницы не с диска, а из памяти. При этом у пользователя создается впечатление, что машина имеет единую общую память. Далее в этой главе мы еще вернемся к распределенной общей памяти.

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

Мультипроцессоры и мультикомпьютеры

Рис. 8.17. Уровни, на которых можно реализовать общую память: аппаратная реализация (а); операционная система (б); программная реализация (в)

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

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

Многое можно сказать о программном обеспечении для параллельных компьютерных систем, однако сейчас мы должны вернуться к основной теме данной главы - архитектуре таких систем. За многие годы было предложено и построено множество видов параллельных компьютерных систем, поэтому хотелось бы их как-либо классифицировать. Это с разными результатами пытались делать многие исследователи [68, 207], но, к сожалению, хорошей классификации до сих пор нет. Чаще всего используют классификация Флинна [68], но даже она является достаточно грубой (табл. 8.3).

Таблица 8.3. Классификация параллельных компьютерных систем по Флинну

Потоки команд Потоки данных Категория Примеры

SISD

Классическая машина фон-Неймана

Много

SIMD

Векторный суперкомпьютер, матричный

     

процессор

Много

MISD

Не существует

Много

Много

MIMD

Мультипроцессор, мультикомпьютер

В основе классификации лежат понятия потоков команд и потоков данных.

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

Потоки команд и данных в какой-то степени независимы, поэтому существует 4 комбинации таких потоков (см. табл. 8.3). SISD (Single Instruction stream Single Data stream - один поток команд с одним потоком данных) - это классическая последовательная компьютерная архитектура фон Неймана. Компьютер фон Неймана имеет один поток команд и один поток данных и в каждый момент времени может выполнять только одно действие. У машины, относящихся к категории SIMD (Single Instruction-stream Multiple Data-stream - один поток команд с несколькими потоками данных), имеется один блок управления, выдающий по одной команде, но при этом есть несколько АЛУ, которые могут обрабатывать несколько наборов данных одновременно. Прототип SIMD-машин - процессор ILLIAC IV (см. рис. 2.6). Хотя SIMD-машины не относятся к числу широко распространенных, в некоторых обычных компьютерах для обработки мультимедийных данных используются SIMD-команды. SSE-команды в процессорах Pentium относятся к категории SIMD-команд. В любом случае существует одна область, где идеи, почерпнутые из "мира SIMD", выходят на первый план, - это потоковые процессоры. Потоковые процессоры специально разработаны для обработки мультимедийных данных и в будущем они могут играть важную роль [107]

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

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

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

Мультипроцессоры и мультикомпьютеры

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

В нашей классификации категория 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 Processor - процессор с массовым параллелизмом) относятся дорогостоящие суперкомпьютеры, которые состоят из большого количества процессоров, связанных высокоскоростной внутренней коммуникационной сетью. В качестве хорошо известного коммерческого примера можно назвать суперкомпьютер SP/3 компании IBM.

Вторая категория мультикомпьютеров включает обычные персональные компьютеры или рабочие станции (иногда смонтированные в стойки), которые связываются в соответствии с той или иной коммерческой коммуникационной технологией. С точки зрения логики принципиальной разницы здесь нет, но мощный суперкомпьютер стоимостью в миллионы долларов безусловно используется иначе, чем собранная конечными пользователями компьютерная сеть, которая обходится во много раз дешевле любой МРР-машины. Эти "доморощенные" системы иногда называют сетями рабочих станций (Network Of Workstations, NOW), кластерами рабочих станций (Cluster Of Workstattions, COW), или просто кластерами (cluster).

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