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

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

Всё разнообразие архитектур ЭВМ в этой таксономии Флинна сводится к четырём классам^[4]:

• ОКОД — Вычислительная система с одиночным потоком команд и одиночным потоком данных
  (SISD, single instruction stream over a single data stream).
• ОКМД — Вычислительная система с одиночным потоком команд и множественным потоком данных
  (SIMD, single instruction, multiple data).
• МКОД — Вычислительная система со множественным потоком команд и одиночным потоком данных
  (MISD, multiple instruction, single data).
• МКМД — Вычислительная система со множественным потоком команд и множественным потоком данных
  (MIMD, multiple instruction, multiple data).

Так как в таксономии в качестве основного критерия используется параллелизм, то таксономия Флинна наиболее часто упоминается в технической литературе^{[5][6][7][4][8]} при классификации параллельных вычислительных систем. MISD — редко используемая архитектура, в основном с целью защиты от сбоев (например, для горячего резервирования вычислительных машин в лётных системах типа «Space Shuttle» или «Энергия — Буран», в SCADA, критичных к сбоям, и т. п.). Поскольку SISD-машина параллельной машиной не является, а MISD не является типичной параллельной архитектурой, все параллельные вычислительные системы попадают в класс либо SIMD, либо в MIMD.

С развитием технологий классы SIMD и MIMD стали охватывать слишком большой круг машин, кардинально отличных друг от друга. В связи с этим в технической литературе^[9][10] используется дополнительный критерий — способ работы с памятью с точки зрения программиста. По этому критерию системы делятся на «системы с общей памятью» (англ. shared memory, SM) и «системы с распределенной памятью» (англ. distributed memory, DM). Соответственно, каждый класс — SIMD и MIMD — делится на подклассы: SM-SIMD/DM-SIMD и SM-MIMD/DM-MIMD.

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

Архитектура SISD — это традиционный компьютер фон-Неймановской архитектуры с одним процессором, который выполняет последовательно одну инструкцию за другой, работая с одним потоком данных. В данном классе не используется параллелизм ни данных, ни инструкций, и, следовательно, SISD-машина не является параллельной. К этому классу также принято относить конвейерные, суперскалярные и VLIW-процессоры.

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

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

Векторные процессоры получили распространение в начале 70-х годов, в первую очередь в суперкомпьютерах тех времен (CDC STAR-100, Cray-1). С середины 70-х до конца 80-х все суперкомпьютеры были векторными машинами, и под суперкомпьютером в те годы подразумевалась векторная машина. Векторные суперкомпьютеры до сих пор находят применение в промышленности и научных вычислениях, и они до сих пор входят в перечень продукции почти всех ведущих производителей суперкомпьютеров: NEC, Fujitsu, Hitachi, Cray. Развитие миниатюризации в вычислительной технике позволило добавить векторный способ обработки данных в современные микропроцессоры, где они представлены набором специальных команд-расширений ассемблера^[11][12]. Выполняя их, процессор переходит в векторный режим и превращается на это время в SM-SIMD-машину.

К этому под-классу относятся так называемые «матричные процессоры». Они представляют собой массив процессоров, которые контролируются одним управляющим процессором, выполняя по его команде одну операцию над своей собственной порцией данных, хранящихся в локальной памяти. Так как обмена данными между процессорами нет, не требуется никакой синхронизации, что позволяет достигать огромных скоростей вычислений и с легкостью расширять систему, просто увеличивая количество процессоров. Для понимания работы матричного процессора достаточно представить себе утренние телевизионные уроки по аэробике, где актёр в студии задает движения, а миллионы телезрителей повторяют их в такт одновременно по всей стране.

Так как матричные процессоры можно использовать только на ограниченном круге задач, долгое время они существовали только в виде экспериментальных, узкоспециализированных машин. Кроме того, для их производства требовалось создавать специализированные процессоры. Первой попыткой (довольно неудачной) построить матричный процессор был компьютер ILLIAC IV^{[англ.][13]} в начале 70-х годов, второй знаменитой попыткой были машины CM-1 и CM-2 компании Thinking Machines и суперкомпьютеры компании MasPar в начале 80-х^[13]. Развитие миниатюризации в вычислительной технике позволило вернуться к идее матричных процессоров и возродить её в графических картах (GPGPU), которые используются для высокопроизводительных вычислений.

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

Класс MIMD включает в себя многопроцессорные системы, где процессоры обрабатывают множественные потоки данных. Сюда принято относить традиционные мультипроцессорные машины, многоядерные и многопоточные процессоры, а также компьютерные кластеры.

По работе с памятью этот класс делится на под-классы.

В эту группу попадают многопроцессорные машины с общей памятью, многоядерные процессоры с общей памятью.

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

