работа (стр. 2 из 7)

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

1.2. Разновидности многопроцессорных систем

В соответствии с классификацией Флинна к многопроцессорным ЭВМ относятся ЭВМ с множественным потоком команд и множественным потоком данных (МКМД-ЭВМ или MIMD-ЭВМ).

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

МКМД-ЭВМ имеют две разновидности: ЭВМ с разделяемой (общей) и распределенной (индивидуальной) памятью. Структура этих ЭВМ представлена на рис. 1.2.1 [8].

Главное различие между МКМД-ЭВМ с общей и индивидуальной (локальной, распределенной) памятью состоит в характере адресной системы.

a b

Рис.1.2.1. Структура ЭВМ с разделяемой (а) и индивидуальной (b) памятью.

Здесь: П – процессор, ИП - индивидуальная память.

В машинах с общей памятью адресное пространство всех процессоров является единым, следовательно, если в программах нескольких процессоров встречается одна и та же переменная VAL, то эти процессоры будут обращаться в одну физическую ячейку общей памяти. Это вызывает как положительные, так и отрицательные последствия [8, 9]:

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

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

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

МКМД-ЭВМ с индивидуальной памятью получили большое распространение ввиду относительной простоты их архитектуры. В таких ЭВМ межпроцессорный обмен осуществляется с помощью передачи сообщений.

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

1.3. Техническая реализация параллельных ЭВМ

Современные многопроцессорные системы делятся на три группы:

симметричные мультипроцессоры (SMP); системы с массовым параллелизмом (МРР); кластеры [9].

Симметричные мультипроцессоры SMP (Symmetric Multi Processors) используют принцип разделяемой памяти. В этом случае система состоит из нескольких однородных процессоров и массива общей памяти (обычно из нескольких независимых блоков). Все процессоры имеют доступ к любой ячейке памяти с одинаковой скоростью. Процессоры подключены к памяти с помощью общей шины или коммутатора. Аппаратно поддерживается когерентность кэш-памяти. Наличие общей памяти сильно упрощает взаимодействие процессоров между собой, однако накладывает сильные ограничения на их число – не более 32 в реальных системах. Вся система работает под управлением единой ОС.

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

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

Первым кластером на рабочих станциях был Beowulf [10]. Проект Beowulf начался летом 1994 года сборкой в научно-космическом центре NASA 16-процессорного кластера на Ethernet-кабеле. С тех пор кластеры на рабочих станциях обычно называют Beowulf-кластерами. Любой Beowulf-кластер состоит из отдельных машин (узлов) и объединяющей их сети (коммутатора). Кроме ОС, необходимо установить и настроить сетевые драйверы, компиляторы, ПО поддержки параллельного программирования и распределения вычислительной нагрузки. В качестве узлов обычно используются однопроцессорные ПЭВМ с быстродействием 1 ГГц и выше или SMP-серверы с небольшим числом процессоров (обычно 2-4).

Для получения хорошей производительности межпроцессорных обменов, как правило, используют полнодуплексную сеть Fast Ethernet с пропускной способностью 100 Mбит/с. При этом для уменьшения числа коллизий устанавливают несколько "параллельных" сегментов Ethernet, или соединяют узлы кластера через коммутатор (switch).

В качестве операционных систем обычно используют OC Linux или Windows NT и ее варианты. В качестве языков программирования используются С, С++ и старшие версии языка Fortran.

Наиболее распространенным интерфейсом параллельного программирования в модели передачи сообщений является MPI (Message Passing Interface).

1.4. Системы программирования для многопроцессорных систем.

Стандарт MPI

Основными средствами программирования для многопроцеccорных систем являются две библиотеки, оформленные как стандарты: библиотека OpenMP для систем с общей памятью (для SMP-систем) и библиотека MPI для систем с индивидуальной памятью.

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

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

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

1. MPI - библиотека функций, а не язык. Она определяет состав, имена, вызовы функций и результаты их работы. Программы, которые пишутся на языках FORTRAN, C и C++, компилируются обычными компиляторами и связаны с MPI-библиотекой.

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

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

Процессы в MPI принадлежат группам. Если группа содержит n процессов, то процессы нумеруются внутри группы номерами, которые являются целыми числами от 0 до n-l. Имеется начальная группа, которой принадлежат все процессы в реализации MPI.

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