Что положено в основу классификации флинна

Обновлено: 03.05.2024

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

Флинна, Р. Хокни, Т. Фен- га, В. Хендлера и некоторых других авторов. Подробный обзор этих классифика- ционных схем можно найти в [11].

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

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

Для обсуждения классификации Флинна нам потребуются еще некоторые поня- тия. Вычислительная система, состоящая из нескольких находящихся в одном или в разных помещениях компьютеров, которые имеют общую внешнюю па- мять и общее программное обеспечение, называется многомашинной системой с косвенной слабой связью (рис. 17.4). Связь между компьютерами осуществля- ется через магнитные диски или магнитные ленты. Каждая машина работает под управлением собственной операционной системы. В архитектурах с косвенной связью обеспечиваются высокая готовность и надежность системы.

Классификация Флинна (рис. 17.7) основана на следующих признаках.

1. Одиночный (ОК) или множественный (МК) поток команд в центральной части вычислительной системы.

2. Одиночный (ОД) или множественный (МД) поток данных в центральной части вычислительной системы.

3. Пословный (С) или поразрядный (Р) способ обработки в центральной части вычислительной системы.

4. Низкая (Нс) или высокая (Вс) связность компонентов вычислительной сис- темы.

5. Однородные (Ор) или неоднородные (Нр) основные компоненты вычисли- тельной системы.

В классификации М. Флинна для определения классификационной группы вы- числительной системы используется краткая формула, содержащая только од- но обозначение из каждого уровня классификации. Обозначения размещаются в порядке от верхнего уровня к нижнему. После первых трех уровней записы- вается косая черта. Например, формула МКМДС/ВсОрПк обозначает вычисли- тельную систему с множественным потоком команд и множественным потоком данных в центральной части, с пословной обработкой, высокой степенью связно- сти (сильной связью), однородной структурой и связями между процессорными элементами и модулями памяти через коммутатор.

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

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

Архитектура ОКОД, или SISD (от Single Instruction Single Data stream) — оди- ночный поток команд и одиночный поток данных, — фактически представляет собой фон-неймановскую архитектуру однопроцессорных вычислительных систем последовательного действия. Бытовым аналогом работы таких систем является ситуация, в которой один человек делает одну деталь, последовательно выпол- няя все необходимые операции по ее обработке.

В вычислительных системах типа О КОД имеется только один поток команд (рис. 17.8, а). Все команды выполняются последовательно друг за другом, каж- дая команда инициирует выполнение процессорным элементом только одной скалярной операции. С середины 40-х и примерно по 70-е гг. XX в. этот класс вычислительных систем был практически единственным.

Архитектура ОКМД, или SIМD (от Single Instruction Multiply Data stream), — одиночный поток команд над множественным потоком данных. Бытовым анало- гом работы таких систем является ситуация, в которой несколько человек одно- временно, синхронно выполняют одну и ту же операцию, последовательность одинаковых операций над разными деталями. Примером также может служить ансамбль музыкальных инструментов, синхронно исполняющих мелодию под управлением дирижера.

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

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

В связи с обсуждением этого класса параллельных систем, по-видимому, следует напомнить о включении основанных на подходе SIМD групп команд ММХ и SSЕ (см. 16.1.4 и 16.1.5) в систему команд процессоров Pentium и аналогичных групп в системы команд других процессоров.

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

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

Векторные процессоры, изображенные на рис.

17.9, не получили широкого распро- странения из-за высокой стоимости организации векторного арифметико-логиче- ского устройства. Более приемлемыми по стоимости оказались векторно-конвей- ерные вычислительные системы, в которых векторные регистры комбинируются с конвейерным арифметико-логическим устройством. В таких системах размер- ности векторов были существенно увеличены. Выдача устройством управления единственной команды, которая должна быть выполнена над группой данных, и их бесперебойная подача на конвейер из векторных регистров обеспечивают постоянную загрузку конвейера и его высокую производительность. Типичным представителем векторно-конвейерных систем является суперкомпьютер Cray-1, .разработанный под руководством Сеймура Крея в компании Cray Research (впо- следствии — подразделение фирмы Silicon Graphics). В то время (1970-е гг.) это была самая мощная вычислительная система в мире. Ее тактовая частота состав- ляла 80 МГц, объем оперативной памяти был равен 8 Мбайт, а пиковая произво- дительность составляла 160 Мфлоп.

