这篇文章分析和说明GPU 片上的kernel 通过stream 作为载体是如何分发到SM 处理器上，同时CUDA 所抽象的grid/block/thread 在GPU 设备层面是如何调度的。调度器通常是被忽略的一个部分，但对CUDA kernel 的编写和后期系统性能分析很有帮助，也可以帮助大家进一步理解CUDA 的语义。

片上的分级调度

stream scheduler：

• FIFO顺序：同一流中的操作按FIFO顺序执行，即先提交的先执行。
• 流隔离：CUDA流与单个应用程序相关联，不同应用程序的流互不干扰。例如，如果应用程序A0正在运行，则应用程序A1的流不会干扰A0。
  并行执行：不同流中的操作可以并行执行，但同一流中的操作必须顺序执行。
• 流优先级：从Maxwell GPU架构（例如Jetson TX1嵌入式板）开始，CUDA提供了一个运行时函数调用，用于为流分配优先级。
• 当前所有测试过的GPU架构（包括Maxwell、Pascal、Volta和Turing）仅支持两个离散的优先级（高和低）。如果低优先级流占用了一个SM的所有计算资源，则后来提交到高优先级流上的内核可以抢占当前运行的内核。

Thread block scheduler：

• 寻找空闲SM 映射CUDA 语义所表达的grid/block/thread 结构
• 在所有内核被分配到一个流时，线程块会通过所有可用的SM进行循环分配（Round-Robin，RR），先分配到偶数ID的SM，然后是奇数ID的SM
• 在分配线程块到SM之前，线程块调度器会进行一个占用测试，检查每个SM当前的资源利用情况（线程/warps数量， 寄存器，共享内存），以确定是否可以容纳新的线程块。此测试的目的是确保当前的占用率能够满足新内核的需求，从而实现线程块到SM的映射
• NVIDIA提供了一个CUDA Occupancy Calculator（CUDA占用计算器），这是一个公开可用的电子表格工具，帮助计算特定线程/块配置下目标GPU的理论占用率。通过结合该计算器与设备查询命令得到的架构参数，可以推导出线程、共享内存和寄存器资源的利用率​目前已经整合到nsight compute 中 （https://docs.nvidia.com/nsight-compute/NsightCompute/index.html#occupancy-calculator）
  Tips: 通过下面的方法可以获取当前thread 所映射的SM id
  int smid; asm volatile("mov.u32%0, %%smid;" : "=r"(smid));
  前两行为stream1的线程数和warp数;
  前两列为stream2的线程数和warp数;
  其他单元格表示一个SM在被stream1上的kernel占用后还能继续容纳的最大warp
  空白底色代表两个block被分配到了不同的SM上
  浅灰底色代表两个block被分配到了同一个SM上

Warp Scheduler

• 每个SM有若干个warp调度器和相应的指令分发单元。
• 例如，在Pascal架构的GPU中，每个SM有两个warp调度器和两个指令分发单元，每个warp调度器每个时钟周期可以调度两条独立的指令；
• 图灵架构包含4个Warp scheduler 同时对SM 进行了partition，分为4份；
• Maxwell, Pascal, Volta和Turing架构中使用的warp调度策略是松散轮询调度（Loose Round Robin, LRR）。
• 在LRR策略下，warp以轮询方式调度，当一个warp遇到未满足的依赖（如全局内存未命中）时，它会暂停，使下一个准备好的warp被调度。这种调度策略通过足够的ready warp来隐藏内存访问的延迟，并确保warp之间的公平性​
  
  关于warp scheduler，我们再进一步深入探讨，上面说道图灵架构每个SM 被划分为4个partition，每个partition 一个scheduler，具体来说：
• 每个SM有4个Warp Scheduler。
• 每个Warp Scheduler可以在同一时间调度32个线程。
• 每个时钟周期内，每个SM可以调度128个线程（4个Warp × 32个线程/每个Warp）。
• 每个SM最多支持2048个并发线程，但这些线程并不会在同一个时钟周期内同时运行。
  因此，对于warp scheduler 来说，多个warp 是通过时分复用的方式实现对scheduler 的占用以及指令的发射，多个warp 间在同一时刻如果处于同一个partition，是串行执行（或者等待前一个warp stall/wait 状态 ），在不同的partion 之间可以实现并行，从编程的角度我们可以利用这一点。

调度器对warp和SM partition（同时也是调度器id）的映射采用如下简单的方式：
scheduler_id = warp_id%4
在同一个block中，warp id 是4 的整数倍的warp 会被调度到同一个partion。
一个极端的情况，假如一个block里只有2个warp要做计算，其余warp直接退出。如果这两个要做计算的warp（称为active的warp）对4同余，那么就会造成因为4个partition负载不均衡而产生的性能损失。

这种情况下，可以看到V100/A100 0/4，1/5 … 以4 同余的warp ，算力利用率都相对较低。

CUDA 对资源的抽象

launch_kernel<<<N,1>>> 和launch_kernel<<<1,N>>> 的区别

• launch_kernel<<<N, 1>>>:
  这表示内核以 N 个线程块启动，每个线程块只有 1 个线程。
  这种配置通常用于当内核需要执行 N 个独立的任务，每个任务由一个单独的线程块完成。
  网格维度为 N，每个线程块的维度为 1。
• launch_kernel<<<1, N>>>:
  这表示内核以 1 个线程块启动，但这个线程块包含 N 个线程。
  这种配置通常用于当内核需要执行一个任务，但这个任务可以被分解为 N 个并行操作，由同一个线程块中的 N 个线程并行完成。
  网格维度为 1，每个线程块的维度为 N。

当每个线程执行的任务是独立的，并且没有线程间同步的需求时，使用 <<<N, 1>>> 配置可能更合适，原因包括：

• 减少线程块内同步：
  在CUDA中，同一个线程块内的线程可以协同工作，但这也意味着它们可能需要进行线程间同步，例如使用 《=》 或 max() 等原子操作。如果任务是独立的，这种同步是不必要的，使用单个线程的线程块可以避免这种同步开销。

• 简化线程索引计算：
  当每个线程执行独立任务时，线程索引的计算通常更简单。使用 <<<N, 1>>> 时，每个线程的全局索引可以直接用其线程块索引表示，因为每个线程块内只有一个线程。

• 提高资源利用率：
  在某些情况下，使用单个线程的线程块可以更有效地利用GPU资源。例如，如果内核设计为每个线程处理一个数据元素，使用 <<<N, 1>>> 可以直接映射N个线程到N个数据元素，而不需要额外的逻辑来分配线程到数据。

• 避免共享内存竞争：
  如果使用多个线程的线程块，这些线程可能会竞争访问共享内存。当任务独立时，每个线程块只有一个线程，因此不存在共享内存访问的竞争问题。

• 提高启动效率：
  启动大量单个线程的线程块可能比启动少量多线程的线程块更有效率，因为每个线程块的启动开销是固定的，而更多的线程块可以更细粒度地利用GPU的并行处理能力。

• 适应性：
  在某些GPU架构中，可能更适合于处理大量小线程块的情况。使用 <<<N, 1>>> 可以更好地适应这种架构特性。

• 减少线程块内线程间通信：
  如果内核中没有线程间通信的需求，使用 <<<N, 1>>> 可以减少线程块内线程间通信的复杂性和开销。

Reference

• Nvidia official site
• Dissecting the NVidia Turing T4 GPU via Microbenchmarking
• Inferring Scheduling Policies of an Embedded CUDA GPU
• Dissecting the CUDA scheduling hierarchy - a Performance and Predictability Perspective
• cuda programming guide