Панков С.В. Лекции по системному анализу

Подождите немного. Документ загружается.

СИСТЕМНЫЙ АНАЛИЗ

(курс лекций, предназначенный для студентов 5-го курса специальностей 071900 и

220100)

Лектор: Панков С.В.

Введение

Параллельные компьютеры и супер-ЭВМ

В любом компьютере все основные параметры тесно связаны. Супер-ЭВМ это

компьютеры, имеющие в настоящее время не только максимальную производительность,

но и максимальный объем оперативной и дисковой памяти. Так компьютер ASCI RED,

занимающий первое место в списке пятисот самых мощных компьютеров мира,

объединяет 9632 процессора PentiumPro с общей оперативной памятью в 600 Гигабайт и

производительностью более 3200 миллиардов операций в секунду.

Супер-ЭВМ и сверхвысокая производительность: зачем?

Возникает целый ряд естественных вопросов: какие задачи настолько важны, что

требуются компьютеры стоимостью несколько миллионов долларов? Или, какие задачи

настолько сложны, что хорошего Пентиума не достаточно? Для того, чтобы оценить

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

например, оптимизацию процесса добычи нефти.

Имеем подземный нефтяной резервуар с каким-то число пробуренных скважин: по одним

на поверхность откачивается нефть, по другим обратно закачивается вода. Нужно

смоделировать ситуацию в данном резервуаре, чтобы оценить запасы нефти.

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

Разумные размеры куба, при которых можно получать правдоподобные результаты - это

100*100*100 точек. В каждой точке куба надо вычислить от 5 до 20 функций: три

компоненты скорости, давление, температуру, концентрацию компонент (вода, газ и

нефть).

Далее, значения функций находятся как решение нелинейных уравнений, что требует от

200 до 1000 арифметических операций.

Если. нужно понять, как эта система ведет себя во времени, то делается 100-1000 шагов по

времени. Пполучилось: 10

(точек сетки)*10(функций)*500(операций)*500(шагов по

времени) = 2.5*10

, т.е. 2500 миллиардов арифметических операций для выполнения

одного лишь расчета!

Примеры использования суперкомпьютеров можно найти не только в нефтедобывающей

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

использование суперкомпьютеров действительно необходимо:

 автомобилестроение

 нефте- и газодобыча

 фармакология

 прогноз погоды и моделирование изменения климата

 сейсморазведка

 проектирование электронных устройств

 синтез новых материалов

 теория массового обслуживания (например моделирование развития транспортной

системы страны, грузопотоков и пассажиропотоков) и теория оптимального

управления,

 и многие другие

В 1995 году корпус автомобиля Nissan Maxima удалось сделать на 10% прочнее благодаря

использованию суперкомпьютера фирмы Cray (The Atlanta Journal, 28 мая, 1995г). С

помощью него были найдены не только слабые точки кузова, но и наиболее эффективный

способ их удаления.

Развитие одной из крупнейших мировых систем резервирования Amadeus, используемой

тысячами агенств со 180000 терминалов в более чем ста странах. Установка двух серверов

Hewlett-Packard T600 по 12 процессоров в каждом позволила довести степень оперативной

доступности центральной системы до 99.85% при текущей загрузке около 60 миллионов

запросов в сутки.

Увеличение производительности ЭВМ, за счет чего?

Производительность ЭВМ растёт, главным образом, благодаря развитию элементной базы

и использованию новых решений в архитектуре компьютеров. За полвека

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

этом выигрыш в быстродействии, связанный с уменьшением времени такта с 2

микросекунд до 1.8 наносекунд, составляет лишь около 1000 раз. Откуда же взялось

остальное? Ответ очевиден -- использование новых решений в архитектуре компьютеров.

Основное место среди них занимает принцип параллельной обработки данных,

воплощающий идею одновременного (параллельного) выполнения нескольких действий.

Параллельная обработка данных на ЭВМ

Параллельная обработка данных, воплощая идею одновременного выполнения нескольких

действий, имеет две разновидности: конвейерность и собственно параллельность.

Параллельная обработка. Если некое устройство выполняет одну операцию за единицу

