基数排序的并行版本未按预期运行 (Java)
Parallel version of radix sort is not behaving as expected (Java)
在我的项目中，我发现排序性能是瓶颈。经过一番谷歌搜索后，我想出了并行版本的基数排序（基数为 256）。但是它的行为并不像我预期的那样。
首先将基数更改为 2^16 不会导致任何加速，理论上应该是 2。
其次，在我的并行版本中，我将它分成 4 个部分（核心数）并对它们进行基数排序，然后合并结果。同样，它仅与串行版本同时运行。
public class RadixSortPrototype {
public static void parallelSort(long[] arr) {
long[] output = new long[arr.length];
int MAX_PART = 1_000_000;
int numProc = Runtime.getRuntime().availableProcessors();
int partL = Math
.min((int) Math.ceil(arr.length / (double) numProc), MAX_PART);
int parts = (int) Math.ceil(arr.length / (double) partL);
Future[] threads = new Future[parts];
ExecutorService worker = Executors.newFixedThreadPool(numProc);
for (int i = 0; i < 8; i++) {
int[][] counts = new int[parts][256];
int radix = i;
for (int j = 0; j < parts; j++) {
int part = j;
threads[j] = worker.submit(() -> {
for (int k = part * partL; k < (part + 1) * partL && k < arr.length;
k++) {
int chunk = (int) ((arr[k] >> (radix * 8)) & 255);
counts[part][chunk]++;
}
});
}
barrier(parts, threads);
int base = 0;
for (int k = 0; k <= 255; k++) {
for (int j = 0; j < parts; j++) {
int t = counts[j][k];
counts[j][k] = base;
base += t;
}
}
for (int j = 0; j < parts; j++) {
int part = j;
threads[j] = worker.submit(() -> {
for (int k = part * partL;
k < (part + 1) * partL && k < arr.length;
k++) {
int chunk = (int) ((arr[k] >> (radix * 8)) & 255);
output[counts[part][chunk]] = arr[k];
counts[part][chunk]++;
}
});
}
barrier(parts, threads);
for (int j = 0; j < parts; j++) {
int part = j;
threads[j] = worker.submit(() -> {
for (int k = part * partL;
k < (part + 1) * partL && k < arr.length;
k++) {
arr[k] = output[k];
}
});
}
barrier(parts, threads);
}
worker.shutdownNow();
}
private static void barrier(int parts, Future[] threads) {
for (int j = 0; j < parts; j++) {
try {
threads[j].get();
} catch (InterruptedException | ExecutionException e) {
e.printStackTrace();
}
}
}
}
知道为什么 运行 这么慢吗？解决此优化的推荐方法是什么？
我真的很好奇答案。
谢谢！
更新
根据答案我改进了数据的局部性，所以现在它使用了所有的核心。更新了代码片段。以下是 2 核 4 线程的结果 CPU。
Java Parallel: 1130 ms
Radixsort Serial: 1218 ms
Radixsort Parallel: 625 ms
如果可以进一步改进，问题仍然悬而未决。
使用基数 2^16 = 65536 最终会有点慢，因为 L1 缓存通常每个内核 32768 字节，而基数 2^16 counts|indexes 数组每个使用 2^20 = 262144 字节。
基数排序的问题在于读取是顺序的，但写入与数据一样随机。根据评论，该程序正在对 2000 万个 long 进行排序，每个 8 个字节，因此 80 MB 的数据，假设 8MB L3 缓存，这些写入中的大部分将是缓存未命中。并行操作没有太大帮助，因为大多数写入都在竞争相同的 80 MB 非缓存主内存。
为了避免这个问题，我使用了另一种实现方式，其中第一遍执行最高有效数字基数排序以产生 256 个 bin（每个 bin 包含具有相同最高有效字节的整数）。然后使用传统的基数排序将最低有效位放在首位对每个 bin 进行排序。对于相当均匀的伪随机数据，256 个 bin 的大小几乎相等，因此 80MB 被分成 256 个 bin，每个大约 312500 字节，对于 4 个线程，有 8 个这样的 bin，4 个用于读取，4 个用于写入，加上计数|索引数组，所有这些都将放入所有 4 个内核通用的 8MB L3 16 路关联 L3 缓存中。
对于较大的阵列，初始遍可以将阵列拆分为 512 到 4096 或更多的箱。
我使用基数 2^8 = 256 对基数排序伪随机 64 位整数进行了一些测试。我测试了 3 个实现，单线程最低有效位，单线程最高有效位数字在前，四线线程最重要的数字在前。当整数个数为2的幂时，会导致一些缓存冲突，部分情况会影响时间。
16000000 - 8 个 bin + 索引数组适合 8MB L3 缓存。
16777216 = 2^24，8 个 bin + 索引数组适合 8MB L3 缓存。
30000000 - 8 个 bin + 索引数组适合 8MB L3 缓存。
33554432 = 2^25，8 个 bins + 索引数组略大于 8MB
36000000 - 8 个 bin + 比 8MB 大一点的索引数组。
Win 7 Pro 64 bit, VS 2015, Intel 3770K 3.5 ghz
count 1 thread LSD 1 thread MSD 4 thread MSD
16000000 0.59 0.38 0.16
16777216 1.35 0.48 0.30
30000000 0.82 0.70 0.30
33554432 3.20 1.09 0.68
36000000 0.95 0.82 0.39
Win 10 Pro 64 bit, VS 2019, Intel 10510U 1.8 ghz to 4.9 ghz
count 1 thread LSD 1 thread MSD 4 thread MSD
16000000 0.312 0.230 0.125
16777216 0.897 0.242 0.150
30000000 0.480 0.430 0.236
33554432 2.880 0.510 0.250
36000000 0.568 0.530 0.305
在我的项目中，我发现排序性能是瓶颈。经过一番谷歌搜索后，我想出了并行版本的基数排序（基数为 256）。但是它的行为并不像我预期的那样。
首先将基数更改为 2^16 不会导致任何加速，理论上应该是 2。
其次，在我的并行版本中，我将它分成 4 个部分（核心数）并对它们进行基数排序，然后合并结果。同样，它仅与串行版本同时运行。
public class RadixSortPrototype {
public static void parallelSort(long[] arr) {
long[] output = new long[arr.length];
int MAX_PART = 1_000_000;
int numProc = Runtime.getRuntime().availableProcessors();
int partL = Math
.min((int) Math.ceil(arr.length / (double) numProc), MAX_PART);
int parts = (int) Math.ceil(arr.length / (double) partL);
Future[] threads = new Future[parts];
ExecutorService worker = Executors.newFixedThreadPool(numProc);
for (int i = 0; i < 8; i++) {
int[][] counts = new int[parts][256];
int radix = i;
for (int j = 0; j < parts; j++) {
int part = j;
threads[j] = worker.submit(() -> {
for (int k = part * partL; k < (part + 1) * partL && k < arr.length;
k++) {
int chunk = (int) ((arr[k] >> (radix * 8)) & 255);
counts[part][chunk]++;
}
});
}
barrier(parts, threads);
int base = 0;
for (int k = 0; k <= 255; k++) {
for (int j = 0; j < parts; j++) {
int t = counts[j][k];
counts[j][k] = base;
base += t;
}
}
for (int j = 0; j < parts; j++) {
int part = j;
threads[j] = worker.submit(() -> {
for (int k = part * partL;
k < (part + 1) * partL && k < arr.length;
k++) {
int chunk = (int) ((arr[k] >> (radix * 8)) & 255);
output[counts[part][chunk]] = arr[k];
counts[part][chunk]++;
}
});
}
barrier(parts, threads);
for (int j = 0; j < parts; j++) {
int part = j;
threads[j] = worker.submit(() -> {
for (int k = part * partL;
k < (part + 1) * partL && k < arr.length;
k++) {
arr[k] = output[k];
}
});
}
barrier(parts, threads);
}
worker.shutdownNow();
}
private static void barrier(int parts, Future[] threads) {
for (int j = 0; j < parts; j++) {
try {
threads[j].get();
} catch (InterruptedException | ExecutionException e) {
e.printStackTrace();
}
}
}
}
知道为什么 运行 这么慢吗？解决此优化的推荐方法是什么？
我真的很好奇答案。
谢谢！
更新
根据答案我改进了数据的局部性，所以现在它使用了所有的核心。更新了代码片段。以下是 2 核 4 线程的结果 CPU。
Java Parallel: 1130 ms
Radixsort Serial: 1218 ms
Radixsort Parallel: 625 ms
如果可以进一步改进，问题仍然悬而未决。
使用基数 2^16 = 65536 最终会有点慢，因为 L1 缓存通常每个内核 32768 字节，而基数 2^16 counts|indexes 数组每个使用 2^20 = 262144 字节。
基数排序的问题在于读取是顺序的，但写入与数据一样随机。根据评论，该程序正在对 2000 万个 long 进行排序，每个 8 个字节，因此 80 MB 的数据，假设 8MB L3 缓存，这些写入中的大部分将是缓存未命中。并行操作没有太大帮助，因为大多数写入都在竞争相同的 80 MB 非缓存主内存。
为了避免这个问题，我使用了另一种实现方式，其中第一遍执行最高有效数字基数排序以产生 256 个 bin（每个 bin 包含具有相同最高有效字节的整数）。然后使用传统的基数排序将最低有效位放在首位对每个 bin 进行排序。对于相当均匀的伪随机数据，256 个 bin 的大小几乎相等，因此 80MB 被分成 256 个 bin，每个大约 312500 字节，对于 4 个线程，有 8 个这样的 bin，4 个用于读取，4 个用于写入，加上计数|索引数组，所有这些都将放入所有 4 个内核通用的 8MB L3 16 路关联 L3 缓存中。
对于较大的阵列，初始遍可以将阵列拆分为 512 到 4096 或更多的箱。
我使用基数 2^8 = 256 对基数排序伪随机 64 位整数进行了一些测试。我测试了 3 个实现，单线程最低有效位，单线程最高有效位数字在前，四线线程最重要的数字在前。当整数个数为2的幂时，会导致一些缓存冲突，部分情况会影响时间。
16000000 - 8 个 bin + 索引数组适合 8MB L3 缓存。
16777216 = 2^24，8 个 bin + 索引数组适合 8MB L3 缓存。
30000000 - 8 个 bin + 索引数组适合 8MB L3 缓存。
33554432 = 2^25，8 个 bins + 索引数组略大于 8MB
36000000 - 8 个 bin + 比 8MB 大一点的索引数组。
Win 7 Pro 64 bit, VS 2015, Intel 3770K 3.5 ghz
count 1 thread LSD 1 thread MSD 4 thread MSD
16000000 0.59 0.38 0.16
16777216 1.35 0.48 0.30
30000000 0.82 0.70 0.30
33554432 3.20 1.09 0.68
36000000 0.95 0.82 0.39
Win 10 Pro 64 bit, VS 2019, Intel 10510U 1.8 ghz to 4.9 ghz
count 1 thread LSD 1 thread MSD 4 thread MSD
16000000 0.312 0.230 0.125
16777216 0.897 0.242 0.150
30000000 0.480 0.430 0.236
33554432 2.880 0.510 0.250
36000000 0.568 0.530 0.305