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

Содержание

 

Введение  ……………………………………………………………………………… 3

1. Классификация Флинна ……………………………………………………….... 4                         
2. Классификация Хокни ………………………………………………………….. 5
3. Классификация Фенга …………………………………………………………. .7                                                                    
4. Классификация Хедлера  ……………………………………………………...... 8
5. Классификация Шнайдера …………………………………………………….. 11
6. Классификация Скилликорна …………………………………………………. 13
7. Классификация Шора ………………………………………………………….. 16
8. Классификация Джонсона …………………………………………………….. 18
9. Классификация Базу …………………………………………………………… 19
10. Классификация Кришнамарфи ……………………………………………….. 21
11. Классификация Дазгупты ……………………………………………………... 23
12. Классификация Дункана ………………………………………………………. 26

Заключение ………………………………………………………………………….. 29

Список литературы …………………………………………………………………. 30

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

Попытки систематизировать  все множество архитектур начались после опубликования М.Флинном первого варианта классификации вычислительных систем в конце 60-х годов и непрерывно продолжаются по сей день. Ясно, что навести порядок в хаосе очень важно для лучшего понимания исследуемой предметной области, однако нахождение удачной классификации может иметь целый ряд существенных следствий.

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

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

1. Классификация Флинна

По-видимому, самой ранней и наиболее известной является классификация  архитектур вычислительных систем, предложенная в 1966 году М.Флинном. Классификация базируется на понятии потока, под которым понимается последовательность элементов, команд или данных, обрабатываемая процессором. На основе числа потоков команд и потоков данных Флинн выделяет четыре класса архитектур: SISD,MISD,SIMD,MIMD.

SISD (single instruction stream / single data stream) - одиночный поток команд и одиночный поток данных. К этому классу относятся, прежде всего, классические последовательные машины, или иначе, машины фон-неймановского типа, например, PDP-11 или VAX 11/780. В таких машинах есть только один поток команд, все команды обрабатываются последовательно друг за другом и каждая команда инициирует одну операцию с одним потоком данных. Не имеет значения тот факт, что для увеличения скорости обработки команд и скорости выполнения арифметических операций может применяться конвейерная обработка - как машина CDC 6600 со скалярными функциональными устройствами, так и CDC 7600 с конвейерными попадают в этот класс.

 

SIMD (single instruction stream / multiple data stream) - одиночный поток команд и множественный поток данных. В архитектурах подобного рода сохраняется один поток команд, включающий, в отличие от предыдущего класса, векторные команды. Это позволяет выполнять одну арифметическую операцию сразу над многими данными - элементами вектора. Способ выполнения векторных операций не оговаривается, поэтому обработка элементов вектора может производится либо процессорной матрицей, как в ILLIAC IV, либо с помощью конвейера, как, например, в машине CRAY-1.

 

MISD (multiple instruction stream / single data stream) - множественный поток команд и одиночный поток данных. Определение подразумевает наличие в архитектуре многих процессоров, обрабатывающих один и тот же поток данных. Однако ни Флинн, ни другие специалисты в области архитектуры компьютеров до сих пор не смогли представить убедительный пример реально существующей вычислительной системы, построенной на данном принципе. Ряд исследователей относят конвейерные машины к данному классу, однако это не нашло окончательного признания в научном сообществе. Будем считать, что пока данный класс пуст.

MIMD (multiple instruction stream / multiple data stream) - множественный поток команд и множественный поток данных. Этот класс предполагает, что в вычислительной системе есть несколько устройств обработки команд, объединенных в единый комплекс и работающих каждое со своим потоком команд и данных.

 

Предложенная схема классификации  вплоть до настоящего времени является самой применяемой при начальной  характеристике того или иного компьютера. Если говорится, что компьютер принадлежит  классу SIMD или MIMD, то сразу становится понятным базовый принцип его  работы, и в некоторых случаях  этого бывает достаточно. Однако видны  и явные недостатки. В частности, некоторые заслуживающие внимания архитектуры, например dataflow и векторно--конвейерные машины, четко не вписываются в данную классификацию. Другой недостаток - это чрезмерная заполненность класса MIMD. Необходимо средство, более избирательно систематизирующее архитектуры, которые по Флинну попадают в один класс, но совершенно различны по числу процессоров, природе и топологии связи между ними, по способу организации памяти и, конечно же, по технологии программирования.

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

 

2. Классификация Хокни

Р. Хокни - известный английский специалист в области параллельных вычислительных систем, разработал свой подход к классификации, введенной им для систематизации компьютеров, попадающих в класс MIMD по систематике Флинна. Хокни, пытаясь систематизировать архитектуры внутри этого класса, получил иерархическую структуру, представленную на рисунке:

Основная идея классификации  состоит в следующем. Множественный  поток команд может быть обработан  двумя способами: либо одним конвейерным  устройством обработки, работающем в режиме разделения времени для  отдельных потоков, либо каждый поток  обрабатывается своим собственным устройством. Первая возможность используется в MIMD компьютерах, которые автор называет конвейерными (например, процессорные модули в Denelcor HEP). Архитектуры, использующие вторую возможность, в свою очередь опять делятся на два класса:

• MIMD компьютеры, в которых возможна прямая связь каждого процессора с каждым, реализуемая с помощью переключателя;
• MIMD компьютеры, в которых прямая связь каждого процессора возможна только с ближайшими соседями по сети, а взаимодействие удаленных процессоров поддерживается специальной системой маршрутизации через процессоры-посредники.

Далее, среди MIMD машин с  переключателем Хокни выделяет те, в которых вся память распределена среди процессоров как их локальная память (например, PASM, PRINGLE). В этом случае общение самих процессоров реализуется с помощью очень сложного переключателя, составляющего значительную часть компьютера. Такие машины носят название MIMD машин с распределенной памятью. Если память это разделяемый ресурс, доступный всем процессорам через переключатель, то такие MIMD являются системами с общей памятью (CRAY X-MP, BBN Butterfly). В соответствии с типом переключателей можно проводить классификацию и далее: простой переключатель, многокаскадный переключатель, общая шина.

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

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

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

 

 

3. Классификация Фенга

В 1972 году Т.Фенг предложил классифицировать вычислительные системы на основе двух простых характеристик. Первая - число бит n в машинном слове, обрабатываемых параллельно при выполнении машинных инструкций. Практически во всех современных компьютерах это число совпадает с длиной машинного слова. Вторая характеристика равна числу слов m, обрабатываемых одновременно данной вычислительной системой. Немного изменив терминологию, функционирование любого компьютера можно представить как параллельную обработку n битовых слоев, на каждом из которых независимо преобразуются m бит. Опираясь на такую интерпретацию, вторую характеристику обычно называют шириной битового слоя.

Если рассмотреть предельные верхние значения данных характеристик, то каждую вычислительную систему C можно  описать парой чисел (n,m) и представить точкой на плоскости в системе координат длина слова - ширина битового слоя. Площадь прямоугольника со сторонами n и m определяет интегральную характеристику потенциала параллельности P архитектуры и носит название максимальной степени параллелизма вычислительной системы: P(C)=mn. По существу, данное значение есть не что иное, как пиковая производительность, выраженная в других единицах. В период появления данной классификации, а это начало 70-х годов, еще казалось возможным перенести понятие пиковой производительности как универсального средства сравнения и описания потенциальных возможностей компьютеров с традиционных последовательных машин на параллельные. Понимание того факта, что пиковая производительность сама по себе не столь важна, пришло позднее, и данный подход отражает, естественно, степень осмысления специфики параллельных вычислений того времени.

Рассмотрим компьютер 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).