I.I. Метод прогонки

Метод прогонки представляет собой частный случай метода исключения Гаусса, ориентированный на специальные системы линей­ных алгебраических уравнений с ленточной структурой матрицы коэффициентов. А именно, на системы трехточечных уравнений:

(1)

Здесь и - компоненты вектора неизвестных и вектора правых частей, а , , образуют трехдиагональную матрицу системы. Формулы метода прогонки для нахождения неизвестных и прогоночных коэффициентов имеют вид /13/

(2)

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

0<<1, 0< (3)

с соответствующими начальными и краевыми условиями

(4)

Для отыскания приближенного решения y задачи (3), (4) на равномерной сетке ,где

hи τ шаги сетки по пространственной x и временной t коорди­нате, используется однопараметрическое семейство разностных схем (схема с весами)

(5)

Здесь вес σ - произвольный вещественный параметр, а разностный оператор Λ является оператором второй разностной производной т.е.

Кроме этого вводится разностный аналог краевых и начальных условий

(6)

Решение разностной краевой задачи (5), (6) состоит в определении на каждом n -м временном слое (n=1,..., n₀) значений сеточной функции yⁿ_i с помощью метода прогонки (2). С этой целью соотно­шения (5), (6) представляются в виде (I). Будем иметь

(7)

Порядок вычислений формул (2) на одном временном слое отра­зим граф-схемой (рис.1), вершины которой означают оператор вы­числения соответствующей величины, а дуги - отношение предшест­вования. Найденное решение схемы (5) является начальным ус­ловием для следующего временного слоя, что отражено на рис.1 дутой из y в f. Кроме того, если коэффициенты разностной схемы не зависят от времени, что, как правило, выполняется при решении линейных задач, то прогоночный коэффициент α_i вычисляется один раз вне временного цикла. В соответствии с этим типичным случаем вычисление α_i; на рис.1 не показано. Вычисление прогоночного коэффициента β_i можно осуществлять по рекуррентной формуле, ана­логичной формуле для сеточной функции y, β_i+1=p_i β_i+q_i, где

(8)

Таким образом, на каждом временном слое по методу прогонки (2) требуется вычислять по N значений β_i, y_i в соответствии с рекуррентными формулами первого порядка, имеющими чисто последо­вательный характер выполнения, на каждом шаге которого требуется одно умножение и одно сложение. Если время выполнения этих двух операций, включая также чтение операндов и запись результатов в память, обозначить через , то время вычисления на одном времен­ном слое сеточных функций β_i, y_i составит значение 2N. Кроме того, на каждом временном слое необходимо вычислять величину q_i, (см.формулу (8)), что потребует умножения значения на величину f_i, для вычисления которой в соответствии с форму­лами (7) потребуется дополнительно два умножения, два вычитания и три сложения^* плюс время t₁, расчета значения , т.е. всего для вычисления значения f_i необходимо время где t₂ -время выполнения двух вычитаний.

^*Величины в формуле для f_i, не зависящие от индекса n, представлены своими значениями, вычисляемыми однократно вне временного цикла.

Последовательный характер вычислений значений y_i, входящих в выражение для f_i, обуслав­ливают последовательное вычисление N-1 значений q_i.. Таким об­разом, формулы последовательной прогонки (2) реализуются на одном процессоре, и время вычислений на одном временном слое составит значение .

Возможности реализации формул (2) более чем на одном процес­соре без применения каких-либо методик распараллеливания весьма ограничены. Исследуем их в случае чисто неявной разностной схемы (σ=1) и в предположении, что правая часть φ не зависит от време­ни. Тогда по формулам (7), (8) имеем , где и значения μ_i, ν_i вычисляются вне временного цикла, т.е. .

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

Так как вычисление значений q_i полностью совмещаются с вычислением значений y_i, то время расчета на одном временном слое составит здесь величину .

Формулы (2) определяют правую прогонку (функция y_i находится последовательно, начиная от правой границы). Аналогично опреде­ляются формулы левой прогонки /13/

(9)

Используя формулы (9) можно совместить расчеты всех трех сеточных функций y_i, β_i, q_i с помощью трех процессоров. Для этого следует чередовать формулы правой (2) и левой (9) прогонки на соседних временных слоях. Пусть первый процессор вычисляет значения y_i например, правой прогонкой. По мере появления второй процессор вычисляет значения q_i для следующего временного слоя. Это позво­ляет третьему процессору вычислять по формулам левой прогонки значения β_i для следующего временного слоя, на котором наоборот первый процессор осуществляет левую, а третий - правую прогонку. По аналогии с рис. 2 на рис. 3 показана диаграмма работы процес­соров. Из диаграммы заключаем, что время вычислений на одном временном слое составляет величину .

Комбинацией правой и левой прогонок на одном временном слое является метод встречных прогонок /13/.В этом методе выбирается некоторый m -й узел сетки и решение в первых m узлах определяется правой прогонкой (2), в последних N-m узлах - левой прогонкой (9), а в m- музле по формуле, содержащей коэффициенты α_m, β_m (полученные при вычислении соотно­шений (2) и (9)) и требующей времени примерно . Понятно, что допустима одновременная работа двух процессоров. Для обеспечения их более равномерной, загрузки следует выбирать где развернутые квадратные скобки означают округление до целого с избыт­ком. Процессоры работают одновременно, поэтому с учетом времени для вычисления y_m легко установить значение совокупного времени работы на одном временном слое . Здесь квадратные скобки означают округление до целого с недостатком. В соответствии с диаграммой на рис. 2 из этого времени можно исключить время расчета значений q_i, выполняя его с помощью двух дополнительных процессоров. Время работы четырех процессоров на одном временном слое составит что равно или всего лишь на меньше времени работы трех процессоров при чередовании правой и левой прогонки на соседних временных слоях.

Результаты анализа алгоритма последовательной прогонки сведем в табл.1. Кроме полученных значений времени и числа процессоров в табл.1 приведены также очевидные значения (приближенные для всех колонок кроме первой) ускорения и эффективности.

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

Дата добавления: 2014-01-14