多线程程序中map模式的性能低于预期(4倍加速比8倍)

Question

我开始在多线程编程，所以请原谅我，如果以下似乎是显而易见的。我正在将多线程添加到图像处理程序中，而且加速比不是我所期望的那样。

目前，在具有超线程(8)的4个物理处理器cpu上，我得到了4倍的加速比，所以我想知道这种加速是否是预期的。我唯一能想到的是，如果单个物理CPU的两个超级线程必须共享某种内存总线，这可能是有意义的。

对于多线程来说，考虑到所有内存都是在RAM中分配的(我知道我的操作系统的虚拟内存管理器将决定从堆中分页/删除这个假定的内存数量)，我的机器有16 be的RAM，如果这有助于决定分页/交换是否是一个问题，我并不完全清楚。

我编写了一个测试程序，用QThreadPool和tbb::parallel_for展示了串行用例和两个并行用例

正如您所看到的，当前的程序没有真正的操作，只有从黑到白设置一个假定的图像，并且在对图像应用任何实际操作之前，它是有意知道基线是什么的。

我附加了这个程序，希望有人能解释我对大约8倍加速比的追求在这种处理算法中是一个失败的原因。请注意，我对其他类型的优化(比如SIMD )并不感兴趣，因为我真正关心的不仅仅是使它更快，而是使用纯多线程来使它更快，而不进入SSE或处理器缓存级别的优化。

#include <iostream>
#include <sys/time.h>

#include <vector>
#include <QThreadPool>
#include "/usr/local/include/tbb/tbb.h"

#define LOG(x) (std::cout << x << std::endl)

struct col4
{
    unsigned char r, g, b, a;
};

class QTileTask : public QRunnable
{
public:
    void run()
    {
        for(uint32_t y = m_yStart; y < m_yEnd; y++)
        {
            int rowStart = y * m_width;
            for(uint32_t x = m_xStart; x < m_xEnd; x++)
            {
                int index = rowStart + x;
                m_pData[index].r = 255;
                m_pData[index].g = 255;
                m_pData[index].b = 255;
                m_pData[index].a = 255;
            }
        }
    }

    col4*          m_pData;
    uint32_t       m_xStart;
    uint32_t       m_yStart;
    uint32_t       m_xEnd;
    uint32_t       m_yEnd;
    uint32_t       m_width;
};

struct TBBTileTask
{
    void operator()()
    {
        for(uint32_t y = m_yStart; y < m_yEnd; y++)
        {
            int rowStart = y * m_width;
            for(uint32_t x = m_xStart; x < m_xEnd; x++)
            {
                int index = rowStart + x;
                m_pData[index].r = 255;
                m_pData[index].g = 255;
                m_pData[index].b = 255;
                m_pData[index].a = 255;
            }
        }
    }

    col4*          m_pData;
    uint32_t       m_xStart;
    uint32_t       m_yStart;
    uint32_t       m_xEnd;
    uint32_t       m_yEnd;
    uint32_t       m_width;
};

struct TBBCaller
{
    TBBCaller(std::vector<TBBTileTask>& t)
        : m_tasks(t)
    {}

    TBBCaller(TBBCaller& e, tbb::split)
        : m_tasks(e.m_tasks)
    {}

    void operator()(const tbb::blocked_range<size_t>& r) const
    {
        for (size_t i=r.begin();i!=r.end();++i)
            m_tasks[i]();
    }

    std::vector<TBBTileTask>& m_tasks;
};

inline double getcurrenttime( void )
{
    timeval t;
    gettimeofday(&t, NULL);
    return static_cast<double>(t.tv_sec)+(static_cast<double>(t.tv_usec) / 1000000.0);
}

char* getCmdOption(char ** begin, char ** end, const std::string & option)
{
    char ** itr = std::find(begin, end, option);
    if (itr != end && ++itr != end)
    {
        return *itr;
    }
    return 0;
}

bool cmdOptionExists(char** begin, char** end, const std::string& option)
{
    return std::find(begin, end, option) != end;
}

