327 lines
9.1 KiB
Typst
327 lines
9.1 KiB
Typst
#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", width: 80%),
|
||
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
|