DRM GPU Scheduler

DRM GPU Scheduler 背景

调度器 顾名思义是用来分配某种有限资源的一种算法。

从CPU的视角来看，CPU的核心数目是远少于线程数目的，所以在某一个时刻只有一部分线程才可以得到执行，控制这些这些线程执行的时机和时长的一种算法，我们称之为CPU的调度算法。同样的在GPU领域也是同理的，在现代的操作系统中，每一个进程都期望可以使用GPU资源进行某种计算，所以GPU的调度器也就有所必要，但是与CPU相比GPU的调度器还是相对来说比较简单的。

GPU的硬件资源 (AMD)

• VMID (Virtual Machine ID) 每一个VMID对应一组GPU的页表的寄存器
• GFX Engine GPU 3D Graphics 图像处理单元
• Compute Engine GPU Compute 处理单元
• sDMA (system Direct Memory Access) GPU内部的DMA单元
• VCN (Video Codec Next) Engine 视频编解码单元
• JPEG 图像处理单元
• ….

硬件资源的个数会根据GPU的类型有所不同，例如在GPU计算卡领域并不需要图形计算，因此并不需要GFX相关的硬件单元，并且在计算领域可能需要更多的数据拷贝，所以因此会包含多个sDMA单元，这种设计可以很好的是陪产品的不同定位。

在GPU Driver中，驱动会为每一种硬件单元创建一个或者多个Ring，这些Ring本质是一个环形的缓冲区，充当软件和硬件沟通的桥梁，软件（用户）作为生产者负责提交命令到Ring中，硬件单元负责从这个Ring中获得要执行的命令，这样软件和硬件就建立某种映射关系。因此每一个线程（包括内核线程）都可以提交命令到这个Ring中，因此GPU的调度器存在就很有必要了。

DRM GPU Scheduler 的调度算法

GPU里的每一个硬件单元提供一个或者多个Ring来与软件进行交互，GPU scheduler会为每一个Ring创建不同等级的RQ队列，由调度线程完成调度。

enum drm_sched_priority {
  	DRM_SCHED_PRIORITY_MIN,
  	DRM_SCHED_PRIORITY_NORMAL,
  	DRM_SCHED_PRIORITY_HIGH,
  	DRM_SCHED_PRIORITY_KERNEL,
  	DRM_SCHED_PRIORITY_COUNT,
  	DRM_SCHED_PRIORITY_UNSET = -2
  };

主要调度策略如下：

• Priority 如果高等级的RQ里有job，低等级的RQ就不能运行
• RR (Round-Robin) 在相同的RQ里按照RR算法，分别运行没一个entity里的job，直至当RQ的job都被调度，在调度下一优先级

RR的算法可以避免进程饿死的问题，但是又没有很好的解决调度延迟的问题，是当前调度算法的一种妥协

数字仅仅是本文章用来标识job，调度器内部并没有使用这些数字。

以GFX的调度为例，GFX 调度器其由4个优先级的RQ组成，每一个RQ里有多个entity，每一个entity由多个job组成的一个队列。

调度算法会先在高优先级RQ里选择一个需要调度的entity，在从选中的entity里挑选出一个job进行运行，直至当前优先级里的所有job运行完毕，在从下一个优先级继续运行，直至所有job运行完成，没有job就绪的时候，调度线程会睡眠，当有新的job 就绪的时候，调度线程会唤醒。

按照现有的调度策略，job按照如下顺序运行：

1. 101 -> 201 -> 102 -> 202 -> 103 -> 203 -> 104
2. 301 -> 302 -> 303
3. 401 -> 501 -> 601 -> 402 -> …. -> 603
4. 701 -> 702

DRM GPU Scheduler 的负载均衡

GPU Scheduler和CPU一样提供了负载均衡的功能，可以平衡不同硬件单元的负载，以提高硬件整体的利用率。

以 AMD Radeon RX 5500 为例，硬件层面提供了2个sDMA单元，每一个硬件单元的功能是完全相同的，因此可以将负载比较高的RQ上的job移动到负载比较低的RQ上进行调度，从而提高硬件整体的利用率和吞吐率。

负载均衡的时机

