Взаимодействие параллельных процессов, синхронизация процессов

1.4 Взаимодействие параллельных процессов, синхронизация процессов

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

Порождение и уничтожение процессов UNIX-подобных операционных системах выполняются операторами (системными вызовами).

Параллелизм часто описывается в терминах макрооператоров, в параллельных языках запуск параллельных ветвей осуществляется с помощью оператора JOIN.

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

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

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

Синхронизация может поддерживаться и аппаратно (например, барьерная синхронизация в суперкомпьютере Cray T3, с помощью которой осуществляется ожидание всеми процессами определенной точки в программе, после достижения которой возможна дальнейшая работа.

1.5 Возможное ускорение при параллельных вычислениях (закон Амдаля)

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

Рисунок 4. Схема к выводу закона Амдаля

Закон Амдаля (1967) связывает потенциальное ускорение вычислений при распараллеливании с долей операций, выполняемых априори последовательно. Пусть f (0<f<1) – часть операций алгоритма, которую распараллелить не представляется возможным; тогда распараллеливаемая часть равна (1-f); при этом затраты времени на передачу сообщений не учитываются, ts – время выполнения алгоритма на одном процессоре (последовательный вариант), n – число процессоров параллельной машины.

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

· f×ts – время выполнения части алгоритма, которую распараллелить невозможно,

· (1-f )×ts/n – время, затраченное на выполнение распараллеленной части алгоритма.

Время t_p, необходимое для расчета на параллельной машине с n процессорами, равно

t_p=f×ts+(1-f)×ts/n .

Ускорение времени расчета при малой доли последовательной операций (f<<1) возможно достичь (не более чем в n раз) ускорения вычислений (рисунок 4).

Рисунок 5. Трехмерный график, количественно отражающий зависимость Амдаля

В случае f=0,5 ни при каком количестве процессоров невозможно достичь S>2! Заметим, что эти ограничения носят фундаментальный характер (их нельзя обойти для заданного алгоритма), однако практическая оценка доли f последовательных операций априори обычно невозможна.

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

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

Рисунок 6. Производительность вычислительной кластерной системы на процедуре умножения матриц (эксперимент и расчет по формуле Амдаля)

На рисунке 6 приведены результаты эксперимента на кластере SCI-MAIN НИВЦ МГУ на задаче умножения матриц по ленточной схеме (размерность 103×103 вещественных чисел двойной точности), экспериментальные данные наилучшим образом (использован метод наименьших квадратов) соответствуют формуле Амдаля при f=0,051.

Закон Амдаля удобен для качественного анализа проблемы распараллеливания.