悩んでいる人
C言語でマルチコアプロセッサ向け並行ソートアルゴリズムを教えて！
こういった悩みにお答えします．
本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Verse（UEFN）, Assembler (x64，aarch64)．
- 東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
- 2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
- 最近は自然言語処理AIとイーサリアムに関する有益な情報発信や，Unreal Editor for Fortnite（UEFN）でゲーム開発に従事．
- （AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でChatGPT/Geminiを訓練するプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
- （スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．
- UEFNで10本以上のゲームを開発し，フォートナイト上で公開（Fortnite，Fortnite.GG）．
こういった私から学べます．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
C言語でマルチコアプロセッサ向けソートアルゴリズム
C言語でマルチコアプロセッサ向け並行ソートアルゴリズムを紹介します．
※並列ソートと言及されることが多いですが，並行ソートは並列ソートを含みます．
並行と並列の違いは以下の記事で詳しく解説されています．
並行ソートにより，ユニプロセッサのソートアルゴリズムを限界突破する方法がわかります．
まずはユニプロセッサ向けソートアルゴリズムを知りたいあなたはこちらからどうぞ．
-
-
【C言語】配列の要素を並び替えるソートアルゴリズム
こういった悩みにお答えします． こういった私から学べます． 配列の要素を並び替えるソートアルゴリズム C言語で配列の要素を並び替えるソートアルゴリズムを紹介します． ここで，安定ソート（ソートが安定す ...
続きを見る
C言語でマルチコアプロセッサ向け並行ソートアルゴリズムを実装する場合，主に以下の方法があります．
- pthread
- C11規格のスレッド
- MPI
- OpenMP
- CUDA（GPGPUプラットフォーム）
本記事ではpthreadの実装を紹介します．
まずはpthreadを知りたいあなたはこちらからどうぞ．
-
-
【C言語】スレッドの生成と実行【pthread，マルチスレッド，スレッドIDの取得】
こういった悩みにお答えします． こういった私から学べます． スレッド スレッドとは，OSにおけるプログラムの実行単位です． スレッドが管理する情報はプロセスより少ないので，スレッド間のコンテキストスイ ...
続きを見る
C11規格のスレッドはこちらの記事で解説しています．
-
-
【C言語】C11規格のスレッド，ミューテックス，スレッド局所記憶「_Thread_local」
こういった悩みにお答えします． こういった私から学べます． 本記事では，C言語のC11規格のスレッド，ミューテックス，スレッド局所記憶「_Thread_local」を紹介します． POSIXスレッドや ...
続きを見る
並行マージソート
並行マージソートは，マージソートの並行実行です．
並行マージソートのコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <pthread.h> #include <time.h> #define N 100 #define MAX 999 #define NR_THREADS 4 #define NR_ARGS 2 struct task { int task_no; int task_low; int task_high; }; void merge(int low, int mid, int high, int a[]) { int left_num = mid - low + 1; int right_num = high - mid; int left[left_num * sizeof(int)]; int right[right_num * sizeof(int)]; int i, j, k; for (i = 0; i < left_num; i++) { left[i] = a[i + low]; } for (i = 0; i < right_num; i++) { right[i] = a[i + mid + 1]; } i = j = 0; k = low; while (i < left_num && j < right_num) { if (left[i] <= right[j]) { a[k++] = left[i++]; } else { a[k++] = right[j++]; } } while (i < left_num) { a[k++] = left[i++]; } while (j < right_num) { a[k++] = right[j++]; } } void merge_sort(int low, int high, int a[]) { int mid; if (low < high) { mid = low + (high - low) / 2; merge_sort(low, mid, a); merge_sort(mid + 1, high, a); merge(low, mid, high, a); } } void *do_merge_sort(void *arg) { int low; int high; int mid; struct task *task = (struct task *)((void **) arg)[0]; int *a = (int *)((void **) arg)[1]; low = task->task_low; high = task->task_high; if (low < high) { mid = low + (high - low) / 2; merge_sort(low, mid, a); merge_sort(mid + 1, high, a); merge(low, mid, high, a); } return NULL; } int main(void) { int a[N]; pthread_t threads[NR_THREADS]; struct task tasklist[NR_THREADS]; struct task *task; void *arg[NR_THREADS][NR_ARGS]; int i; int ret; int low = 0; int len = N / NR_THREADS; srand(time(NULL)); printf("Before:"); for (i = 0; i < N; i++) { a[i] = rand() / (RAND_MAX / (MAX + 1) + 1); printf(" %3d", a[i]); } printf("\n"); for (i = 0; i < NR_THREADS; i++, low += len) { task = &tasklist[i]; task->task_no = i; task->task_low = low; task->task_high = low + len - 1; if (i == NR_THREADS - 1) { task->task_high = N - 1; } } for (i = 0; i < NR_THREADS; i++) { arg[i][0] = &tasklist[i]; arg[i][1] = a; if ((ret = pthread_create(&threads[i], NULL, do_merge_sort, arg[i])) != 0) { fprintf(stderr, "pthread_create(): ret = %d\n", ret); exit(i + 1); } } for (i = 0; i < NR_THREADS; i++) { if ((ret = pthread_join(threads[i], NULL)) != 0) { fprintf(stderr, "pthread_join(): ret = %d\n", ret); exit(NR_THREADS + i + 1); } } for (i = 1; i < NR_THREADS; i++) { task = &tasklist[i]; merge(tasklist[0].task_low, task->task_low - 1, task->task_high, a); } printf("After: "); for (i = 0; i < N; i++) { printf(" %3d", a[i]); } printf("\n"); return 0; } |
実行結果の例は以下になります．
|
1 2 3 4 |
$ gcc concurrent_merge_sort.c $ a.out Before: 158 752 272 899 798 665 368 562 371 358 321 960 37 14 428 729 368 225 549 542 153 742 468 835 773 425 467 819 115 487 852 274 240 124 174 38 790 543 601 161 902 922 122 939 936 550 669 305 775 219 848 929 961 316 765 734 742 232 553 858 720 406 133 960 530 308 999 320 851 600 482 753 523 604 692 459 155 362 765 931 581 613 860 542 930 625 277 673 858 831 531 578 237 665 539 768 973 538 88 824 After: 14 37 38 88 115 122 124 133 153 155 158 161 174 219 225 232 237 240 272 274 277 305 308 316 320 321 358 362 368 368 371 406 425 428 459 467 468 482 487 523 530 531 538 539 542 542 543 549 550 553 562 578 581 600 601 604 613 625 665 665 669 673 692 720 729 734 742 742 752 753 765 765 768 773 775 790 798 819 824 831 835 848 851 852 858 858 860 899 902 922 929 930 931 936 939 960 960 961 973 999 |
並行クイックソート
並行クイックソートは，クイックソートの並行実行です．
並行クイックソートのコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <stdatomic.h> #include <pthread.h> #include <time.h> #define N 100 #define NR_THREADS 4 #define MAX 999 struct worker_data { int id; int *start; int n; }; static struct worker_data worker_data[NR_THREADS]; void swap(int *pa, int *pb) { int tmp; tmp = *pa; *pa = *pb; *pb = tmp; } void quick_sort(int left, int right, int a[]) { int i, last; if (left >= right) { return; } swap(&a[left], &a[(left + right) / 2]); last = left; for (i = left + 1; i <= right; i++) { if (a[i] < a[left]) { swap(&a[++last], &a[i]); } } swap(&a[left], &a[last]); quick_sort(left, last - 1, a); quick_sort(last + 1, right, a); } void concurrent_quick_sort(int *start, int n); void *start_thread(void *data) { struct worker_data *p = (struct worker_data *) data; concurrent_quick_sort(p->start, p->n); return NULL; } void concurrent_quick_sort(int *start, int n) { static atomic_int active_workers = 0; static pthread_t workers[NR_THREADS]; int pivot_index, store_index, right; int i; pthread_t id; void *status; int ret; if (active_workers < NR_THREADS) { id = active_workers; atomic_fetch_add_explicit(&active_workers, 1, memory_order_seq_cst); pivot_index = n / 2; right = n - 1; swap(&start[pivot_index], &start[right]); store_index = 0; for (i = 0; i < right; i++) { if (start[i] < start[right]) { swap(&start[i], &start[store_index]); store_index++; } } swap(&start[store_index], &start[right]); pivot_index = store_index; worker_data[id].id = id; worker_data[id].start = start + pivot_index; worker_data[id].n = n - pivot_index; if ((ret = pthread_create(&workers[id], NULL, start_thread, &worker_data[id])) != 0) { fprintf(stderr, "Error pthread_create() ret = %d\n", ret); exit(2 * id + 1); } concurrent_quick_sort(start, pivot_index); if ((ret = pthread_join(workers[id], &status)) != 0) { fprintf(stderr, "Error pthread_join() ret = %d\n", ret); exit(2 * id + 2); } } else { quick_sort(0, n, start); } } int main(void) { int i; int a[N]; for (i = 0; i < NR_THREADS; i++) { worker_data[i].id = 0; worker_data[i].start = 0; worker_data[i].n = 0; } srand(time(NULL)); printf("Before:"); for (i = 0; i < N; i++) { a[i] = rand() / (RAND_MAX / (MAX + 1) + 1); printf(" %3d", a[i]); } printf("\n"); concurrent_quick_sort(&a[0], N); printf("After: "); for (i = 0; i < N; i++) { printf(" %3d", a[i]); } printf("\n"); return 0; } |
実行結果の例は以下になります．
|
1 2 3 4 |
$ gcc concurrent_quick_sort.c $ a.out Before: 421 41 974 747 862 341 730 984 181 496 678 958 392 438 628 244 98 15 710 544 345 13 488 585 286 179 250 75 62 624 672 483 666 647 231 528 988 962 513 169 458 192 128 851 630 756 95 729 771 805 273 117 819 762 702 106 941 952 182 3 577 854 487 243 501 718 772 490 680 285 660 139 477 788 990 108 544 85 838 316 891 111 433 710 873 135 817 814 88 999 818 665 854 305 909 356 23 681 846 704 After: 3 13 15 23 41 62 75 85 88 95 98 106 108 111 117 128 135 139 169 179 181 182 192 231 243 244 250 273 285 286 305 316 341 345 356 392 421 433 438 458 477 483 487 488 490 496 501 513 528 544 544 577 585 624 628 630 647 660 665 666 672 678 680 681 702 704 710 710 718 729 730 747 756 762 771 772 788 805 814 817 818 819 838 846 851 854 854 862 873 891 909 941 952 958 962 974 984 988 990 999 |
また，並行クイックソートを一般化した「サンプルソート」があります．
サンプルソートの実装例は以下になります．
並行分布数えソート
並行分布数えソートは，分布数えソートの並行実行です．
並行分布数えソートのコードは以下になります．（入力は0～MAXの整数を仮定しています．）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <stdatomic.h> #include <time.h> #include <pthread.h> #define N 100 #define MAX 999 #define NR_THREADS 4 #define NR_ARGS 3 struct task { int task_no; int task_low; int task_high; }; void *counting_sort(void *arg) { struct task *task = (struct task *)((void **) arg)[0]; atomic_int *dst = (atomic_int *)((void **) arg)[1]; int *src = (int *)((void **) arg)[2]; int i; for (i = task->task_low; i <= task->task_high; i++) { atomic_fetch_add_explicit(&dst[src[i]], 1, memory_order_seq_cst); } return NULL; } int main(void) { atomic_int dst[MAX + 1]; int src[N]; pthread_t threads[NR_THREADS]; struct task tasklist[NR_THREADS]; struct task *task; void *arg[NR_THREADS][NR_ARGS]; int i, j; int ret; int low = 0; int len = N / NR_THREADS; srand(time(NULL)); printf("Before:"); for (i = 0; i < N; i++) { src[i] = rand() / (RAND_MAX / (MAX + 1) + 1); printf(" %3d", src[i]); } for (i = 0; i < MAX; i++) { dst[i] = 0; } printf("\n"); for (i = 0; i < NR_THREADS; i++, low += len) { task = &tasklist[i]; task->task_no = i; task->task_low = low; task->task_high = low + len - 1; if (i == NR_THREADS - 1) { task->task_high = N - 1; } } for (i = 0; i < NR_THREADS; i++) { arg[i][0] = &tasklist[i]; arg[i][1] = dst; arg[i][2] = src; if ((ret = pthread_create(&threads[i], NULL, counting_sort, arg[i])) != 0) { fprintf(stderr, "pthread_create(): ret = %d\n", ret); exit(i + 1); } } for (i = 0; i < NR_THREADS; i++) { if ((ret = pthread_join(threads[i], NULL)) != 0) { fprintf(stderr, "pthread_join(): ret = %d\n", ret); exit(NR_THREADS + i + 1); } } printf("After: "); for (i = 0; i < MAX + 1; i++) { if (dst[i] > 0) { for (j = 0; j < dst[i]; j++) { printf(" %3d", i); } } } printf("\n"); return 0; } |
実行結果の例は以下になります．
|
1 2 3 4 |
$ gcc concurrent_counting_sort.c $ a.out Before: 525 338 848 164 808 177 914 619 141 111 959 464 321 28 352 479 211 688 685 41 66 428 753 563 384 511 220 113 400 815 240 926 153 89 90 962 267 4 581 408 116 541 872 437 569 225 917 781 914 602 822 980 31 576 543 416 88 764 529 488 579 770 415 733 859 505 695 127 509 277 536 626 818 409 64 388 634 981 169 548 584 992 529 615 568 73 31 656 837 560 145 417 330 560 151 190 65 847 318 575 After: 4 28 31 31 41 64 65 66 73 88 89 90 111 113 116 127 141 145 151 153 164 169 177 190 211 220 225 240 267 277 318 321 330 338 352 384 388 400 408 409 415 416 417 428 437 464 479 488 505 509 511 525 529 529 536 541 543 548 560 560 563 568 569 575 576 579 581 584 602 615 619 626 634 656 685 688 695 733 753 764 770 781 808 815 818 822 837 847 848 859 872 914 914 917 926 959 962 980 981 992 |
バイトニックソート
バイトニックソートは，ソーティングネットワークの並行ソートアルゴリズムです．
バイトニックソートのコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <stdatomic.h> #include <pthread.h> #include <time.h> /* NOTE: N must be power of 2. */ #define N 128 #define MAX 999 #define NR_THREADS 4 atomic_int active_workers = 0; int thread_layers; #define ASCENDING true #define DESCENDING false struct task { int low; int count; int layer; bool dir; }; int a[N]; int asc(const void *pa, const void *pb) { int a = *(int *) pa; int b = *(int *) pb; if (a < b) { return -1; } else if (a == b) { return 0; } else { return 1; } } int desc(const void *pa, const void *pb) { int a = *(int *) pa; int b = *(int *) pb; if (a > b) { return -1; } else if (a == b) { return 0; } else { return 1; } } void swap(int *pa, int *pb) { int tmp; tmp = *pa; *pa = *pb; *pb = tmp; } void compare(int i, int j, bool dir) { if (dir == (a[i] > a[j])) { swap(&a[i], &a[j]); } } void bitonic_merge(int low, int count, bool dir) { int i, k; if (count > 1) { k = count / 2; for (i = low; i < low + k; i++) { compare(i, i + k, dir); } bitonic_merge(low, k, dir); bitonic_merge(low + k, k, dir); } } void *concurrent_bitonic_merge(void *arg) { struct task *p = (struct task *) arg; int low = p->low; int count = p->count; int layer = p->layer; bool dir = p->dir; int i, k; struct task args[2]; pthread_t threads[2]; int ret; if (count > 1) { k = count / 2; for (i = low; i < low + k; i++) { compare(i, i + k, dir); } if (layer <= 0) { bitonic_merge(low, k, dir); bitonic_merge(low + k, k, dir); return NULL; } args[0].low = low; args[0].count = k; args[0].layer = layer - 1; args[0].dir = dir; args[1].low = low + k; args[1].count = k; args[1].layer = layer - 1; args[1].dir = dir; for (i = 0; i < 2; i++) { if ((ret = pthread_create(&threads[i], NULL, concurrent_bitonic_merge, &args[i])) != 0) { fprintf(stderr, "Error: pthread_create() ret = %d\n", ret); exit(i + 1); } } for (i = 0; i < 2; i++) { if ((ret = pthread_join(threads[i], NULL)) != 0) { fprintf(stderr, "Error: pthread_join() ret = %d\n", ret); exit(i + 3); } } } return NULL; } void *bitonic_sort(void *arg) { struct task *p = (struct task *) arg; int low = p->low; int count = p->count; int layer = p->layer; bool dir = p->dir; int i, k; struct task args[3]; pthread_t threads[2]; int ret; if (count > 1) { k = count / 2; if (layer >= thread_layers) { qsort(a + low, k, sizeof(int), asc); qsort(a + low + k, k, sizeof(int), desc); } else { args[0].low = low; args[0].count = k; args[0].layer = layer + 1; args[0].dir = ASCENDING; args[1].low = low + k; args[1].count = k; args[1].layer = layer + 1; args[1].dir = DESCENDING; for (i = 0; i < 2; i++) { if ((ret = pthread_create(&threads[i], NULL, bitonic_sort, &args[i])) != 0) { fprintf(stderr, "Error: pthread_create() ret = %d\n", ret); exit(i + 1); } atomic_fetch_add_explicit(&active_workers, 1, memory_order_seq_cst); } for (i = 0; i < 2; i++) { if ((ret = pthread_join(threads[i], NULL)) != 0) { fprintf(stderr, "Error: pthread_join() ret = %d\n", ret); exit(i + 3); } } } args[2].low = low; args[2].count = count; args[2].layer = thread_layers - layer; args[2].dir = dir; concurrent_bitonic_merge(&args[2]); } return NULL; } int main(void) { int i; struct task arg; thread_layers = NR_THREADS; if (thread_layers != 0 && thread_layers != 1) { thread_layers--; } srand(time(NULL)); printf("Before:"); for (i = 0; i < N; i++) { a[i] = rand() / (RAND_MAX / (MAX + 1) + 1); printf(" %3d", a[i]); } printf("\n"); arg.low = 0; arg.count = N; arg.layer = 0; arg.dir = ASCENDING; bitonic_sort(&arg); printf("After: "); for (i = 0; i < N; i++) { printf(" %3d", a[i]); } printf("\n"); return 0; } |
実行結果の例は以下になります．
|
1 2 3 4 |
$ gcc bitonic_sort.c $ a.out Before: 739 706 936 513 597 65 372 215 670 775 620 350 831 373 524 136 902 944 138 782 380 798 105 563 294 158 586 974 599 819 111 339 525 48 853 123 113 225 338 784 1 958 134 832 332 659 968 234 603 106 17 984 905 122 547 199 280 133 174 880 953 286 219 479 335 72 602 449 298 940 233 299 899 367 131 231 26 100 465 630 207 482 614 113 605 162 312 886 296 487 766 250 774 986 729 109 59 331 558 357 271 791 656 171 159 788 402 186 888 868 817 96 351 431 209 956 594 522 842 891 9 609 141 784 595 870 893 654 After: 1 9 17 26 48 59 65 72 96 100 105 106 109 111 113 113 122 123 131 133 134 136 138 141 158 159 162 171 174 186 199 207 209 215 219 225 231 233 234 250 271 280 286 294 296 298 299 312 331 332 335 338 339 350 351 357 367 372 373 380 402 431 449 465 479 482 487 513 522 524 525 547 558 563 586 594 595 597 599 602 603 605 609 614 620 630 654 656 659 670 706 729 739 766 774 775 782 784 784 788 791 798 817 819 831 832 842 853 868 870 880 886 888 891 893 899 902 905 936 940 944 953 956 958 968 974 984 986 |
バッチャー奇偶マージソート
バッチャー奇偶マージソートは，ケン・バッチャーにより提案されたソーティングネットワークの並行ソートアルゴリズムです．
バッチャー奇偶マージソートのコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <pthread.h> #include <time.h> /* NOTE: N must be power of 2. */ #define N 128 #define MAX 999 #define NR_THREADS 4 #define NR_ARGS 2 struct task { int task_no; int task_low; int task_high; }; void merge(int low, int mid, int high, int a[]) { int left_num = mid - low + 1; int right_num = high - mid; int left[left_num * sizeof(int)]; int right[right_num * sizeof(int)]; int i, j, k; for (i = 0; i < left_num; i++) { left[i] = a[i + low]; } for (i = 0; i < right_num; i++) { right[i] = a[i + mid + 1]; } i = j = 0; k = low; while (i < left_num && j < right_num) { if (left[i] <= right[j]) { a[k++] = left[i++]; } else { a[k++] = right[j++]; } } while (i < left_num) { a[k++] = left[i++]; } while (j < right_num) { a[k++] = right[j++]; } } void compare_and_swap(int *pa, int *pb) { int tmp; if (*pa > *pb) { tmp = *pa; *pa = *pb; *pb = tmp; } } void batcher_odd_even_merge(int low, int high, int r, int a[]) { int step = r * 2; int i; if (step < high - low) { batcher_odd_even_merge(low, high, step, a); batcher_odd_even_merge(low + r, high, step, a); for (i = low + r; i < high - r; i += step) { compare_and_swap(&a[i], &a[i + r]); } } else { compare_and_swap(&a[low], &a[low + r]); } } void batcher_odd_even_merge_sort(int low, int high, int a[]) { int mid; if (low < high) { mid = low + (high - low) / 2; batcher_odd_even_merge_sort(low, mid, a); batcher_odd_even_merge_sort(mid + 1, high, a); batcher_odd_even_merge(low, high, 1, a); } } void *do_batcher_odd_even_merge_sort(void *arg) { int low; int high; int mid; struct task *task = (struct task *)((void **) arg)[0]; int *a = (int *)((void **) arg)[1]; low = task->task_low; high = task->task_high; if (low < high) { mid = low + (high - low) / 2; batcher_odd_even_merge_sort(low, mid, a); batcher_odd_even_merge_sort(mid + 1, high, a); batcher_odd_even_merge(low, high, 1, a); } return NULL; } int main(void) { int a[N]; pthread_t threads[NR_THREADS]; struct task tasklist[NR_THREADS]; struct task *task; void *arg[NR_THREADS][NR_ARGS]; int i; int ret; int low = 0; int len = N / NR_THREADS; srand(time(NULL)); printf("Before:"); for (i = 0; i < N; i++) { a[i] = rand() / (RAND_MAX / (MAX + 1) + 1); printf(" %3d", a[i]); } printf("\n"); for (i = 0; i < NR_THREADS; i++, low += len) { task = &tasklist[i]; task->task_no = i; task->task_low = low; task->task_high = low + len - 1; if (i == NR_THREADS - 1) { task->task_high = N - 1; } } for (i = 0; i < NR_THREADS; i++) { arg[i][0] = &tasklist[i]; arg[i][1] = a; if ((ret = pthread_create(&threads[i], NULL, do_batcher_odd_even_merge_sort, arg[i])) != 0) { fprintf(stderr, "pthread_create(): ret = %d\n", ret); exit(i + 1); } } for (i = 0; i < NR_THREADS; i++) { if ((ret = pthread_join(threads[i], NULL)) != 0) { fprintf(stderr, "pthread_join(): ret = %d\n", ret); exit(NR_THREADS + i + 1); } } for (i = 1; i < NR_THREADS; i++) { task = &tasklist[i]; merge(tasklist[0].task_low, task->task_low - 1, task->task_high, a); } printf("After: "); for (i = 0; i < N; i++) { printf(" %3d", a[i]); } printf("\n"); return 0; } |
シェアソート
シェアソートは，データを長方形に並べた上で，各行／各列ごとにソートを行う並行ソートアルゴリズムです．
シェアソートのコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <pthread.h> #include <math.h> #define TWO_DIM_ARRAY 10 #define N (TWO_DIM_ARRAY * TWO_DIM_ARRAY) #define MAX 999 int a[TWO_DIM_ARRAY][TWO_DIM_ARRAY]; #define MAX_PHASES ((log(N) / log(2)) + 1) int phase = 0; int phase_sync_count = 0; pthread_mutex_t mutex; pthread_cond_t cond; void swap(int *pa, int *pb) { int tmp; tmp = *pa; *pa = *pb; *pb = tmp; } void print_array(int a[TWO_DIM_ARRAY][TWO_DIM_ARRAY]) { int i, j; for (i = 0; i < TWO_DIM_ARRAY; i++) { for (j = 0; j < TWO_DIM_ARRAY; j++) { printf(" %3d", a[i][j]); } printf("\n"); } printf("\n"); } void bubble_sort_row_odd(int num) { int i, j; for (i = 0; i < TWO_DIM_ARRAY - 1; i++) { for (j = 0; j < TWO_DIM_ARRAY - i - 1; j++) { if (a[num][j] > a[num][j + 1]) { swap(&a[num][j], &a[num][j + 1]); } } } } void bubble_sort_row_even(int num) { int i, j; for (i = 0; i < TWO_DIM_ARRAY - 1; i++) { for (j = TWO_DIM_ARRAY - 1; j > i; j--) { if (a[num][j] > a[num][j - 1]) { swap(&a[num][j], &a[num][j - 1]); } } } } void bubble_sort_col(int num) { int i, j; for (i = 0; i < TWO_DIM_ARRAY - 1; i++) { for (j = 0; j < TWO_DIM_ARRAY - i - 1; j++) { if (a[j][num] > a[j + 1][num]) { swap(&a[j][num], &a[j + 1][num]); } } } } void *shear_sort(void *arg) { int id = *(int *) arg; while (phase < MAX_PHASES) { pthread_mutex_lock(&mutex); if (((phase + 1) & 1) == 0) { bubble_sort_col(id); } else { if (((id + 1) & 1) == 0) { bubble_sort_row_even(id); } else { bubble_sort_row_odd(id); } } phase_sync_count++; if (phase_sync_count == TWO_DIM_ARRAY) { phase++; phase_sync_count = 0; pthread_cond_broadcast(&cond); } else { pthread_cond_wait(&cond, &mutex); } pthread_mutex_unlock(&mutex); } return NULL; } int main(void) { int ret; int i, j; int ids[TWO_DIM_ARRAY]; pthread_t threads[TWO_DIM_ARRAY]; srand(time(NULL)); printf("Before:\n"); for (i = 0; i < TWO_DIM_ARRAY; i++) { for (j = 0; j < TWO_DIM_ARRAY; j++) { a[i][j] = rand() / (RAND_MAX / (MAX + 1) + 1); } } print_array(a); pthread_mutex_init(&mutex, NULL); pthread_cond_init(&cond, NULL); for (i = 0; i < TWO_DIM_ARRAY; i++) { ids[i] = i; if ((ret = pthread_create(&threads[i], NULL, shear_sort, &ids[i])) != 0) { fprintf(stderr, "Error: pthread_create() ret = %d\n", ret); exit(i + 1); } } for (i = 0; i < TWO_DIM_ARRAY; i++) { if ((ret = pthread_join(threads[i], NULL)) != 0) { fprintf(stderr, "Error: pthread_join() ret = %d\n", ret); exit(TWO_DIM_ARRAY + 1); } } pthread_mutex_destroy(&mutex); pthread_cond_destroy(&cond); printf("Done:\n"); print_array(a); for (i = 1; i < TWO_DIM_ARRAY; i += 2) { for (j = 0; j < TWO_DIM_ARRAY / 2; j++) { swap(&a[i][j], &a[i][TWO_DIM_ARRAY - 1 - j]); } } printf("After:\n"); print_array(a); return 0; } |
実行結果の例は以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
$ gcc shear_sort.c $ a.out Before: 782 234 751 421 46 573 945 408 262 887 211 389 389 688 897 932 497 511 835 968 105 563 605 121 678 901 15 101 946 729 929 729 964 680 151 10 254 97 418 516 985 630 905 374 318 803 307 815 315 142 784 420 705 389 541 384 291 557 485 238 287 415 968 251 96 119 262 350 217 680 867 202 311 772 576 630 576 883 446 891 26 230 311 732 620 853 116 911 411 602 150 698 18 118 950 114 238 212 464 455 Done: 10 15 18 26 46 96 97 101 105 114 212 211 202 151 150 142 121 119 118 116 217 230 234 238 238 251 254 262 262 287 389 384 374 350 318 315 311 311 307 291 389 389 408 411 415 418 420 421 446 455 576 573 563 557 541 516 511 497 485 464 576 602 605 620 630 630 678 680 680 688 803 784 782 772 751 732 729 729 705 698 815 835 853 867 883 887 891 897 901 905 985 968 968 964 950 946 945 932 929 911 After: 10 15 18 26 46 96 97 101 105 114 116 118 119 121 142 150 151 202 211 212 217 230 234 238 238 251 254 262 262 287 291 307 311 311 315 318 350 374 384 389 389 389 408 411 415 418 420 421 446 455 464 485 497 511 516 541 557 563 573 576 576 602 605 620 630 630 678 680 680 688 698 705 729 729 732 751 772 782 784 803 815 835 853 867 883 887 891 897 901 905 911 929 932 945 946 950 964 968 968 985 |
まとめ
C言語でマルチコアプロセッサ向け並行ソートアルゴリズムを紹介しました．
並行ソートアルゴリズムを利用する際に参考にして下さい．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
