Skip to content

parallel_for_design

Jump to bottom
YangWC edited this page Apr 27, 2021 · 4 revisions

前言

此wiki记录渲染系统的parallel_for设计。渲染系统遍历需要渲染的像素窗口，从每个像素出发发射一条射线，与场景中的物体进行光路传输方程的计算。显然不同的像素之间没有依赖性，因此非常适合并行化，这里我们考虑基于cpu的多线程并行，利用多核来加速渲染进度。这对于离线渲染来说非常重要，因为极大的计算量使得每次渲染都需要等待很长一段时间，人生苦短！

尝试

目前已有不少c++的开源多线程库，例如tbb多线程库。tbb提供了非常友好的接口，能够非常便捷地进行多线程并行化。在这里我们只需要利用tbb::parallel_for就能够实现多线程并行化，但综合考虑下来，tbb对于当前的需求来说有点太过庞大，我们不需要非常复杂的并行化设计，只需要一个良好设计的parallel_for就够了！所以最终还是选择放弃用tbb，转而考虑自己用c++11标准的thread库来实现一个简便、高效的parallel_for函数！

在此之前，我们需要确定parallel_for的输入参数，一般来讲，我们希望函数输入三个参数，分别是：起始下标start，终止下标end，以及函数体func。我们希望在[start, end)之间的区间上并行执行函数func(i)，其中i取值[start, end)，在这里我们假定不同的func(i)之间无前后的数据依赖关系，可以直接并行化。

方案一

一个最简单的方案，就是根据当前cpu的核心数量，对输入的任务量end-start进行简单均匀地划分，为每个线程计算其相应负责的起始下标和终止下标，这样就能够把一个[start, end)之间的任务量分派给不同的线程，然后分别对各自的区间执行func，保证不同线程之间不会影响对方，实现的代码如下所示：

template<typename Callable>
static void parallel_for(size_t start, size_t end, Callable function)
{
	DCHECK(start < end);
	//Note: this parallel_for split the task in a simple averaging manner
	//      which is inefficient for inbalance task among threads
	const int n_threads = numSystemCores();
	const size_t n_task = end - start;

	const int n_max_tasks_per_thread = (n_task / n_threads) + (n_task % n_threads == 0 ? 0 : 1);
	const int n_lacking_tasks = n_max_tasks_per_thread * n_threads - n_task;

	auto inner_loop = [&](const int thread_index)
	{
		const int n_lacking_tasks_so_far = std::max(thread_index - n_threads + n_lacking_tasks, 0);
		const int inclusive_start_index = thread_index * n_max_tasks_per_thread - n_lacking_tasks_so_far;
		const int exclusive_end_index = inclusive_start_index + n_max_tasks_per_thread
			- (thread_index - n_threads + n_lacking_tasks >= 0 ? 1 : 0);

		for (int k = inclusive_start_index; k < exclusive_end_index; ++k)
		{
			function(k);
		}
	};
	std::vector<std::thread> threads;
	for (int j = 0; j < n_threads; ++j)
	{
		threads.push_back(std::thread(inner_loop, j));
	}
	for (auto& t : threads)
	{
		t.join();
	}
}

这种方案最大的问题在于负载不均衡。如果[start,end)之间的任务量相差无几，那么该方案能够实现非常不错的性能提升。但如果[start,end)任务量差别很大，那么上述的方案将导致不同线程之间负载差距过大，从而限制了性能效率的提升。举个简单的例子，假设两个线程A和B，分别分派了[start,mid)和[mid, end)的任务，其中[start,mid)的任务计算量很小（例如追踪光线只弹射到背景），而[mid,end)的任务计算量很大（例如追踪光线打到一个拥有非常复杂材质表面的几何体）。那么该方案将导致这样的一个的局面：线程A早早结束了自己的工作，然后一直等待B结束！

方案二

为此，为了使得线程之间能够比较均匀地负载工作，另一个方案就是采用原子计数抢占的方式来实现多线程并行化！这里用一个原子操作的变量来记录当前的任务下标（如下代码所示的task_index），对于每个线程，以抢占计数的方式来获取自己需要执行的任务。有点类似于一个任务队列，每次线程从队头获取一个任务然后执行；一个线程执行完之后，再从队头获取一个新的任务继续执行，直到队列为空！具体的逻辑见如下代码：

template<typename Callable>
static void parallel_for_seize(size_t start, size_t end, Callable func)
{
	DCHECK(start < end);
	//Note: this parallel_for assign the task to thread by atomic 
	//      opertion over task index which is more efficient in general case

	const int n_threads = numSystemCores();
	const size_t n_task = end - start;

	std::atomic<size_t> task_index(start);
	auto inner_loop = [&](const int thread_index)
	{
		size_t index;
		while ((index = task_index.fetch_add(1)) < end)
		{
			func(index);
		}
	};
	std::vector<std::thread> threads;
	for (int j = 0; j < n_threads; ++j)
	{
		threads.push_back(std::thread(inner_loop, j));
	}
	for (auto& t : threads)
	{
		t.join();
	}
}

这种方案代码反而更简洁，但对于大部分的情况都能够更加高效。当然这里假定一个任务func(i)的计算量不会太大也不会太小，这对于我们的分块光追渲染来说是成立的！当然也可修改上述的代码使得可以通过参数指定每次获取的任务粒度，这里不再赘述。

测试结果

这里做了简单的对比实验，分别用tbb::parallel_for、方案一和方案二测试对比渲染的时间，结果如下图所示：

可以看到方案一设置比tbb的还要快一点点，当然这是因为tbb的任务自动划分并非此应用场景下的最优。方案一明显慢于方案二，这里只是简单地测试了一下，场景更复杂、采样数量更多时他们的差距会更大！最后贴一下没有多线程加速的时间耗费：

测试的电脑为本人的渣渣笔记本，cpu为i5-8265U（4核8线程），加速前后的时间比接近1:4，非常接近理想的最大加速比！

Clone this wiki locally