IV РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ ПРОГРАММ

Понятие декомпозиции. Планирование параллельных программ.  Реализация программы и анализ её производительности.

Для использования нескольких ядер современных процессоров необходимо использование параллельных программ. В данном разделе рассмотрены этапы разработки параллельных программ.

Этапу разработки параллельных программ должен предшествовать этап создания последовательной программы для решения поставленной задачи. Здесь всегда нужно помнить высказывание Топу Ноаге и Donald Knut о том, что преждевременная оптимизация.

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

Далее с помощью Intel® Parallel Inspector желательно исследовать исходный код последовательного алгоритма на наличие мест, которые могут быть проблематичны при параллельном выполнении программы (race condition, deadlock).

Далее с помощью Profiler (например, встроенного в VS), определяется часть кода, которая требует наибольшего времени выполнения. Если функция требует менее 5% процессорного времени, её оптимизировать не следует. Таким образом, выделяются функции программной системы, для которых выполняются этапы, рассмотренные ниже.

Декомпозиция

Этот шаг обычно выполняется первым. Задача, которую необходимо решить, разбивается на порции, которые можно выполнить параллельно. Разбить на порции можно двумя способами:

1. разбиваем на порции все функции, которые надо выполнить (Functional);
2. разбиваем на порции, все данные, которые надо обработать или получить (Domain).

Декомпозиция по функциям

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

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

Декомпозиция по данным

Каждая параллельная задача работает с порцией данных.

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

Здесь возможно использовать несколько вариантов:

1. каждая задача выполняет обработку всей порции данных целиком;
2. задача выполняет обработку одного данного, а затем берет очередное необработанное данное;
3. комбинация первых двух вариантов: каждая задача выполняет работу над порцией данных заданной длины, а после завершения получает очередную порцию.

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

Если обрабатывается 2-х мерный массив, здесь вариантов значительно больше, т.е. обработка по строкам, столбцам и прямоугольникам.

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

Кеше, то в этом случае данный метод не эффективен. Определим размерность матрицы, при которой все 3 матрицы помещаются в Кеше из расчета размера Кеша 32 кБ. В этом случае на одну матрицу примерно приходится 10 кБ, т.е. 10000 байтов, если под один элемент отводится 4 байта, то одна матрица может иметь размер 2500 элементов или 50 * 50 строк – столбцов.

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

Планирование параллельных программ

Анализируются данные, которые используются отдельными задачами. Если есть зависимости по данным, параллельное выполнение исключается (определение зависимостей).

Если используются общие данные, то для них определяются режимы использования и выбираются необходимые элементы синхронизации. Если используется неразделяемая память, то планируются средства коммуникации между процессами.

Анализируются функции и их временная диаграмма. Если необходимо, то планируются средства синхронизации для функций с точки зрения их завершения.

На этапе планирования решаются следующие задачи:

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

Зависимости данных

Введем наборы входных и выходных переменных программы. Обозначим набор входных переменных программы \(R(P)\) (\(R\) от слова read) – это набор входных переменных для всех ее операторов. Аналогично, набор выходных переменных программы \(W(P)\) (\(W\) от слова write) – набор выходных переменных для всех ее операторов. Например, для программы

получаем \(R(P) = {u, v х, w}, W(P) = {х, у}\). Заметим, что переменная \(х\) присутствует как в \(R(P)\) так и в \(W(Р)\).

Теперь сформулируем условия Бернстайна.

Если для двух участков программ \(Р\) и \(Q\):

• пересечение \(W(P)\) и \(W(Q)\) пусто,
• пересечение \(W(P)\) с \(R(Q)\) пусто,
• пересечение \(R(P)\) и \(W(Q)\) пусто,

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

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

Условия Бернстайна проверить просто, но, к сожалению, они исключают параллельное выполнение даже в тех случаях, когда оно возможно. Так, запись в одну и ту же область памяти возможна двумя параллельными потоками, если используются соответствующие объекты синхронизации. Напоминаем, что в случае конкурентного использования общей памяти говорят, что имеет место race condition (состояние гонки). В приведенном выше примере процессы состязаются за вычисление значений переменных \(х\) и \(у\).

