![並列化できる処理
int A[5000], B[5000], C[5000];
for(int i=0; i<5000; i++){
C[i] = A[i] + B[i];
}
12](https://image.slidesharecdn.com/slide-190829015758/85/-12-320.jpg)
![並列化できる処理
int A[5000], B[5000], C[5000];
for(int i=0; i<5000; i++){
C[i] = A[i] + B[i];
}
13
GPUコア
……
C[0]=A[0]+B[0]
GPUコア
C[1]=A[1]+B[1]
GPUコア
C[2]=A[2]+B[2]
GPUコア
C[3]=A[3]+B[3]](https://image.slidesharecdn.com/slide-190829015758/85/-13-320.jpg)
![並列化できない処理
int A[5002] = {1,1};
for(int i=0; i<5000; i++){
A[i+2] = A[i] + A[i+1];
}
14](https://image.slidesharecdn.com/slide-190829015758/85/-14-320.jpg)
![並列化できない処理
int A[5002] = {1,1};
for(int i=0; i<5000; i++){
A[i+2] = A[i] + A[i+1];
}
逐次処理の必要あり → 並列化難しい
15](https://image.slidesharecdn.com/slide-190829015758/85/-15-320.jpg)
![ソースコード (抜粋)
#define BS 1000
__global__ void solve(int W, int *w, long long *v, long long *dp, int i){
int j = blockIdx.x*blockDim.x + threadIdx.x;
if(j >= W) return;
dp[(i&1)*(W+1)+j] = dmax(dp[((i-1)&1)*(W+1)+j],
-(j>=w[i]) & (dp[dmax(0,((i-1)&1)*(W+1)+j-w[i])]+v[i]));
}
int main(){
(入力の受け取り，メモリのコピーなど)
solve0<<<(W +BS-1)/BS,BS>>>(W, dw, dv, dp, 0);
for(int i=1; i<N; i++){
cudaDeviceSynchronize();
solve<<<(W +BS-1)/BS,BS>>>(W, dw, dv, dp, i);
}
(答えの出力など)
}
41
CUDAの解説は
次以降の人の発表を聞いてね！](https://image.slidesharecdn.com/slide-190829015758/85/-41-320.jpg)
![計算速度の比較
CPU
N
103
104
105
W
103
3.579 20.32 187.5
104
19.00 175.6 1746
105
178.7 1720 17064
GPU
N
103
104
105
W
103
219.1 319.4 1323
104
222.9 322.9 1299
105
237.5 326.1 1336
42
各20種のテストケースで計測した平均値 [単位:ms]](https://image.slidesharecdn.com/slide-190829015758/85/-42-320.jpg)
![計算速度の比較 (N=105)
47
0
5000
10000
15000
20000
1e3 1e4 1e5
W
GPU
CPU
[単位：ms]](https://image.slidesharecdn.com/slide-190829015758/85/-47-320.jpg)
![計算速度の比較 (N=105)
48
0
5000
10000
15000
20000
1e3 1e4 1e5
W
GPU
CPU
[単位：ms]](https://image.slidesharecdn.com/slide-190829015758/85/-48-320.jpg)
![計算速度の比較 (N=105)
49
0
5000
10000
15000
20000
1e3 1e4 1e5
W
GPU
CPU
[単位：ms]](https://image.slidesharecdn.com/slide-190829015758/85/-49-320.jpg)
![計算速度の比較 (N=105)
50
0
5000
10000
15000
20000
1e3 1e4 1e5
W
GPU
CPU
[単位：ms]
GPUすごい！](https://image.slidesharecdn.com/slide-190829015758/85/-50-320.jpg)
![ソースコード (抜粋)
__global__ void solve(int *d, int *state, int *num, int *dp, int V, int i){
int j = blockIdx.x*blockDim.x + threadIdx.x;
if(j >= num[i]*V) return;
int k = j % V; j /= V;
if(!((state[j*V+i]>>k)&1)) return;
for(int l=0; l<V; l++)
dp[state[j*V+i]*V+k] = dmin(dp[state[j*V+i]*V+k], dp[(state[j*V+i]^(1<<k))*V+l]+d[l*V+k]);
}
int main(){
(入力の受け取りなど)
for(int i=0; i<V+1; i++) num[i] = 0
for(int i=0; i<(1<<V); i++){
int c = 0;
for(int j=1; j<(1<<V); j<<=1)
if(i&j) c++;
state[num[c]*V+c] = i;
num[c]++;
}
(メモリのコピーなど)
for(int i=0; i<=V; i++){
solve<<<(num[i]*V +BS-1)/BS,BS>>>(dd, dstate, dnum, dp, V, i);
cudaDeviceSynchronize();
}
(答えの出力など)
}
60
CUDAの解説は
次以降の人の発表を聞いてね！](https://image.slidesharecdn.com/slide-190829015758/85/-60-320.jpg)
![計算速度の比較
CPU
V time V time V time
2 1.9 11 2.15 20 690.2
3 1.75 12 2.75 21 1563.6
4 1.85 13 4.05 22 3498.8
5 1.7 14 6.7 23 7826.6
6 1.55 15 13.4 24 17303
7 1.75 16 27.35 25 37929
8 1.85 17 58.4 26 81735
9 1.8 18 131
10 2.1 19 297.35
GPU
V time V time V time
2 150 11 151.5 20 221.4
3 152 12 151.3 21 297.5
4 150.35 13 153.3 22 405.05
5 151.65 14 153.2 23 691.55
6 150.2 15 155.5 24 1296.6
7 150.05 16 154.3 25 2597.6
8 152.2 17 158.55 26 5356.5
9 151.6 18 166.2
10 151.6 19 183.5
61
各20種のテストケースで計測した平均値 [単位:ms]](https://image.slidesharecdn.com/slide-190829015758/85/-61-320.jpg)
![計算速度の比較 (V≦22)
62
0
1000
2000
3000
4000
2 4 6 8 10 12 14 16 18 20 22
CPU
GPU
[単位：ms]](https://image.slidesharecdn.com/slide-190829015758/85/-62-320.jpg)
![計算速度の比較 (V≦22)
63
0
1000
2000
3000
4000
2 4 6 8 10 12 14 16 18 20 22
CPU
GPU
GPUは起動に
時間がかかる
[単位：ms]](https://image.slidesharecdn.com/slide-190829015758/85/-63-320.jpg)
![計算速度の比較 (V≦26)
64
0
10000
20000
30000
40000
50000
60000
70000
80000
90000
2 4 6 8 10 12 14 16 18 20 22 24 26
CPU
GPU
[単位：ms]](https://image.slidesharecdn.com/slide-190829015758/85/-64-320.jpg)
![計算速度の比較 (V≦26)
65
0
10000
20000
30000
40000
50000
60000
70000
80000
90000
2 4 6 8 10 12 14 16 18 20 22 24 26
CPU
GPU
CPU82秒
GPU5秒
約16倍高速！
[単位：ms]](https://image.slidesharecdn.com/slide-190829015758/85/-65-320.jpg)
![計算速度の比較 (V≦26)
66
0
10000
20000
30000
40000
50000
60000
70000
80000
90000
2 4 6 8 10 12 14 16 18 20 22 24 26
[単位：ms]
GPU
CPU
CPU82秒
GPU5秒
約16倍高速！
https://umaibou.jp/product/](https://image.slidesharecdn.com/slide-190829015758/85/-66-320.jpg)
![計算速度の比較 (V≦26)
67
0
10000
20000
30000
40000
50000
60000
70000
80000
90000
2 4 6 8 10 12 14 16 18 20 22 24 26
[単位：ms]
GPU
CPU
CPU82秒
GPU5秒
約16倍高速！
https://umaibou.jp/product/](https://image.slidesharecdn.com/slide-190829015758/85/-67-320.jpg)
More Related Content
What's hot (20)
Similar to 动的计画法の并列化 (20)
动的计画法の并列化
- 2. 自己紹介 ? きたむー (@Pro_ktmr) ? 大阪府立 大手前高校 3年 ? 『CUDA C プロフェッショナル プログラミング』 班 ? ほとんど読んでない??? ? 去年の夏季セミにもいた 2
- 3. 1年間の成長 夏季セミナー2018 ? AtCoder 緑 ? JOI 予選落ち ? 大規模開発経験なし ? 研究発表で校内1位 夏季セミナー2019 ? AtCoder 黄 ? JOI春6位 APIO銀メダル ? PCKモバ ベストアイデア賞 ? SSHのポスター賞 3
- 4. 1年間の成長 夏季セミナー2018 ? AtCoder 緑 ? JOI 予選落ち ? 大規模開発経験なし ? 研究発表で校内1位 夏季セミナー2019 ? AtCoder 黄 ? APIO 銀メダル ? PCKモバ ベストアイデア賞 ? 研究発表で全国レベルの賞 4 夏季セミでトップ層と 交流できたから
- 5. ストーリー 第1話 GPU ? CPUの前に突如現れたGPUとは？ 第2話 条件分岐 ? minとmaxが危ない！ 第3話 ナップサック問題 ? ピクニックに行こう 第4話 巡回セールスマン問題 ? bitDPと戦え！ 5
- 12. 並列化できる処理 int A[5000], B[5000], C[5000]; for(int i=0; i<5000; i++){ C[i] = A[i] + B[i]; } 12
- 13. 並列化できる処理 int A[5000], B[5000], C[5000]; for(int i=0; i<5000; i++){ C[i] = A[i] + B[i]; } 13 GPUコア …… C[0]=A[0]+B[0] GPUコア C[1]=A[1]+B[1] GPUコア C[2]=A[2]+B[2] GPUコア C[3]=A[3]+B[3]
- 14. 並列化できない処理 int A[5002] = {1,1}; for(int i=0; i<5000; i++){ A[i+2] = A[i] + A[i+1]; } 14
- 15. 並列化できない処理 int A[5002] = {1,1}; for(int i=0; i<5000; i++){ A[i+2] = A[i] + A[i+1]; } 逐次処理の必要あり → 並列化難しい 15
- 16. 動的計画法とは (Wikipedia) 下記2条件を満たすアルゴリズムの総称である． ? 帰納的な関係の利用：より小さな問題例の解や計算 結果を帰納的な関係を利用してより大きな問題例を 解くのに使用する． ? 計算結果の記録：小さな問題例，計算結果から記録 し，同じ計算を何度も行うことを避ける．帰納的な関 係での参照を効率よく行うために，計算結果は整数， 文字やその組みなどを見出しにして管理される． 16
- 17. 動的計画法とは (Wikipedia) 下記2条件を満たすアルゴリズムの総称である． ? 帰納的な関係の利用：より小さな問題例の解や計算 結果を帰納的な関係を利用してより大きな問題例を 解くのに使用する． ? 計算結果の記録：小さな問題例，計算結果から記録 し，同じ計算を何度も行うことを避ける．帰納的な関 係での参照を効率よく行うために，計算結果は整数， 文字やその組みなどを見出しにして管理される． 17
- 20. ストーリー 第1話 GPU ? CPUの前に突如現れたGPUとは？ 第2話 条件分岐 ? minとmaxが危ない！ 第3話 ナップサック問題 ? ピクニックに行こう 第4話 巡回セールスマン問題 ? bitDPと戦え！ 20
- 22. 22 GPUコア GPUコア 10 < 5 かも いや 10 = 5
- 25. ところで動的計画法 ナップサック問題の漸化式 ? ?, ? = max ? ? ? 1, ? , ? ? ? 1, ? ? ?? + ?? 25
- 26. ところで動的計画法 ナップサック問題の漸化式 ? ?, ? = ??? ? ? ? 1, ? , ? ? ? 1, ? ? ?? + ?? DPの漸化式には max や min が多々存在 26
- 27. ところで動的計画法 ナップサック問題の漸化式 ? ?, ? = ??? ? ? ? 1, ? , ? ? ? 1, ? ? ?? + ?? DPの漸化式には max や min が多々存在 27 maxやminを条件分岐なしで 実装出来たら???
- 28. maxとminをビット演算で実装 int max(int a, int b){ if(a > b) return a; else return b; } int max(int a, int b){ return ((-(a>b)) & a) + ((-(a<=b)) & b); } 28
- 29. maxとminをビット演算で実装 ? ? > ? のとき int max(int a, int b){ return ((-(a>b)) & a) + ((-(a<=b)) & b); } ? ? ≤ ? のとき int max(int a, int b){ return ((-(a>b)) & a) + ((-(a<=b)) & b); } 29
- 30. maxとminをビット演算で実装 ? ? > ? のとき int max(int a, int b){ return ((-1) & a) + ((0) & b); } ? ? ≤ ? のとき int max(int a, int b){ return ((0) & a) + ((-1) & b); } 30
- 31. maxとminをビット演算で実装 ? ? > ? のとき int max(int a, int b){ return ((???1111) & a) + ((???0000) & b); } ? ? ≤ ? のとき int max(int a, int b){ return ((???0000) & a) + ((???1111) & b); } 31 2進数表記
- 32. ストーリー 第1話 GPU ? CPUの前に突如現れたGPUとは？ 第2話 条件分岐 ? minとmaxが危ない！ 第3話 ナップサック問題 ? ピクニックに行こう 第4話 巡回セールスマン問題 ? bitDPと戦え！ 32
- 34. (一応)問題文 価値が ?? 重さが ?? であるような ? 個の品物と，容量 が ? のナップザックがあります．次の条件を満たすよ うに，品物を選んでナップザックに入れます： ? 選んだ品物の価値の合計をできるだけ高くする． ? 選んだ品物の重さの総和は ? を超えない． 価値の合計の最大値を求めてください． (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp) 34
- 35. 並列化したい 漸化式は ? ?, ? = max ? ? ? 1, ? , ? ? ? 1, ? ? ?? + ?? つまり ? ?, ? = max ? ? ? 1, ? , ? ? ? 1, ? + ?? 35
- 36. 並列化したい 漸化式は ? ?, ? = max ? ? ? 1, ? , ? ? ? 1, ? ? ?? + ?? つまり ? ?, ? = max ? ? ? 1, ? , ? ? ? 1, ? + ?? ? ?, ? を求めるのに ? ? ? 1,0 ~? ? ? 1, ? が必要 ? ?, ? を求めるのに ? ?, 0 ~? ?, ? は必要ない 36
- 41. ソースコード (抜粋) #define BS 1000 __global__ void solve(int W, int *w, long long *v, long long *dp, int i){ int j = blockIdx.x*blockDim.x + threadIdx.x; if(j >= W) return; dp[(i&1)*(W+1)+j] = dmax(dp[((i-1)&1)*(W+1)+j], -(j>=w[i]) & (dp[dmax(0,((i-1)&1)*(W+1)+j-w[i])]+v[i])); } int main(){ (入力の受け取り，メモリのコピーなど) solve0<<<(W +BS-1)/BS,BS>>>(W, dw, dv, dp, 0); for(int i=1; i<N; i++){ cudaDeviceSynchronize(); solve<<<(W +BS-1)/BS,BS>>>(W, dw, dv, dp, i); } (答えの出力など) } 41 CUDAの解説は 次以降の人の発表を聞いてね！
- 42. 計算速度の比較 CPU N 103 104 105 W 103 3.579 20.32 187.5 104 19.00 175.6 1746 105 178.7 1720 17064 GPU N 103 104 105 W 103 219.1 319.4 1323 104 222.9 322.9 1299 105 237.5 326.1 1336 42 各20種のテストケースで計測した平均値 [単位:ms]
- 43. 計算速度の比較 43 CPU GPU N 103 104 105 W 103 0.016 0.06 0.142 104 0.085 0.544 1.345 105 0.753 5.275 12.77 GPUはCPUの ? 倍高速
- 44. 計算速度の比較 44 CPU GPU N 103 104 105 W 103 0.016 0.06 0.142 104 0.085 0.544 1.345 105 0.753 5.275 12.77 GPUはCPUの ? 倍高速 12倍高速化
- 45. 計算速度の比較 45 CPU GPU N 103 104 105 W 103 0.016 0.06 0.142 104 0.085 0.544 1.345 105 0.753 5.275 12.77 GPUはCPUの ? 倍高速 12倍高速化
- 46. 計算速度の比較 46 CPU GPU N 103 104 105 W 103 0.016 0.06 0.142 104 0.085 0.544 1.345 105 0.753 5.275 12.77 GPUはCPUの ? 倍高速 12倍高速化
- 47. 計算速度の比較 (N=105) 47 0 5000 10000 15000 20000 1e3 1e4 1e5 W GPU CPU [単位：ms]
- 48. 計算速度の比較 (N=105) 48 0 5000 10000 15000 20000 1e3 1e4 1e5 W GPU CPU [単位：ms]
- 49. 計算速度の比較 (N=105) 49 0 5000 10000 15000 20000 1e3 1e4 1e5 W GPU CPU [単位：ms]
- 50. 計算速度の比較 (N=105) 50 0 5000 10000 15000 20000 1e3 1e4 1e5 W GPU CPU [単位：ms] GPUすごい！
- 51. ストーリー 第1話 GPU ? CPUの前に突如現れたGPUとは？ 第2話 条件分岐 ? minとmaxが危ない！ 第3話 ナップサック問題 ? ピクニックに行こう 第4話 巡回セールスマン問題 ? bitDPと戦え！ 51
- 53. (一応)問題文 重み付き有向グラフ ?(?, ?) について，以下の条件を満 たす最短経路の距離を求めて下さい： ? ある頂点から出発し，出発点へ戻る閉路である． ? 各頂点をちょうど 1 度通る． (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A&lang=jp) 53
- 54. (一応)解法 ? 頂点 0 から巡回を始めるとして一般性を失わない ? 今いる頂点の番号 ? 通り，すでに行ったことのある 頂点の情報 2 ? 通りを持ってbitDP ? 各遷移は次にどの頂点に行くかの ? 通り ? ?(?2 2 ? ) 54
- 55. bitDPを並列化したい もらうDPを考える 例) ?? 010101 を計算するには ?? 0?0101 , ?? 010?01 , ?? 01010? が必要 55
- 56. bitDPを並列化したい もらうDPを考える 例) ?? 010101 を計算するには ?? 0?0101 , ?? 010?01 , ?? 01010? が必要 【一般化】 ? bit 立っている ?? を求めるには ? ? 1 bit 立っている ?? が必要 56
- 59. bitDPを並列化したい 図示すると 59 0000 0001 0010 0100 1000 0011 0101 0110 1001 1010 1100 0111 1011 1101 1110 1111 ビ ッ ト 0 グ ル ー プ ビ ッ ト 1 グ ル ー プ ビ ッ ト 2 グ ル ー プ ビ ッ ト 3 グ ル ー プ ビ ッ ト 4 グ ル ー プ ? + 1 グループ GPUコア GPUコア GPUコア GPUコア GPUコア GPUコア
- 60. ソースコード (抜粋) __global__ void solve(int *d, int *state, int *num, int *dp, int V, int i){ int j = blockIdx.x*blockDim.x + threadIdx.x; if(j >= num[i]*V) return; int k = j % V; j /= V; if(!((state[j*V+i]>>k)&1)) return; for(int l=0; l<V; l++) dp[state[j*V+i]*V+k] = dmin(dp[state[j*V+i]*V+k], dp[(state[j*V+i]^(1<<k))*V+l]+d[l*V+k]); } int main(){ (入力の受け取りなど) for(int i=0; i<V+1; i++) num[i] = 0 for(int i=0; i<(1<<V); i++){ int c = 0; for(int j=1; j<(1<<V); j<<=1) if(i&j) c++; state[num[c]*V+c] = i; num[c]++; } (メモリのコピーなど) for(int i=0; i<=V; i++){ solve<<<(num[i]*V +BS-1)/BS,BS>>>(dd, dstate, dnum, dp, V, i); cudaDeviceSynchronize(); } (答えの出力など) } 60 CUDAの解説は 次以降の人の発表を聞いてね！
- 61. 計算速度の比較 CPU V time V time V time 2 1.9 11 2.15 20 690.2 3 1.75 12 2.75 21 1563.6 4 1.85 13 4.05 22 3498.8 5 1.7 14 6.7 23 7826.6 6 1.55 15 13.4 24 17303 7 1.75 16 27.35 25 37929 8 1.85 17 58.4 26 81735 9 1.8 18 131 10 2.1 19 297.35 GPU V time V time V time 2 150 11 151.5 20 221.4 3 152 12 151.3 21 297.5 4 150.35 13 153.3 22 405.05 5 151.65 14 153.2 23 691.55 6 150.2 15 155.5 24 1296.6 7 150.05 16 154.3 25 2597.6 8 152.2 17 158.55 26 5356.5 9 151.6 18 166.2 10 151.6 19 183.5 61 各20種のテストケースで計測した平均値 [単位:ms]
- 62. 計算速度の比較 (V≦22) 62 0 1000 2000 3000 4000 2 4 6 8 10 12 14 16 18 20 22 CPU GPU [単位：ms]
- 63. 計算速度の比較 (V≦22) 63 0 1000 2000 3000 4000 2 4 6 8 10 12 14 16 18 20 22 CPU GPU GPUは起動に 時間がかかる [単位：ms]
- 64. 計算速度の比較 (V≦26) 64 0 10000 20000 30000 40000 50000 60000 70000 80000 90000 2 4 6 8 10 12 14 16 18 20 22 24 26 CPU GPU [単位：ms]
- 65. 計算速度の比較 (V≦26) 65 0 10000 20000 30000 40000 50000 60000 70000 80000 90000 2 4 6 8 10 12 14 16 18 20 22 24 26 CPU GPU CPU82秒 GPU5秒 約16倍高速！ [単位：ms]
- 66. 計算速度の比較 (V≦26) 66 0 10000 20000 30000 40000 50000 60000 70000 80000 90000 2 4 6 8 10 12 14 16 18 20 22 24 26 [単位：ms] GPU CPU CPU82秒 GPU5秒 約16倍高速！ https://umaibou.jp/product/
- 67. 計算速度の比較 (V≦26) 67 0 10000 20000 30000 40000 50000 60000 70000 80000 90000 2 4 6 8 10 12 14 16 18 20 22 24 26 [単位：ms] GPU CPU CPU82秒 GPU5秒 約16倍高速！ https://umaibou.jp/product/
- 68. 68
- 69. まとめ ? 性能の悪いコアがたくさん集まったのがGPU ? 条件分岐をbit演算に落とし込むと高速 ? maxやminも ? DPは「ひとかたまり」を意識して並列化 ? bitDPは「ビット数のグループ」ごとに並列化 ? 最大で約16倍高速になった！ 69
- 70. Thank you