c - 多线程如何提供大于内核数量的加速因子？

Question

我在 gcc 中使用 pthreads。简单的代码示例将线程数“N”作为用户提供的输入。它将一个长数组拆分为 N 个大小大致相等的子 block 。每个子 block 都由单独的线程写入。

此示例的虚拟处理实际上涉及为每个数组索引休眠一段固定的时间，然后将一个数字写入该数组位置。

代码如下:

/******************************************************************************
* FILE: threaded_subblocks_processing
* DESCRIPTION:
* We have a bunch of parallel processing to do and store the results in a
* large array. Let's try to use threads to speed it up.
******************************************************************************/
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <math.h>

#define BIG_ARR_LEN 10000

typedef struct thread_data{
  int start_idx;
  int end_idx;
  int id;
} thread_data_t;

int big_result_array[BIG_ARR_LEN] = {0};

void* process_sub_block(void *td)
{
   struct thread_data *current_thread_data = (struct thread_data*)td;
   printf("[%d] Hello World! It's me, thread #%d!\n", current_thread_data->id, current_thread_data->id);
   printf("[%d] I'm supposed to work on indexes %d through %d.\n", current_thread_data->id, 
       current_thread_data->start_idx, 
       current_thread_data->end_idx-1);

   for(int i=current_thread_data->start_idx; i<current_thread_data->end_idx; i++)
   {
       int retval = usleep(1000.0*1000.0*10.0/BIG_ARR_LEN);
       if(retval)
       {
         printf("sleep failed");
       }

       big_result_array[i] = i;
   }

   printf("[%d] Thread #%d done, over and out!\n", current_thread_data->id, current_thread_data->id);
   pthread_exit(NULL);
}

int main(int argc, char *argv[])
{
   if (argc!=2)
   {
     printf("usage: ./a.out number_of_threads\n");
     return(1);
   }

   int NUM_THREADS = atoi(argv[1]);

   if (NUM_THREADS<1)
   {
     printf("usage: ./a.out number_of_threads (where number_of_threads is at least 1)\n");
     return(1);
   }

   pthread_t *threads = malloc(sizeof(pthread_t)*NUM_THREADS);
   thread_data_t *thread_data_array = malloc(sizeof(thread_data_t)*NUM_THREADS);

   int block_size = BIG_ARR_LEN/NUM_THREADS;
   for(int i=0; i<NUM_THREADS-1; i++)
   {
     thread_data_array[i].start_idx = i*block_size;
     thread_data_array[i].end_idx = (i+1)*block_size;
     thread_data_array[i].id = i;
   }
   thread_data_array[NUM_THREADS-1].start_idx = (NUM_THREADS-1)*block_size;
   thread_data_array[NUM_THREADS-1].end_idx = BIG_ARR_LEN;
   thread_data_array[NUM_THREADS-1].id = NUM_THREADS;

   int ret_code;
   long t;
   for(t=0;t<NUM_THREADS;t++){
     printf("[main] Creating thread %ld\n", t);
     ret_code = pthread_create(&threads[t], NULL, process_sub_block, (void *)&thread_data_array[t]);
     if (ret_code){
       printf("[main] ERROR; return code from pthread_create() is %d\n", ret_code);
       exit(-1);
       }
     }

   printf("[main] Joining threads to wait for them.\n");
   void* status;
   for(int i=0; i<NUM_THREADS; i++)
   {
     pthread_join(threads[i], &status);
   }

   pthread_exit(NULL);
}

然后我编译它

gcc -pthread threaded_subblock_processing.c

然后我像这样从命令行调用它:

$ time ./a.out 4

当我增加线程数时，我发现速度有所提高。使用 1 个线程，该过程仅需 10 秒多一点。这是有道理的，因为我为每个数组元素睡 1000 微秒，并且有 10,000 个数组元素。接下来，当我转到 2 个线程时，它会下降到 5 秒多一点，依此类推。

我不明白的是，即使我的线程数超过了我计算机上的内核数，我的速度仍然提高了!我有 4 个内核，所以我预计 >4 个线程不会加速。但是，令人惊讶的是，当我运行时

$ time ./a.out 100

我得到了 100 倍的加速，并且处理在大约 0.1 秒内完成!这怎么可能？

Answer 1

一些一般背景

很多事情都会减慢程序的进度，但一般来说，您可以将减慢点(也称为热点)分为两类:

• CPU Bound:在这种情况下，处理器正在执行一些繁重的数字运算(如三角函数)。如果 CPU 的所有内核都在执行此类任务，则其他进程必须等待。

• 内存限制:在这种情况下，处理器正在等待从硬盘或 RAM 中检索信息。由于这些通常比处理器慢几个数量级，因此从 CPU 的角度来看，这需要永远。

但您也可以想象进程必须等待的其他情况，例如网络响应。

在许多这些受内存/网络限制的情况下，可以在内存向 CPU 爬行时将线程“暂停”并同时执行其他有用的工作。如果这一点做得好，那么多线程程序可以很好地胜过它的单线程程序。 Node.js 利用这种异步编程 技术来实现良好的性能。

这是对各种延迟的简单描述:

您的问题

现在，回到您的问题:您有多个线程在运行，但它们既不执行 CPU 密集型工作也不执行内存密集型工作:没有太多时间可以占用。事实上， sleep 功能本质上是在告诉操作系统没有工作正在完成。在这种情况下，操作系统可以在您的线程休眠时在其他线程中工作。因此，表观性能自然会显着提高。

请注意，对于低延迟应用程序，例如 MPI，busy waiting 有时是 used 而不是 sleep 函数。在这种情况下，程序会进入一个紧密循环并反复检查条件。从外部看，效果看起来相似，但 sleep 不使用 CPU，而忙等待使用约 100% 的 CPU。