361 lines
11 KiB
Typst
361 lines
11 KiB
Typst
#import "@local/nure:0.1.0": *
|
||
|
||
#show: pz-lb.with(..yaml("doc.yaml"), worknumber: 1, title: "Розробка багатопоточних паралельних додатків")
|
||
|
||
|
||
== Мета роботи
|
||
#v(-spacing)
|
||
Вивчити способи організації паралельних багатопоточних додатків на
|
||
прикладі розробки програмного засобу обробки зображення, накладання фільтру,
|
||
тощо.
|
||
|
||
== Хід роботи
|
||
#v(-spacing)
|
||
|
||
Для виконання роботи було обрано тему "Шум Перліна". Шум Перліна -- це алгоритм
|
||
генерації процедурного шуму, розроблений Кеном Перліном, який
|
||
створює природно виглядаючі випадкові текстури та рельєфи. На відміну від
|
||
звичайного випадкового шуму, шум Перліна генерує плавні, безперервні градієнти
|
||
шляхом інтерполяції між випадковими векторами градієнтів на регулярній сітці,
|
||
що дає органічний вигляд хмар, ландшафтів, мармуру та інших природних візерунків.
|
||
|
||
Нижче наведено формулу розрахунку часу виконання алгоритму у ідеальному випадку ($E_p = 1$).
|
||
Такий випадок, звісно, дуже малоймовірний у реальному житті, але ми використаємо цю формулу для подальших теоретичних розрахунків.
|
||
$ T_p = T_1/p $
|
||
|
||
Використаємо стандартну формулу розрахунку прискорення, підставивши значення часу виконання на декількох процесорах з минулого рівняння.
|
||
$ S_p = T_1/T_p = T_1/(T_1/p) = p $
|
||
|
||
Для конкретних розрахунків візьмемо час виконання на одному
|
||
потоці з реальної роботи програми з шумом
|
||
розміру 8129 на 8129 пікселів (було взято середнє значення з 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: [Теоретичні результати розрахунків],
|
||
)
|
||
|
||
Під час виконання програми, були отримані наступні значення:
|
||
|
||
#let practical = (
|
||
decimal("6.48301"),
|
||
decimal("3.25753"),
|
||
decimal("1.66985"),
|
||
decimal("1.34714"),
|
||
decimal("1.06098"),
|
||
decimal("1.18834"),
|
||
decimal("1.15044"),
|
||
decimal("1.12474"),
|
||
decimal("1.09344"),
|
||
)
|
||
|
||
#figure(table(
|
||
columns: 4,
|
||
table.header([$p$], [$T_p$ (сер. за 10 запусків)], [$S_p$ (разів)], [$E_p$]),
|
||
..(1, ..range(2, 16 + 1, step: 2))
|
||
.zip(practical)
|
||
.map(v => {
|
||
let (p, prac) = v
|
||
let speedup = t1 / prac
|
||
let effcy = speedup / p
|
||
(
|
||
[$#p$],
|
||
[$#prac$],
|
||
[$#(calc.round(speedup, digits: 5))$],
|
||
[$#(calc.round(effcy, digits: 5)) approx #(calc.round(effcy * 100, digits: 2))%$],
|
||
)
|
||
})
|
||
.flatten(),
|
||
))
|
||
|
||
Приклад повідомлень про виконані обчислення можна побачити на @calc[рис.].
|
||
#figure(
|
||
image("./calculations.png", width: 40%),
|
||
caption: [Приклад програмного виводу],
|
||
) <calc>
|
||
|
||
Як можна помітити, час запису до файлу завжди є пропорційно залежним від розміру файлу
|
||
та незалежним від кількості потоків, бо запис виконується в однопоточному режимі.
|
||
|
||
Також, було зображенно порівняння замірів на графіку (@plot[рис.]). Можна побачити, що
|
||
після того, як значення $p$ досягає чотирьох одиниць, дані практичного і теоретичного
|
||
розрахунків розходяться. Скоріш за все, це пов'язано з тим, що комп'ютер, на якому було виконану
|
||
лабораторну роботу має лише чотири фізичних ядра.
|
||
Іншими словами, він може виконувати лише чотири завдання справді паралельно.
|
||
Якщо кількість використаних потоків збільшується,
|
||
відбувається розділення ресурсів одного фізичного ядра
|
||
(наприклад, кеш-пам'яті першого та другого рівня, або просто розділення по часу)
|
||
для декількох користувачів (потоків).
|
||
|
||
#figure(
|
||
image("./plot.png"),
|
||
caption: [Порівняння теоретичного та практичного часу виконання],
|
||
) <plot>
|
||
|
||
Приклад шуму, згенерованого програмою наведено на @noise[рис.].
|
||
|
||
#figure(
|
||
image("./noise.png", width: 50%),
|
||
caption: [Приклад згенерованого шуму перліна],
|
||
) <noise>
|
||
|
||
/* 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)
|
||
Було проведено роботу з способами організації паралельних
|
||
багатопоточних додатків на прикладі розробки програмного засобу,
|
||
що генерує статичний шум Перліна. Було проведено бенчмаркінг
|
||
програмного засобу на декількох різних конфігураціях та порівняно
|
||
резульати теоретичних розрахунків з отриманими на практиці значеннями.
|