stringtranslate.com

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

Таксономия Флинна — это классификация компьютерных архитектур , предложенная Майклом Дж. Флинном в 1966 году [1] и расширенная в 1972 году. [2] Система классификации закрепилась и использовалась в качестве инструмента при проектировании современных процессоров и их функциональных возможностей. С появлением многопроцессорных центральных процессоров (ЦП) контекст многопрограммирования развился как расширение системы классификации. Векторная обработка , охватываемая таксономией Дункана , [3] отсутствует в работе Флинна, поскольку Cray-1 был выпущен в 1977 году: вторая статья Флинна была опубликована в 1972 году.

Классификации

Четыре первоначальные классификации, определенные Флинном, основаны на количестве параллельных потоков инструкций (или управления) и потоков данных, доступных в архитектуре. [4] Флинн определил три дополнительные подкатегории SIMD в 1972 году. [2]

Один поток инструкций, один поток данных (SISD)

Последовательный компьютер, который не использует параллелизм ни в потоках инструкций, ни в потоках данных. Один блок управления (CU) извлекает из памяти один поток инструкций (IS). Затем CU генерирует соответствующие сигналы управления, чтобы направить один процессорный элемент (PE) на работу с одним потоком данных (DS), т. е. одну операцию за раз.

Примерами архитектур SISD являются традиционные однопроцессорные машины, такие как старые персональные компьютеры (ПК) (к 2010 году многие ПК имели несколько ядер) и мэйнфреймы .

Один поток инструкций, несколько потоков данных (SIMD)

Одна инструкция одновременно применяется к нескольким различным потокам данных. Инструкции могут выполняться последовательно, например, конвейеризацией, или параллельно несколькими функциональными блоками. В статье Флинна 1972 года SIMD подразделяется на три дополнительные категории: [2]

Процессор массива

Современный термин для процессора массива — « одна инструкция, несколько потоков » (SIMT). Это отдельная классификация в таксономии Флинна 1972 года как подкатегория SIMD. Она идентифицируется по параллельным подэлементам, имеющим собственный независимый регистровый файл и память (кэш и память данных). В оригинальных работах Флинна приводятся два исторических примера процессоров SIMT: SOLOMON и ILLIAC IV .

Nvidia обычно использует этот термин в своих маркетинговых материалах и технических документах, где она доказывает новизну своей архитектуры. [6] SOLOMON опередил Nvidia более чем на 60 лет.

Aspex Microelectronics Associative String Processor (ASP) [7] в своих маркетинговых материалах классифицировал себя как «массивный широкий SIMD», но имел битовые ALU и битовую предикацию (таксономия Флинна: ​​ассоциативная обработка), и каждый из 4096 процессоров имел свои собственные регистры и память (таксономия Флинна: ​​обработка массивов). Linedancer, выпущенный в 2010 году, содержал 4096 2-битовых предицированных SIMD ALU, каждое со своей собственной адресуемой по содержимому памятью , и был способен выполнять 800 миллиардов инструкций в секунду. [8] Aspex ASP associative array SIMT процессор предшествовал NVIDIA на 20 лет. [9] [10]

Конвейерный процессор

В то время, когда Флинн написал свою статью 1972 года, многие системы использовали основную память как ресурс, из которого конвейеры читали и писали. Когда ресурс, из которого все «конвейеры» читают и пишут, является файлом регистра, а не основной памятью, получаются современные варианты SIMD. Примерами являются Altivec , NEON и AVX .

Альтернативное название для этого типа SIMD на основе регистров - "упакованный SIMD" [11] и еще одно - SIMD в регистре (SWAR) . Когда применяется предикация, она становится ассоциативной обработкой (ниже)

Ассоциативный процессор

Современный термин для ассоциативного процессора — « предикативный » (или маскированный) SIMD. Примеры включают AVX-512 .

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

Несколько потоков инструкций, один поток данных (MISD)

Несколько инструкций работают с одним потоком данных. Это необычная архитектура, которая обычно используется для обеспечения отказоустойчивости. Гетерогенные системы работают с одним и тем же потоком данных и должны согласовывать результаты. Примерами служат компьютер управления полетом Space Shuttle . [12]

Несколько потоков инструкций, несколько потоков данных (MIMD)

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

Диаграмма сравнения классификаций

Эти четыре архитектуры показаны ниже визуально. Каждый процессорный блок (PU) показан для одноядерного или многоядерного компьютера:

Дальнейшие подразделения

По состоянию на 2006 год все 10 лучших и большинство суперкомпьютеров TOP500 основаны на архитектуре MIMD.

Хотя это и не является частью работы Флинна, некоторые далее делят категорию MIMD на две категории ниже, [13] [14] [15] [16] [17] и иногда рассматриваются даже более поздние подразделения. [18]

Одна программа, несколько потоков данных (SPMD)

Несколько автономных процессоров одновременно выполняют одну и ту же программу (но в независимых точках, а не в режиме lockstep , который накладывает SIMD) на разных данных. Также называется одиночным процессом, множественными данными [17] — использование этой терминологии для SPMD технически неверно, поскольку SPMD — это модель параллельного выполнения, предполагающая выполнение программы несколькими взаимодействующими процессорами. SPMD — наиболее распространенный стиль явного параллельного программирования. [19] Модель SPMD и термин были предложены Фредерикой Даремой из команды RP3. [20]

Несколько программ, несколько потоков данных (MPMD)

