On 2022-08-23 14:30, Luben Tuikov wrote:
On 2022-08-23 14:13, Andrey Grodzovsky wrote:
On 2022-08-23 12:58, Luben Tuikov wrote:
Inlined:
On 2022-08-22 16:09, Andrey Grodzovsky wrote:
Poblem: Given many entities competing for same rq on
^Problem
same scheduler an uncceptabliy long wait time for some
^unacceptably
jobs waiting stuck in rq before being picked up are
observed (seen using GPUVis).
The issue is due to Round Robin policy used by scheduler
to pick up the next entity for execution. Under stress
of many entities and long job queus within entity some
^queues
jobs could be stack for very long time in it's entity's
queue before being popped from the queue and executed
while for other entites with samller job queues a job
^entities; smaller
might execute ealier even though that job arrived later
^earlier
then the job in the long queue.
Fix:
Add FIFO selection policy to entites in RQ, chose next enitity
on rq in such order that if job on one entity arrived
ealrier then job on another entity the first job will start
executing ealier regardless of the length of the entity's job
queue.
Signed-off-by: Andrey Grodzovsky <andrey.grodzovsky@xxxxxxx>
Tested-by: Li Yunxiang (Teddy) <Yunxiang.Li@xxxxxxx>
---
drivers/gpu/drm/scheduler/sched_entity.c | 2 +
drivers/gpu/drm/scheduler/sched_main.c | 65 ++++++++++++++++++++++--
include/drm/gpu_scheduler.h | 8 +++
3 files changed, 71 insertions(+), 4 deletions(-)
diff --git a/drivers/gpu/drm/scheduler/sched_entity.c b/drivers/gpu/drm/scheduler/sched_entity.c
index 6b25b2f4f5a3..3bb7f69306ef 100644
--- a/drivers/gpu/drm/scheduler/sched_entity.c
+++ b/drivers/gpu/drm/scheduler/sched_entity.c
@@ -507,6 +507,8 @@ void drm_sched_entity_push_job(struct drm_sched_job *sched_job)
atomic_inc(entity->rq->sched->score);
WRITE_ONCE(entity->last_user, current->group_leader);
first = spsc_queue_push(&entity->job_queue, &sched_job->queue_node);
+ sched_job->submit_ts = ktime_get();
+
/* first job wakes up scheduler */
if (first) {
diff --git a/drivers/gpu/drm/scheduler/sched_main.c b/drivers/gpu/drm/scheduler/sched_main.c
index 68317d3a7a27..c123aa120d06 100644
--- a/drivers/gpu/drm/scheduler/sched_main.c
+++ b/drivers/gpu/drm/scheduler/sched_main.c
@@ -59,6 +59,19 @@
#define CREATE_TRACE_POINTS
#include "gpu_scheduler_trace.h"
+
+
+int drm_sched_policy = -1;
+
+/**
+ * DOC: sched_policy (int)
+ * Used to override default entites scheduling policy in a run queue.
+ */
+MODULE_PARM_DESC(sched_policy,
+ "specify schedule policy for entites on a runqueue (-1 = auto(default) value, 0 = Round Robin,1 = use FIFO");
+module_param_named(sched_policy, drm_sched_policy, int, 0444);
As per Christian's comments, you can drop the "auto" and perhaps leave one as the default,
say the RR.
I do think it is beneficial to have a module parameter control the scheduling policy, as shown above.
Christian is not against it, just against adding 'auto' here - like the
default.
Exactly what I said.
Also, I still think an O(1) scheduling (picking next to run) should be
what we strive for in such a FIFO patch implementation.
A FIFO mechanism is by it's nature an O(1) mechanism for picking the next
element.
Regards,
Luben
The only solution i see for this now is keeping a global per rq jobs
list parallel to SPCP queue per entity - we use this list when we switch
to FIFO scheduling, we can even start building it ONLY when we switch
to FIFO building it gradually as more jobs come. Do you have other solution
in mind ?
Andrey
+
+
#define to_drm_sched_job(sched_job) \
container_of((sched_job), struct drm_sched_job, queue_node)
@@ -120,14 +133,16 @@ void drm_sched_rq_remove_entity(struct drm_sched_rq *rq,
}
/**
- * drm_sched_rq_select_entity - Select an entity which could provide a job to run
+ * drm_sched_rq_select_entity_rr - Select an entity which could provide a job to run
*
* @rq: scheduler run queue to check.
*
- * Try to find a ready entity, returns NULL if none found.
+ * Try to find a ready entity, in round robin manner.
+ *
+ * Returns NULL if none found.
*/
static struct drm_sched_entity *
-drm_sched_rq_select_entity(struct drm_sched_rq *rq)
+drm_sched_rq_select_entity_rr(struct drm_sched_rq *rq)
{
struct drm_sched_entity *entity;
@@ -163,6 +178,45 @@ drm_sched_rq_select_entity(struct drm_sched_rq *rq)
return NULL;
}
+/**
+ * drm_sched_rq_select_entity_fifo - Select an entity which could provide a job to run
+ *
+ * @rq: scheduler run queue to check.
+ *
+ * Try to find a ready entity, based on FIFO order of jobs arrivals.
+ *
+ * Returns NULL if none found.
+ */
+static struct drm_sched_entity *
+drm_sched_rq_select_entity_fifo(struct drm_sched_rq *rq)
+{
+ struct drm_sched_entity *tmp, *entity = NULL;
+ ktime_t oldest_ts = KTIME_MAX;
+ struct drm_sched_job *sched_job;
+
+ spin_lock(&rq->lock);
+
+ list_for_each_entry(tmp, &rq->entities, list) {
+
+ if (drm_sched_entity_is_ready(tmp)) {
+ sched_job = to_drm_sched_job(spsc_queue_peek(&tmp->job_queue));
+
+ if (ktime_before(sched_job->submit_ts, oldest_ts)) {
+ oldest_ts = sched_job->submit_ts;
+ entity = tmp;
+ }
+ }
+ }
Here I think we need an O(1) lookup of the next job to pick out to run.
I see a number of optimizations, for instance keeping the current/oldest
timestamp in the rq struct itself,
This was my original design with rb tree based min heap per rq based on
time stamp of
the oldest job waiting in each entity's job queue (head of entity's SPCP
job queue). But how in this
case you record the timestamps of all the jobs waiting in entity's the
SPCP queue behind the head job ?
If you record only the oldest job and more jobs come you have no place
to store their timestamps and so
on next job select after current HEAD how you will know who came before
or after between 2 job queues of
of 2 entities ?
or better yet keeping the next job
to pick out to run at a head of list (a la timer wheel implementation).
For suck an optimization to work, you'd prep things up on job insertion, rather
than on job removal/pick to run.
I looked at timer wheel and I don't see how this applies here - it
assumes you know before
job submission your deadline time for job's execution to start - which
we don't so I don't see
how we can use it. This seems more suitable for real time scheduler
implementation where you
have a hard requirement to execute a job by some specific time T.
I also mentioned a list, obviously there is the brute force solution of
just ordering all jobs in one giant list and get
naturally a FIFO ordering this way with O(1) insertions and extractions
but I assume we don't want one giant jobs queue
for all the entities to avoid more dependeies between them (like locking
the entire list when one specific entity is killed and
needs to remove it's jobs from SW queue).
I'm also surprised that there is no job transition from one queue to another,
as it is picked to run next--for the above optimizations to implemented, you'd
want a state transition from (state) queue to queue.
Not sure what you have in mind here ? How this helps ?
Andrey
Regards,
Luben
In my origianl design
+
+ if (entity) {
+ rq->current_entity = entity;
+ reinit_completion(&entity->entity_idle);
+ }
+
+ spin_unlock(&rq->lock);
+ return entity;
+}
+
/**
* drm_sched_job_done - complete a job
* @s_job: pointer to the job which is done
@@ -804,7 +858,10 @@ drm_sched_select_entity(struct drm_gpu_scheduler *sched)
/* Kernel run queue has higher priority than normal run queue*/
for (i = DRM_SCHED_PRIORITY_COUNT - 1; i >= DRM_SCHED_PRIORITY_MIN; i--) {
- entity = drm_sched_rq_select_entity(&sched->sched_rq[i]);
+ entity = drm_sched_policy != 1 ?
+ drm_sched_rq_select_entity_rr(&sched->sched_rq[i]) :
+ drm_sched_rq_select_entity_fifo(&sched->sched_rq[i]);
+
if (entity)
break;
}
diff --git a/include/drm/gpu_scheduler.h b/include/drm/gpu_scheduler.h
index addb135eeea6..95865881bfcf 100644
--- a/include/drm/gpu_scheduler.h
+++ b/include/drm/gpu_scheduler.h
@@ -314,6 +314,14 @@ struct drm_sched_job {
/** @last_dependency: tracks @dependencies as they signal */
unsigned long last_dependency;
+
+ /**
+ * @submit_ts:
+ *
+ * Marks job submit time
+ */
+ ktime_t submit_ts;
+
};
static inline bool drm_sched_invalidate_job(struct drm_sched_job *s_job,
Regards,