void baselineSerial(col4* pData, int resolution)
{
    double t = getcurrenttime();
    for(int y = 0; y < resolution; y++)
    {
        int rowStart = y * resolution;
        for(int x = 0; x < resolution; x++)
        {
            int index = rowStart + x;
            pData[index].r = 255;
            pData[index].g = 255;
            pData[index].b = 255;
            pData[index].a = 255;
        }
    }
    LOG((getcurrenttime() - t) * 1000 << " ms. (Serial)");
}

void baselineParallelQt(col4* pData, int resolution, uint32_t tileSize)
{
    double t = getcurrenttime();

    QThreadPool pool;
    for(int y = 0; y < resolution; y+=tileSize)
    {
        for(int x = 0; x < resolution; x+=tileSize)
        {
            uint32_t xEnd = std::min<uint32_t>(x+tileSize, resolution);
            uint32_t yEnd = std::min<uint32_t>(y+tileSize, resolution);

            QTileTask* t = new QTileTask;
            t->m_pData = pData;
            t->m_xStart = x;
            t->m_yStart = y;
            t->m_xEnd = xEnd;
            t->m_yEnd = yEnd;
            t->m_width = resolution;
            pool.start(t);
        }
    }
    pool.waitForDone();
    LOG((getcurrenttime() - t) * 1000 << " ms. (QThreadPool)");
}

void baselineParallelTBB(col4* pData, int resolution, uint32_t tileSize)
{
    double t = getcurrenttime();

    std::vector<TBBTileTask> tasks;
    for(int y = 0; y < resolution; y+=tileSize)
    {
        for(int x = 0; x < resolution; x+=tileSize)
        {
            uint32_t xEnd = std::min<uint32_t>(x+tileSize, resolution);
            uint32_t yEnd = std::min<uint32_t>(y+tileSize, resolution);

            TBBTileTask t;
            t.m_pData = pData;
            t.m_xStart = x;
            t.m_yStart = y;
            t.m_xEnd = xEnd;
            t.m_yEnd = yEnd;
            t.m_width = resolution;
            tasks.push_back(t);
        }
    }

    TBBCaller caller(tasks);
    tbb::task_scheduler_init init;
    tbb::parallel_for(tbb::blocked_range<size_t>(0, tasks.size()), caller);

    LOG((getcurrenttime() - t) * 1000 << " ms. (TBB)");
}

int main(int argc, char** argv)
{
    int resolution = 1;
    uint32_t tileSize = 64;

    char * pResText = getCmdOption(argv, argv + argc, "-r");
    if (pResText)
    {
        resolution = atoi(pResText);
    }

    char * pTileSizeChr = getCmdOption(argv, argv + argc, "-b");
    if (pTileSizeChr)
    {
        tileSize = atoi(pTileSizeChr);
    }

    if(resolution > 16)
        resolution = 16;

    resolution = resolution << 10;

    uint32_t tileCount = resolution/tileSize + 1;
    tileCount *= tileCount;

    LOG("Resolution: " << resolution << " Tile Size: "<< tileSize);
    LOG("Tile Count: " << tileCount);

    uint64_t pixelCount = resolution*resolution;
    col4* pData = new col4[pixelCount];

    memset(pData, 0, sizeof(col4)*pixelCount);
    baselineSerial(pData, resolution);

    memset(pData, 0, sizeof(col4)*pixelCount);
    baselineParallelQt(pData, resolution, tileSize);

    memset(pData, 0, sizeof(col4)*pixelCount);
    baselineParallelTBB(pData, resolution, tileSize);

    delete[] pData;

    return 0;
}

Answer 1

是的，4倍的加速是预期的。Hypertreading是一种在硬件中实现的时间共享，因此，如果一个线程正在耗尽核心上所有可用的超标量管道，就像您的情况一样，您不能期望从它中获益。另一个线程必须等待。

如果您的内存总线带宽被运行在少于可用内核总数中的线程所饱和，那么您可以期待更低的加速速度。通常，如果你有太多的核心，比如在这个问题中：

Why doesn't this code scale linearly?