Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции - Параллельные процесы - файл Лек.1-2.doc


Лекции - Параллельные процесы
скачать (1337 kb.)

Доступные файлы (2):

Лек.1-2.doc771kb.01.09.2008 20:28скачать
Лек.3-4.doc791kb.08.09.2008 13:26скачать

содержание

Лек.1-2.doc

Вводная часть


Японский проект параллельных интеллектуальных вычислительных систем 5-го поколения (конец 80-х – начало 90-х годов) не увенчался успехом [1], но его идеи и достижения даром не пропали, и сейчас без особой помпы в США развиваются работы по программе Американской Стратегической Компьютерной Инициативы (ASCI), в рамках которой к 2004 г. предполагалось создать на базе процессоров Pentium вычислительную систему на 100 тысяч процессоров с производительностью 100 терафлопс (1014 операций с плавающей запятой в секунду) с основным предназначением – развитие ядерного оружия без его натурных испытаний; в настоящее время уже реализован образец ASCI White на базе 8192 процессоров IBM SP Power3 375МГц с производительностью 7.3 тфлопс [2] (9.9 тфлопс). Безусловным лидером TOP500 является векторный суперкомпьютер NEC Earth Simulator с производительностью порядка 35.8 ТФлопс (40.9 ТФлопс). Наряду с военными применениями такого рода техника найдет широкое применение для прогнозирования погоды, синтеза новых лекарственных веществ с требуемыми свойствами, обеспечения защиты банковских систем и т.п. В [2] приведена таблица распределения суперкомпьютеров по странам и организациям и, оказывается, большая их часть используется правительственными учреждениями и банками, а не научно-исследовательскими организациями. К сожалению, вычислительная система, созданная в нашей стране занимает на данный момент только 95-е место в рейтинге с производительностью около 734 ГФлопс (1024ГФлопс). Многопроцессорные вычислительные системы и параллельное программирование приходят к нам не только со стороны суперЭВМ, но и от широко распространенных персональных ЭВМ на базе процессоров Intel (многопроцессорные конфигурации, параллельные процессы), что определяет практическую значимость и актуальность курса «Параллельное программирование».

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

Основные архитектурные особенности современных вычислительных машин


П
6
рограммы составляются для выполнения на вычислительных системах, при этом традиционно используемые системы, реализующие принцип программного управления Джона фон Неймана (последовательные ЭВМ) [3], в настоящее время разрабатываются так, что программы, написанные для одной последовательной ЭВМ, можно практически без изменений переносить на другие, хотя и здесь, конечно, имеются архитектурные различия, например длина машинного слова. Тем не менее, последовательное программирование достаточно унифицировано и проблемы переноса программ с одной машины на другую не слишком сложны, так как в их основе лежит одна и та же модель организации вычислений, которая может быть проиллюстрирована рис. 1. Здесь программа (коды операций) и обрабатываемые данные хранятся в одной Оперативной Памяти (ОП) – линейном адресном пространстве, где каждой ячейке памяти (например, байту) поставлен во взаимно однозначное соответствие её номер – адрес. Программа выполняется за счет того, что в Счетчик Адреса (СчА) записывается адрес байта, начиная с которого располагается код первой команды программы. Устройство Управления

Р
6
ис. 1

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

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

В последнее время архитектура Джона фон Неймана все чаще подвергается критике из-за ее недостатков, и на арену выходят в частности решения, основанные на управлении не потоком команд (программой), а данными.
^

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


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

В
8

8
се вычислительные системы Флинн классифицировал по потокам команд и данных следующим образом:



где SISD (ОКОД) – одиночный поток команд, одиночный поток данных;

SIMD (ОКМД) – одиночный поток команд, множественный поток данных;

MISD (МКОД) – множественный поток команд, одиночный поток данных;

MIMD (МКМД) – множественный поток команд, множественный поток данных.

Первый из этих классов – ОКОД – соответствует последовательным ЭВМ с одним СчА, через который реализуется один поток команд, определяющий обработку одного потока данных.

Второй класс – ОКМД – соответствует ситуации, когда в системе имеется несколько АЛУ, каждое со своей памятью данных, а УУ и СчА – в одном экземпляре. Так же, как и в системах ОКОД, УУ считывает из области кодов очередную команду, дешифрирует ее, готовится к выполнению очередной команды, но данная команда уже поступает на выполн
8
ение не в одно АЛУ, а в несколько одновременно, и каждое из них считывает операнды из ячеек с указанными адресами, но каждое из своей локальной ОП - области данных. Эта ситуация может быть проиллюстрирована следующей бытовой ситуацией: руководитель туристической группы дает указания туристам по заполнению, например, таможенной декларации, при пересечении границы – «Напишите фамилию в пункте 1» и т.д. Здесь руководитель выступает в роли общего УУ, каждый турист – в роли АЛУ, а его память и бланк – в роли локальной памяти данных. Системы ОКМД называют часто векторными или матричными, так как элементарные процессоры (АЛУ + локальная ОП) организованы в виде одномерного (вектор) или многомерного (в частности, двумерного) массива.

