Краткий_Курс (1184370), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Динамические сети

Динамические сети - сети с возможностью динамического (коммутируемого) соединения узлов сети друг с другом. Особое место занимает полный коммутатор.

Полный коммутатор обеспечивает полную связность каждого узла в сети, причем, обеспечивает независимость (не блокируемость) пересылок. Недостаток: высокая стоимость аппаратуры и ограниченная размерность. Перечисленные выше однокаскадные сети обмена содержат фиксированное число каскадов или один каскад переключателей. Многокаскадные сети могут быть получены комбинацией некоторых однокаскадных сетей и могут составить конкуренцию полному ком­мутатору. Например, стандартная сеть Клоша может иметь нечетное число каскадов и строится из сетей меньших размеров. Трехкаскадная сеть Клоша имеет с Н входами и Н выходами имеет р модулей

23. Симметричные мультипроцессоры

Системы данного класса: SMP (Scalable Parallel Processor) состоят из нескольких однородных процессоров и массива общей памяти (разделяемой памяти – shared memory): любой процессор может обращаться к любому элементу памяти. По этой схеме построены 2,4 процессорные SMP сервера на базе процессоров Intel, НР и т. д., причем процессоры подключены к памяти с помощью общей шины. Системы с большим числом процессоров (но не более 32) подключаются к общей памяти, разделенной на блоки, через не блокирующийся полный коммутатор: crossbar. Любой процессор системы получает данное по произвольному адресу памяти за одинаковое время, такая структура памяти называется: UMA - Uniform Memory Access (Architecture). Пример:НР-9000. Дальнейшее масштабирование (увеличение числа процессоров системы) SMP систем обеспечивается переходом к архитектуре памяти: NUMA - Nоn Uniform Memory Access. По схеме, называемой, этой иногда, кластеризацией SMP, соответствующие блоки памяти двух (или более) серверов соединяются кольцевой связью, обычно по GCI интерфейсу. При запросе данного, расположенного вне локального с сервере диапазона адресов, это данное по кольцевой связи переписывается дублируется в соответствующий блок локальной памяти, ту часть его, которая специально отводится для буферизации глобальных данных и из этого буфера поставляется потребителю. Эта буферизация прозрачна (невидима) пользователю, для которого вся память кластера имеет сквозную нумерацию, и время выборки данных, не локальных в сервере, будет равно времени выборки локальных данных при повторных обращениях к глобальному данному, когда оно уже переписано в буфер. Данный аппарат буферизации есть типичная схема кэш памяти. Так как к данным возможно обращение из любого процессора кластера, то буферизация, размножение данных требует обеспечение их когерентности. Когерентность данных состоит в том, что при изменении данного все его потребители должны получать это значение. Проблема когерентности усложняется дублированием данных еще и в процессорных кэшах системы. Системы, в которых обеспечена когерентность данных, буферизуемых в кэшах, называются кэш когерентными (cc-cache coherent), а архитектура памяти описываемого кластера: cc- NUMA (cache coherent Nоn Uniform Memory Access). Классической архитектурой принято считать систему SPP1000.

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

"Процесс - группа ячеек памяти, содержимое которых меняется по определенным правилам. Эти правила описываются программой, которую ин­терпретирует процессор." /Цикритзис Д./.

Вычислительный процесс можно рассматривать как последовательность команд ЭВМ, которая работает с данными ей ресурсами. (Задача, задание, процесс, нить, TASK). Так, на микропроцессоре могут работать одновременно несколько независимых процессов: счет вычислительной задачи, редактирование текстов и т.д. Далее рассматриваются вычислительные процессы, одновременно выполняющиеся на нескольких процессорах для решения общей задачи. Работа такой задачи может начинаться с порождения главного процесса, который при работе может порождать другие процессы динамически. Эти процессы могут работать параллельно с главной и также порождать другие процессы.

Другим способом порождения процессов является статический способ, когда производится одновременная инициализация на всех процессорах одинаковых процессов (SPMD – Single Program Multiple Data). Эти процессы опрашивают состояние решающего поля и настраиваются на выполнение своей части вычислений.(Они могут узнать: сколько их порождено, свои уникальные, внутренние имена, и т.д.)

Процессы, работающие на равных правах (не вызовы процедур и не процессы, связанные понятиями "главная-подчиненная"), иногда называемые сопроцессами, могут выполняться параллельно и при этом общаться друг с другом - не часто (слабо связанные процессы).

25. Двоичные и общие семафоры

Процессы для своей работы могут использовать логические и физические ресурсы вычислительной системы и ее окружения, причем ресурсы могут быть: поделены между процессами и закреплены постоянно (на все время работы процесса) или использованы всеми или некоторыми процессами по-очереди. Некоторые ресурсы могут быть общими и допускать параллельное обслуживание процессов. Ресурс, который допускает обслуживание только одного процесса в текущее время, называется критическим ресурсом.

Участки программы процесса, в которых происходит обращение к кри­тическим ресурсам, называются критическими участками. Такие участки должны быть выполнены в режиме "взаимного исключения", т.е. в каждый момент времени не более чем один процесс может быть занят выполнением своего, критического относительно некоторого ресурса, участка. Пробле­ма критического участка - программирование работы критических участков в режиме взаимного исключения решается с помощью семафоров. Общий семафор - это целочисленная переменная, над которой разре­шены только две неделимые операции P и V. Аргументом у этих операций является семафор. Определять семантику этих операций можно только для семафоров - положительных чисел, или включать и отрицательный диапа­зон. Операции могут быть определены так:

