Таксономия Флинна

From Bauman National Library
This page was last modified on 20 December 2016, at 04:07.
Revision as of 04:07, 20 December 2016 by Aleksey Peskov (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Классификация, или таксономия, Флинна (англ. Flynn's taxonomy) — общая классификация архитектур ЭВМ оп признакам наличия параллелизма в потоках команд и данных. Предложил Майкл Флинн в 1966 году[1], расширил в 1972 году[2][3]

Одиночный поток команд
(Single Instruction)
Множественный поток команд
(Multiple Instruction)
Одиночная программа
(Single Program)
Множество программ
(Multiple Programs)
Одиночный поток данных
(Single Data)
SISD MISD
Множество потоков данных
(Multiple Data)
SIMD MIMD SPMD MPMD

Поскольку в таксономии в качестве основного критерия используют параллелизм, таксономию Флинна чаще всего упоминают в технической литературе[3] [4] при классификации параллельных вычислительных систем. В большинстве случаев параллельные вычислительные системы относятся к SIMD или MIMD-классам. При этом SISD-машина параллельной не считается, а существование ЭВМ с архитектурой MISD под большим вопросом, потому что даже главный пример (систолический массив) нельзя строго рассматривать как подходящий под определение данного типа.

Чтобы лучше понять, что такое классификация Флинна, что отличает SIMD и MIMD, а также SISD-тип от рассматриваемой в данной статье MISD-архитектуры, ниже будет представлена некоторая характеристика этих категорий.

Стоит также отметить, что наиболее популярные классы (SIMD и MIMD) делятся по способу работы с памятью с точки зрения программиста[5]Template:Sfn. Таким образом, выделяют системы с общей памятью (англ. shared memory, SM) и с распределённой (англ. distributed memory, DM).

Оговорка «с точки зрения программиста» обусловлена тем, что есть вычислительные системы, где память физически распределена по узлам системам, тем не менее, для всех процессоров системы она вся видна как общее единое глобальное адресное пространство.

  • SISD (англ. Single Instruction stream over a Single Data stream, одиночный поток команд с одиночным потоком данных, ОКОД) — традиционный компьютер фон-Неймановской архитектуры с одним процессором, выполняющий последовательно одну команду за другой, работая с одним потоком данных. К этому типу относят конвейерные, суперскалярные и VLIW-процессоры.
    SISD.png
  • SIMD (англ. Single Instruction stream, Multiple Data stream, одиночный поток команд, множественный поток данных, ОКМД) — один из наиболее распространённых типов параллельных ЭВМ. К данному классу относят векторные процессоры; обычные современные процессоры, когда выполняют команды векторных расширений; матричные процессоры. Здесь один процессор загружает одну команду, набор данных к ним и выполняет операцию, описанную в этой команде, над всем набором данных одновременно.
    SIMD.png
    • SM-SIMD (shared memory SIMD) — подкласс SIMD с общей памятью с точки зрения программиста. Сюда относятся векторные процессоры.
    • DM-SIMD (distributed memory SIMD) — подкласс SIMD с распределённой памятью с точки зрения программиста. Сюда относятся матричные процессоры — особый подвид с большим количеством процессоров.
  • MISD — по сути, гипотетический класс, поскольку реальных систем-представителей данного типа пока не существует. Некоторые исследователи относят к нему конвейерные ЭВМ. Выше рассмотрен пример систолического массива, чья принадлежность к MISD оспаривается в связи с представлением входных данных.
  • MIMD (англ. Multiple Instruction stream, Multiple Data stream, множественный поток команд, множественный поток данных, МКМД) — ещё один распространённый тип параллельных ЭВМ. Включает в себя многопроцессорные системы, где процессоры обрабатывают множественные потоки данных. Сюда, как правило, относят традиционные мультипроцессорные машины, многоядерные и многопоточные процессоры, а также компьютерные кластеры.
    MIMD.png
    • SM-MIMD (shared memory MIMD) — подкласс MIMD с общей памятью с точки зрения программиста. К нему относятся мультипроцессорные машины и многоядерные процессоры с общей памятью. Мультипроцессоры легко программировать, поддержка SMP (симметричной мультипроцессорности) давно присутствует во всех основных операционных системах. Однако у таких ЭВМ невысокая масштабируемость: увеличение процессоров в системе чревато высокой нагрузкой на общую шину.
    • Существует так называемый DSM-MIMD (distributed shared memory MIMD) подкласс. То есть программисту память видна как одно общее адресное пространство, но физически она может быть распределена по узлам системы. В этом подклассе у каждого процессора есть своя локальная память, а к другим участкам памяти процессор обращается через высокоскоростное соединение. Поскольку доступ к разным участкам общей памяти неодинаков, такие системы называются NUMA (англ. Non-Uniform Memory Access). Возникает проблема: надо, чтобы процессор видел в памяти изменения, сделанные другими процессорами. Для её решения возникли ccNUMA (через согласование кэша) и nccNUMA (без согласования кэша). NUMA-системы имеют более высокую масштабируемость, по сравнению с мультипроцессорами, что позволяет создавать массово-параллельные вычислительные системы, где число процессоров достигает нескольких тысяч.
    • DM-MIMD (distributed memory MIMD) — подкласс MIMD с распределённой памятью с точки зрения программиста. Сюда относятся многопроцессорные ЭВМ с распределённой памятью и компьютерные кластеры типа Beowulf как Network of Workstations. Локальная память отдельно взятого процессора не видна другим. У каждого процессора своя задача. Если же ему необходимы данные из памяти другого процессора, он обменивается с ним сообщениями. У таких машин высокая масштабируемость, как у NUMA.
  • SPMD (англ. Single Program Multiple Data, одиночная программа, множество данных, ОПМД) — система, где на всех процессорах MIMD-машины выполняется только одна программа, и на каждом процессоре она обрабатывает разные блоки данных.
  • MPMD (англ. Multiple Programs, Multiple Data, множество программ, множество данных, МПМД) — система, где а) на одном процессоре MIMD-машины работает мастер-программа, а на других — подчинённая программа, чьей работой руководит мастер-программа (принцип master / slave или master / worker); б) на разных узлах MIMD-машины работают разные программы, которые по-разному обрабатывают один и тот же массив данных (принцип coupled analysis), большей частью они работают независимо друг от друга, но время от времени обмениваются данными для перехода к следующему шагу.

Классификация тех или иных ЭВМ зависит от точки зрения исследователя. Например, конвейерные машины могут быть отнесены к любому из четырёх основных типов[3]. По этой причине к MISD то относят систолические массивы, то оспаривают их принадлежность к данному классу. Также классификация зависит от уровня интеграции, но у MISD и до таких расхождений во взглядах не доходит.

Примечания

  1. Флинн М. Дж.: Высокоскоростные компьютеры. Proc IEEE 54:1901-1901. — 1966.
  2. Флинн М. Дж.: Некоторые компьютерные организации и их эффективность. IEEE Transactions on Computers, 21(9): 948—960. — 1972.
  3. 3.0 3.1 3.2 Падуя, 2012. Стр. 689-697.
  4. Валентин Седых. Мультипроцессинг сегодня. — 2004 г.
  5. «Обзор недавних компьютеров: Основные классы архитектур