Третий класс – МКОД – по мнению ряда исследователей, соответствует параллельным системам конвейерного типа. Здесь имеется несколько исполнительных процессоров (ИП), каждый из которых работает под управлением своего потока команд, но обрабатываемые данные последовательно передаются от одного процессора к другому. Так, например, осуществляется сборка автомобилей на современных заводах – одно изделие продвигается последовательно по ступеням конвейера от первой к последней, на каждой ступени подвергаясь специфическим преобразованиям. Готовое изделие получается на выходе последней ступени конвейера. В конвейерных вычислительных системах также результат вычислений получается только на выходе последней ступени. Обработка каждого данного изделия (задачи) протекает столько же времени и так же точно, как при последовательной обработке, но за счет того, что обрабатывающих устройств много, сделав некоторую операцию для данной задачи, обрабатывающая ступень может перейти к выполнению такой же операции, но уже для другой задачи. Для эффективной работы конвейера требуется поток однотипных задач, тогда при условии, что на каждой ступени конвейера операция выполняется за время , результат на выходе конвейера в стационарном режиме будет также получаться со скважностью . Для эффективной работы систем типа ОКМД требуется, чтобы была возможность массового распараллеливания алгоритма по данным, т.е. чтобы много разных данных обрабатывались единообразно. Системы обоих указанных типов нашли широкое применение, так как многие математические и физические задачи удовлетворяют указанным ограничениям. В то же время, во многих ситуациях алгоритмы обработки более сложны, данные неоднородны, и системы указанных типов в таких ситуациях недостаточно эффективны.

Применительно к системам МКОД имеет смысл отметить, что большинство ученых все-таки полагают, что реальных прототипов таких систем в мире не существует.

Системы класса МКМД позволяют каждому исполнительному процессору ра­ботать под управлением своего потока команд. Такая архитектура – наиболее гибкая и распространенная из рассмотренных, однако наиболее сложна в реализации и программировании.

В последнее время стал популярен подход ОПМД (SPMD) – одна программа – много потоков данных, когда каждый ИП работает под управлением своего УУ, в локальную ОП каждого ИП загружена одна и та же программа (коды), но разные данные. Такой подход чаще всего используется при кластерных вычислениях.

Одним из недостатков классификации Флинна является чрезмерная заполненность класса MIMD. Этот недостаток попытался устранить Р.Хокни. Классификация Хокни приведена на рис. 2.



Рис. 2

Конвейерные MIMD обрабатывают множественный поток данных одним конвейером, работающим в режиме разделения времени между потоками.

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

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

1. Примеры параллельных вычислительных систем

1.1. CRAY-X-MP


CRAY-X-MP – векторная двухпроцессорная ВС [6] (рис. 3).



Рис. 3

В данной системе каждый из двух процессоров Пр - это процессор CRAY-1 (рис. 4).

О
10
перативная память ОП (2М 64-разрядных слов) - разделяемая и оба процессора могут обращаться к ней одновременно. Время машинн
ого такта – 9,5 нс. Эта система была разработана в 1982-1983 годах. Промежуточная память – 32М 64-разрядных слов. Далее рассмотрим состав процессора. Блок адресных регистров процессора содержит 8 общих адресных и 8 общих скалярных регистров, также имеется 32 семафорных одноразрядных регистра (регистры для синхронизации). Кроме того, процессор содержит 12 функциональных устройств (ФУ), организованных в 4 группы:

векторные функциональные устройства – ^ ВФУ;

функциональные устройства для работы с плавающей запятой – ФУПЗ;

скалярные функциональные устройства – СФУ;

адресные функциональные устройства – АФУ.



Рис. 4

Все ФУ - конвейерного типа и могут работать параллельно друг с другом.

Между памятью и ФУ находятся следующие группы регистров: 8 адресных (АР), 64 буферных адресных (БАР), 8 скалярных (СР), 64 буферных скалярных (БСР), 8 64-элементных векторных регистров (ВР) : каждый элемент – слово, все слова 64-разрядные.

Дальнейшим развитием явилась в частности вычислительная машина Cray C90, созданная в самом начале 90-х годов. Время такта для нее составляло 4,1 нс (250 МГц), размер машинного слова – 80 бит, где 64 бита – сами данные, а еще 16 бит предназначались для коррекции ошибок. Производительность одного процессора порядка 1 ГФлопс. Максимальное число процессоров – 16.
^

1.2. Вычислительная система ILLIAC IV


Работы над системой начались в 1967 году. В реальном использовании система была до 1982 года.

Центральная часть системы состоит из матрицы из 64 независимых идентичных процессорных элементов (рис. 1.5). Роль устройства управления (УУ) выполняет простая вычислительная система небольшой производительности. УУ выдает поток команд, синхроннао исполняемый процессорными элементами (ПЭ). Каждый процессорный элемент – это АЛУ с собственной памятью объемом 2048 64-разрядных слов. Все процессорные элементы имеют доступ только к своей локальной памяти. Для обмена данными в ходе выполнения программы каждый процессорный элемент может использовать непосредственную связь с четырмя соседями по схеме двумерного тора со сдвигом на единицу по вертикали.



Рис. 1.5

Всего в системе имеется 4 квадранта по 64 ПЭ (рис. 1.6), имеющих общее управление.



Рис. 1.6

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

В предполагаемом варианте система никогда не была реализована. Реально работавший прототип содержал только 64 ПЭ (один квадрант) и обладал производительностью 50МФлопс.

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

1.3. Система Alliant FX/80


Система Alliant FX/80 (1985) – использует общую шину для связи между процессорами[6] (рис. 1.7). В качестве вычислительных элементов здесь используются микропроцессоры Motorola 68000.

Рис. 1.7

Производительность системы на уровне 188 МФлопс.
^

1.4. Вычислительная система Intel iPSC




Рис. 1.8

Вычислительная система Intel iPSC (1985) [6]. Модификация системы d5 – система на 32 узла – пятимерный куб, d7 – система на 128 узлов – семимерный куб. Для примера приведем (рис. 1.8) схему четырехмерного куба (d4 - 16 узлов).

Каждый процессор может работать параллельно с другими процессорами, двоичные номера соседних вершин отличаются на одну цифру, что облегчает маршрутизацию пакетов при доступе к отдельному процессору. Каждый узел - это процессор i80286 или i80386. При
16
32-х узлах на базе i80386 (40МГц) производительность составляет 1,3 GFlops


Скачать файл (1337 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации