lkml.org 
[lkml]   [2011]   [Apr]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: [PATCH 4/4] perf, x86: Fix event scheduler to solve complex scheduling problems
From
Date
On Sat, 2011-04-16 at 02:27 +0200, Robert Richter wrote:
> The current x86 event scheduler fails to resolve scheduling problems
> of certain combinations of events and constraints. This happens esp.
> for events with complex constraints such as those of the AMD family
> 15h pmu. The scheduler does not find then an existing solution.
> Examples are:
>
> event code counter failure possible
> solution
>
> 1) 0x043 PMC[2:0] 0 1
> 0x02E PMC[3,0] 3 0
> 0x003 PMC3 FAIL 3
>
> 2) 0x02E PMC[3,0] 0 3
> 0x043 PMC[2:0] 1 0
> 0x045 PMC[2:0] 2 1
> 0x046 PMC[2:0] FAIL 2
>
> Scheduling events on counters is a Hamiltonian path problem. To find a
> possible solution we must traverse all existing paths. This patch
> implements this.
>
> We need to save all states of already walked paths. If we fail to
> schedule an event we now rollback the previous state and try to use
> another free counter until we have analysed all paths.
>
> We might consider to later remove the constraint weight implementation
> completely, but I left this out as this is a much bigger and more
> risky change than this fix.

Argh, crap. That's because AMD is now the first with overlapping
constraints. Be sure to let your hardware guys know that they went from
top to bottom om my appreciation list. AMD used to have no constraints
and now they have the absolute worst.

I'd really prefer not to do this for .39, and I'll have to sit down and
actually read this code. It looks like we went from O(n^2) to O(n!) or
somesuch, also not much of an improvement. I'll have to analyze the
solver to see what it does for 'simple' constraints set to see if it
will indeed be more expensive than the O(n^2) solver we had.

Also, I think this code could do with a tiny bit of comments ;-)


\
 
 \ /
  Last update: 2011-04-16 10:53    [from the cache]
©2003-2014 Jasper Spaans. Advertise on this site