12.Параллельные вычисления

12.1.Классификация моделей параллельных вычислений.

Одна из формальных моделей алгоритма – многоленточная (k-ленточная) машина Тьюринга за один такт времени обрабатывает k ячеек ленты. Это наводит на мысль о параллельных вычислениях – организации такой работы, чтобы за один такт работы одновременно выполнялось несколько действий.

Но как это организовать? Сначала формулируются принципы параллельного вычисления. И тут сразу же выясняется, что разные принципы порождают разные модели параллельных вычислений.

Классический (фон-неймановский) компьютер появился в начале 1940-х годов, а уже в 1950-е годы в высилительных схемах начали анализировать идеи распараллеливания. Объектами распараллеливания стали два процесса: поток команд и поток данных. В этой связи в 1960-е годы появилась классификация, предложенная еще в 1966 г. М.Д.Флином .

В одиночном потоке команд (SI) в один момент времени может выполняться только одна команда, а все компоненты компьютера ее обслуживают.

Во множественном потоке команд (MI) в один момент времени может выполняться много команд, при этом работа компонент компьютера распараллеливается - каждую команду обслуживает «часть» компьютера.

В одиночном потоке последовательно выполняются отдельные команды, во множественном потоке – группы команд.

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

Множественный поток данных (MD) состоит из многих зависимых или независимых одиночных потоков данных.

В соответствии со сказанным, все вычислительные системы были разделены Флином на четыре типа:

1. SISD (ОКОД);

2. MISD (МКОД);

3. SIMD (ОКМД);

4. MIMD (МКМД).

Это деление затем стало широко использоваться.

Вычислительная система SISD представляет собой классическую однопроцессорную ЭВМ. На вычислительную системы MISD существуют различные точки зрения. По одной них – за всю историю развития вычислительной техники системы MISD не были созданы. По другой точке зрения к MISD-системам относятся векторно-конвейерные вычислительные системы. Вычислительная система SIMD содержит много процессоров, которые синхронно (как правило) выполняют одну и ту же команду над разными данными. Системы SIMD делятся на два больших класса:

1. векторно-конвейерные вычислительные системы;

2. векторно-параллельные вычислительные системы или матричные вычислительные системы.

Вычислительная система MIMD содержит много процессоров, которые (как правило, асинхронно) выполняют разные команды над разными данными. Это архитектура современных ЭВМ.

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

Последняя классификация связаны с тематикой следующего раздела: коммуникационной сложностью. Дело в том, что в обоих случаях компоненты памяти процессоров связаны между собой, но в первом случае (UMA-системы) коммуникационными (временными) затратами на эту связь можно пренебречь до такой степени, что память считается общей, поэтому такие системы называются еще сильносвязанными вычислительными системами с одинаковым доступом к памяти, то во втором случае (NUMA-системы) затраты на обмен информацией между отдельными локальными компонентами памяти существенны, и они учитываются в модели. Поэтому такие системы называются слабосвязанными. Если коммуникационный ресурс является критичным, то возникает проблематика коммуникационной сложности вычислений.

В настоящее время большинство высокопроизводительных систем относятся к классу однородных систем с общей памятью или к классу однородных систем с распределенной памятью.

Разделения и классификации являются формальными теоретическими инструментами, а на практике мы, как правило, имеем дело с гибридными системами, причем в силу иерархической структуры современных ЭВМ, на каждом уровне своя «гибридность».. Например, на верхнем уровне иерархии система относится к классу MIMD, каждый процессор которой представляет собой систему MIMD или систему SIMD. Память физически распределена по различным частям системы, но логически разделяема (образует единое адресное пространство) и время доступа к различным частям оперативной памяти различно.