International research journal

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

---

Международный научно-исследовательский журнал 
▪
 № 5 (95) ▪ Часть 3 ▪ Май 
93 
Численное решение краевой задачи для уравнения теплопроводности с использованием неявной конечно-
разностной схемы сводится к решению системы линейных алгебраических уравнений, имеющей специальный 
(трехдиагональный) вид. Для нахождения решения таких систем используется метод прогонки, который реализуется в 
последовательном режиме. Для требуемого ускорения расчетов при большом объеме начальных данных и высокой 
требуемой точности вычисления необходимо использовать параллельные алгоритмы для решения СЛАУ с 
трехдиагональной матрицей коэффициентов при неизвестных. 
Так как данная разработка предназначена для использования в образовательном процессе для студентов, 
изучающих как численное моделирование, так и методы распараллеливания вычислений, были выполнены несколько 
реализаций распараллеливания алгоритма прогонки на общей памяти средствами OpenMP и с использованием 
технологии организации параллельных вычислений на основе потоков. 
Особенности организации параллельных вычислений с использованием многопроцессорных вычислительных 
систем рассматриваются в работах [1], [2], [3]. Варианты организации ускорения параллельных расчетов задачи 
теплопроводности рассматривались разными коллективами авторов. Очевидно, что практический интерес вызывают 
работы, связанные с реализацией неявной разностной схемы для уравнения теплопроводности с использованием 
методов распараллеливания трехдиагональной прогонки [6], [7], [9].
Среди различных способов распараллеливания вычислений при решении систем алгебраических уравнений с 
трехдиагональной матрицей рассматривались алгоритмы, вычислительная практика использования которых достаточно 
известна: метод встречной прогонки, метод параметрической прогонки (метод Яненко [4]), параллельно-конвейерный 
метод [6], метод параллельно-циклической редукции, горизонтально-блочный параллельный алгоритм [5]. 
В данной работе для распараллеливания метода трехдиагональной прогонки рассматривается использование 
алгоритма встречной прогонки и блочного алгоритма на системах с общей памятью.
Кратко рассмотрим особенности этих подходов для системы линейных уравнений с трехдиагональной матрицей 
коэффициентов при неизвестных вида:
𝑎
𝑖
𝑥
𝑖−1
− 𝑏
𝑖
𝑥
𝑖
+ 𝑐
𝑖
𝑥
𝑖 + 1
= 𝑓
𝑖 
𝑖 = 0, … , 𝑛 , 𝑎
0
= 0, 𝑐
𝑛
= 0.
(1) 
Прямой ход метода правой прогонки позволяет вычислить прогоночные коэффициенты по формулам: 
𝛼
1
=
−𝑏
0
𝑐
0
, 

1
=
−𝑓
0
𝑐
0
,
𝛼
𝑖+1
=
−𝑏
𝑖
𝑎
𝑖
𝛼
𝑖
+𝑐
𝑖
,

𝑖+1
=
𝑓
𝑖
−𝑎
𝑖
𝑏
𝑖
𝑎
𝑖
𝛼
𝑖
+𝑐
𝑖
, 𝑖 = 1, … , 𝑛 − 1
(2) 
По формулам обратного хода правой прогонки вычисляются неизвестные 
𝑥
𝑖
. 
𝑥
𝑛
=
𝑓
𝑛
−𝑎
𝑛
𝑏
𝑛
𝑎
𝑛
𝛼
𝑛
+𝑐
𝑛
,
𝑥
𝑖
= 𝛼
𝑖+1
𝑥
𝑖+1
+ 𝛽
𝑖+1
, 𝑖 = 𝑛 − 1, … ,0
(3) 
Для выполнения левой прогонки расчётные формулы строятся аналогично. 
Прямой ход: 
𝜉
𝑛
=
−𝑎
𝑛
𝑐
𝑛
,
𝜂
𝑛
=
𝑓
𝑛
𝑐
𝑛
,
𝜉
𝑖
=
−𝑎
𝑖
𝑏
𝑖
−𝑐
𝑖
𝜉
𝑖+1
,
𝜂
𝑖
=
𝑓
𝑖
−𝑐
𝑖
𝜂
𝑖+1
𝑏
𝑖
−𝑐
𝑖
𝜉
𝑖+1
, 𝑖 = 𝑛 − 1, … ,1
(4) 
Обратный ход: 
𝑥
0
=
𝑓
0
−𝑐
0
𝜂
1
𝑏
0
−𝑐
1
𝜉
1
,
𝑥
𝑖+1
= 𝜉
𝑖+1
𝑥
𝑖
+ 𝜂
𝑖+1
, 𝑖 = 0, … , 𝑛 − 1
(5) 
Алгоритм встречной прогонки подразумевает независимое применение обоих методов, что позволяет 
одновременно использовать два параллельных потока, реализующих эти методы . Первый из потоков, реализуя метод 
правой прогонки для уравнений с номерами 
1 ≤ 𝑖 ≤ 𝑝
, 
𝑝 = [
𝑛
2
] , 
вычисляет коэффициенты
𝛼
𝑖
, 𝛽
𝑖
по формулам (1) и (2). 
Вычисление прогоночных коэффициентов (4) метода левой прогонки 
𝜉
𝑖
, 𝜂
𝑖
для уравнений с номерами 
𝑝 ≤ 𝑖 ≤ 𝑛
выполняется во втором потоке.
Сопряжение решений обоих потоков в виде (3) и (5) происходит при