Geekly Articles each Day

CUDAでの同時バブルソート

こんにちは、Habr。 CUDAプラットフォームで比較的簡単な実装と高性能を備えた並列ソートが必要になると思いました。 これはバブルソートです。 猫の下には説明とコードがあり、役に立つかもしれません（またはそうでないかもしれません...）。 すぐに、提示されたプログラムはGPUとCPUのパフォーマンスの比較におけるベンチマークであることを言わなければなりません。 読者を気にしない場合は、コンパイルして、計算結果をこの記事のコメントに入れてください。 これは科学用ではありません。 ただ面白い=）


少し思い出させてください


バブルソート方法の本質は、要素をペアワイズで比較し、ソートの方向に応じて特定の条件が満たされた場合に要素を置き換えることです。 シングルスレッドモードでのアルゴリズムの反復を以下に示します。整数の増加する配列を降順で並べ替えます（各行は現在の配列の状態です）-これは表1です。

表2は、マルチスレッドモードでのバブルによる並べ替えの繰り返しを示しています。これは非常に簡単に実装されます。一つなど したがって、配列全体が「ポップアップ」し始め、計算時間が大幅に短縮されます。

利益


すでに実行されたアクションの数から、並列ソートの方が速いことがわかります。 ただし、常にそうとは限りません。小さなサイズの配列では、データ転送に問題がないため、シングルスレッドモードの方が高速です。 ここでいくつかのテスト計算を行いましたが、結果は次のとおりです。
画像

横軸は要素の数、縦軸は秒単位の実行時間です。


実装


CUDA C言語の実装コードを提供します。CUDAC言語には、CUDAとCPU（シングルスレッドモード）でSECURITY SECURITYソートを実行するコードが含まれています。 実際、これは、ビデオカードとプロセスでスマートソートがどのように機能するかについてのコンピューターのベンチマークです。 このプログラムの一部は、CUDAプラットフォーム上のビデオカードの並べ替え機能です。これは、基本的なcopy'n'pastを使用して、傑作の健康に使用できます。 コードは表の下に表示されます。

コンパイル方法???


さて、このためには、NVIDIAのWebサイトからCUDAのドライバーをダウンロードし、インストールし、Nvidia Toolkitをダウンロードし、Nvidia SDKをインストールし、インストールする必要があります。 幸いなことに、すべてがすでに1つのパッケージに含まれています。 要望があればCUDAをインストールする方法を書きますが、初心者の方には幸運を祈っています。
すべての準備が整い、nvidia CUDAがコンピューターで動作するようになったら、main.cuファイル（またはそこで呼び出されたもの）をコンパイルして、プログラムを実行し、結果を取得して、ここに配置します。
ワット、それは今のところ、読んでくれてありがとう。 じゃあね
PSアルゴリズムを高速化する方法を教えていただければ幸いです=）

表1：シングルソートバブルソート


01234567891011121314
10234567891011121314
12034567891011121314
12304567891011121314
12340567891011121314
12345067891011121314
12345607891011121314
12345670891011121314
12345678091011121314
12345678901011121314
12345678910011121314
12345678910110121314
12345678910111201314
123456789101112130
12345678910111213140
1234567891011121314
21345678910111213140
23145678910111213140
23415678910111213140
23451678910111213140
23456178910111213140
23456718910111213140
23456781910111213140
23456789110111213140
23456789101111213140
23456789101111213140
23456789101112113140
23456789101112131140
2345678910111213141
234567891011121314
32456789101112131410
34256789101112131410
34526789101112131410
34562789101112131410
34567289101112131410
34567829101112131410
34567892101112131410
34567891021112131410
34567891011212131410
34567891011122131410
34567891011121321410
34567891011121314210
34567891011121314
43567891011121314210
45367891011121314210
45637891011121314210
45673891011121314210
45678391011121314210
45678931011121314210
45678910311121314210
45678910113121314210
45678910111231314210
45678910111213314210
45678910111213143210
456789101112131410
54678910111213143210
56478910111213143210
56748910111213143210
56784910111213143210
56789410111213143210
56789104111213143210
56789101141213143210
56789101112413143210
56789101112134143210
56789101112131443210
567891011121314210
65789101112131443210
67589101112131443210
67859101112131443210
67895101112131443210
67891051112131443210
67891011512131443210
67891011125131443210
67891011121351443210
67891011121314543210
678910111213143210
76891011121314543210
78691011121314543210
78961011121314543210
78910611121314543210
78910116121314543210
78910111261314543210
78910111213614543210
78910111213146543210
789101112131443210
87910111213146543210
89710111213146543210
89107111213146543210
89101171213146543210
89101112713146543210
89101112137146543210
89101112131476543210
891011121314543210
98101112131476543210
91081112131476543210
91011812131476543210
91011128131476543210
91011121381476543210
91011121314876543210
910111213146543210
10911121314876543210
10119121314876543210
10111291314876543210
10111213914876543210
10111213149876543210
101112131476543210
11101213149876543210
11121013149876543210
11121310149876543210
11121314109876543210
11121314876543210
12111314109876543210
12131114109876543210
12131411109876543210
1213149876543210
13121411109876543210
13141211109876543210
1314109876543210
14131211109876543210