P(S) - декремент и анализ семафора

S := S-1

IF (S < 0) THEN <блокировка текущего процесса>

ENDIF

V(S) - инкремент семафора

S := S+1

IF S <= 0 THEN <запустить блокированный процесс>

ENDIF

P и V операции неделимы: в каждый момент только один процесс может выполнять Р или V операцию над данным семафором.

Если семафор используется как счетчик ресурсов, то:

S >= 1 - есть некоторое количество (S) доступных ресурсов,

S = 0 - нет доступного ресурса,

S < 0 - один или несколько (S) процессов находятся в очереди к ресурсу.

Вводится, также, операция инициализации семафора (присвоение начального значения).

Общий семафор - избыточный, т.к. его можно реализовать через двоичные семафоры, которые принимают только два значения 0,1.

Семафоры позволяют:

- синхронизировать работу процессов,

- управлять распределением ресурсом (использованием положительного диапазона значений семафора как счетчика ресурсов) ,

- организовывать очередь блокированных процессов (отрицательные значения семафора показывают число блокированных процессов).

В системах программирования вводится специальный тип данных, оп­ределяющий структуру семафора, например, SEMAPHOR,SIGNAL,GETA.

Использование семафоров

begin integer S; S:=1;

parbegin

task1: begin

do while (true)

P(S);

<критический участок 1>;

V(S);

<обычный участок>;

enddo

end;

task2: begin

do while (true)

P(S);

<критический участок 2>;

V(S);

<обычный участок>;

enddo

end

parend

end

26. Назначение системы МPI

Главные цели создания системы параллельного программирования:

Создать интерфейс прикладного программирования для МРР систем;

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

Допускать удобное сопряжение с языками C, Fortran 77, Fortran 90 и C++;

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

Основные понятия языка

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

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

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

Имеются предопределенные коммуникаторы (точнее, создавае­мые при инициализации MPI-системы): * MPI_COMM_ALL - все процессы и операции над группами (локальные, без обмена сообщениями), например, Дай размер группы. MPI_GROUP_SIZE(IN group, OUT size) Дай номер в группе обратившегося процесса. MPI_GROUP_RANK(IN group, OUT rank)

Основные операции - send, receive

Операции могут быть блокирующими и неблокирующими.

В операции send задается:

- адрес буфера в памяти;

- количество посылаемых элементов;

- тип данных каждого элемента;

- номер процесса-адресата в его группе;

- тег сообщения;

- коммуникатор.

MPI_SEND(IN start, IN count, IN datatype, IN dest, IN tag, IN comm) Типы данных - свои в MPI, но имеется соответствие между ними и типами Fortran и С.

В операции receive задается:

- адрес буфера в памяти;

- количество принимаемых элементов;

- тип данных каждого элемента;

- номер процесса-отправителя в его группе;

- тег сообщения;

- коммуникатор;

- ссылка на объект-статус, содержащий необходимую инфор­мацию о состоянии и результате операции.

Имеется возможность указать "любой отправитель" и "любой тег".

Имеется три режима коммуникаций - стандартный, режим готовности и синхронный.

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

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

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

27. Распараллеливание последовательных программ. ( Метод гиперплоскостей)

Метод гиперплоскостей применим только к многомерным циклам. В пространстве итераций ищется прямая (плоскость), на которой возможно параллельное асинхронное выполнение тела цикла, причем в отличие от метода координат, эта прямая (плоскость) может иметь наклон по отношению к осям координат. Цикл вида:

DO I = 2,N

DO J = 2,M

A(I,J) = ( A(I-1,J) + A(I,J-1) ) * 0.5

методом координат не векторизуется. Действительно, при фиксированном

значении переменной I (I = i) значение, вычисленное в точке (i,j)

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

точке (i,j-1), так что параллельное выполнение тела цикла по переменной J невозможно. Аналогично нельзя проводить параллельные вычисления по переменной I.

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

на 1-м шаге - в точке (2,2),

на 2-м шаге - в точках (3,2) и (2,3),

на 3-м шаге - в точках (4,2), (3,3) и (2,4),

на 4-м шаге - в точках (5,2), (4,3), (3,4) и (2,5) и т.д.

Вычисления в указанных точках для каждого шага, начиная со второго, можно проводить параллельно и асинхронно. Перечисленные кортежи точек лежат на параллельных прямых вида I+J=K, а именно: на первом ша­ге - на прямой I+J=4, на втором - I+J=5, на третьем шаге - I+J=6 и т.д., на последнем ((N-2)+(M-2)+1) - ом шаге - на прямой I+J=M+N.

Для приведенного примера множество точек, в которых возможно параллельное выполнение, является однопараметрическим (прямая) и определяется из решения уравнения I+J=K. Цикл (5) может быть преобразован к виду: DO 5 K = 4,M+N

Tн = MMAX(2,K-N)

Tк = MMIN(M,K-2)

DO 5 T = Tн,Tк : PAR

I = T

J = K - T

5 A(I,J) = ( A(I-1,J) + A(I,J-1) ) * 0.5

Характеристики

Список файлов книги