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

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

1) ОКОД (одиночный поток команд одиночный поток данных) или SISD (Single Instruction Single Data). Это последовательные ЭВМ, в которых выполняется единственная программа, т. е. имеется только один счетчик команд.

2) ОКМД (одиночный поток команд множественный поток данных) или SIMD (Single Instruction – Multiple Data). В таких ЭВМ выполняется единственная программа, но каждая команда обрабатывает массив данных. Это соответствует векторной форме параллелизма.

3) МКОД (множественный поток команд одиночный поток данных) или MISD (Multiple Instruction Single Data). Подразумевается, что в данном классе несколько команд одновременно работает с одним элементом данных, однако эта позиция классификации Флинна на практике не нашла применения.

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

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

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

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

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

(«П» – процессор, «ИП» – индивидуальная память)

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

Пусть в первом процессоре выполняется процесс L1, во втором – L2:

L1: ... X := X + 1; ...

L2: ... X := X + 1; ...

Процессы выполняются асинхронно, используя общую перемен-ную X. При выполнении процессов возможно различное их взаим о-расположение во времени, например, возможны следующие две си-туации:

L1 R1: = X; R1: = R1 + 1; X: = R1; ... (1.1)

L2 R2: = X; R2: = R2 + 1; X:= R2;

L1 R1: = X; R1: = R1 + 1; X: = R1; (1.2)

L2 R2: = Х; R2:=R 2+1; X: = R2;

Пусть в начальный момент X=V. Тогда в случае (1.1) второй процессор производит чтение X до завершения всех операций в первом процессоре, поэтому X = V + 1.

В случае (1.2) второй процессор читает X после завершения всех операций первым процессором, поэтому X = V + 2. Таким образом, результат зависит от взаиморасположения процессов во времени, что для асинхронных процессов определяется случайным образом. Чтобы исключить такие ситуации, необходимо ввести систему синхронизации параллельных процессов (например, семафоры), что усложняет механизмы операционной системы.

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

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