Date post: | 07-Aug-2015 |
Category: |
Science |
Upload: | david-barina |
View: | 43 times |
Download: | 5 times |
Akcelerace DWT pomocí SIMD
David Bařina
Fakulta informačních technologií VUT v Brně
30. dubna 2013
David Bařina (FIT VUT v Brně) Akcelerace DWT pomocí SIMD 30. dubna 2013 1 / 18
Úvod
co: akcelerace / vektorizace / paralelizacečeho: diskrétní vlnková transformace (DWT)kde: PC (x86-64) a ASVP (EdkDSP)
David Bařina (FIT VUT v Brně) Akcelerace DWT pomocí SIMD 30. dubna 2013 2 / 18
Vlnka CDF 9/7
−3 −2 −1 0 1 2 3−0.5
0
0.5
1
1.5
φ
−4 −2 0 2 4−0.5
0
0.5
1
1.5
φ̃
−3 −2 −1 0 1 2 3 4
−0.4
−0.2
0
0.2
0.4
0.6
0.8ψ
−3 −2 −1 0 1 2 3 4
−0.5
0
0.5
1
ψ̃
David Bařina (FIT VUT v Brně) Akcelerace DWT pomocí SIMD 30. dubna 2013 3 / 18
DWT schématem lifting
di ← di − α(si + si+1)
si ← si + β(di−1 + di )
di ← di − γ(si + si+1)
si ← si + δ(di−1 + di )
di ← ζ−1di
si ← ζsi
David Bařina (FIT VUT v Brně) Akcelerace DWT pomocí SIMD 30. dubna 2013 4 / 18
Dataflow DWT
α
β
γ
δ
David Bařina (FIT VUT v Brně) Akcelerace DWT pomocí SIMD 30. dubna 2013 5 / 18
Dataflow DWT: multi-loop (ML)
α
β
γ
δ
David Bařina (FIT VUT v Brně) Akcelerace DWT pomocí SIMD 30. dubna 2013 6 / 18
Dataflow DWT: double-loop (DL)
α
β
γ
δ
David Bařina (FIT VUT v Brně) Akcelerace DWT pomocí SIMD 30. dubna 2013 7 / 18
Dataflow DWT: shifted double-loop (SDL)
α
β
γ
δ
David Bařina (FIT VUT v Brně) Akcelerace DWT pomocí SIMD 30. dubna 2013 8 / 18
Srovnání 1D na PC (jen výpočet)
1.0n
10.0n
100.0n
1.0u
10.0 100.0 1.0k 10.0k 100.0k 1.0M 10.0M 100.0M
seconds/sample
samples
ML (0)DL (4)SDL (9)
David Bařina (FIT VUT v Brně) Akcelerace DWT pomocí SIMD 30. dubna 2013 9 / 18
Srovnání 1D na ASVP (jen výpočet)
100.0n
1.0u
10.0u
100.0u
10.0 100.0 1.0k 10.0k 100.0k 1.0M
seconds/sample
samples
ML/CPU (0)ML/BCE (1)
DL (4)SDL (5)
David Bařina (FIT VUT v Brně) Akcelerace DWT pomocí SIMD 30. dubna 2013 10 / 18
2D DWT
David Bařina (FIT VUT v Brně) Akcelerace DWT pomocí SIMD 30. dubna 2013 11 / 18
2D DWT
David Bařina (FIT VUT v Brně) Akcelerace DWT pomocí SIMD 30. dubna 2013 12 / 18
2D DWT
David Bařina (FIT VUT v Brně) Akcelerace DWT pomocí SIMD 30. dubna 2013 13 / 18
L1 data cache
4096 = 1024 × float
Intel Core2 Duo (L1d = 32kB, 8-way, 64 B)
[tag][cache set:6][offset:6]
4-way
[…000][xxxxxx][xxxxxx]
[…001][xxxxxx][xxxxxx]
[…010][xxxxxx][xxxxxx]
[…011][xxxxxx][xxxxxx]
[…100][xxxxxx][xxxxxx]
[…101][xxxxxx][xxxxxx]
David Bařina (FIT VUT v Brně) Akcelerace DWT pomocí SIMD 30. dubna 2013 14 / 18
Srovnání 2D na PC (cache)
1.0n
10.0n
100.0n
1.0k 10.0k 100.0k 1.0M 10.0M 100.0M
seconds/pixel
pixels
non-optimal stride (0)prime stride (1)
prime-set stride (2)
David Bařina (FIT VUT v Brně) Akcelerace DWT pomocí SIMD 30. dubna 2013 15 / 18
Srovnání 2D na PC (implementace)
1.0n
10.0n
100.0n
1.0k 10.0k 100.0k 1.0M 10.0M 100.0M
seconds/pixel
pixels
ML (0)SDL (9)DL4 (11)ML4 (12)
David Bařina (FIT VUT v Brně) Akcelerace DWT pomocí SIMD 30. dubna 2013 16 / 18
Srovnání 2D na ASVP
100.0n
1.0u
10.0u
1.0k 10.0k 100.0k 1.0M
seconds/pixel
pixels
ML/CPU (0)ML/BCEx1 (1)ML/BCEx2 (1)
DL (4)SDL (5)
David Bařina (FIT VUT v Brně) Akcelerace DWT pomocí SIMD 30. dubna 2013 17 / 18
Závěr
1D3 řezy dataflow pro operace SIMD (ML, DL, SDL)PC: nejrychlejší SDL s SSE (zrychlení 3,1×)ASVP: nejrychlejší ML s BCE (zrychlení 3,1×)
2DPC: vliv cache (zrychlení 3,6× při 9Mpx)PC: lepší SIMD se 4 řádky najednouASVP: ML s BCE (zrychlení 3,6× při 1Mpx)
David Bařina (FIT VUT v Brně) Akcelerace DWT pomocí SIMD 30. dubna 2013 18 / 18