Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Konspekt_Trsipv_Ch_2.doc
Скачиваний:
1
Добавлен:
01.07.2025
Размер:
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 Операторы представления суперпозиции и примитивной рекурсии

  1. Суперпозиция

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.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]