表2：マルチスレッドモードでのバブルソート


01234567891011121314
01234567891011121314
01234567891011121314
10234567891011121314
12034567891011121314
21304567891011121314
23140567891011121314
32415067891011121314
34251607891011121314
43526170891011121314
45362718091011121314
54637281901011121314
56473829110011121314
65748392101110121314
67584931021111201314
76859410311212113014
78695104113122131140
87961051141231321410
89710611512413314210
98107116125134143210
91081171261351443210
10911812713614543210
10119128137146543210
11101291381476543210
11121013914876543210
12111310149876543210
12131114109876543210
13121411109876543210
13141211109876543210
14131211109876543210
14131211109876543210



コード：


#include <stdio.h> #include <time.h> __global__ void bubbleMove(int *array_device, int N, int step){ int idx = blockDim.x * blockIdx.x + threadIdx.x; if (idx<(N-1)) { if (step-2>=idx){ if (array_device[idx]<array_device[idx+1]){ int buffer = array_device[idx]; array_device[idx]=array_device[idx+1]; array_device[idx+1] = buffer; } } } } void bubleSortCUDA(int *array_host,int N, int blockSize){ int *array_device; cudaMalloc((void **)&array_device, N * sizeof(int)); for (int i = 0; i < N; i++) array_host[i]=i; cudaMemcpy(array_device,array_host,N*sizeof(int),cudaMemcpyHostToDevice); int nblocks = N / blockSize+1; for (int step = 0; step <= N+N; step++) { bubbleMove<<<nblocks,blockSize>>>(array_device,N,step); cudaThreadSynchronize(); } cudaMemcpy(array_host,array_device,N*sizeof(int),cudaMemcpyDeviceToHost); cudaFree(array_device); } void bubleSortCPU(int *array_host, int N){ for (int i = 0; i < N; i++){ for (int j = 0; j < Ni-1; j++) { if (array_host[j]<array_host[j+1]){ int buffer = array_host[j]; array_host[j]=array_host[j+1]; array_host[j+1] = buffer; } } } } int checkArray(int *array_host, int N){ int good=1; for (int i = 0; i < N-1; i++) if (array_host[i]<array_host[i+1]) {good=0; printf("i=%da=%d\n", i,array_host[i] );} return good; } float measureCUDA(int N,int blockSize){ int *array_host = (int *)malloc(N * sizeof(int)); for (int i = 0; i < N; i++) array_host[i]=i; clock_t start = clock(); bubleSortCUDA(array_host,N,blockSize); clock_t end = clock(); if (checkArray(array_host,N)==1){ free(array_host); return (float)(end - start) / CLOCKS_PER_SEC; } else { free(array_host); return -1; } } float measureCPU(int N) { int *array_host = (int *)malloc(N * sizeof(int)); for (int i = 0; i < N; i++) array_host[i]=i; clock_t start = clock(); bubleSortCPU(array_host,N); clock_t end = clock(); if (checkArray(array_host,N)==1){ free(array_host); return (float)(end - start) / CLOCKS_PER_SEC; } else { free(array_host); return -1; } } int main(int argc, char const *argv[]) { for (int i = 1; i < 10000000; i*=2) printf("%d %f\t%f\n",i, measureCUDA(i,256),measureCPU (i )); return 0; }

Source: https://habr.com/ru/post/J235391/

More articles:


All Articles