c - 使用多线程渲染图像

Question

我有一个光线跟踪算法，该算法仅适用于1个线程，而我正在尝试使其适用于任意数量的线程。

我的问题是，我可以通过哪种方式在线程之间分配此任务。

起初，我的讲师告诉我只是划分图像的宽度，例如，如果我有一个8x8图像，并且我想要2个线程来完成任务，则让线程1渲染0到3个水平区域(当然一直向下垂直)，线程2渲染4到7的水平区域。

当我的图像长度和线程数均为2的幂时，我发现这种方法可以完美地工作，但是我不知道如何处理奇数个线程或任何数量的线程而不能在没有提醒的情况下划分宽度。

我解决这个问题的方法是让线程交替显示图像，例如，如果我有一个8x8的图像，而让我说如果我有3个线程。

线程1在水平方向上渲染像素0、3、6

线程1在水平方向上渲染像素1,4,7

线程1在水平方向上渲染像素2,5

抱歉，我无法提供所有代码，因为每个文件中有5个以上的文件，几百行代码。

这是循环通过水平区域的for循环，而垂直循环位于这些循环的内部，但我将不在这里提供。

我的老师的建议

for( int px=(threadNum*(width/nthreads)); px < ((threadNum+1)*(width/nthreads)); ++px )

threadNum是我正在使用的当前线程(表示线程0,1,2，依此类推)
width是图像的宽度
nthreads是线程的总数。

我对这个问题的解决方案

for( int px= threadNum; px< width; px+=nthreads  )

我知道我的问题不太清楚，很抱歉，但是我不能在此处提供完整的代码，但是基本上我要问的是，哪种方法是在给定数量的线程之间划分图像呈现的最佳方法(可以是任何正数数字)。我也想让线程按列渲染图像，这意味着我不能碰到处理垂直渲染的代码部分。

谢谢，对于困惑的问题，我们深表歉意。

Answer 1

首先，让我告诉您，假设每个像素的渲染都与其他像素无关，那么您的任务就是在HPC字段中称为“令人尴尬的并行问题”；也就是说，可以在任意数量的线程之间有效地划分问题(直到每个线程具有单个“工作单元”)，而进程之间没有任何相互通信(这是很好的)。

就是说，这并不意味着任何并行化方案都比其他任何方案都好。对于您的特定问题，我想说要记住的两个主要因素是负载平衡和缓存效率。

负载平衡意味着您应按每个线程具有大致相同的工作量的方式在线程之间分配工作:这样，您可以防止一个或多个线程等待必须完成最后一个工作的最后一个线程。

例如。

您有5个线程，将图像分成5个大块(假设有5个水平条，但它们可能是垂直的，不会改变点)。作为并行处理的难题，您希望获得5倍的加速，而获得的却只有1.2倍。

原因可能是您的图像在图像的下部具有大部分计算上昂贵的细节(我不知道渲染，但我假设反射对象比平坦的空白空间要花更多的时间)，因为由一组抛光的金属大理石在一个空框架的地板上组成。

在这种情况下，只有一个线程(该线程的底部为图像的1/5)仍然可以完成所有工作，而其他4个线程在完成其简短任务后仍然处于空闲状态。

可以想象，这不是一个很好的并行化:仅考虑负载平衡，最好的并行化方案是在(非常合理的)假设下，将交错像素分配给每个核心以供它们处理。图像将在每个线程上平均(自然图像为真，在非常有限的情况下可能会产生意外)。

使用此解决方案，您的图像就可以均匀地分布在像素之间(统计上)，最坏的情况是N-1个线程在等待单个线程计算单个像素(就性能而言，您不会注意到)。

为此，您需要以这种方式遍历所有忘记行的像素(伪代码，未经测试):

for(i = thread_num; i < width * height; i+=thread_num)

第二个因素是 缓存效率处理计算机的设计方式，特别是它们具有多层缓存以加速计算并防止CPU饥饿(在等待数据时保持空闲状态)以及访问计算机中的数据。 “正确的方法”可以大大加快计算速度。

这是一个非常复杂的主题，但是在您的情况下，一条经验法则可能是“向每个线程提供正确数量的内存将改善计算”(强调“正确数量”的强调...)。

这意味着，即使传递给每个线程的像素都可能是完美的平衡，也可能是您可能设计的最糟糕的内存访问模式，并且应将“更大的块”传递给它们，因为这会使CPU忙(注意:内存要求也很重要:如果您的图片在每行之后都有填充，请保留它们的32字节的倍数，就像某些图片格式一样，您应该考虑它!!)

在不扩大对警报大小已经很冗长的答案的情况下，这就是我要做的(我假设图像的存储是连续的，行之间没有填充!):

创建一个程序，为M个线程中的每个线程将图像分成N个连续像素(使用预处理程序常量或N的命令参数，因此您可以更改它!)，如下所示:

1111111122222222333333334444444411111111

对N的各种值进行了一些分析，以2的幂次幂从1扩展到2048(要测试的好值可能是:1获得基线，32、64、128、256、512、1024 ，2048)

找出完美的平衡在完美的负载平衡(N = 1)和最佳缓存(N <=系统中最大的缓存行)之间的位置

和在一个以上的系统上尝试该程序，并保持N的smalles值，以使您在机器之间获得最佳的测试结果，以使您的代码在任何地方都可以快速运行(因为缓存细节因系统而异)。

b 如果您真的真的要从安装代码的每个系统中抽出每个周期，请忽略步骤4a，并创建一个代码，该代码通过在处理前渲染一个小的测试图像来自动找出N的最佳值。指定的任务:)

到处都是SIMD指令(只是在开玩笑...有点像:))

有点理论性(而且太长了...)，但我仍然希望它能有所帮助!