Как уже было сказано выше, память, которая программисту видна как одно общее адресное пространство, может быть физически распределена по узлам системы. Такой подкласс машин называется DSM-MIMD (distributed shared memory MIMD). В этом подклассе машин у каждого процессора имеется своя локальная память, а к другим участкам памяти процессор обращается через высокоскоростное соединение. Так как доступ к разным участкам общей памяти является неодинаковым (к своему локальному участку быстрее, к другим — медленнее), то такие системы носят название NUMA (от Non-Uniform Memory Access). Так как память физически распределена, возникает трудность с тем, чтобы каждый процессор видел в памяти изменения, сделанные другими процессорами. Придумано несколько способов решения этой проблемы: через согласование кэша — ccNUMA, без согласования кэша — nccNUMA.

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

Модель программирования в таких системах остается прежней — потоки исполнения обмениваются друг с другом данными через общие переменные.

Достоинства: относительно легко программировать, поддержка SMP существует уже давно во всех ведущих операционных системах.

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

В этот подкласс попадают многопроцессорные MIMD-машины с распределенной памятью.

У каждого процессора имеется своя собственная локальная память, которая не видна другим процессорам. Каждый процессор в такой системе выполняет свою задачу со своим набором данных в своей локальной памяти. Если процессору нужны данные из памяти другого процессора, данный процессор обменивается с другим процессором сообщениями, то есть в таких системах используется модель программирования Message Passing, с помощью Parallel Virtual Machine (PVM) или какой-нибудь реализации Message Passing Interface (MPI).

Главное преимущество DM-MIMD машин — их высокая масштабируемость, позволяющая создавать массово-параллельные системы из нескольких сотен тысяч процессоров.

Компьютерные кластеры типа Beowulf тоже относятся к этому классу как network of workstations.

В специализированной литературе^[14][15] можно встретить еще такие подклассы MIMD-класса: SPMD (single program, multiple data) и MPMD (multiple programs, multiple data).

SPMD (single program, multiple data) — описывает систему, где на всех процессорах MIMD-машины выполняется только одна единственная программа, и на каждом процессоре она обрабатывает разные блоки данных.

MPMD (multiple programs, multiple data) — описывает систему, а) где на одном процессоре MIMD-машины работает мастер-программа, а на других подчиненная программа, работой которой руководит мастер-программа (принцип master/slave или master/worker); б) где на разных узлах MIMD-машины работают разные программы, которые по-разному обрабатывают один и тот же массив данных (принцип coupled analysis), большей частью они работают независимо друг от друга, но время от времени обмениваются данными для перехода к следующему шагу.

Отношение конкретных машин к конкретному классу сильно зависит от точки зрения исследователя. Так, конвейерные машины могут быть отнесены и к классу SISD (конвейер — единый процессор), и к классу SIMD (векторный поток данных с конвейерным процессором), и к классу MISD (множество процессоров конвейера обрабатывают один поток данных последовательно), и к классу MIMD — как выполнение последовательности различных команд (операций ступеней конвейера) с множественным скалярным потоком данных (вектором).

Рассматривая вычислительный комплекс на разных уровнях интеграции, его можно относить к разным классам: например, высокопроизводительный массово-параллельный суперкомпьютер ASCI Blue Pacific являлся DM-MIMD-машиной, где каждый узел общался с другим с помощью передачи сообщений (message passing), но каждый узел в этом суперкомпьютере, в свою очередь, представлял собой многопроцессорный SMP-сервер RS/6000, то есть являлся SM-MIMD-машиной. В то же время высокопроизводительный массово-параллельный суперкомпьютер ASCI Blue Mountain являлся системой SMP-серверов (SM-MIMD), связанных в общую машину с распределённой общей памятью (то есть DSM-MIMD).

• RS/6000 Scalable POWERparallel System: Scientific and Technical Computing Overview (SG24-4541-01). — IBM Corporation, 1996. — 184 p. — ISBN 0738409154. (англ.)

• Charles Severance, Kevin Dowd. High Performance Computing (RISC Architectures, Optimization & Benchmarks), 2nd Edition. — O'Reilly Media, 1998. — 466 p. — ISBN 156592312X. (англ.)

• Yukiya Aoyama, Jun Nakano. RS/6000 SP: Practical MPI Programming (SG24-5380-00). — IBM Corporation, 1999. — 238 p. — ISBN 0738413658. (англ.)

• William Stallings. Computer Organization and Architecture - Designing for Performance, 8th Edition. — Prentice Hall, 2009. — 792 p. — ISBN 0136073735. (англ.)

• David A. Patterson, John L. Hennessy. Computer Organization and Design, Fourth Edition: The Hardware/Software Interface. — Morgan Kaufmann, 2011. — 914 p. — ISBN 0123747503. (англ.)

• Encyclopedia of Parallel Computing / Ed. by David Padua. — Springer, 2011. — ISBN 978-0-387-09765-7. (англ.)