Примером более современных векторно-конвейерных вычислительных систем является разработанный в начале 1990-х годов в той же фирме суперкомпьютер

Cray Т9О. Эта система может содержать до 16 процессорных элементов, использую- щих общую оперативную память. Тактовая частота процессоров равна 250 МГц, а пиковая производительность достигает 32 Гфлоп. Можно упомянуть еще и ис- пользующую векторные процессоры вычислительную систему Earth Simulator компании NEC. Система была пущена в эксплуатацию в 2002 г. В это время она состояла из 640 вычислительных узлов, в каждом из которых находилось по 8 процессоров. Пиковая производительность всей системы из 5120 процессоров составляла 40 Тфлоп.

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

Сначала планировалось создать систему, включающую матрицу из 16 х 16 вычис- лительных узлов. Хотя система строилась с 1967 по 1975 г., ее действующий вариант содержал только один квадрант планируемой матрицы размерностью 8x8 узлов с пиковой производительностью 10 Гфлоп. Суперкомпьютер ILLIАС 4 находился в эксплуатации до 1982 г.

Другой разновидностью систем класса ОКМД являются системы ОКМДР с по- разрядной обработкой данных. Единственными представителями этого класса считаются ассоциативные системы, в которых процессор выбирает данные не по адресу, а по значению (см. 9.1.3). Системы с ассоциативными процессорами опе- рируют не совокупностью разрядов одного и того же слова, а совокупностью раз- рядов с одним и тем же номером из различных слов оперативной памяти. Такую совокупность называют разрядным срезом.

На рис. 17.11 изображена схема, иллюстрирующая разницу между адресной выборкой в обычных процессорах и выборкой разрядного среза в ассоциатив- ных процессорах. В примере рассматривается блок оперативной памяти, со- стоящий из 32 четырехбайтовых полей. Во время выполнения адресной выборки (рис. 17.11, а) в процессорный элемент передается 32-битовое поле с заданным адресом. В примере на рисунке выбирается поле с адресом 00AAFE0C16. Во время ассоциативной выборки разрядного среза (рис. 17.11, б) в процессорный элемент передается также группа из 32 битов, но они выбираются из одного и того же разряда всех полей. В примере на рисунке биты выбираются из 20-го разряда всех 32 рассматриваемых полей.


При наличии нескольких процессорных элементов различные разрядные срезы поступают на обработку в разные элементы и обрабатываются одновременно. Это позволяет выделить слова памяти с желательным содержимым в тех или иных

разрядах. Такой подход находит применение в специализированных вычисли- тельных системах, таких как, например, машины баз данных, которые обеспечи- вают быстрое выполнение операций поиска в базах данных.

Архитектура МКОД, или МISD (от Multiply Instruction Single Data stream — мно- жественный поток команд обрабатывает одиночный поток данных) (рис. 17.12, а). Подразумевается наличие нескольких процессорных элементов, которые од- новременно обрабатывают один и тот же поток данных, выполняя над ним одни и те же или разные операции. Некоторые специалисты относят к этому классу конвейерные системы. Однако в конвейере отсутствует одновременность вы- полнения действий ступенями конвейера над одним и тем же кодом. Разные ступени обрабатывают один код последовательно. Одновременно разные сту- пени конвейера работают над разными кодами данных. По мнению других специалистов, класс МКОД пустой. Мы также будем считать его пустым, а кон- вейерные процессоры отнесем к классу О КОД для скалярных аргументов или к классу ОКМД в случае обработки векторных данных (векторно-конвейерные системы).

Архитектура МКМД или МIМD (от Multiply Instruction Multiply Data stream — множественный поток команд, обрабатывающих множественный поток данных). Бытовым аналогом работы таких систем является ситуация, в которой несколь- ко человек одновременно делают несколько различных деталей одного и того же устройства, выполняя одинаковые или различные операции над ними.

Классификация Флинна в классе МКМД выделяет пустой подкласс МКМДР с поразрядной обработкой и подкласс МКМД С, содержащий слабосвязанные системы типа МКМДС/Нс и сильносвязанные системы типа МКМДС/Вс. На- помним, что системы со слабой связью называются многомашинными (или муль- тикомпьютерами), а системы с сильной связью — многопроцессорными (или мультипроцессорами).