CPU线程最好的负载均衡时机是线程刚创建的时候，因为这个时候所有TLB都是冷的，如果线程运行一段时间TLB变热之后，负载均衡的成本是相对较高的。

同CPU一样，GPU的job也是在刚创建的时候进行负载均衡成本是最低的，所有TLB对于这个新出生的job是一样的，不过与CPU不同的是，GPU的job通常来说只会运行一次，下次运行需要重新提交新的job，因此负载均衡的时机只能发生在job创建的阶段。

负载均衡的算法

当前GPU调度器没有办法推测job运行的时间长短，也无法衡量job对硬件资源的负载贡献，因此现阶段简单暴力的用job的数量来作为负载均衡的唯一条件。

这是相当不严谨的，job仅仅是软件层面对GPU命令的一种抽象，每一个job对GPU的负载是不一样的，但是好在一个job只会执行一次。

关键代码分析：

struct drm_gpu_scheduler *
drm_sched_pick_best(struct drm_gpu_scheduler **sched_list,
		     unsigned int num_sched_list)
{
	struct drm_gpu_scheduler *sched, *picked_sched = NULL;
	int i;
	unsigned int min_score = UINT_MAX, num_score;

	for (i = 0; i < num_sched_list; ++i) {
		sched = sched_list[i];
		if (!sched->ready) {
			DRM_WARN("scheduler %s is not ready, skipping",
				 sched->name);
			continue;
		}
		num_score = atomic_read(&sched->score);
		if (num_score < min_score) {
			min_score = num_score;
			picked_sched = sched;
		}
	}

	return picked_sched;
}

调度算法先通过函数drm_sched_pick_best在同类型的调度器里选择运行job数量最少的硬件单元。

void drm_sched_entity_select_rq(struct drm_sched_entity *entity)
{
	struct dma_fence *fence;
	struct drm_gpu_scheduler *sched;
	struct drm_sched_rq *rq;

	if (spsc_queue_count(&entity->job_queue) || entity->num_sched_list <= 1)
		return;

	fence = READ_ONCE(entity->last_scheduled);
	if (fence && !dma_fence_is_signaled(fence))
		return;

	spin_lock(&entity->rq_lock);
	sched = drm_sched_pick_best(entity->sched_list, entity->num_sched_list);
	rq = sched ? &sched->sched_rq[entity->priority] : NULL;
	if (rq != entity->rq) {
		drm_sched_rq_remove_entity(entity->rq, entity);
		entity->rq = rq;
	}

	spin_unlock(&entity->rq_lock);
}

把当的entity迁移到与同等优先级的RQ上来完成负载均衡，值得注意的是，负载均衡的基本单位是entity不是job。

DRM GPU Scheduler 的事件

事件	Scheduler Fence 类型	说明
job已经schedule	scheduled	标识job已经投入运行
job执行完成	finished	标识job已经运行完成

scheduler使用dma_fence来与外部接口完成事件的同步，在内核中dma_fence常作为一种异步同步机制存在驱动代码中，dma_fence主要提供2种功能：

1. Wait: 等待某一事件是否触发，如果没事件没有触发，会让当前线程睡眠
2. Signal: 标识某一个事件处罚，dma_fence触发后会一次调用绑定在当前fence上的所有callback函数，来分发某一事件，来完成事件同步的机制。

DRM GPU Scheduler 对硬件行为的抽象

struct drm_sched_backend_ops {
	/**
         * @dependency: Called when the scheduler is considering scheduling
         * this job next, to get another struct dma_fence for this job to
	 * block on.  Once it returns NULL, run_job() may be called.
	 */
	struct dma_fence *(*dependency)(struct drm_sched_job *sched_job,
					struct drm_sched_entity *s_entity);

	/**
         * @run_job: Called to execute the job once all of the dependencies
         * have been resolved.  This may be called multiple times, if
	 * timedout_job() has happened and drm_sched_job_recovery()
	 * decides to try it again.
	 */
	struct dma_fence *(*run_job)(struct drm_sched_job *sched_job);

	/**
         * @timedout_job: Called when a job has taken too long to execute,
         * to trigger GPU recovery.
	 */
	void (*timedout_job)(struct drm_sched_job *sched_job);

