On 28/01/2021 16:26, Chris Wilson wrote:
Quoting Tvrtko Ursulin (2021-01-28 15:56:19)
-static void assert_priolists(struct i915_sched_engine * const se)
-{
- struct rb_node *rb;
- long last_prio;
-
- if (!IS_ENABLED(CONFIG_DRM_I915_DEBUG_GEM))
- return;
-
- GEM_BUG_ON(rb_first_cached(&se->queue) !=
- rb_first(&se->queue.rb_root));
-
- last_prio = INT_MAX;
- for (rb = rb_first_cached(&se->queue); rb; rb = rb_next(rb)) {
- const struct i915_priolist *p = to_priolist(rb);
-
- GEM_BUG_ON(p->priority > last_prio);
- last_prio = p->priority;
- }
+ root->prng = next_pseudo_random32(root->prng);
+ return __ffs(root->prng) / 2;
Where is the relationship to I915_PRIOLIST_HEIGHT? Feels root->prng %
I915_PRIOLIST_HEIGHT would be more obvious here unless I am terribly
mistaken. Or at least put a comment saying why the hack.
HEIGHT is the maximum possible for our struct. skiplists only want to
increment the height of the tree one step at a time. So we choose a level
with decreasing probability, and then limit that to the maximum height of
the current tree + 1, clamped to HEIGHT.
You might notice that unlike traditional skiplists, this uses a
probability of 0.25 for each additional level. A neat trick discovered by
Con Kolivas (I haven't found it mentioned elsewhere) as the cost of the
extra level (using P=.5) is the same as the extra chain length with
P=.25. So you can scale to higher number of requests by packing more
requests into each level.
So that is split between randomly choosing a level and then working out
the height of the node.
Choosing levels with decreasing probability by the virtue of using ffs
on a random number? Or because (BITS_PER_TYPE(u32) / 2) is greater than
I915_PRIOLIST_HEIGHT?
Regards,
Tvrtko
_______________________________________________
Intel-gfx mailing list
Intel-gfx@xxxxxxxxxxxxxxxxxxxxx
https://lists.freedesktop.org/mailman/listinfo/intel-gfx
