Quoting Tvrtko Ursulin (2021-01-29 09:37:27)
>
> 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?
/*
* Given a uniform distribution of random numbers over the u32, then
* the probability each bit is unset is P=0.5. The probability of a
* successive sequence of bits being unset is P(n) = 0.5^n [n > 0].
* P(level:1) = 0.5
* P(level:2) = 0.25
* P(level:3) = 0.125
* P(level:4) = 0.0625
* ...
* So we can use ffs() on a good random number generator to pick our
* level. We divide by two to reduce the probability of choosing a
* level to .25, as the cost of descending a level is the same as
* following an extra link in the chain at that level (so we can
* pack more nodes into fewer levels without incurring extra cost,
* and allow scaling to higher volumes of requests without expanding
* the height of the skiplist).
*/
-Chris
_______________________________________________
Intel-gfx mailing list
Intel-gfx@xxxxxxxxxxxxxxxxxxxxx
https://lists.freedesktop.org/mailman/listinfo/intel-gfx