времени, то тысячу операций оно выполнит за тысячу единиц. Если предположить, что

есть пять таких же независимых устройств, способных работать одновременно, то ту же

тысячу операций система из пяти устройств может выполнить уже не за тысячу, а за

двести единиц времени. Аналогично система из N устройств ту же работу выполнит за

1000/N единиц времени.

Конвейерная обработка. Идея конвейерной обработки заключается в выделении

отдельных этапов выполнения общей операции, причем каждый этап, выполнив свою

работу, передавал бы результат следующему, одновременно принимая новую порцию

входных данных. Получаем очевидный выигрыш в скорости обработки за счет

совмещения прежде разнесенных во времени операций.

Краткая история появления параллелизма в архитектуре ЭВМ

Все современные микропроцессоры, будь то Pentium III или PA-8600, MIPS R14000, Е2К

или Power2 SuperChip используют тот или иной вид параллельной обработки.

Совершим краткий экскурс в историю, начав практически с момента рождения первых

ЭВМ.

IBM 701 (1953), IBM 704 (1955): разрядно-параллельная память, разрядно-параллельная

арифметика.

Все самые первые компьютеры (EDSAC, EDVAC, UNIVAC) имели разрядно-

последовательную память, из которой слова считывались последовательно бит за битом.

IBM 709 (1958): независимые процессоры ввода/вывода.

Процессоры первых компьютеров сами управляли вводом/выводом. Однако скорость

работы самого быстрого внешнего устройства, а то тем временам это магнитная лента,

была в 1000 раз меньше скорости процессора, поэтому во время операций ввода/вывода

процессор фактически простаивал. В 1958г. к компьютеру IBM 704 присоединили 6

независимых процессоров ввода/вывода, которые после получения команд могли работать

параллельно с основным процессором, а сам компьютер переименовали в IBM 709.

Данная модель получилась удивительно удачной, так как вместе с модификациями было

продано около 400 экземпляров, причем последний был выключен в 1975 году - 20 лет

существования!

ATLAS (1963): конвейер команд.

Впервые конвейерный принцип выполнения команд был использован в машине ATLAS,

разработанной в Манчестерском университете. Выполнение команд разбито на 4 стадии:

выборка команды, вычисление адреса операнда, выборка операнда и выполнение

операции. Конвейеризация позволила уменьшить время выполнения команд с 6 мкс до 1,6

мкс.

CDC 6600 (1964): независимые функциональные устройства.

Фирма Control Data Corporation (CDC).

Для сравнения с сегодняшним днем приведем некоторые параметры компьютера:

 время такта 100нс,

 производительность 2-3 млн. операций в секунду,

 оперативная память разбита на 32 банка по 4096 60-ти разрядных слов,

 цикл памяти 1мкс,

 10 независимых функциональных устройств.

CDC 7600 (1969): конвейерные независимые функциональные устройства.

. Основные параметры:

 такт 27,5 нс,

 10-15 млн. опер/сек.,

 8 конвейерных ФУ,

 2-х уровневая память.

ILLIAC IV (1974): матричные процессоры. Проект: 256 процессорных элементов (ПЭ) = 4

квадранта по 64ПЭ, возможность реконфигурации: 2 квадранта по 128ПЭ или 1 квадрант

из 256ПЭ, такт 40нс, производительность 1Гфлоп.

Пентральная часть: устройство управления (УУ) + матрица из 64 ПЭ;

 УУ это простая ЭВМ с небольшой производительностью, управляющая матрицей

ПЭ; все ПЭ матрицы работали в синхронном режиме, выполняя в каждый момент

времени одну и ту же команду, поступившую от УУ, но над своими данными;

 ПЭ имел собственное АЛУ с полным набором команд, ОП - 2Кслова по 64 разряда,

цикл памяти 350нс, каждый ПЭ имел непосредственный доступ только к своей ОП;

 сеть пересылки данных: двумерный тор со сдвигом на 1 по границе по

горизонтали;

CRAY 1 (1976): векторно-конвейерные процессоры

Время такта 12.5нс, 12 конвейерных функциональных устройств, пиковая

производительность 160 миллионов операций в секунду, оперативная память до 1Мслова

