2. Принципы, языки, технологии параллельного программирования.

   1. Параллелизм задач, его особенности и характеристики.

Параллелизм  процесс, одновременность актов.

Процесс:

• дискретный (можно наблюдать в точках с частотой генераторов, работающих в системе).

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

• асинхронный (не вводит временных ограничений).

• синхронный (сохраняет причинно-следственные связи и вводит ограничения на время актов, которое не нарушает связи).

Может быть временное и событийное описание процесса.

Синхронный процесс.

a_i – акты, k₁..k₄- команды.

После выполнения a₁ –может выполнятся a₂.

Введено ограничение на время протекания событий.

–синхронная схема последовательная.

Асинхронный процесс.

Абсолютно параллельное вычисление.

1. Процессы, их характеристики.

1. Дискретный процесс – это множество протекающих (во времени) актов, упорядоченных отношениями (как правило) причинно-следственных связей между актами.

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

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

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

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

Пример конструктивного процесса.

Правила выполнения:

• Выполнить P(x); в зависимости от истинности.

• и окончить.

• и окончить.

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

6. Каждый параллельный алгоритм характеризуется множеством потоков, каждый поток фиксирует последовательность выполнения актов при применении параллельного алгоритма к данным.

1. Типы и характеристики параллелизма.

1. Коэффициент ускорения.

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

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

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

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

, где - ближайшее целое к. Очевидно,.

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

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

По закону Амдала, предельное ускорение решения задачи в параллельной форме равно:

, где - доля операций, которые выполняются последовательно в программе (- доля параллельно выполняющихся операций),- количество компьютеров ВС.

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

2. Глубина распараллеливания.

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

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

1. - сложность вычисления одной строки результирующей матрицы.

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

2. - сложность вычисления одного элемента результирующей матрицы.

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

3. - сложность выполнения операции умножения.

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

4. -усредненная сложность выполнения операции умножения и параллельное вычисление суммы , при вычислении элементов результирующей матрицы.

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

Во всех четырех случаях коэффициент ускорения неограниченно растет с увеличением . Задача с неограниченным параллелизмом..

3. Ширина максимального яруса при выполнении параллельных алгоритмов.

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

4. Понятие эффективности использования ресурсов.

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

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

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