- •Теории параллельных вычислений
- •Часть 2
- •Теории параллельных вычислений. Часть 2. Методические указания / Сост. К.В.Кротов - Севастополь: Изд-во СевНту, 2009.- 81 с.
- •Содержание
- •1. Понятия отношений. Классы эквивалентности
- •2. Понятие зависимостей между операторами программы
- •Отношениями зависимости и независимости операций
- •3.1 Непосредственная (сильная) зависимость операций
- •Понятие линейной программы
- •Понятие множеств переменных, используемых в программе
- •Понятие входных переменных в программе
- •3.2 Слабая зависимость операций
- •3.3 Слабая независимость операций
- •3.4 Сильная независимость операций
- •Свойства отношений зависимости и независимости между операциями
- •Алгоритм распараллеливания последовательных программ путем приведения их к полной параллельной форме (ппф)
- •4.1 Условия приводимости к ппф
- •Упрощенная интерпретация условия
- •Пояснение к условию
- •Правило изменения порядка:
- •4.2 Процедура приводимости к ппф
- •Алгоритм преобразования программы к ппф
- •4.3 Метод формирования параллельных групповых операторов
- •Особенности распараллеливания программы путем приведения ее к ппф
- •5.1 Понятие двумерной модели вычислительного процесса
- •5.2 Уточнение множеств двумерной модели вычислительного процесса
- •6 Распараллеливание программ с использованием понятия модели вычислительного процесса Понятие операции и выражения
- •6.1 Постановка задачи распараллеливания
- •Правила построения таблицы для распараллеливания
- •6.2 Условия формирования множества *Aк (функция f1 - функция двумерной модели)
- •Условие бесконфликтности
- •6.3 Правила построения япф программы
- •6.4 Формализация условий вынесения операций ai на k-ый ярус япф
- •Операции с тремя входами
- •7 Распараллеливание программ на основе понятий примитивно-вычислимых и частично-вычислимых функций Понятие вычислимых и рекурсивных функций
- •7.1 Задание рекурсивных функций (Формирование процесса задания алгоритма вычислимых функций)
- •7.2 Суперпозиция вычислимых функций Задание области определения для оператора суперпозиции вычислимых функций
- •7.3 Оператор примитивной рекурсии
- •7.4 Распараллеливание алгоритмов примитивной рекурсии
- •7.5 Распараллеливание простейших аддитивных и мультипликативных функций
- •7.6 Операторы представления суперпозиции и примитивной рекурсии
- •Суперпозиция
- •Оператор рекурсии
- •7.7 Обобщенная форма операторов суперпозиции и рекурсии
- •7.8 Обобщенный вид оператора рекурсии
- •7.9 Обобщенный вид оператора суперпозиции для множественного потока данных
- •8 Распараллеливание программ с использованием моделей вычислительных процессов Модели программ
- •8.1 Граф управления
- •Информационный граф программы
- •8.2 Понятие графа зависимости между операторами
- •8.3 Граф влияния
- •8.4 Теоретико-графовый подход к распараллеливанию алгоритмов
- •8.5 Транзитивные замыкания
- •Формирование транзитивного замыкания
- •Формализация транзитивного замыкания (транзитивного образа вершины)
- •Формализация процедуры определения транзитивного прообраза вершины
- •8.6 Алгоритм формирования параллельной формы программы по графу управления на основе понятия транзитивного образа замыкания вершины
- •8.7 Алгоритм распараллеливания на основе понятия прообраза
- •8.8 Приведение стандартной схемы программы к ярусно-параллельной форме
- •Модели параллельных процессов
- •9 Сети петри
- •Алгоритм функционирования сети Петри
- •Возможности применения сетей Петри
- •10 Графовые модели. Общие понятия
- •10.1 Модель биологического графа
- •Правило функционирования моделей биологических графов
- •10.2 Модель модифицированного биологического графа
- •11.1 Алгоритм формирования а-схемы
- •11.2 Понятие спусковых и управляющих функций
- •11.3 Функционирование a-схем
- •11.4 Понятие вычислительного процесса
- •Аксиомы вычислительного процесса
- •Требования информационного обеспечения оператора а
- •11.5 Понятие конечного автомата (ка)
- •11.6 Логические рассуждения. Комментирование функционирования ка
- •12 Параллельные операторные схемы
- •Правило функционирования операторных схем
7.5 Распараллеливание простейших аддитивных и мультипликативных функций
Для решения задачи распараллеливания вычислений используется утверждения следующих теорем.
Теорема
1
Вычисление примитивно-рекурсивной
функции
,
представленной в виде (17), можно
распараллелить на уровне примитивно-рекурсивных
функций
,
формирующих выражение (17).
Доказательство: основывается на предположении о том, что простейшая вычислимая функция является независимой от результатов других вычислений.
f (x1, x2, …, xn, 0) = f (x1, x2, …, xn, 0) ; (19)
f (x1, x2, …, xn, 1) = f (x1, x2, …, xn, 0) + q (x1, x2, …, xn, 1); (20)
f (x1, x2, …, xn, 1) = q (x1, x2, …, xn, 0) + q (x1, x2, …, xn, 1);
Таким образом, (20) представлена суммой простейших вычислимых функций, не образованных в результате применения операторов суперпозиции и примитивной рекурсии.
Рассуждая по аналогии, n-ый шаг рекурсии:
f (x1, x2, …, xn, M) = q (x1, x2, …, xn, 0) + q (x1, x2, …, xn, 1) …+… q (x1, x2, …, xn, M) (21)
Так как q в (21) является независимыми, то они могут быть определены параллельно с последовательным суммированием результата.
Следствие из теоремы 1
Решение задачи распараллеливания функции f(.), определяемой через (17), предполагает одновременное вычисление функций q(.), значения которых определяются на разных шагах цикла рекурсии (естественно, с последующим суммированием полученных значений).
Теорема
2
Вычисление примитивно-рекурсивной
функции
,
представленной в виде (18), можно
распараллелить на уровне примитивно-рекурсивных
функций
.
Следствие из Теоремы 2.
Решение задачи распараллеливания вычисления функции f(.), представленной в виде (18), предполагает одновременное вычисление функций q(.), соответствующих каждому из шагов алгоритма примитивной рекурсии (последовательности операторов примитивной рекурсии), при последующей операции мультиплексирования полученных значений.
7.6 Операторы представления суперпозиции и примитивной рекурсии
Суперпозиция
f (x1, x2, …, xn, Y) = Smn ( h (m), q(n)1, q(n)2, … , q(n)m)
h (m) – это (m+1) – местная функция вида в предположении, что ее аргументами являются простейшие вычислимые функции q(n)i.
h (m) = h (z1, z2, …, zm, Y)
q(n)I = q(x(n)1i, x(n)2i, … , x(n)ni, zi ) – это (n+1)-местная функция от аргументов x(n)ki, где zi - некоторый результат вычисления данной функции.
Аналогично Y в h обозначает результат вычисления этой функции.
Таким образом, оператор суперпозиции реализуется путем применения функции h к простейшим вычислимым функциям q.
Пример:
У идентифицирует некоторый результат вычислений, сопоставляемый с определенным шагом реализации оператора суперпозиции.
h (m) = h (z1, z2, …, zm, Y)
Допустим, что h интерпретируется как произведение аргументов zi.
Y = h (m) (z1, z2,)= (z1 *z2,)
q(n)1
= q(x1,
z1
)
z1
=
q(x1)
= x2
q(n)2 = q(x1, z2 ) z2 = q(x1) = 3x
Таким образом, оператор суперпозиции, имеющий вид:
h (m) = h (z1, z2, Y)
Y = h (m) (q (n)1, q(n)2) = 3х3
h (2) (q (1)1, q(1)2) = q (1)1, q(1)2
Таким образом, h (m) определяет функцию, реализующую оператор суперпозиции, применяемый к простейшим вычислимым функциям q.