(слово - 64 разряда), цикл памяти 50нс. Главным новшеством является введение

векторных команд, работающих с целыми массивами независимых данных.

Две модели программирования: последовательная и параллельная

Традиционная архитектура ЭВМ была последовательной. Это означало, что в любой

момент времени выполнялась только одна операция и только над одним операндом.

Совокупность приемов программирования, структур данных, отвечающих

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

программирования. Ее основными чертами являются применение стандартных языков

программирования (как правило, это ФОРТРАН-77, ФОРТРАН-90, С/С++), достаточно

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

производительность.

Основными особенностями модели параллельного программирования являются высокая

эффективность программ, применение специальных приемов программирования и, как

следствие, более высокая трудоемкость программирования, проблемы с переносимостью

программ.

1. ИДЕОЛОГИИ ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ

В настоящее время существуют два основных подхода к распараллеливанию вычислений.

Это параллелизм данных и параллелизм задач.

В основе обоих подходов лежит распределение вычислительной работы по доступным

пользователю процессорам параллельного компьютера. При этом приходится решать

прежде всего две проблемы:

1. Равномерная загрузка процессоров (сбалансированная их работа).

2. Минимизация времени обмена информацией между процессорами.

Рассматриваемые идеологии программирования различаются методами решения этих

двух проблем.

1.1 Параллелизм данных

Основная идея подхода, основанного на параллелизме данных, заключается в том, что

одна операция выполняется сразу над всеми элементами массива данных. Различные

фрагменты такого массива обрабатываются на векторном процессоре или на разных

процессорах параллельной машины. Распределением данных между процессорами

занимается программа, а не программист. Векторизация или распараллеливание в этом

случае чаще всего выполняется уже на этапе компиляции.

Роль программиста в этом случае обычно сводится к заданию компилятору директив

параллельной компиляции, использованию специализированных языков для

параллельных вычислений. Наиболее распространенными такими языками являются

Высокопроизводительный ФОРТРАН (High Performance FORTRAN) и параллельные

версии языка C (это, например, C*).

При разработке таких программ используется базовый набор параллельных операций,

среди которых следующие операции:

 операции над массивами в целом и их фрагментами;

 условные операции;

 операции приведения;

Операции над массивами

Аргументами таких операций являются массивы в целом или их фрагменты (сечения), при

этом данная операция применяется одновременно (параллельно) ко всем элементам

массива. Примерами операций такого типа являются вычисление поэлементной суммы

массивов, умножение элементов массива на скалярный или векторный множитель.

Условные операции

Эти операции могут выполняться лишь над теми элементами массива, которые

удовлетворяют какому-то определенному условию.

Операции приведения

Операции приведения применяются ко всем элементам массива (или его сечения), а

результатом является одно единственное значение, например, сумма элементов массива

или максимальное значение его элементов.

1.2. Параллелизм задач

Стиль программирования, основанный на параллелизме задач подразумевает, что

вычислительная задача разбивается на несколько относительно самостоятельных подзадач

и каждый процессор загружается своей собственной подзадачей. Для каждой подзадачи

пишется своя собственная программа на обычном языке программирования, обычно это

ФОРТРАН или С.

Все эти программы должны обмениваться результатами своей работы. Такой обмен

осуществляется вызовом процедур специализированной библиотеки. Программист при

этом может контролировать распределение входных данных и обмен данными в ходе

выполнения между подзадачами.

В этом случае на программиста ложится ответственность за равномерную загрузку

процессоров параллельного компьютера; за минимизацию обмена данными между

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

ситуаций.

Главным преимуществом данного подхода является большая гибкость, предоставляемая

программисту, позволяющая эффективно использовать ресурсы параллельного

компьютера.

Примерами специализированных библиотек являются библиотеки MPI (Message Passing

Interface) и PVM (Parallel Virtual Machines).

1.3. Правила работы с MPI

MPI является одним из наиболее попудярных средств параллельного программирования.

В состав MPI входят, как правило, два обязательных компонента:

 библиотека программирования для языков Си, Си++ и Фортран,

 загрузчик исполняемых файлов.

