程序正在对前 10,000 个整数求和。
这是单线程程序
#include <stdio.h>
#include <time.h>
int main() {
int sum = 0;
clock_t start, end;
double cpu_time_used;
start = clock();
for (int i = 1; i <= 10000; i++) {
sum += i;
}
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("Sum of first 10000 positive integers: %d\n", sum);
printf("Time taken: %f seconds\n", cpu_time_used);
return 0;
}
这是多线程的对应部分;我将工作平均分配给 4 个线程
#include <stdio.h>
#include <pthread.h>
#include <time.h>
#define NUM_THREADS 4
#define ARRAY_SIZE 10000
int sum = 0;
int partialSums[NUM_THREADS] = {0};
void *calculateSum(void *threadid) {
long tid;
tid = (long)threadid;
int chunkSize = ARRAY_SIZE / NUM_THREADS;
int start = tid * chunkSize + 1;
int end = (tid + 1) * chunkSize;
for (int i = start; i <= end; i++) {
partialSums[tid] += i;
}
pthread_exit(NULL);
}
int main() {
pthread_t threads[NUM_THREADS];
int rc;
long t;
clock_t start, end;
double cpu_time_used;
start = clock();
for (t = 0; t < NUM_THREADS; t++) {
rc = pthread_create(&threads[t], NULL, calculateSum, (void *)t);
if (rc) {
printf("ERROR; return code from pthread_create() is %d\n", rc);
return -1;
}
}
for (t = 0; t < NUM_THREADS; t++) {
pthread_join(threads[t], NULL);
}
for (int i = 0; i < NUM_THREADS; i++) {
sum += partialSums[i];
}
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("Sum of first 10000 positive integers: %d\n", sum);
printf("Time taken: %f seconds\n", cpu_time_used);
pthread_exit(NULL);
}
单线程程序平均需要 0.000019 秒,而多线程程序大约需要 0.000300 秒
这是为什么呢?什么时候多线程程序比单线程程序性能更高?我们什么时候应该使用它?
PS:我应该如何比较它们的执行时间,因为我听说使用时钟有时会输出错误的值;特别是在大负载下?
答案是不言而喻的:您正在尝试并行化一个问题,其单线程解决方案比通过并行化产生的开销更快。
这是通常的情况。想一想:2 GHz CPU 的 10,000 个整数通常可以实现每个时钟周期 1 条整数指令的吞吐量1,除了内存访问开销之外,这还需要 10,000 / (2 GHz) = 5 µs。通常,与计算所需的时间相比,获取基准测试当前时间的开销和不确定性要大得多!
启动一个新线程需要超过5 µs;使用多写入器安全结构或线程之间的跨核心原子进行通信(这是
pthread_join
需要做的)需要更长的时间。
在这种粒度上的并行性是没有意义的。遇到更大的问题了!例如,如果每秒有一亿个整数进入,并且在您的应用处理器(即英特尔、AMD 或现代处理器)上执行的不仅仅是求和(这实际上是数量级,我们在软件定义的无线电中执行此操作) ARM 处理器),那么如果您的目标是性能,那么将多个缓存行大小的块中的“解交错”求和到多个处理器核心可能会开始有意义。请注意,对于简单的加法情况,您的问题通常不是 CPU 性能,而是内存带宽,因此即使在通信开销为零的完美世界中您也无法通过将求和分布在多个 CPU 核心上来加快求和速度; CPU 核心不是瓶颈。
一般来说,您通常不会并行化基本指令;这对于缓存局部性来说非常糟糕:假设您想在求和之前对这些数字进行一些其他操作(例如,将它们除以其他数字),那么您将获得需要在核心之间进行洗牌的中间结果。
¹ “吞吐量”在这里指的是:在执行此操作时,我的 CPU 在每个时钟周期平均完成多少次操作。这是衡量一条指令完成需要多少周期的不同方法,因为 CPU 有“管道”,即为什么第一个指令仍在计算,下一个指令仍在处理(事实上,它通常远远超过 2 条指令)。
请注意,每个周期 1 个整数求和是一个“非常”保守的估计。现代 x86_64 CPU 以 1/3 的吞吐量执行“这对 8 个 32 位整数相加”(_mm256_add_epi32
),这意味着每 3 个周期获得 8 次求和,即在 2 GHz 时每秒超过 50 亿次加法。大致就像这样演示;
并行化在很多方面都有开销。一是操作系统启动线程、线程切换和终止线程需要时间。如果你的单线程程序花费的时间比启动线程的恒定时间少,那么单线程程序会更快。