Типы зависимостей

Зависимость типа «Чтение после записи»

Возникает, если оператор с номером i формирует значение некоторой переменной (записывает ее), а оператор с номером j (j>i) использует значение этой переменной.

Зависимость типа «Запись после записи»

Возникает, если оператор с номером i формирует значение некоторой переменной (записывает ее), и оператор с номером j (j>i) записывает значение этой же переменной ((j>i)). Значение переменной между операторами i,j не используется.

Зависимость типа «Запись после чтения»

Возникает, если оператор с номером i читает значение некоторой переменной, и это значение меняется, оператором j (j>i). Последние 2 зависимости называются антизависимостями, их легко избежать, если для предыдущего и последующего значений переменной использовать разные переменные.

Способы синхронизации

Барьеры (Barrier). Обычно используются для всех параллельных задач. Устанавливаются, если необходимо обеспечить продолжение кода в данной точке после завершения всех параллельных участков кода — например, всех итераций цикла, которые выполняются параллельно.

Блокировки (Семафоры). Используются для защиты общих данных (критические секции). Первая задача устанавливает «замок». Остальные задачи ждут, пока собственник «замка» не откроет его.

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

Балансировка

Под балансировкой понимаем равномерность загрузки процессоров при выполнении задач.

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

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

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

Гранулярность

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

Поэтому следует определить минимальный блок, который имеет смысл выполнять параллельно. Для этого после определения предполагаемых параллельных участков следует провести вычислительный эксперимент по определению времени выполнения этого участка в последовательном () и параллельном () режиме.

Минимальный размер блока определяется значением, при котором и не менее ожидаемого ускорения.

Учет операций ввода-вывода

Операции ввода-вывода могут существенно замедлить выполнение итерации. Асинхронный ввод-вывод является платформенно-зависимым, и использовать его для программ, которые должны работать на разных платформах, не рекомендуется.

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

Если ввод-вывод данных выполняется с удаленных ЭВМ, то нельзя прогнозировать время, необходимое для доступа к таким данным.

Есть параллельные файловые системы, которые на уровне файловой системы поддерживают параллельный файловый доступ. Примеры таких систем: PVFS/PVFS2, Linux; GPFS: General Parallel File System для AIX (IBM). Но, к сожалению, ни одна из файловых систем, которые используются с Windows, не является параллельной.

Исходя из рассмотренного, рекомендуется операции ввода-вывода выполнять в последовательном режиме. Если это не получается, то каждая ветвь пусть использует свой файл, а потом результаты работы можно объединить.

Определение необходимых ресурсов

Использование параллельных вычислений обычно приводит к увеличению необходимых ресурсов и особенно памяти. Так, вычисление суммы последовательным методом не требует дополнительной памяти. Если для вычисления используется метод последовательного деления пополам, то необходимо \(n/2\) ячеек для хранения промежуточных значений сумм. Поэтому необходимо оценить объем требуемых данных, возможность их размещения в оперативной памяти, так как хранение промежуточных данных на диске может свести к 0 все преимущества параллельных вычислений

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

Масштабируемость

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

Реализация программы и анализ ее производительности

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

Для анализа производительности программы следует использовать встроенные средства анализа производительности программной среды, которая используется для разработки параллельной программы.

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

1. Krishnamurthy E.V. Parallel Processing Principles and Practice. Addi-son-Wesley Pub. Company. – 1989. -P. 208-246.
   Офман // Доклады Академии Наук СССР. – 1962. -Т. 145, № 2. – 293-294 с.
2. Качко, Е.Г. Параллельное программирование: Учебное пособие / Е.Г. Качко. –
   Харьков:Изд-во «Форт», 2011. – 528 с.
3. Воеводин, Вл.В. Параллельная обработка данных. Курс лекций [Электронный ресурс]: электрон. учебник / Вл.В. Воеводин. — Режим доступа: http://parallel.ru/vvv/