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

#show: pz-lb.with(..yaml("doc.yaml"), worknumber: 1, title: "Розробка багатопоточних паралельних додатків")


== Мета роботи
#v(-spacing)
Вивчити способи організації паралельних багатопоточних додатків на
прикладі розробки програмного засобу обробки зображення, накладання фільтру,
тощо.

== Хід роботи
#v(-spacing)
/* TODO: work
    3. Розрахувати прискорення та ефективність для розробленого паралельного алгоритму.
    // 4. Написати програмний засіб обробки зображення, якій накладає фільтр згідно з отриманим завданням.
    // 5. Зібрати статистику витрат часу на обробку зображенні в одному та декількох потоках (1, 2, 4, 6, 8, 10, 12, 14, 16).
    6. Побудувати графік залежності часу обробки зображення та створених потоків.
    7. Порівняти отримані практичні результати з теоретичними.
*/

Для виконання роботи було обрано тему "Шум Перліна". Шум Перліна -- це алгоритм
генерації процедурного шуму, розроблений Кеном Перліномб який
створює природно виглядаючі випадкові текстури та рельєфи. На відміну від
звичайного випадкового шуму, шум Перліна генерує плавні, безперервні градієнти
шляхом інтерполяції між випадковими векторами градієнтів на регулярній сітці,
що дає органічний вигляд хмар, ландшафтів, мармуру та інших природних візерунків.

Нижче наведено формулу розрахунку часу виконання алгоритму у ідеальному випадку ($E_p = 1$).
Такий випадок, звісно, дуже малоймовірний у реальному житті, але ми використаємо цю формулу для подальших теоретичних розрахунків.
$ T_p = T_1/p $

Використаємо стандартну формулу розрахунку прискорення, підставивши значення часу виконання на декількох процесорах з минулого рівняння.
$ S_p = T_1/T_p = T_1/(T_1/p) = p $

Для конкретних розрахунків візьмемо час виконання на одному потоці з реальної роботи програми (середнє значення з 10 запусків):
$ T_1 = 6.48301 (sec) $

#let t1 = decimal("6.48301")
#figure(
  table(
    columns: 3,
    table.header([$p$], [$S_p$ (разів)], [$T_p$ (теор.)]),
    ..(1, ..range(2, 16 + 1, step: 2))
      .map(i => {
        ([$#i$], [$#(i)$], [$#(calc.round(t1 / decimal(i), digits: 5))$])
      })
      .flatten(),
  ),
  caption: [Теоретичні результати розрахунків],
)

Під час виконання програми, були отримані наступні значення:

#figure(
  table(
    columns: 2,
    table.header([$p$], [$T_p$]),
    [1], [6.48301],
    [2], [3.25753],
    [4], [1.66985],
    [6], [1.34714],
    [8], [1.06098],
    [10], [1.18834],
    [12], [1.15044],
    [14], [1.12474],
    [14], [1.09344],
  ),
)

Також, було зображенно значення на графіку (@plot[рис.]). Можна побачити, що
після того, як значення $p$ досягає чотирьох одиниць, дані практичного і теоретичного
розрахунків розходяться. Скоріш за все, це пов'язано з тим, що цей комп'ютер має
лише чотири фізичних ядра. Тобто, може виконувати лише чотири завдання справді паралельно.
Далі використовуються "потоки",
що означає розділення ресурсів одного фізичного ядра
(наприклад, кеш-пам'яті першого та другого рівня, або просто розділення по часу)
для декількох користувачів.

#figure(
  image("./plot.png"),
  caption: [Порівняння теоретичного та практичного часу виконання],
) <plot>

/* 1 THREAD{{{
performing warmup run #1, stay tuned!
warmup calculation time: 6.498818s.
performing warmup run #2, stay tuned!
warmup calculation time: 6.481534s.
performing warmup run #3, stay tuned!
warmup calculation time: 6.480006s.
performing 10 runs!
6.485858
6.481472
6.489044
6.478120
6.478225
6.477820
6.497720
6.480843
6.476514
6.484445


6.48301
write to file time (single-threaded): 5.777791s.
*/
// }}}

/* 2 THREADS{{{
rows per thread: 4096
performing warmup run #1, stay tuned!
warmup calculation time: 3.256548s.
performing warmup run #2, stay tuned!
warmup calculation time: 3.255972s.
performing warmup run #3, stay tuned!
warmup calculation time: 3.244320s.
performing 10 runs!
3.256898
3.254369
3.273234
3.253884
3.253703
3.257059
3.253436
3.254229
3.255219
3.263258


3.25753
write to file time (single-threaded): 5.813933s.
*/// }}}

