Параллельная Обработка Данных, 03 лекция (от 18 сентября)

Материал из eSyr's wiki.

Предыдущая лекция | Следующая лекция

Какого ускорения можно достичь?

^T₁/_Tp = S < ¹/_{(a + ^{(1 − a)}/p)}

• T₁ — время исполнения на 1 процессоре
• T_p — время исполнения на p процессорах
• a — доля последовательных операций.

Если а = 0,1, то ускорения больше чем в 10 раз нельзя получить.

Пример. Суммирование элементов массива.

s = 0;

for (int i = 0; i < n; i++)
{
  s = s + A[i];
}

«То что вычислили, используем позже». Поэтому при данной реализации а = 1.

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

Возникает вопрос, можно ли в программе не глядя заменить первый алгоритм на второй? Например, компилятор может заменить? В связи с этим возникают следующие проблемы:

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

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

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

Задача распараллеливания в общем не очень легкая.

Этапы построения распараллеленной программы

1. Итак, пусть перед нами стоит некоторая задача, для решения которой мы должны использовать параллельный компьютер. Например решение СЛАУ.
2. Для решения задачи выбирается метод. Например, метод Гаусса или Зейделя. Метод — математически обоснованная последовательность действий, следуя которой можно получить решение задачи (более конкретное описание, чем сама постановка задачи)
3. Далее надо зафиксировать алгоритм. То есть, четко записать все множество операций, которое будет выполнено, и порядок их исполнения. С одной стороны, казалось бы, каждый метод однозначно определяет это. Но на самом деле этот шаг — принципиальный. Например, берем метод Гаусса. Можно выполнять суммирование с убыванием индексов (обратный) или с возрастанием. Вариант метода с возрастанием индексов — последовательный, а с обратным порядком суммирования он отлично распараллеливается. Разница принципиальна — во втором случае можно идти на большую систему, а в первом нам с ней делать нечего. На этом этапе определяются свойства алгоритма.
4. После того, как выбран алгоритм, выбирается технология программирования. Технологий огромное количество. Можно полагаться на компилятор, что он распараллелит, но эту иллюзию можно отбросить сразу. Чтобы считать на суперкомпьютерах, придется работать руками. Можно использовать написанные профессионалами уже распараллеленные пакеты.
5. После этого появляется программа, которая поступает на вход компилятору.
6. И только после этого мы добираемся до компьютера.

Каждый из вышеперечисленных шагов важен для конечного результата. Например, если на шаге выбран неперспективный метод, нет смысла запускать её на суперкомпьютере. Если плохо написана программа — то же самое. Компилятор — тоже очень серьезный этап. Сравните код, генерируемый GNU CC и каким-нибудь хорошим коммерческим компилятором — можно получить сразу ускорение в 2—3 раза. Во время курса мы поговорим о всех этих этапах. Вообще, курс будет состоять из трех частей:

• Архитектура компьютеров
• Технологии программирования. Есть ли соответствия между видами технологий и классами компьютеров. Познакомимся с технологиями.
• Введение в структуру анализа алгоритмов. Подробно рассмотрим пример с Гауссом.

Часть 1. Архитектура параллельных вычислительных систем

Практически все современные компьютеры делятся на два больших класса:

1. Компьютеры с общей памятью. Есть какое-то количество процессоров, сидящих на общей памяти. Все процессоры одинаковы. Всем процессорам одинаково доступна единая оперативная память. У них есть единое адресное пространство. В таких системах единая память, единая ОС, единая подсистема ввода-вывода. Для обозначения этого класса процессоров существует специальная аббревиатура — SMP (Shared Memory Processors). Система симметрична относительно любого из процессоров. Этот факт также нашел отображение в аббревиатуре, иногда он расшифровывается как SMP (Symmetric MultiProcessors). Конкретная расшифровка зависит от производителя.
2. Компьютеры с распределенной памятью. В таких системах имеется единая коммуникационная среда, через которую объединяются уже не процессоры, а полноценные компьютеры, каждый со своим процессором, своей памятью. То есть, память физически распределена по разным узлам. Если одному процессору нужны данные из локальной памяти другого, то он передает запрос через коммуникационную среду.

Плюсы и минусы архитектур с распределённой памятью по сравнению с архитектурой с общей памятью:

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

Простенький пример — сложение двух векторов.

В случае 1 — проблем вообще нет:

for(int i = 0; i < n ; i ++)
{
  A[i] = B[i] + C[i];
}

Каждому процессору отдается по куску векторов, и он их обрабатывает.

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

Вторая схема не столь эффективна, но более распространена на практике. В TOP500 самых мощных систем практически все системы — второго вида. По чисто технологическим причинам, чистый SMP не может содержать больше 16—32 процессоров. В то же время, системы второго вида практически не ограничены по количеству узлов, и содержат их сотни и тысячи. То есть, SMP-системы не самые мощные. Но зато сложность программирования для них гораздо меньше. В этих двух подходах хорошо видна борьба двух целей, которые ставят при построении подобных систем: построить компьютер максимальной производительности или построить самую эффективную технологию программирования. Надо найти компромисс.

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

NUMA (Non-Uniform Memory Acces) — архитектура с неоднородным доступом к памяти — объединяет плюсы предыдущих подходов. Первый компьютер, построенный по архитектуре NUMA — Cm* (конец 70-х годов). Компьютер объединяет несколько кластеров, связанных между собой по широкой межкластерной шине. Все кластеры имеют выход на эту шину и устроены следующим образом — есть контроллер памяти, а дальше все как обычно: есть процессор, локальная память, на локальной шине устройства ввода-вывода — все вместе называется кластером. Все кластеры идентичны, все устроены абсолютно одинаково, и какое-то их число висит на межкластерной шине.

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

Другой вариант был предложен чуть позже. BBN Butterfly (80-е годы). Коммерческая версия достигала 256 процессоров. Рассмотрим схему работы этой системы для 16 процессоров.

Схема коммутации устроена следующим образом — коммутатор 4 × 4, то есть 4 входа, 4 выхода, и любой вход может быть скоммутирован с любым выходом. Для соединения 16 процессоров использовались две линейки по 4 коммутатора. Первая линейка соединялась напрямую. Выходы с первого коммутатора шли на первые входы коммутаторов второй линейки. Выходы второго — на вторые позиции второй линейки. Точно так же с 3 и 4. А выходы второй линейки опять соединяются в прямом порядке с процессорами. В такой схеме все связаны со всеми. Дальше все как в случае с Cm*. В каждом узле процессор, локальная память, контроллер памяти. Узлы одинаковые.

Но оба последних случая — NUMA. Зато мы сохранили единое адресное пространство.