#import "@local/nure:0.1.0": *

#show: pz-lb.with(..yaml("doc.yaml"), worknumber: 3, title: "Розв'язування систем лінійних рівнянь")

#v(-spacing)

== Мета роботи
#v(-spacing)

Реалізувати розв’язання системи лінійних алгебраїчних рівнянь методом
Гауса з імітацією паралельних обчислень та розрахувати показники ефективності.

== Хід роботи
#v(-spacing)
Запишемо вихідну систему. Ми використаємо алгоритм Гауса для знаходження її рівнянь.
Почнемо з прямого ходу.
$
  mat(
    1, 3, 2, 1;
    2, 7, 5, 18;
    1, 4, 6, 26;
    augment: #(-1)
  )
$

Маємо $a_11 = 1$, тож можемо не ділити перший рядок, а одразу віднімати його
(помножений на 2 та 1, відповідно) від другого та третього. У результаті
отримуємо:
$
  mat(
    1, 3, 2, 1;
    0, 1, 1, 16;
    0, 1, 4, 25;
    augment: #(-1)
  )
$

Помноживши його на 1, віднімаємо другий рядок від третього. Результат:
$
  mat(
    1, 3, 2, 1;
    0, 1, 1, 16;
    0, 0, 3, 9;
    augment: #(-1)
  )
$

Для зворотнього ходу застосуємо формулу $x_i = (b_i - sum_(j=i+1)^n a_(i j) dot x_j)/a_(i i)$
$ x_3 = 9 / 3 = 3 $
$ x_2 = (16 - 3) / 1 = 13 $
$ x_1 = (1 - (39 + 6)) / 1 = -44 $

Для розпаралелювання алгоритму використано схему стрічкового циклічного
розділення даних. Це дозволяє рівномірно
розподілити навантаження, оскільки кількість активних рядків зменшується з
кожною ітерацією.

Відповідно до методичних вказівок, для ефективної реалізації операцій розсилки
даних обрана топологія мережі "Гіперкуб".
Це зумовлено тим, що основною комунікаційною операцією є
передача ведучого рядка від одного процесора всім іншим, що в такій топології
виконується за логарифмічний час $O(log_2 p)$.

Прямий хід складається з $n-1$ ітерацій. Нехай $k$ — номер поточної ітерації ($0 <= k < n-1$).

+ Вибір ведучого елемента: процесор, що містить рядок $k$, обирає головний елемент $a_(k k)$;
+ комунікація (Broadcast): процесор-власник розсилає рядок $k$ та елемент $b_k$ усім іншим процесорам. Трудомісткість цієї операції оцінюється як: $(n-1) log_2 p dot (alpha + w dot n / beta)$;
+ Обчислення: кожен процесор модифікує свої локальні рядки $i$ ($i > k$):
  $ l_(i k) = a_(i k) / a_(k k) $
  $ a_(i j) = a_(i j) - l_(i k) dot a_(k j) $
  $ b_i = b_i - l_(i k) dot b_k $

Алгоритм розпаралелювання зворотнього ходу виконується від $i = n-1$ до $0$.

1. Обчислення кореня: Процесор-власник рядка $i$ знаходить $x_i$:
  $ x_i = (b_i - sum_(j=i+1)^(n-1) a_(i j) dot x_j) / a_(i i) $
2. Комунікація: Знайдене значення $x_i$ розсилається всім процесорам.
  Трудомісткість: $(n-1) log_2 p (alpha + w/beta)$.
3. Оновлення: Процесори підставляють відоме $x_i$ у свої рівняння для рядків $k < i$.

Оцінка ефективності базується на припущенні про використання топології
"Гіперкуб", що дозволяє виконувати операції розсилки даних
(Broadcast) та редукції за логарифмічний час $O(log_2 p)$.

1. послідовний алгоритм ($T_1$):
  трудомісткість послідовного методу Гаусса складається з суми операцій прямого ходу ($approx 2/3 n^3$) та зворотного ходу ($approx n^2$, враховуючи лише ділення та множення). Згідно з методичними вказівками, загальна складність становить:
  $ T_1 approx 2/3 n^3 + 2 n^2 $

2. паралельний алгоритм ($T_p$):
  загальний час виконання складається з обчислювальної частини та комунікаційних витрат.
  Обчислювальна складова: При використанні циклічного розподілу рядків навантаження балансується рівномірно, тому час обчислень зменшується пропорційно кількості процесорів:
  $ T_("comp") approx 1/p dot (2/3 n^3) dot tau $
  де $tau$ — час виконання однієї базової арифметичної операції.

  Комунікаційна складова ($T_("comm")$): Включає три основні етапи взаємодії на кожній ітерації (пошук ведучого елемента, розсилка рядка, зворотна підстановка). Для $n$ ітерацій на топології гіперкуба сумарні витрати оцінюються формулою:
  $ T_("comm") approx (n-1) dot log_2 p dot (3 alpha + (w(n+2))/beta) $
  де $alpha$ — латентність мережі, $beta$ — пропускна здатність каналу, $w$ — розмір елемента даних у байтах.

  Сумарна трудомісткість ($T_p$):
  $ T_p = T_("comp") + T_("comm") approx (2 n^3)/(3 p) tau + n log_2 p (3 alpha + (w n)/beta) $

3. показники ефективності:
  на основі наведених вище оцінок, теоретичне прискорення ($S_p$) та ефективність ($E_p$) розраховуються як:
  $ S_p = T_1 / T_p = (2/3 n^3 + 2 n^2)/((2 n^3)/(3 p) tau + n log_2 p (3 alpha + (w n)/beta)) $
  $ E_p = S_p / p = (2/3 n^3 + 2 n^2)/((2 n^3)/(3 p) tau + n log_2 p (3 alpha + (w n)/beta))/p $

  При $n >> p$ (коли розмірність задачі значно перевищує кількість процесорів), вплив комунікаційної складової зменшується, і $E_p$ наближається до 1. Однак при фіксованому $n$ збільшення $p$ призводить до зростання частки $T_("comm")$ у загальному часі, що знижує ефективність.

== Висновки

Було реалізувано розв’язання системи лінійних алгебраїчних рівнянь методом
Гауса з імітацією паралельних обчислень та розрахувано показники ефективності.
Для розв'язання СЛАР методом Гаусса на $p$ процесорах використано
одновимірну декомпозицію даних по рядках.
Оптимальною топологією було визначено гіперкуб,
оскільки алгоритм потребує постійної
розсилки даних ("один-до-всіх") на кожній ітерації.