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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Классификация по Флинну
  Одиночный поток команд
(Single Instruction)
Множество потоков команд
(Multiple Instruction)
Одиночный поток данных
(Single Data)
SISD
(ОКОД)
MISD
(МКОД)
Множество потоков данных
(Multiple Data)
SIMD
(ОКМД)
MIMD
(МКМД)

Таксономия (Классификация) Флинна (англ. 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] при классификации параллельных вычислительных систем. Поскольку 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 — это традиционный компьютер фон-Неймановской архитектуры с одним процессором, который выполняет последовательно одну инструкцию за другой, работая с одним потоком данных. В данном классе не используется параллелизм ни данных, ни инструкций, и следовательно SISD-машина не является параллельной. К этому классу также принято относить конвейерные, суперскалярные и VLIW-процессоры.

SISD.svg

SIMD[править | править вики-текст]

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

SIMD.svg

SM-SIMD (shared memory SIMD)[править | править вики-текст]

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

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

DM-SIMD (distributed memory SIMD)[править | править вики-текст]

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

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

MISD[править | править вики-текст]

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

MISD.svg

MIMD[править | править вики-текст]

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

MIMD.svg

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

SM-MIMD (shared memory MIMD)[править | править вики-текст]

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

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

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

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

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

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

DM-MIMD (distributed memory MIMD)[править | править вики-текст]

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

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

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

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

SPMD и MPMD[править | править вики-текст]

В специализированной литературе[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 (англ.)
  • под ред. David Padua. Encyclopedia of Parallel Computing. — Springer, 2012. — 2366 p. — ISBN 0387098445 (англ.)

Примечания[править | править вики-текст]

  1. Flynn MJ (1966) Very high speed computers. Proc IEEE 54:1901-1901
  2. M.J. Flynn. Some computer organizations and their effectiveness. IEEE Transactions on Computers, 21(9): 948—960, 1972
  3. Padua, 2012, p. 689
  4. 1 2 Padua, 2012, p. 689-697
  5. Severance_Dowd, 1998, p. 258
  6. Stallings, 2009, p. 630
  7. Patterson_Hennessy, 2011, p. 649
  8. Валентин Седых / Мультипроцессинг сегодня. 2004 г.
  9. OVERVIEW OF RECENT SUPERCOMPUTERS: The Main Architectural Classes
  10. Severance_Dowd, 1998, p. 259-267
  11. SSE
  12. 3DNow!
  13. 1 2 Patterson_Hennessy, 2011, p. 7.14
  14. RS/6000 SP, 1996, p. 3
  15. Practical MPI Programming, 1999, p. 7