	/**
         * @free_job: Called once the job's finished fence has been signaled
         * and it's time to clean it up.
	 */
	void (*free_job)(struct drm_sched_job *sched_job);
};

• dependency: 用于判断job是否可以投入运行
• run_job: 用于提交一个job
• timeout_job: 当finished fence超过一定的时间没有释放，调度器会通过这个接口通知驱动
• free_job: 负责job的清理工作

DRM GPU Scheduler 调度线程

static int drm_sched_main(void *param)
{
	struct drm_gpu_scheduler *sched = (struct drm_gpu_scheduler *)param;
	int r;

	sched_set_fifo_low(current);

	while (!kthread_should_stop()) {
		struct drm_sched_entity *entity = NULL;
		struct drm_sched_fence *s_fence;
		struct drm_sched_job *sched_job;
		struct dma_fence *fence;
		struct drm_sched_job *cleanup_job = NULL;

		wait_event_interruptible(sched->wake_up_worker,
					 (cleanup_job = drm_sched_get_cleanup_job(sched)) ||
					 (!drm_sched_blocked(sched) &&
					  (entity = drm_sched_select_entity(sched))) ||
					 kthread_should_stop());

		if (cleanup_job) {
			sched->ops->free_job(cleanup_job);
			/* queue timeout for next job */
			drm_sched_start_timeout(sched);
		}

		if (!entity)
			continue;

		sched_job = drm_sched_entity_pop_job(entity);

		complete(&entity->entity_idle);

		if (!sched_job)
			continue;

		s_fence = sched_job->s_fence;

		atomic_inc(&sched->hw_rq_count);
		drm_sched_job_begin(sched_job);

		trace_drm_run_job(sched_job, entity);
		fence = sched->ops->run_job(sched_job);
		drm_sched_fence_scheduled(s_fence);

		if (!IS_ERR_OR_NULL(fence)) {
			s_fence->parent = dma_fence_get(fence);
			r = dma_fence_add_callback(fence, &sched_job->cb,
						   drm_sched_process_job);
			if (r == -ENOENT)
				drm_sched_process_job(fence, &sched_job->cb);
			else if (r)
				DRM_ERROR("fence add callback failed (%d)\n",
					  r);
			dma_fence_put(fence);
		} else {
			if (IS_ERR(fence))
				dma_fence_set_error(&s_fence->finished, PTR_ERR(fence));

			drm_sched_process_job(NULL, &sched_job->cb);
		}

		wake_up(&sched->job_scheduled);
	}
	return 0;
}

通过以上简单的介绍，现在来看DRM GPU的调度算法是比较容易的，简单来分析下

1. sched_set_fifo_low(current) 会将调度线程设置RT-FIFO调度算法，这样可以以一个相对相对较高的优先级运行，从而减少调度的延迟
2. entity = drm_sched_select_entity(sched) 选择需要调度entity，每一个entity用来标示一组job, 一个进程可以 创建一个或者多个entity
3. sched_job = drm_sched_entity_pop_job(entity); 每一个entity内部有一个spsc无锁队列，每次调度其中一个job
4. atomic_inc(&sched->hw_rq_count); hw_rq_count 用来表示有多少job可以同时在硬件中运行，这个在AMD平台设置成2,避免过多的job处于“fly”状态，同时也可以保证硬件吞吐率处于一个比较合理的范围，大致就是ping - pong - ping - pong的节奏，这个功能也会影响scheduler的recover功能
5. drm_sched_job_begin(sched_job);登记当前job，并且启动一个定时器，来判断这个job后续是否运行超时
6. fence = sched->ops->run_job(sched_job); 提交这个job到硬件，并返回一个硬件fence， 这个fence可以表示job是否在硬件上执行完成
7. drm_sched_fence_scheduled(s_fence);释放scheduled fence，用来通知外部接口，来表示当前job已经投入运行了。
8. r = dma_fence_add_callback(fence, &sched_job->cb, drm_sched_process_job); 将硬件返回的fence和 调度器内部的finished fence进行绑定，
   硬件fence触发，会导致 scheduler finished fence 触发，finished fence 作为标准接口可以继续通知其他关心这个事件的人。