Параллелизм как способ параллельной обработки данных (стр. 3 из 5)
Рассмотримкомпьютер Advanced Scientific Computer фирмы Texas Instruments (TI ASC). В основном режиме он работает с 64-х разрядным словом, причем все разряды обрабатываются параллельно. Арифметико-логическое устройство имеет четыре одновременно работающих конвейера, содержащих по восемь ступеней. Такая организация дает 4x8=32 бита в каждом битовом слое, и значит компьютер TI ASC может быть представлен в виде (64,32).
На основе введенных понятий все вычислительные системы в зависимости от способа обработки информации, заложенного в их архитектуру, можно разделить на четыре класса.
· Разрядно-последовательные пословно-последовательные (n=m=1). В каждый момент времени такие компьютеры обрабатывают только один двоичный разряд. Представителем данного класса служит давняя система MINIMA с естественным описанием (1,1).
· Разрядно-параллельные пословно-последовательные (n>1, m=1). Большинство классических последовательных компьютеров, так же как и многие вычислительные системы, эксплуатируемые до сих пор, принадлежит к данному классу: IBM 701 с описанием (36,1), PDP-11 (16,1), IBM 360/50 и VAX 11/780 – обе с описанием (32,1).
· Разрядно-последовательные пословно-параллельные (n = 1, m > 1). Как правило вычислительные системы данного класса состоят из большого числа одноразрядных процессорных элементов, каждый из которых может независимо от остальных обрабатывать свои данные. Типичными примерами служат STARAN (1, 256) и MPP (1,16384) фирмы Goodyear Aerospace, прототип известной системы ILLIAC IV компьютер SOLOMON (1, 1024) и ICL DAP (1, 4096).
· Разрядно-параллельные пословно-параллельные (n > 1, m > 1). Большая часть существующих параллельных вычислительных систем, обрабатывая одновременно mn двоичных разрядов, принадлежит именно к этому классу: ILLIAC IV (64, 64), TI ASC (64, 32), C.mmp (16, 16), CDC 6600 (60, 10), BBN Butterfly GP1000 (32, 256).
Недостатки предложенной классификации достаточно очевидны и связаны со способом вычисления ширины битового слоя m. По существу Фенг не делает никакого различия между процессорными матрицами, векторно-конвейерными и многопроцессорными системами. Не делается акцент на том, за счет чего компьютер может одновременно обрабатывать более одного слова: множественности функциональных устройств, их конвейерности или же какого-то числа независимых процессоров. Если в системе N независимых процессоров имеют каждый по F конвейерных функциональных устройств с длиной конвейера L, то для вычисления ширины битового слоя надо просто найти произведение данных характеристик. Конечно же, опираясь на данную классификацию, достаточно трудно (а иногда и невозможно) осознать специфику той или иной вычислительной системы. Однако достоинством является введение единой числовой метрики для всех типов компьютеров, которая вместе с описанием потенциала вычислительных возможностей конкретной архитектуры позволяет сравнить любые два компьютера между собой.
3.3 Классификация Хокни
Р. Хокни – известный английский специалист в области параллельных вычислительных систем, разработал свой подход к классификации, введенной им для систематизации компьютеров, попадающих в класс MIMD по систематике Флинна.
Как отмечалось выше (см. классификацию Флинна), класс MIMD чрезвычайно широк, причем наряду с большим числом компьютеров он объединяет и целое множество различных типов архитектур. Хокни, пытаясь систематизировать архитектуры внутри этого класса, получил иерархическую структуру, представленную на рисунке:
Основная идея классификации состоит в следующем. Множественный поток команд может быть обработан двумя способами: либо одним конвейерным устройством обработки, работающем в режиме разделения времени для отдельных потоков, либо каждый поток обрабатывается своим собственным устройством. Первая возможность используется в MIMD компьютерах, которые автор называет конвейерными (например, процессорные модули в Denelcor HEP). Архитектуры, использующие вторую возможность, в свою очередь опять делятся на два класса:
· MIMD компьютеры, в которых возможна прямая связь каждого процессора с каждым, реализуемая с помощью переключателя;
· MIMD компьютеры, в которых прямая связь каждого процессора возможна только с ближайшими соседями по сети, а взаимодействие удаленных процессоров поддерживается специальной системой маршрутизации через процессоры-посредники.
Далее, среди MIMD машин с переключателем Хокни выделяет те, в которых вся память распределена среди процессоров как их локальная память (например, PASM, PRINGLE). В этом случае общение самих процессоров реализуется с помощью очень сложного переключателя, составляющего значительную часть компьютера. Такие машины носят название MIMD машин с распределенной памятью. Если память это разделяемый ресурс, доступный всем процессорам через переключатель, то такие MIMD являются системами с общей памятью (CRAY X-MP, BBN Butterfly). В соответствии с типом переключателей можно проводить классификацию и далее: простой переключатель, многокаскадный переключатель, общая шина.
Многие современные вычислительные системы имеют как общую разделяемую память, так и распределенную локальную. Такие системы автор рассматривает как гибридные MIMD c переключателем.
При рассмотрении 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, обозначаемая Sa, – это последовательность, чей i-й элемент – набор, сформированный из адресов i-х элементов каждой последовательности из S: потока S, обозначаемая Sv, – это последовательность, чей i-й элемент – набор, образованный слиянием наборов значений i-х элементов каждой последовательности из S.
Если Sx – последовательность элементов, где каждый элемент – набор из n чисел, то для обозначения «ширины» последовательности будем пользоваться обозначением: w(Sx) = n.
Каждую пару (I, D) с потоком команд I и потоком данных D будем называть вычислительным шаблоном, а все компьютеры будем разбивать на классы в зависимости от того, какой шаблон они могут исполнить. В самом деле, компьютер может исполнить шаблон (I, D), если он в состоянии:
· выдать w(Ia) адресов команд для одновременной выборки из памяти;
· декодировать и проинтерпретировать одновременно w(Iv) команд;
· выдать одновременно w(Da) адресов операндов и
· выполнить одновременно w(Dv) операций над различными данными.
Если все эти условия выполнены, то компьютер может быть описан следующим образом: Iw(Ia)w(Iv)Dw(Da)w(Dv).
Поэтому описание однопроцессорной машины с фон-неймановской архитектурой будет выглядеть так: I1,1D1,1.
Теперь возьмем две машины из класса SIMD: Goodyear Aerospace MPP и ILLIAC IV, причем не будем принимать во внимание разницу в способах обработки данных отдельными процессорными элементами. Единственный поток команд означает I = 1 для обеих машин. По тем же соображениям, использованным только что для последовательной машины, для потока команд получаем равенство w(Ia) = w(Iv) = 1. Далее, вспомним, что для доступа к операндам устройство управления MPP рассылает один и тот же адрес всем процессорным элементам, поэтому в этой терминологии MPP имеет единственную последовательность в потоке данных, т.е. D = 1. Однако затем выборка данных из памяти и последующая обработка осуществляется в каждом процессорном элементе, поэтому w(Dv)=16384, а вся система MPP может быть описана так: I1,1D1,16384.
В ILLIAC IV устройство управления, так же, как и в MPP, рассылает один и тот же адрес всем процессорным элементам, однако каждый из них может получить свой уникальный адрес, добавляя содержимое локального индексного регистра. Это означает, что D = 64 и в системе присутствуют 64 потока адресов данных, определяющих одиночные потоки операндов, т.е. w(Da) = w(Dv) = 64. Суммируя сказанное, приходим к описанию ILLIAC IV: I1,1D64,64.
Для более четкой классификации Шнайдер вводит три предиката для обозначения значений, которые могут принимать величины w(Ia), w(Iv), w(Da) и w(Dv):