[lkml]   [2011]   [Nov]   [14]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: [PATCH] perf_events: fix and improve x86 event scheduling
Let's take Robert's example:
c0 c1 c2
e0 x x
e1 x x
e2 x x

The nodes in the graph:

- S (starting point)
- T (the ending point)
- e0, e1, e2 (the events)
- c0, c1, c2 (the counters)

There is an edge from the source to all the events.
There is an edge from all the counters to the sync.
There is an edge between an event and a counter, if
it can count the event.

The capacity of any edge is 1.

The max flow algorithm returns the maximum number of
events that can be measured together. If max_flow ==
number of events, we maxed out.

To find the assignment, we simply need to inspect the
outgoing edges from events and use the only edge which
has a flow == 1.

If we list all the edges for the example above, we have:
S -> e0
S -> e1
S -> e2
e0 -> c0
e0 -> c2
e1 -> c1
e1 -> c2
e2 -> c0
e2 -> c1
c0 -> T
c1 -> T
c2 -> T

then we do max_flow(S, T), Here we find 3.

Given the capacity is either 0 or 1, I think we could use
bitmasks to describe the edges.

On Mon, Nov 14, 2011 at 3:12 PM, Peter Zijlstra <> wrote:
> On Mon, 2011-11-14 at 13:55 +0100, Stephane Eranian wrote:
>> I have been talking with co-workers experts in operational research
>> about our problem. They all pointed to me to the max flow algorithm from
>> Ford-Fulkerson (search for it on Wikipedia). I think it solves the complexity
>> and recursion problems. My understanding is that the complexity is also
>> more under control.
> How would you apply this algorithm to the problem at hand? I'm probably
> missing the obvious thing here, but if we want the flow to be the number
> of assigned counter then we end up with nodes being the various
> permutations of assignments or so, which isn't helpful since that'd be
> n! nodes.

 \ /
  Last update: 2011-11-14 15:29    [W:0.050 / U:13.704 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site