Sieve of Eratosthenes Pthread 实现：线程数不影响计算时间
Sieve of Eratosthenes Pthread implementation: thread number doesn't affect computation time
我正在尝试使用 Pthread 实现并行的埃拉托色尼筛法程序。我已经完成了我的编码并且程序按预期正常工作，这意味着如果我使用 1 个以上的线程，计算时间将少于顺序程序（仅使用 1 个线程）。然而，无论我使用多少额外线程，计算时间基本相同。例如，如果我从 1 计算到 10 亿，顺序程序使用了大约 21 秒，而具有 2 个线程的并行程序使用了大约 14 秒。但是当我尝试使用 3、4、5、10、20、50 个线程时，它总是需要大约 14 秒。我想知道是什么导致了这个问题以及如何解决它。我的代码如下：
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//The group of arguments passed to thread
struct thrd_data{
long id;
long start;
long end; /* the sub-range is from start to end */
};
typedef struct {
pthread_mutex_t count_lock; /* mutex semaphore for the barrier */
pthread_cond_t ok_to_proceed; /* condition variable for leaving */
long count; /* count of the number of threads who have arrived */
} mylib_barrier_t;
//global variable
bool *GlobalList;//The list of nature number
long Num_Threads;
mylib_barrier_t barrier;/* barrier */
void mylib_barrier_init(mylib_barrier_t *b)
{
b -> count = 0;
pthread_mutex_init(&(b -> count_lock), NULL);
pthread_cond_init(&(b -> ok_to_proceed), NULL);
}
void mylib_barrier(mylib_barrier_t *b, long id)
{
pthread_mutex_lock(&(b -> count_lock));
b -> count ++;
if (b -> count == Num_Threads)
{
b -> count = 0; /* must be reset for future re-use */
pthread_cond_broadcast(&(b -> ok_to_proceed));
}
else
{
while (pthread_cond_wait(&(b -> ok_to_proceed), &(b -> count_lock)) != 0);
}
pthread_mutex_unlock(&(b -> count_lock));
}
void mylib_barrier_destroy(mylib_barrier_t *b)
{
pthread_mutex_destroy(&(b -> count_lock));
pthread_cond_destroy(&(b -> ok_to_proceed));
}
void *DoSieve(void *thrd_arg)
{
struct thrd_data *t_data;
long i,start, end;
long k=2;//The current prime number in first loop
long myid;
/* Initialize my part of the global array */
t_data = (struct thrd_data *) thrd_arg;
myid = t_data->id;
start = t_data->start;
end = t_data->end;
printf ("Thread %ld doing look-up from %ld to %ld\n", myid,start,end);
//First loop: find all prime numbers that's less than sqrt(n)
while (k*k<=end)
{
int flag;
if(k*k>=start)
flag=0;
else
flag=1;
//Second loop: mark all multiples of current prime number
for (i = !flag? k*k-1:start+k-start%k-1; i <= end; i += k)
GlobalList[i] = 1;
i=k;
//wait for other threads to finish the second loop for current prime number
mylib_barrier(&barrier,myid);
//find next prime number that's greater than current one
while (GlobalList[i] == 1)
i++;
k = i+1;
}
//decrement the counter of threads before exit
pthread_mutex_lock (&barrier.count_lock);
Num_Threads--;
if (barrier.count == Num_Threads)
{
barrier.count = 0; /* must be reset for future re-use */
pthread_cond_broadcast(&(barrier.ok_to_proceed));
}
pthread_mutex_unlock (&barrier.count_lock);
pthread_exit(NULL);
}
int main(int argc, char *argv[])
{
long i, n,n_threads;
long k, nq, nr;
FILE *results;
struct thrd_data *t_arg;
pthread_t *thread_id;
pthread_attr_t attr;
/* Pthreads setup: initialize barrier and explicitly create
threads in a joinable state (for portability) */
mylib_barrier_init(&barrier);
pthread_attr_init(&attr);
pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
/* ask to enter n and n_threads from the user */
printf ("enter the range n = ");
scanf ("%ld", &n);
printf ("enter the number of threads n_threads = ");
scanf ("%ld", &n_threads);
time_t start = time(0);//set initial time
//Initialize global list
GlobalList=(bool *)malloc(sizeof(bool)*n);
for(i=0;i<n;i++)
GlobalList[i]=0;
/* create arrays of thread ids and thread args */
thread_id = (pthread_t *)malloc(sizeof(pthread_t)*n_threads);
t_arg = (struct thrd_data *)malloc(sizeof(struct thrd_data)*n_threads);
/* distribute load and create threads for computation */
nq = n / n_threads;
nr = n % n_threads;
k = 1;
Num_Threads=n_threads;
for (i=0; i<n_threads; i++){
t_arg[i].id = i;
t_arg[i].start = k;
if (i < nr)
k = k + nq + 1;
else
k = k + nq;
t_arg[i].end = k-1;
pthread_create(&thread_id[i], &attr, DoSieve, (void *) &t_arg[i]);
}
/* Wait for all threads to complete then print all prime numbers */
for (i=0; i<n_threads; i++) {
pthread_join(thread_id[i], NULL);
}
int j=1;
//Get the spent time for the computation works by all participanting threads
time_t stop = time(0);
printf("Time to do everything except print = %lu seconds\n", (unsigned long) (stop-start));
//print the result of prime numbers
printf("The prime numbers are listed below:\n");
for (i = 1; i < n; i++)
{
if (GlobalList[i] == 0)
{
printf("%ld ", i + 1);
j++;
}
if (j% 15 == 0)
printf("\n");
}
printf("\n");
// Clean up and exit
free(GlobalList);
pthread_attr_destroy(&attr);
mylib_barrier_destroy(&barrier); // destroy barrier object
pthread_exit (NULL);
}
你的观察很有道理。更多线程并不意味着完成更多工作。
你是 运行 你在双核上编程 CPU。您已经用 2 个线程使系统饱和。
1 个线程只使用 1 个内核。使用 2 个线程将使用 2 个内核。假设有 4 个线程，您将看到与 2 个线程大致相同的性能。超线程没有帮助，因为逻辑核心（HT 核心）与其物理核心共享内存系统。
这是 运行
的输出
perf stat -d sieve
23879.553188 task-clock (msec) # 1.191 CPUs utilized
3,666 context-switches # 0.154 K/sec
1,470 cpu-migrations # 0.062 K/sec
219,177 page-faults # 0.009 M/sec
76,070,790,848 cycles # 3.186 GHz
<not supported> stalled-cycles-frontend
<not supported> stalled-cycles-backend
34,500,622,236 instructions # 0.45 insns per cycle
4,172,395,541 branches # 174.727 M/sec
1,020,010 branch-misses # 0.02% of all branches
21,065,385,093 L1-dcache-loads # 882.152 M/sec
1,223,920,596 L1-dcache-load-misses # 5.81% of all L1-dcache hits
69,357,488 LLC-loads # 2.904 M/sec
<not supported> LLC-load-misses:HG
这是 i5-4460 CPU 的硬件性能监视器的输出。它跟踪一些有趣的统计数据。
请注意每个周期的指令计数较低。 cpu 每个周期执行 0.45 条指令。通常你希望看到这个值 > 1.
更新：这里要注意的关键是增加线程数没有帮助。 CPU 只能进行有限数量的分支和内存访问。
两个观察结果。
首先，如果您修复筛选代码，那么它应该 运行 比现在快大约 25 倍，大致对应于将当前代码成功分布到 32 个内核上的预期收益。
看看 prime number summing still slow after using sieve，我在其中展示了如何在所有语言的 C# 中在 1.25 秒内筛选最多 2,000,000,000 个数字。本文分别讨论（和基准测试）每个 step/technique，以便您选择自己喜欢的并推出一个解决方案，以达到满足您需求的完美 bang/buck 比率。在 C/C++ 中事情会更快，因为你可以指望编译器为你处理这些小东西（至少对于像 gcc 或 VC++ 这样的优秀编译器）。
其次：筛选大范围时最重要的资源是CPU的一级缓存。其他一切都排在第二位 fiddle。您也可以从我文章中的基准测试中看到这一点。要在多个 CPU 之间分配筛选任务，请计算系统中的 L1 缓存并将筛选作业分配给每个缓存（范围的 1/k，其中 k 是 L1 缓存的数量）。这有点简化，因为您通常会为工作项的大小选择更精细的粒度，但它给出了总体思路。
我说的是 'caches'，而不是 'cores'、'virtual cores' 或 'threads'，因为这正是您需要做的：分配工作，使每个工作都有自己的职责自己的一级缓存。它的工作原理不仅取决于操作系统，还取决于系统中特定的 CPU(s)。如果两个 'whatevers' 共享一个 L1 缓存，则仅将作业分配给两者中的一个并忽略另一个（或者更确切地说，设置作业的关联性，使其可以 运行 在两个中的任何一个上但别无他处）。
这对于操作系统 API（例如 Win32）来说很容易，但我对 pthreads 的了解还不够，无法判断它是否提供了所需的精度。作为第一个近似值，您可以将线程数与怀疑的 L1 缓存数相匹配。
我正在尝试使用 Pthread 实现并行的埃拉托色尼筛法程序。我已经完成了我的编码并且程序按预期正常工作，这意味着如果我使用 1 个以上的线程，计算时间将少于顺序程序（仅使用 1 个线程）。然而，无论我使用多少额外线程，计算时间基本相同。例如，如果我从 1 计算到 10 亿，顺序程序使用了大约 21 秒，而具有 2 个线程的并行程序使用了大约 14 秒。但是当我尝试使用 3、4、5、10、20、50 个线程时，它总是需要大约 14 秒。我想知道是什么导致了这个问题以及如何解决它。我的代码如下：
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//The group of arguments passed to thread
struct thrd_data{
long id;
long start;
long end; /* the sub-range is from start to end */
};
typedef struct {
pthread_mutex_t count_lock; /* mutex semaphore for the barrier */
pthread_cond_t ok_to_proceed; /* condition variable for leaving */
long count; /* count of the number of threads who have arrived */
} mylib_barrier_t;
//global variable
bool *GlobalList;//The list of nature number
long Num_Threads;
mylib_barrier_t barrier;/* barrier */
void mylib_barrier_init(mylib_barrier_t *b)
{
b -> count = 0;
pthread_mutex_init(&(b -> count_lock), NULL);
pthread_cond_init(&(b -> ok_to_proceed), NULL);
}
void mylib_barrier(mylib_barrier_t *b, long id)
{
pthread_mutex_lock(&(b -> count_lock));
b -> count ++;
if (b -> count == Num_Threads)
{
b -> count = 0; /* must be reset for future re-use */
pthread_cond_broadcast(&(b -> ok_to_proceed));
}
else
{
while (pthread_cond_wait(&(b -> ok_to_proceed), &(b -> count_lock)) != 0);
}
pthread_mutex_unlock(&(b -> count_lock));
}
void mylib_barrier_destroy(mylib_barrier_t *b)
{
pthread_mutex_destroy(&(b -> count_lock));
pthread_cond_destroy(&(b -> ok_to_proceed));
}
void *DoSieve(void *thrd_arg)
{
struct thrd_data *t_data;
long i,start, end;
long k=2;//The current prime number in first loop
long myid;
/* Initialize my part of the global array */
t_data = (struct thrd_data *) thrd_arg;
myid = t_data->id;
start = t_data->start;
end = t_data->end;
printf ("Thread %ld doing look-up from %ld to %ld\n", myid,start,end);
//First loop: find all prime numbers that's less than sqrt(n)
while (k*k<=end)
{
int flag;
if(k*k>=start)
flag=0;
else
flag=1;
//Second loop: mark all multiples of current prime number
for (i = !flag? k*k-1:start+k-start%k-1; i <= end; i += k)
GlobalList[i] = 1;
i=k;
//wait for other threads to finish the second loop for current prime number
mylib_barrier(&barrier,myid);
//find next prime number that's greater than current one
while (GlobalList[i] == 1)
i++;
k = i+1;
}
//decrement the counter of threads before exit
pthread_mutex_lock (&barrier.count_lock);
Num_Threads--;
if (barrier.count == Num_Threads)
{
barrier.count = 0; /* must be reset for future re-use */
pthread_cond_broadcast(&(barrier.ok_to_proceed));
}
pthread_mutex_unlock (&barrier.count_lock);
pthread_exit(NULL);
}
int main(int argc, char *argv[])
{
long i, n,n_threads;
long k, nq, nr;
FILE *results;
struct thrd_data *t_arg;
pthread_t *thread_id;
pthread_attr_t attr;
/* Pthreads setup: initialize barrier and explicitly create
threads in a joinable state (for portability) */
mylib_barrier_init(&barrier);
pthread_attr_init(&attr);
pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
/* ask to enter n and n_threads from the user */
printf ("enter the range n = ");
scanf ("%ld", &n);
printf ("enter the number of threads n_threads = ");
scanf ("%ld", &n_threads);
time_t start = time(0);//set initial time
//Initialize global list
GlobalList=(bool *)malloc(sizeof(bool)*n);
for(i=0;i<n;i++)
GlobalList[i]=0;
/* create arrays of thread ids and thread args */
thread_id = (pthread_t *)malloc(sizeof(pthread_t)*n_threads);
t_arg = (struct thrd_data *)malloc(sizeof(struct thrd_data)*n_threads);
/* distribute load and create threads for computation */
nq = n / n_threads;
nr = n % n_threads;
k = 1;
Num_Threads=n_threads;
for (i=0; i<n_threads; i++){
t_arg[i].id = i;
t_arg[i].start = k;
if (i < nr)
k = k + nq + 1;
else
k = k + nq;
t_arg[i].end = k-1;
pthread_create(&thread_id[i], &attr, DoSieve, (void *) &t_arg[i]);
}
/* Wait for all threads to complete then print all prime numbers */
for (i=0; i<n_threads; i++) {
pthread_join(thread_id[i], NULL);
}
int j=1;
//Get the spent time for the computation works by all participanting threads
time_t stop = time(0);
printf("Time to do everything except print = %lu seconds\n", (unsigned long) (stop-start));
//print the result of prime numbers
printf("The prime numbers are listed below:\n");
for (i = 1; i < n; i++)
{
if (GlobalList[i] == 0)
{
printf("%ld ", i + 1);
j++;
}
if (j% 15 == 0)
printf("\n");
}
printf("\n");
// Clean up and exit
free(GlobalList);
pthread_attr_destroy(&attr);
mylib_barrier_destroy(&barrier); // destroy barrier object
pthread_exit (NULL);
}
你的观察很有道理。更多线程并不意味着完成更多工作。
你是 运行 你在双核上编程 CPU。您已经用 2 个线程使系统饱和。
1 个线程只使用 1 个内核。使用 2 个线程将使用 2 个内核。假设有 4 个线程，您将看到与 2 个线程大致相同的性能。超线程没有帮助，因为逻辑核心（HT 核心）与其物理核心共享内存系统。
这是 运行
的输出perf stat -d sieve
23879.553188 task-clock (msec) # 1.191 CPUs utilized
3,666 context-switches # 0.154 K/sec
1,470 cpu-migrations # 0.062 K/sec
219,177 page-faults # 0.009 M/sec
76,070,790,848 cycles # 3.186 GHz
<not supported> stalled-cycles-frontend
<not supported> stalled-cycles-backend
34,500,622,236 instructions # 0.45 insns per cycle
4,172,395,541 branches # 174.727 M/sec
1,020,010 branch-misses # 0.02% of all branches
21,065,385,093 L1-dcache-loads # 882.152 M/sec
1,223,920,596 L1-dcache-load-misses # 5.81% of all L1-dcache hits
69,357,488 LLC-loads # 2.904 M/sec
<not supported> LLC-load-misses:HG
这是 i5-4460 CPU 的硬件性能监视器的输出。它跟踪一些有趣的统计数据。
请注意每个周期的指令计数较低。 cpu 每个周期执行 0.45 条指令。通常你希望看到这个值 > 1.
更新：这里要注意的关键是增加线程数没有帮助。 CPU 只能进行有限数量的分支和内存访问。
两个观察结果。
首先，如果您修复筛选代码，那么它应该 运行 比现在快大约 25 倍，大致对应于将当前代码成功分布到 32 个内核上的预期收益。
看看 prime number summing still slow after using sieve，我在其中展示了如何在所有语言的 C# 中在 1.25 秒内筛选最多 2,000,000,000 个数字。本文分别讨论（和基准测试）每个 step/technique，以便您选择自己喜欢的并推出一个解决方案，以达到满足您需求的完美 bang/buck 比率。在 C/C++ 中事情会更快，因为你可以指望编译器为你处理这些小东西（至少对于像 gcc 或 VC++ 这样的优秀编译器）。
其次：筛选大范围时最重要的资源是CPU的一级缓存。其他一切都排在第二位 fiddle。您也可以从我文章中的基准测试中看到这一点。要在多个 CPU 之间分配筛选任务，请计算系统中的 L1 缓存并将筛选作业分配给每个缓存（范围的 1/k，其中 k 是 L1 缓存的数量）。这有点简化，因为您通常会为工作项的大小选择更精细的粒度，但它给出了总体思路。
我说的是 'caches'，而不是 'cores'、'virtual cores' 或 'threads'，因为这正是您需要做的：分配工作，使每个工作都有自己的职责自己的一级缓存。它的工作原理不仅取决于操作系统，还取决于系统中特定的 CPU(s)。如果两个 'whatevers' 共享一个 L1 缓存，则仅将作业分配给两者中的一个并忽略另一个（或者更确切地说，设置作业的关联性，使其可以 运行 在两个中的任何一个上但别无他处）。
这对于操作系统 API（例如 Win32）来说很容易，但我对 pthreads 的了解还不够，无法判断它是否提供了所需的精度。作为第一个近似值，您可以将线程数与怀疑的 L1 缓存数相匹配。