本节书摘来自华章计算机《CUDA C编程权威指南》一书中的第3章，第3.6节，作者 [美] 马克斯·格罗斯曼（Max Grossman），译 颜成钢 殷建 李亮，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
3.6 动态并行
在本书中，到目前为止，所有核函数都是从主机线程中被调用的。GPU的工作负载完全在CPU的控制下。CUDA的动态并行允许在GPU端直接创建和同步新的GPU内核。在一个核函数中在任意点动态增加GPU应用程序的并行性，是一个令人兴奋的新功能。
到目前为止，我们需要把算法设计为单独的、大规模数据并行的内核启动。动态并行提供了一个更有层次结构的方法，在这个方法中，并发性可以在一个GPU内核的多个级别中表现出来。使用动态并行可以让递归算法更加清晰易懂，也更容易理解。
有了动态并行，可以推迟到运行时决定需要在GPU上创建多少个块和网格，可以动态地利用GPU硬件调度器和加载平衡器，并进行调整以适应数据驱动或工作负载。
在GPU端直接创建工作的能力可以减少在主机和设备之间传输执行控制和数据的需求，因为在设备上执行的线程可以在运行时决定启动配置。
在本节中，将通过使用动态并行实现递归归约核函数的例子，对如何利用动态并行有一个基本的了解。
3.6.1 嵌套执行
通过动态并行，我们已经熟悉了内核执行的概念（网格、块、启动配置等），也可以直接在GPU上进行内核调用。相同的内核调用语法被用在一个内核内启动一个新的核函数。
在动态并行中，内核执行分为两种类型：父母和孩子。父线程、父线程块或父网格启动一个新的网格，即子网格。子线程、子线程块或子网格被父母启动。子网格必须在父线程、父线程块或父网格完成之前完成。只有在所有的子网格都完成之后，父母才会完成。
图3-26说明了父网格和子网格的适用范围。主机线程配置和启动父网格，父网格配置和启动子网格。子网格的调用和完成必须进行适当地嵌套，这意味着在线程创建的所有子网格都完成之后，父网格才会完成。如果调用的线程没有显式地同步启动子网格，那么运行时保证父母和孩子之间的隐式同步。在图3-26中，在父线程中设置了栅栏，从而可以与其子网格显式地同步。
设备线程中的网格启动，在线程块间是可见的。这意味着，线程可能与由该线程启动的或由相同线程块中其他线程启动的子网格同步。在线程块中，只有当所有线程创建的所有子网格完成之后，线程块的执行才会完成。如果块中所有线程在所有的子网格完成之前退出，那么在那些子网格上隐式同步会被触发。
当父母启动一个子网格，父线程块与孩子显式同步之后，孩子才能开始执行。
父网格和子网格共享相同的全局和常量内存存储，但它们有不同的局部内存和共享内存。有了孩子和父母之间的弱一致性作为保证，父网格和子网格可以对全局内存并发存取。有两个时刻，子网格和它的父线程见到的内存完全相同：子网格开始时和子网格完成时。当父线程优于子网格调用时，所有的全局内存操作要保证对子网格是可见的。当父母在子网格完成时进行同步操作后，子网格所有的内存操作应保证对父母是可见的。
共享内存和局部内存分别对于线程块或线程来说是私有的，同时，在父母和孩子之间不是可见或一致的。局部内存对线程来说是私有存储，并且对该线程外部不可见。当启动一个子网格时，向局部内存传递一个指针作为参数是无效的。
3.6.2 在GPU上嵌套Hello World
在Wrox.com上可以下载nestedHelloWorld.cu文件，里面有本例的所有代码。可以用以下命令编译代码：
因为动态并行是由设备运行时库所支持的，所以nestedHelloWorld函数必须在命令行使用-lcudadevrt进行明确链接。
当-rdc标志为true时，它强制生成可重定位的设备代码，这是动态并行的一个要求。在本书的第10章将会介绍到更多可重定位设备代码的内容。
嵌套核函数的输出如下：
从输出信息中可见，由主机调用的父网格有1个线程块和8个线程。nestedHelloWorld核函数递归地调用三次，每次调用的线程数是上一次的一半。可以用nvvp工具通过以下的命令证明这一点：
图3-28所示为由nvvp显示的嵌套执行。子网格被适当地嵌套，并且每个父网格会等待直到它的子网格执行结束，空白处说明内核在等待子网格执行结束。
现在，试着使用两个线程块调用父网格，而不是使用一个。
嵌套内核程序的输出如下：
为什么在输出信息里所有子网格线程块的ID都是0？图3-29说明了子网格是如何被两个初始线程块递归调用的。父网格包含两个线程块，所有嵌套的子网格仍然只包含一个线程块，这是由于线程配置核函数在nestedHelloWorld函数里启动：
可以尝试使用不同的启动策略。图3-30所示为另一种生成相同数量并行性的方法，这一部分留给读者作为练习。
3.6.3 嵌套归约
归约可以被表示为一个递归函数。本章中的3.4节已经用C语言演示了递归归约。在CUDA里使用动态并行，可以确保CUDA里的递归归约核函数的实现像在C语言中一样简单。
下面列出了带有动态并行的递归归约的内核代码。这个核函数采取图3-29所示的方法，原始的网格包含许多线程块，但所有嵌套的子网格中只有一个由其父网格的线程0调用的线程块。核函数的第一步是将全局内存地址g_idata转换为每个线程块的本地地址。接着，如果满足停止条件（这是指如果该条件是嵌套执行树上的叶子），结果就被拷贝回全局内存，并且控制立刻返回到父内核中。如果它不是一片叶子内核，就需要计算本地归约的大小，一半的线程执行就地归约。在就地归约完成后，同步线程块以保证所有部分和的计算。紧接着，线程0产生一个只有一个线程块和一个当前线程块一半线程数量的子网格。在子网格被调用后，所有子网格会设置一个障碍点。因为在每个线程块里，一个线程只产生一个子网格，所以这个障碍点只会同步一个子网格。
在Wrox.com上可以下载nestedReduce.cu文件，里面有本例的所有代码。可以用以下命令编译代码：
用Kepler K40设备的输出结果展示如下，相较于使用相邻配对方法的内核实现，嵌套内核慢到无法接受：
正如输出结果显示，最初有2 048个线程块。因为每个线程块执行8次递归，所以总共创建了16 384个子线程块，用于同步线程块内部的__syncthreads函数也被调用了16 384次。如此大量的内核调用与同步很可能是造成内核效率很低的主要原因
当一个子网格被调用后，它看到的内存与父线程是完全一样的。因为每一个子线程只需要父线程的数值来指导部分归约，所以在每个子网格启动前执行线程块内部的同步是没有必要的。去除所有同步操作会产生如下的核函数：
在Wrox.com上可以下载nestedReduceNosync.cu文件，里面有本例的完整代码。编译运行它。下面列出了在Kepler K40设备上的输出结果。所需时间减少到了第一次动态并行实现的1/3：
然而，相较于相邻配对内核，它的性能仍然很差。需要考虑如何减少由大量的子网格启动引起的消耗。在当前的实现中，每个线程块产生一个子网格，并且引起了大量的调用。如果使用了图3-30展示的方法，当创建的子网格数量减少时，那么每个子网格中线程块的数量将会增加，以保持相同数量的并行性。
以下的核函数实现了这种方法：网格中第一个线程块中的第一个线程在每一步嵌套时都调用子网格。比较这两个核函数的特征码，会发现多了一个参数。因为每次嵌套调用时，子线程块大小会减到其父线程块大小的一半，父线程块的维度也必须传递给嵌套的子网格。这使得每个线程都能为它的工作负载部分正确计算出消耗部分的全局内存偏移地址。值得注意的是，在这个实现中，所有空闲的线程都是在每次内核启动时被移除的，而对于第一次实现而言，在每个嵌套层的内核执行过程中都会有一半的线程空闲下来。这样的改变将会释放一半的被第一个核函数消耗的计算资源，这样可以让更多的线程块活跃起来。
在Wrox.com上可以下载nestedReduce2.cu文件，里面有本例的完整代码。K40 GPU设备输出结果如下：
从这个结果可以看到，递归归约核函数的第三种实现比前两种实现更快了，大概是由于调用了较少的子网格。可以使用nvprof来验证性能提高的原因：
部分输出结果概括如下。第二列显示了设备内核的调用次数。第一个和第二个内核在设备上共创建了16 384个子网格。gpuRecursiveReduce2内核中的8层嵌套并行只创建了8个子网格。
该递归归约的例子说明了动态并行。对于一个给定的算法，通过使用不同的动态并行技术，可以有多种可能的实现方式。避免大量嵌套调用有助于减少消耗并提升性能。同步对性能与正确性都至关重要，但减少线程块内部的同步次数可能会使嵌套内核效率更高。因为在每一个嵌套层上设备运行时系统都要保留额外的内存，所以内核嵌套的最大数量可能是受限制的。这种限制的程度依赖于内核，也可能会限制任何使用动态并行应用程序的扩展、性能以及其他的性能。