Классификация вычислительных сетей параллельной обработки ( SISD , SIMD , MIMD , MISD )

Общая классификация архитектур ЭВМ по признакам наличия параллелизма в потоках команд и данных. Была предложена в 70-е годы Майклом Флинном (Michael Flynn). Все разнообразие архитектур ЭВМ в этой таксономии Флинна сводится к четырем классам:

  1. SISD (single instruction stream / single data stream) - одиночный поток команд и одиночный поток данных. К этому классу относятся, прежде всего, классические последовательные машины, или иначе, машины фон-неймановского типа, например, PDP-11 или VAX 11/780. В таких машинах есть только один поток команд, все команды обрабатываются последовательно друг за другом и каждая команда инициирует одну операцию с одним потоком данных. Не имеет значения тот факт, что для увеличения скорости обработки команд и скорости выполнения арифметических операций может применяться конвейерная обработка - как машина CDC 6600 со скалярными функциональными устройствами, так и CDC 7600 с конвейерными попадают в этот класс.
  2. SIMD (single instruction stream / multiple data stream) - одиночный поток команд и множественный поток данных. В архитектурах подобного рода сохраняется один поток команд, включающий, в отличие от предыдущего класса, векторные команды. Это позволяет выполнять одну арифметическую операцию сразу над многими данными - элементами вектора. Способ выполнения векторных операций не оговаривается, поэтому обработка элементов вектора может производится либо процессорной матрицей, как в ILLIAC IV, либо с помощью конвейера, как, например, в машине CRAY-1.
  3. MISD (multiple instruction stream / single data stream) - множественный поток команд и одиночный поток данных. Определение подразумевает наличие в архитектуре многих процессоров, обрабатывающих один и тот же поток данных. Однако ни Флинн, ни другие специалисты в области архитектуры компьютеров до сих пор не смогли представить убедительный пример реально существующей вычислительной системы, построенной на данном принципе. Ряд исследователей относят конвейерные машины к данному классу, однако это не нашло окончательного признания в научном сообществе. Будем считать, что пока данный класс пуст.
  4. MIMD (multiple instruction stream / multiple data stream) - множественный поток команд и множественный поток данных. Этот класс предполагает, что в вычислительной системе есть несколько устройств обработки команд, объединенных в единый комплекс и работающих каждое со своим потоком команд и данных.

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

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

Если ЦП обратился к какому-либо объекту оперативной памяти, с высокой долей вероятности ЦП вскоре снова обратится к этому объекту. Примером этой ситуации может быть код или данные в циклах. Эта концепция описывается принципом временной локальности , в соответствии с которым часто используемые объекты оперативной памяти должны быть "ближе" к ЦП (в кэше ).

Для согласования содержимого кэш-памяти и оперативной памяти используют три метода записи:

  • Сквозная запись (write through) - одновременно с кэш-памятью обновляется оперативная память.
  • Буферизованная сквозная запись (buffered write through) - информация задерживается в кэш-буфере перед записью в оперативную память и переписывается в оперативную память в те циклы, когда ЦП к ней не обращается.
  • Обратная запись (write back) - используется бит изменения в поле тега, и строка переписывается в оперативную память только в том случае, если бит изменения равен 1.

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

В структуре кэш-памяти выделяют два типа блоков данных:

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

Пространство памяти отображения данных в кэше разбивается на строки - блоки фиксированной длины (например, 32, 64 или 128 байт). Каждая строка кэша может содержать непрерывный выровненный блок байт из оперативной памяти. Какой именно блок оперативной памяти отображен на данную строку кэша, определяется тегом строки и алгоритмом отображения. По алгоритмам отображения оперативной памяти в кэш выделяют три типа кэш-памяти:

Даже краткое перечисление типов современных параллельных вычислительных систем (ВС) дает понять, что для ориентирования в этом многообразии необходи­ма четкая система классификации. От ответа на главный вопрос — что заложить в основу классификации — зависит, насколько конкретная система классификации помогает разобраться с тем, что представляет собой архитектура ВС и насколько успешно данная архитектура позволяет решать определенный круг задач. Попыт­ки систематизировать все множество архитектур параллельных вычислительных систем предпринимались достаточно давно и длятся по сей день, но к однознач­ным выводам пока не привели.