/* 4 THREADS{{{
rows per thread: 2048
performing warmup run #1, stay tuned!
warmup calculation time: 1.656087s.
performing warmup run #2, stay tuned!
warmup calculation time: 1.656606s.
performing warmup run #3, stay tuned!
warmup calculation time: 1.651284s.
performing 10 runs!
1.653661
1.680330
1.698069
1.663428
1.721254
1.651755
1.644072
1.671594
1.659138
1.655216


1.66985
write to file time (single-threaded): 5.817255s.
*/// }}}

/* 6 THREADS{{{
rows per thread: 1365
performing warmup run #1, stay tuned!
warmup calculation time: 1.338387s.
performing warmup run #2, stay tuned!
warmup calculation time: 1.351296s.
performing warmup run #3, stay tuned!
warmup calculation time: 1.348886s.
performing 10 runs!
1.349408
1.344556
1.354476
1.370135
1.340126
1.338552
1.343501
1.347066
1.341447
1.342093


1.34714
write to file time (single-threaded): 5.843012s.
*/// }}}

/* 8 THREADS{{{
rows per thread: 1024
performing warmup run #1, stay tuned!
warmup calculation time: 1.056011s.
performing warmup run #2, stay tuned!
warmup calculation time: 1.058755s.
performing warmup run #3, stay tuned!
warmup calculation time: 1.062063s.
performing 10 runs!
1.055696
1.054573
1.062060
1.061573
1.060853
1.071647
1.060886
1.060964
1.061237
1.060295


1.06098
write to file time (single-threaded): 5.849602s.
*/// }}}

/* 10 THREADS{{{
rows per thread: 819
performing warmup run #1, stay tuned!
warmup calculation time: 1.184474s.
performing warmup run #2, stay tuned!
warmup calculation time: 1.110894s.
performing warmup run #3, stay tuned!
warmup calculation time: 1.236176s.
performing 10 runs!
1.240800
1.190502
1.149874
1.145224
1.166882
1.191344
1.197383
1.175277
1.177462
1.248642


1.18834
write to file time (single-threaded): 5.804186s.
*/// }}}

/* 12 THREADS{{{
rows per thread: 682
performing warmup run #1, stay tuned!
warmup calculation time: 1.157902s.
performing warmup run #2, stay tuned!
warmup calculation time: 1.151911s.
performing warmup run #3, stay tuned!
warmup calculation time: 1.146184s.
performing 10 runs!
1.145244
1.128753
1.141891
1.172025
1.143231
1.139481
1.152526
1.168733
1.172086
1.140409


1.15044
write to file time (single-threaded): 5.844610s.
*/// }}}

/* 14 THREADS{{{
rows per thread: 585
performing warmup run #1, stay tuned!
warmup calculation time: 1.101157s.
performing warmup run #2, stay tuned!
warmup calculation time: 1.131439s.
performing warmup run #3, stay tuned!
warmup calculation time: 1.124504s.
performing 10 runs!
1.135715
1.116137
1.154087
1.127029
1.116847
1.145039
1.126409
1.108209
1.118908
1.098983


1.12474
write to file time (single-threaded): 5.839399s.
*/// }}}

/* 16 THREADS{{{
rows per thread: 512
performing warmup run #1, stay tuned!
warmup calculation time: 1.066169s.
performing warmup run #2, stay tuned!
warmup calculation time: 1.087413s.
performing warmup run #3, stay tuned!
warmup calculation time: 1.095996s.
performing 10 runs!
1.080556
1.079299
1.097067
1.088530
1.078512
1.094765
1.112028
1.090462
1.104614
1.108524


1.09344
write to file time (single-threaded): 5.833199s.
*/// }}}

/*
NOTE: cpu info:
Architecture:                x86_64
  CPU op-mode(s):            32-bit, 64-bit
  Address sizes:             43 bits physical, 48 bits virtual
  Byte Order:                Little Endian
CPU(s):                      8
  On-line CPU(s) list:       0-7
Vendor ID:                   AuthenticAMD
  Model name:                AMD Ryzen 5 3400G with Radeon Vega Graphics
    CPU family:              23
    Model:                   24
    Thread(s) per core:      2
    Core(s) per socket:      4
    Socket(s):               1
*/

== Висновки
#v(-spacing)
// TODO: conclusions