MISD (Multiple Instruction stream, Single Data stream)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 07:12, 20 декабря 2016.
(перенаправлено с «MISD»)

MISD-архитектура (англ. Multiple Instruction stream, Single Data stream, множественный поток команд, одиночный поток данных, МКОД) — тип архитектуры параллельных вычислений, где множество функциональных блоков выполняют различные операции над одними и теми же данными. Один из классов вычислительных систем в классификации Флинна.[1]

MISD.png

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

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

Систолические массивы, как правило, запрограммированы под конкретную операцию, вроде умножения с накоплением, чтобы выполнять крупную параллельную интеграцию, свёртку, корреляцию, умножение матриц или сортировку данных. Обычно систолический массив содержит большую интегральную схему примитивных вычислительных узлов, что могут быть аппаратно или программно настроены под конкретное приложение. Узлы, как правило, фиксированы и идентичны, в то время как межсоединения программируются. Более общие волновые процессоры, напротив, используют сложные и индивидуально программируемые узлы, что могут или не могут быть монолитными, в зависимости от размера массива и параметров конструкции. Так как волнообразное распространение данных через систолический массив напоминает импульс кровеносной системы человека, название «систолический» почерпнули из медицинской терминологии.[2]

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

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

Несмотря на все расписанные характеристики, связанные с отнесением систолических массивов к типу MISD, их классификация несколько спорна. Безусловно, с учётом того, что на вход подаётся, как правило, вектор независимых величин, систолический массив никак не может быть SISD. Поскольку входные значения сливаются и объединяются в результат(ы) и не сохраняют свою независимость, как в блоке обработки векторов SIMD, массив нельзя отнести и к этому типу. Как следствие, массив нельзя классифицировать и как MIMD, потому что MIMD, по большому счёту, это ряд меньших SISD или SIMD-ЭВМ.

Наконец, в связи с тем, что совокупность данных изменяется, проходя через массив от узла к узлу, множественные узлы не действуют на одних и тех же данных, это делает классификацию как MISD некорректной. Более того, систолический массив нельзя рассматривать как MISD по тем же причинам, по каким не подходит под тип SISD: входные данные представляют вектор не одиночных величин, хотя можно возразить, что данный входной вектор — одиночный набор данных. На вышеуказанное замечание можно закрыть глаза. Систолические массивы часто предлагают в качестве классического примера MISD-архитектуры в учебниках по параллельным вычислениям и в инженерном классе. Если рассматривать массив как неделимую структуру, его можно классифицировать как ОФуМДОбР = одиночная функция, множественные данные, общий результат (англ. SFMuDMeR = Single Function, Multiple Data, Merged Result(s)).

Классификация Флинна

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

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

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

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

Стоит также отметить, что наиболее популярные классы (SIMD и MIMD) делятся по способу работы с памятью с точки зрения программиста[10][11]. Таким образом, выделяют системы с общей памятью (англ. 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), большей частью они работают независимо друг от друга, но время от времени обмениваются данными для перехода к следующему шагу.

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

Примечания

  1. MISD — Википедия.
  2. MISD — Wikipedia.
  3. Флинн М. Дж.: Высокоскоростные компьютеры. Proc IEEE 54:1901-1901. — 1966.
  4. Флинн М. Дж.: Некоторые компьютерные организации и их эффективность. IEEE Transactions on Computers, 21(9): 948—960. — 1972.
  5. 5,0 5,1 5,2 Падуя, 2012. Стр. 689-697.
  6. Шаблон:Книга
  7. Шаблон:Книга
  8. Шаблон:Книга
  9. Валентин Седых. Мультипроцессинг сегодня. — 2004 г.
  10. «Обзор недавних компьютеров: Основные классы архитектур
  11. Severance_Dowd 1998, p. 259-267.