Кроме того, может присутствовать справочная система (manual pages для Юникса),

командные файлы для облегчения компиляции/компоновки программ.

Для MPI принято писать программу, содержащую код всех процессов сразу. MPI-

загрузчиком запускается указываемое количество экземпляров программы. Каждый

экземпляр определяет свой порядковый номер в запущенном коллективе, и в зависимости

от этого номера выполняет тот или иной процесс. Такая модель параллелизма называется

Single program/Multiple data ( SPMD ),

Каждый процесс имеет пространство данных, полностью изолированное от других

процессов. Обмениваются данными процессы только в виде сообщений MPI.

Все процессы запускаются загрузчиком одновременно как процессы Юникса. Количество

процессов фиксировано - в ходе работы порождение новых процессов невозможно. Если

MPI-приложение запускается в сети, запускаемый файл приложения должен

присутствовать на каждой машине.

1.4. SPMD-технология параллельного программирования

SPMD-программа P задаётся параллельной композицией конечного числа экземпляров

программы p на зыке высокого уровня (ЯВУ) для последовательного программирования,

дополненном средствами взаимодействия. Один экземпляр программы p называется

процессом. Каждый процесс работает над собственной памятью и может

взаимодействовать с любым другим процессом посредством передачи сообщений,

предполагающей наличие буфера у процесса. Каждый процесс реализует индивидуальную

функцию в зависимости от своих начальных данных и своего номера.

Пример 1.1. SPMD-программа на Си и MPI, отыскивающая скалярное произведение

векторов A и B длины KP*N, где KP – количество процессов, а N – длина фрагмента

векторов A и B, распределяемые одному процессу.

/* скалярное произведение векторов */

#include <stdio.h>

#include <stdlib.h>

#include <mpi.h>

#define N 100 /* длинна фрагментов векторов */

int main(int argc, char **argv)