Несколько автономных процессоров одновременно работают по крайней мере с двумя независимыми программами. В контексте HPC такие системы часто выбирают один узел в качестве «хоста» («явная модель программирования хост/узел») или «менеджера» (стратегия «менеджер/работник»), который запускает одну программу, которая передает данные всем остальным узлам, которые запускают вторую программу. Затем эти другие узлы возвращают свои результаты непосредственно менеджеру. Примером этого может служить игровая консоль Sony PlayStation 3 с ее процессором SPU/PPU .

MPMD распространен в не-HPC-контекстах. Например, система сборки make может создавать несколько зависимостей параллельно, используя целевые программы в дополнение к самому исполняемому файлу make. MPMD также часто принимает форму конвейеров. Простая команда оболочки Unix, например ls | grep "A" | more, запускает три процесса, выполняющих отдельные программы параллельно, при этом вывод одного из них используется в качестве ввода для следующего.

Оба они отличаются от явного параллельного программирования, используемого в HPC, тем, что отдельные программы являются общими строительными блоками, а не реализуют часть конкретного параллельного алгоритма. В подходе конвейеризации объем доступного параллелизма не увеличивается с размером набора данных.

Смотрите также

Ссылки

  1. ^ Флинн, Майкл Дж. (декабрь 1966 г.). «Очень высокоскоростные вычислительные системы». Труды IEEE . 54 (12): 1901–1909. doi :10.1109/PROC.1966.5273.
  2. ^ abc Flynn, Michael J. (сентябрь 1972 г.). «Некоторые компьютерные организации и их эффективность» (PDF) . IEEE Transactions on Computers . C-21 (9): 948–960. doi :10.1109/TC.1972.5009071. S2CID  18573685.
  3. ^ Дункан, Ральф (февраль 1990 г.). «Обзор архитектур параллельных компьютеров» (PDF) . Компьютер . 23 (2): 5–16. doi :10.1109/2.44900. S2CID  15036692. Архивировано (PDF) из оригинала 2018-07-18 . Получено 2018-07-18 .
  4. ^ «Параллелизм на уровне данных в векторной, SIMD и архитектуре GPU» (PDF) . 12 ноября 2013 г.
  5. ^ Флинн, Майкл Дж. (сентябрь 1972 г.). «Некоторые компьютерные организации и их эффективность» (PDF) . IEEE Transactions on Computers . C-21 (9): 948–960. doi :10.1109/TC.1972.5009071.
  6. ^ "Вычислительная архитектура CUDA следующего поколения от NVIDIA: Fermi" (PDF) . Nvidia .
  7. ^ Ли, РМ (1988). «ASP: экономичный параллельный микрокомпьютер». IEEE Micro . 8 (5): 10–29. doi :10.1109/40.87518. S2CID  25901856.
  8. ^ "Linedancer HD – Overview". Aspex Semiconductor . Архивировано из оригинала 13 октября 2006 г.
  9. ^ Крикелис, А. (1988). Искусственная нейронная сеть на массивно-параллельной ассоциативной архитектуре . Международная конференция по нейронным сетям. Дордрехт: Springer . doi :10.1007/978-94-009-0643-3_39. ISBN 978-94-009-0643-3.
  10. ^ Одор, Геза; Крикелис, Арги; Вестергомби, Дьёрдь; Рорбах, Франсуа. «Эффективное моделирование Монте-Карло на архитектуре массово-параллельной обработки ассоциативных строк System-V» (PDF) .
  11. ^ Мияока, Y.; Чой, J.; Тогава, N.; Янагисава, M.; Оцуки, T. (2002). Алгоритм генерации аппаратных блоков для синтеза ядра процессора с упакованными инструкциями типа SIMD . Азиатско-Тихоокеанская конференция по схемам и системам. стр. 171–176. doi :10.1109/APCCAS.2002.1114930. hdl : 2065/10689 . ISBN 0-7803-7690-0.
  12. ^ Спектор, А.; Гиффорд, Д. (сентябрь 1984 г.). «Основная компьютерная система космического челнока». Communications of the ACM . 27 (9): 872–900. doi : 10.1145/358234.358246 . S2CID  39724471.
  13. ^ "Single Program Multiple Data stream (SPMD)". Llnl.gov. Архивировано из оригинала 2004-06-04 . Получено 2013-12-09 .
  14. ^ "Требования к программированию для компиляции, сборки и запуска заданий". Руководство пользователя Lightning . Архивировано из оригинала 1 сентября 2006 г.
  15. ^ "Виртуальный семинар CTC". Web0.tc.cornell.edu . Получено 2013-12-09 .
  16. ^ "NIST SP2 Primer: Distributed-memory programming". Math.nist.gov. Архивировано из оригинала 2013-12-13 . Получено 2013-12-09 .
  17. ^ ab "Понимание параллельного управления заданиями и передачи сообщений в системах IBM SP". Архивировано из оригинала 3 февраля 2007 г.
  18. ^ "9.2 Стратегии". Распределенное программирование памяти . Архивировано из оригинала 10 сентября 2006 года.
  19. ^ "Одна программа, несколько данных". Nist.gov. 2004-12-17 . Получено 2013-12-09 .
  20. ^ Darema, Frederica ; George, David A.; Norton, V. Alan; Pfister, Gregory F. (1988). "Вычислительная модель с одной программой и несколькими данными для EPEX/FORTRAN". Parallel Computing . 7 (1): 11–24. doi :10.1016/0167-8191(88)90094-4.