Оптимизация обращений к памяти при сеточных методах решения трехмерных задач.

 

Схема решения сформулированных задач при семиточечном шаблоне выглядит примерно следующим образом:

 

do 99 k = 1, n

do 99 i = 1, n

do 99 j = 1, n

99 A(i, j, k) = A(i-1, j, k) + A(i+1, j, k) + A(i, j-1, k)+ A(i, j+1, k) + A(i, j, k-1)+ A(i, j, k+1)

 

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

Пусть количество процессоров p = n. 

Разместим трехмерный массив A в параллельной памяти поблочно с размерами блоков p^1/3. Количество пересылочных тактов равно 6*p^1/3. 

Если массив разместить так, что элемент A(i, j, k) находится в модуле памяти с номером i mod p, то количество пересылочных тактов 2*p. Таким образом, блочное размещение имеет очевидные преимущества. 

Рассмотрим решение данной трехмерной задачи на вычислительной модели с кэш-памятью.

Предположим, что массив A считывается параллелепипедами со сторонами M1, M2, M3 (M1*M2*M3 = M). Тогда на считывание M данных приходится вычислений тела цикла

 

ValumeCulc = (M1 – 2)*(M2 – 2)*(M3 – 2)

= M – 2*(M1*M2 + M2*M3 + M1*M3) + 4*(M1 + M2 + M3) – 8

 

Несложно установить, что данная функция достигает оптимального значения (M^1/3 -2)³ при равенстве всех сторон параллелепипеда M1 = M2 = M3 = M^1/3.

Количество чтений памяти равно n³/(M^1/3 -2)³.

Если выполнять программу непосредственно, как она записана тройным циклом, то будут считываться строки (i, j), (i-1, j), (i+1, j), (i, j-1), (i, j+1) по M/5 чисел. То есть 

 

ValumeCulc = M/5 – 2.

 

Количество чтений памяти равно R = n³/(M/5 – 2) ≈ 5*n³/M.

Выигрыш при блочном размещении данных асимптотически (при больших M) в 5 раз.

 

 

Блочные размещения данных для решения СЛАУ с ленточной матрицей.

 

Рассмотрим СЛАУ с ленточными матрицами, решение которых методами редукции и окаймления приводит к СЛАУ с блочными трехдиагональными матрицами.

Любая ленточная матрица может быть разбита на блоки так, что она станет блочной трехдиагональной матрицей.

 

                  

 

Имеет место следующий очевидный факт.

       Пусть для матрицы A = {a_ij }_{i, j=1, …, n} m – такое наименьшее число, что a_ij = 0, если ½ i-j½ > m. Тогда для того, чтобы матрица A после разбиения на блоки стала блочной трехдиагональной, необходимо и достаточно, чтобы размер блоков был не меньше m. 

       Теперь к СЛАУ с блочной трехдиагональной матрицей может быть применен метод редукции, который, в частности, допускает параллельное выполнение [90], [91]. В случае треугольной ленточной СЛАУ получается блочная двухдиагональная матрица. Решение СЛАУ с такой матрицей равносильно вычислению цикла с линейной рекуррентной зависимостью. Параллельные алгоритмы вычисления таких циклов приводятся в [103], [108]. При размещении блочной матрицы в параллельной памяти, очевидно, для нормального выполнения указанных алгоритмов все элементы каждого блока должны находиться в одном и том же модуле памяти. Следовательно, для параллельных алгоритмов решения СЛАУ с такими матрицами естественным является блочное размещение данных. 

 

 

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

 

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

 

 

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

       Пусть задана рекуррентная последовательность

 

 

Обозначим матрицу коэффициентов отображения f_n 

 

 

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

 

B₁ = A₁

B₂ = A₁ * A₂

B₃ = A₁ * A₂ * A₃

………………….

B_n-1 = A₁ * A₂ * A₃ *…* A_n-1

 

(Параллельный алгоритм вычисления всех таких произведений можно найти в [ 25 ]). Теперь все члены последовательности x_k могут быть одновременно вычислены по элементам матриц

 

 

по формулам

 

 

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

 

 

⇐ Предыдущая6789101112131415Следующая ⇒

Поделиться: