Реферат: Параллелизм как способ параллельной обработки данных

При рассмотрении MIMD машин с сетевой структурой считается, что все они имеют распределенную память, а дальнейшая классификация проводится в соответствии с топологией сети: звездообразная сеть (lCAP), регулярные решетки разной размерности (Intel Paragon, CRAY T3D), гиперкубы (NCube, Intel iPCS), сети с иерархической структурой, такой, как деревья, пирамиды, кластеры (Cm^* , CEDAR) и, наконец, сети, изменяющие свою конфигурацию.

Заметим, что если архитектура компьютера спроектирована с использованием нескольких сетей с различной топологией, то, по всей видимости, по аналогии с гибридными MIMD с переключателями, их стоит назвать гибридными сетевыми MIMD, а использующие идеи разных классов – просто гибридными MIMD. Типичным представителем последней группы, в частности, является компьютер Connection Machine 2, имеющим на внешнем уровне топологию гиперкуба, каждый узел которого является кластером процессоров с полной связью.

3.4 Классификация Шнайдера

В 1988 году Л. Шнайдер (L. Snyder) предложил новый подход к описанию архитектур параллельных вычислительных систем, попадающих в класс SIMD систематики Флинна. Основная идея заключается в выделении этапов выборки и непосредственно исполнения в потоках команд и данных. Именно разделение потоков на адреса и их содержимое позволяет описать такие ранее «неудобные» для классификации архитектуры, как компьютеры с длинным командным словом, систолические массивы и целый ряд других.

Пусть S произвольный поток ссылок. Последовательность адресов потока S , обозначаемая S_a , – это последовательность, чей i-й элемент – набор, сформированный из адресов i-х элементов каждой последовательности из S : потока S , обозначаемая S_v , – это последовательность, чей i-й элемент – набор, образованный слиянием наборов значений i-х элементов каждой последовательности из S .

Если S_x – последовательность элементов, где каждый элемент – набор из n чисел, то для обозначения «ширины» последовательности будем пользоваться обозначением: w(S_x ) = n.

Каждую пару (I, D) с потоком команд I и потоком данных D будем называть вычислительным шаблоном , а все компьютеры будем разбивать на классы в зависимости от того, какой шаблон они могут исполнить. В самом деле, компьютер может исполнить шаблон (I, D) , если он в состоянии:

· выдать w(I_a ) адресов команд для одновременной выборки из памяти;

· декодировать и проинтерпретировать одновременно w(I_v ) команд;

· выдать одновременно w(D_a ) адресов операндов и

· выполнить одновременно w(D_v ) операций над различными данными.

Если все эти условия выполнены, то компьютер может быть описан следующим образом: I_{w ( Ia ) w ( Iv )} D_{w ( Da ) w ( Dv ).}

Поэтому описание однопроцессорной машины с фон-неймановской архитектурой будет выглядеть так: I_1,1 D_1,1.

Теперь возьмем две машины из класса SIMD: Goodyear Aerospace MPP и ILLIAC IV, причем не будем принимать во внимание разницу в способах обработки данных отдельными процессорными элементами. Единственный поток команд означает I = 1 для обеих машин. По тем же соображениям, использованным только что для последовательной машины, для потока команд получаем равенство w(I_a ) = w(I_v ) = 1. Далее, вспомним, что для доступа к операндам устройство управления MPP рассылает один и тот же адрес всем процессорным элементам, поэтому в этой терминологии MPP имеет единственную последовательность в потоке данных, т.е. D = 1. Однако затем выборка данных из памяти и последующая обработка осуществляется в каждом процессорном элементе, поэтому w(D_v )=16384, а вся система MPP может быть описана так: I_1,1 D_1,16384.

В ILLIAC IV устройство управления, так же, как и в MPP, рассылает один и тот же адрес всем процессорным элементам, однако каждый из них может получить свой уникальный адрес, добавляя содержимое локального индексного регистра. Это означает, что D = 64 и в системе присутствуют 64 потока адресов данных, определяющих одиночные потоки операндов, т.е. w(D_a ) = w(D_v ) = 64. Суммируя сказанное, приходим к описанию ILLIAC IV: I_1,1 D_64,64.

Для более четкой классификации Шнайдер вводит три предиката для обозначения значений, которые могут принимать величины w(I_a ), w(I_v ), w(D_a ) и w(D_v ):

s – предикат «равен 1»;

с – предикат «от 1 до некоторой (небольшой) константы»;

m – предикат «от 1 до произвольно большого конечного числа».

В этих обозначениях, например, фон-неймановская машина принадлежит к классу I_ss D_ss . Несмотря на то, что и 'c' и 'm' в принципе не имеют определенной верхней границы, они отражают разные свойства архитектуры компьютера. Описатель 'c' предполагает жесткие ограничения сверху со стороны аппаратуры, и соответствующий параметр не может быть значительно увеличен относительно простыми средствами. Примером может служить число инструкций, упакованных в командном слове VLIW компьютера. С другой стороны, описатель 'm' используется тогда, когда обозначаемая величина может быть легко изменена, т.е. другими словами, компьютер по данному параметру масштабируем. Например, относительная проста в увеличении числа процессорных элементов в системе MPP является основанием для того, чтобы отнести ее к классу I_ss D_sm . Конечно же, различие между 'c' и 'm' в достаточной мере условное и, как правило, порождает массу вопросов. В частности, как описать машину, в которой процессоры связаны через общую шину? С одной стороны, нет никаких принципиальных ограничений на число подключаемых процессоров. Однако каждый дополнительный процессор увеличивает загруженность шины, и при достижении некоторого порога подключение новых процессоров бессмысленно. Как описать такую систему, 'c' или 'm'? Автор оставляет данный вопрос открытым.

На основе указанных предикатов можно выделить следующие классы компьютеров:

· I_ss D_ss – фон-неймановские машины;

· I_ss D_sc – фон-неймановские машины, в которых заложена возможность выбирать данные, расположенные с разным смещением относительно одного и того же адреса, над которыми будет выполнена одна и та же операция. Примером могут служить компьютеры, имеющие команды, типа одновременного выполнения двух операций сложения над данными в формате полуслова, расположенными по указанному адресу.

· I_ss D_sm – SIMD компьютеры без возможности получения уникального адреса для данных в каждом процессорном элементе, включающие MPP, Connection Machine 1 так же, как и систолические массивы.

· I_ss D_cc – многомерные SIMD машины – фон-неймановские машины, способные расщеплять поток данных на независимые потоки операндов;

· I_ss D_mm – это SIMD компьютеры, имеющие возможность независимой модификации адресов операндов в каждом процессорном элементе, например, ILLIAC IV и Connection Machine 2.

· I_sc D_cc – вычислительные системы, выбирающие и исполняющие одновременно несколько команд, для доступа к которым используется один адрес. Типичным примером являются компьютеры с длинным командным словом (VLIW).

· I_cc D_cc – многомерные MIMD машины. Фон-неймановские машины, которые могут расщеплять свой цикл выборки / выполнения с целью обработки параллельно нескольких независимых команд.

· I_mm D_mm – к этому классу относятся все компьютеры типа MIMD.