Среди всех рассматриваемых систем классификации ВС наибольшее признание получила классификация, предложенная в 1966 году М. Флинном [99, 100]. В ее основу положено понятие потока, под которым понимается последовательность элементов, команд или данных, обрабатываемая процессором. В зависимости от количества потоков команд и потоков данных Флинн выделяет четыре класса ар­хитектур: SISD, MISD, SIMD, MIMD.

SISD

SISD(Single Instruction Stream/Single Data Stream) — одиночный поток команд и одиночный поток данных (рис. 89, а). Представителями этого класса являют­ся, прежде всего, классические фон-неймановские ВМ, где имеется только один поток команд, команды обрабатываются последовательно и каждая команда ини­циирует одну операцию с одним потоком данных. То, что для увеличения скорос­ти обработки команд и скорости выполнения арифметических операций может применяться конвейерная обработка, не имеет значения, поэтому в класс SISD од­новременно попадают как ВМ CDC 6600 со скалярными функциональными уст­ройствами, так и CDC 7600 с конвейерными. Некоторые специалисты считают, что к SISD-системам можно причислить и векторно-конвейерные ВС, если рассмат­ривать вектор как неделимый элемент данных для соответствующей команды.

MISD

MISD(Multiple Instruction Stream/Single Data Stream) — множественный поток команд и одиночный поток данных (рис. 89, б). Из определения следует, что в ар­хитектуре ВС присутствует множество процессоров, обрабатывающих один и тот же поток данных. Примером могла бы служить ВС, на процессоры которой пода­ется искаженный сигнал, а каждый из процессоров обрабатывает этот сигнал с по­мощью своего алгоритма фильтрации. Тем не менее ни Флинн, ни другие специа­листы в области архитектуры компьютеров до сих пор не сумели представить убедительный пример реально существующей вычислительной системы, постро­енной на данном принципе. Ряд исследователей относят к данному классу конвейерные системы, однако это не нашло окончательного признания. Отсюда принято считать, что пока данный класс пуст. Наличие пустого класса не следует считать недостатком классификации Флинна. Такие классы, по мнению некоторых исследователей, могут стать чрезвычайно полезными для раз­работки принципиально новых концепций в теории и практике построения вы­числительных систем.

Рис. 89. Архитектура вычислительных систем по Флинну: а – SISD; б –MISD; в – SIMD; г – MIMD.

SIMD

SIMD (Single Instruction Stream/Multiple Data Stream) — одиночный поток команд и множественный поток данных (рис. 89, в). ВМ данной архитектуры позволяют выполнять одну арифметическую операцию сразу над многими данными — элементами вектора. Бесспорными представителями класса SIMD считаются матрицы процессоров, где единое управляющее устройство контролирует множество процессорных элементов. Все процессорные элементы получают от устройства управления одинаковую команду и выполняют ее над своими локальными данными. В принципе в этот класс можно включить и векторно-конвейерные ВС, если каждый элемент вектора рассматривать как отдельный элемент потока данных.

MIMD

MIMD (Multiple Instruction Stream/Multiple Data Stream) – множественный поток команд и множественный поток данных (рис. 89, г). Класс предполагает наличие в вычислительной системе множества устройств обработки команд, объединенных в единый комплекс и работающих каждое со своим потоком команд и данных. Класс MIMD чрезвычайно широк, поскольку включает в себя всевозможные мультипроцессорные системы. Кроме того, приобщение к классу MIMD зависит от трактовки. Так, ранее упоминавшиеся векторно-конвейерные ВС можно вполне отнести и к классу MIMD, если конвейерную обработку рассматривать как выполнение множества команд (операций ступеней конвейера) над множественным скалярным потоком.

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

Контрольные вопросы

1. Сравните схемы классификации параллелизма по уровню и гранулярности.
Каковы, на ваш взгляд, достоинства, недостатки и области применения этих
схем классификации?

2. Для заданной программы и конфигурации параллельной вычислительной сис­темы рассчитайте значения метрик параллельных вычислений.

3. Поясните суть закона Амдала, приведите примеры, поясняющие его ограничения.

4. Какую проблему закона Амдала решает закон Густафсона? Как он это делает? Сформулируйте области применения этих двух законов.

Читайте также: