对我的程序进行多线程处理的负加速

Question

在配备Intel Pentium双核处理器T2370(Acer Extensa)的笔记本电脑上,我运行了一个简单的多线程加速测试.我正在使用Linux.代码粘贴在下面.虽然我期待加速2-3次,但我惊讶地发现速度减慢了2倍.我尝试了同样的gcc优化等级-O0 ... -O3,但每次我得到相同的结果.我正在使用pthreads.我也尝试了同样只有两个线程(而不是代码中的3个线程),但性能类似.

可能是什么原因？更快的版本需要相当长的时间 - 大约20秒 - 所以它似乎不是启动开销的问题.

注意:这个代码有很多错误(事实上它没有多大意义,因为串行和并行版本的输出会有所不同).目的只是"获得"相同数量指令的加速比较.

#include <stdio.h>
#include <time.h>
#include <unistd.h>
#include <pthread.h>

class Thread{
    private:
            pthread_t thread;
            static void *thread_func(void *d){((Thread *)d)->run();}
    public:
            Thread(){}
            virtual ~Thread(){}

            virtual void run(){}
            int start(){return pthread_create(&thread, NULL, Thread::thread_func, (void*)this);}
            int wait(){return pthread_join(thread, NULL);}
};


#include <iostream>

const int ARR_SIZE = 100000000;
const int N = 20;
int arr[ARR_SIZE];

int main(void)
{

    class Thread_a:public Thread{
            public:
                    Thread_a(int* a): arr_(a) {}
                    void run()
                    {
                            for(int n = 0; n<N; n++)
                            for(int i=0; i<ARR_SIZE/3; i++){ arr_[i] += arr_[i-1];}
                    }
            private:
                    int* arr_;
    };
    class Thread_b:public Thread{
            public:
                    Thread_b(int* a): arr_(a) {}
                    void run()
                    {
                            for(int n = 0; n<N; n++)
                            for(int i=ARR_SIZE/3; i<2*ARR_SIZE/3; i++){ arr_[i] += arr_[i-1];}
                    }
            private:
                    int* arr_;
    };

    class Thread_c:public Thread{
            public:
                    Thread_c(int* a): arr_(a) {}
                    void run()
                    {
                            for(int n = 0; n<N; n++)
                            for(int i=2*ARR_SIZE/3; i<ARR_SIZE; i++){ arr_[i] += arr_[i-1];}
                    }
            private:
                    int* arr_;
    };

    {
            Thread *a=new Thread_a(arr);
            Thread *b=new Thread_b(arr);
            Thread *c=new Thread_c(arr);

            clock_t start = clock();

            if (a->start() != 0) {
                    return 1;
            }

            if (b->start() != 0) {
                    return 1;
            }
            if (c->start() != 0) {
                    return 1;
            }

            if (a->wait() != 0) {
                    return 1;
            }

            if (b->wait() != 0) {
                    return 1;
            }

            if (c->wait() != 0) {
                    return 1;
            }

            clock_t end = clock();
            double duration = (double)(end - start) / CLOCKS_PER_SEC;

            std::cout << duration << "seconds\n";
            delete a;
            delete b;

    }
    {
            clock_t start = clock();
            for(int n = 0; n<N; n++)
            for(int i=0; i<ARR_SIZE; i++){ arr[i] += arr[i-1];}
            clock_t end = clock();
            double duration = (double)(end - start) / CLOCKS_PER_SEC;

            std::cout << "serial: " << duration << "seconds\n";
    }

    return 0;
  }

---

另请参阅:使用更多线程时,什么可以使程序运行得更慢？

Answer 1

您报告的时间是使用时钟功能测量的:

该clock()函数返回程序使用的处理器时间的近似值.

$ time bin/amit_kumar_threads.cpp
6.62seconds
serial: 2.7seconds

real    0m5.247s
user    0m9.025s
sys 0m0.304s

多处理器任务的实时时间会更短,但处理器时间通常会更长.

当您使用多个线程时,工作可能由多个处理器完成,但工作量相同,此外可能会有一些开销,例如争用有限的资源.clock()测量总处理器时间,这将是工作+任何争用开销.因此,它应该永远不会少于在单个线程中完成工作的处理器时间.

从问题中你是否知道这一点有点难以理解,并且惊讶于返回的值clock()是单个线程的两倍而不是仅仅多一点,或者你期望它更少.

clock_gettime()改为使用(你需要实时库librt g++ -lrt等)给出:

$ time bin/amit_kumar_threads.cpp
2.524 seconds
serial: 2.761 seconds

real    0m5.326s
user    0m9.057s
sys 0m0.344s

这仍然不像人们希望的那样加速,但至少这些数字是有道理的.

100000000*20/2.5s = 800Hz,总线频率为1600 MHz,所以我怀疑每次迭代都有读取和写入(假设有一些缓存),你的内存带宽有限,正如tstenner建议的那样,clock()值显示大多数某些处理器正在等待数据的时间.(有谁知道clock()时间是否包括这样的摊位？)

Answer 2

你的线程唯一做的就是添加一些元素,所以你的应用程序应该是IO绑定的.当你添加一个额外的线程时,你有2个CPU共享内存总线,所以它不会更快,相反,你将有缓存未命中等.

Answer 3

我相信你的算法本质上使你的缓存毫无用处。

您可能看到的是三个线程之间引用的（非）局部性的影响。本质上，因为每个线程都在与其他线程相距很远的不同数据部分上进行操作，所以当一个线程的数据部分替换了缓存中另一个线程的数据部分时，您会导致缓存未命中。如果您的程序被构造为使得线程对较小的数据部分（以便它们都可以保存在内存中）或更靠近的数据部分进行操作（以便所有线程可以使用相同的缓存内页面），您会看到性能提升。事实上，我怀疑您的速度变慢是因为必须从主内存而不是从缓存满足大量内存引用。