{

MPI_Status status;

double s; /* результирующая сумма */

double s1; /* промежуточная сумма */

double a[N],b[N]; /* массивы */

int i,j;

int KP; /* число процессов */

int pid; /* № процесса */

MPI_Init(&argc,&argv); /* инициализация MPI */

/* определение числа процессов в общей группе */

MPI_Comm_size(MPI_COMM_WORLD, &KP);

MPI_Comm_rank(MPI_COMM_WORLD, &pid);

if (pid == 0)

{

for (i=0; i<=KP-1; i++)

{

for (j=0; j <= N-1; j=j+1)

{

scanf("%lg %lg",a[j], b[j]);

};

MPI_Send(a,N,MPI_DOUBLE,i,1,MPI_COMM_WORLD);

MPI_Send(b,N,MPI_DOUBLE, i,1,MPI_COMM_WORLD);

};

}; /* конец ветви pid==0 */

MPI_Recv(a,N,MPI_DOUBLE,

0,1,MPI_COMM_WORLD,&status);

MPI_Recv(b,N,MPI_DOUBLE,

0,1,MPI_COMM_WORLD, &status);

s=0.0;

for (j=0; j<=N-1; j++)

s=s+a[j]*b[j];

MPI_Send(&s,1,MPI_DOUBLE,0,2,MPI_COMM_WORLD);

if (pid == 0)

{

S=0;

for (i=0; i<=KP-1; i++)

{

MPI_Recv(&s1,1,MPI_DOUBLE,

MPI_ANY_SOURCE,2,MPI_COMM_WORLD, &status);

s=s+s1;

};

printf("Скалярное произведение=%lg",s);

}; /* конец ветви pid==0 */

MPI_Finalize();

return(0);

2. БИБЛИОТЕКА ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ.

MPI

2.1. MPI. Терминология и обозначения

 MPI - message passing interface - библиотека функций, предназначенная для

поддержки работы параллельных процессов в терминах передачи сообщений.

 Номер процесса - целое неотрицательное число, являющееся уникальным

атрибутом каждого процесса.

 Атрибуты сообщения - номер процесса-отправителя, номер процесса-

получателя и идентификатор сообщения. Для них заведена структура

MPI_Status, содержащая три поля: MPI_Source (номер процесса отправителя),

MPI_Tag (идентификатор сообщения), MPI_Error (код ошибки); могут быть и

добавочные поля.

 Идентификатор сообщения (msgtag) - атрибут сообщения, являющийся целым

неотрицательным числом, лежащим в диапазоне от 0 до 32767.

Процессы объединяются в группы, могут быть вложенные группы. Внутри группы все

процессы перенумерованы. С каждой группой ассоциирован свой коммуникатор.

Поэтому при осуществлении пересылки необходимо указать идентификатор группы,

внутри которой производится эта пересылка. Все процессы содержатся в группе с

предопределенным идентификатором MPI_COMM_WORLD.

При описании процедур MPI будем пользоваться словом OUT для обозначения

"выходных" параметров, т.е. таких параметров, через которые процедура возвращает

результаты.

2.2. Общие процедуры MPI

int MPI_Init( int* argc, char*** argv)

MPI_Init - инициализация параллельной части приложения. Реальная инициализация для

каждого приложения выполняется не более одного раза, а если MPI уже был

инициализирован, то никакие действия не выполняются и происходит немедленный

возврат из подпрограммы. Все оставшиеся MPI-процедуры могут быть вызваны только

после вызова MPI_Init.

Возвращает: в случае успешного выполнения - MPI_SUCCESS, иначе - код ошибки. (То же

самое возвращают и все остальные функции, рассматриваемые в данном руководстве.)

int MPI_Finalize( void )

MPI_Finalize - завершение параллельной части приложения. Все последующие обращения

к любым MPI-процедурам, в том числе к MPI_Init, запрещены. К моменту вызова

MPI_Finalize некоторым процессом все действия, требующие его участия в обмене

сообщениями, должны быть завершены.

Сложный тип аргументов MPI_Init предусмотрен для того, чтобы передавать всем

процессам аргументы main:

int main(int argc, char** argv)

{

MPI_Init(&argc, &argv);

...

MPI_Finalize();

}

int MPI_Comm_size( MPI_Comm comm, int* size)

Определение общего числа параллельных процессов в группе comm.

 comm - идентификатор группы

 OUT size - размер группы

int MPI_Comm_rank( MPI_comm comm, int* rank)

Определение номера процесса в группе comm. Значение, возвращаемое по адресу &rank,

лежит в диапазоне от 0 до size_of_group-1.

 comm - идентификатор группы

 OUT rank - номер вызывающего процесса в группе comm

double MPI_Wtime(void)

Функция возвращает астрономическое время в секундах (вещественное число),

прошедшее с некоторого момента в прошлом. Гарантируется, что этот момент не будет

изменен за время существования процесса.

2.3. Прием/передача сообщений между отдельными процессами

2.3.1. Прием/передача сообщений с блокировкой

int MPI_Send(void* buf, int count, MPI_Datatype datatype, int dest, int msgtag,

MPI_Comm comm)

 buf - адрес начала буфера посылки сообщения

 count - число передаваемых элементов в сообщении

 datatype - тип передаваемых элементов

 dest - номер процесса-получателя

 msgtag - идентификатор сообщения

 comm - идентификатор группы

Блокирующая посылка сообщения с идентификатором msgtag, состоящего из count

элементов типа datatype, процессу с номером dest. Все элементы сообщения расположены

подряд в буфере buf. Значение count может быть нулем. Тип передаваемых элементов

datatype должен указываться с помощью предопределенных констант типа. Разрешается

передавать сообщение самому себе.

Блокировка гарантирует корректность повторного использования всех параметров после

возврата из подпрограммы. Выбор способа осуществления этой гарантии: копирование в

промежуточный буфер или непосредственная передача процессу dest, остается за MPI.

Следует специально отметить, что возврат из подпрограммы MPI_Send не означает ни

того, что сообщение уже передано процессу dest, ни того, что сообщение покинуло

процессорный элемент, на котором выполняется процесс, выполнивший MPI_Send.

int MPI_Recv(void* buf, int count, MPI_Datatype datatype, int source, int msgtag,

MPI_comm comm, MPI_Status *status)

 OUT buf - адрес начала буфера приема сообщения

 count - максимальное число элементов в принимаемом сообщении