[
Date Prev][
Date Next][
Thread Prev][
Thread Next][
Date Index][
Thread Index]
[
List Home]
|
Re: [linuxtools-dev] TMF: Expressing dependency information and displaying it
|
Hi Michel,
Thanks for your feedback.
I'd propose to use a graph structure to represent those dependencies
(a set of vertices - an object at a given timestamp - and edges - a link
between two vertices).
Do the "vertices" already exist or you plan to "add" new objects. Currently, events in the trace may be seen as vertices. Similarly, state begin and end could be seen as vertices. State intervals may be seen as some sort of edge.
Ideally, I wouldn't "add" new objects, but most probably create classes
to link vertices and edges to some existing object (state change,
events, state intervals) to describe vertices and edges. Depending on
analysis, events can be vertices (the sending of a network packet) or an
edge (a sched_switch passing control from process A to B)
The dependency links added by the analysis link a state change in one process to the state change in another process. For example, the wake-up of A by B connects the two and "reroutes" the critical path from B to A. However, this happen at a well defined time, (unlike state intervals having a duration). You mention later another example of two processes interacting through the network. In that case, the network latency could be represented by another state interval (packet in the network) or included into the dependency link?
I had a discussion with Francis about this, whether to add the network
as an entry and have the network travel by it (one communication = 3
edges: 2 punctual to and from the network at send and receive time and 1
state interval on the network) or not (one communication = 1 edge from
sender to receiver). The former would show all packets sent, even those
not matched to a receiving event but the graphical representation
wouldn't be as clear as to which packet matches which. The latter would
show more clearly who sends to who, but only matching packets, we
wouldn't see the unmatched events.
We came to no definitive conclusion about this.
Each type of trace analysis would produce its own graph of dependencies,
as the edges needed by each are not the same. Each graph will be saved
to disk as a supplementary file.
State history is tricky because each state interval has a variable duration, hence the tree like index to search for all intervals intersecting the current time. If the dependency links are punctual in time, it then becomes more like the events in traces which are sorted by time and easily accessed by binary search.
I don't mean to use the state history backend to save the graph. I'll
look into the various java graph classes available to see which suits
the need best and that graph itself would be saved (in a compact way) in
the supplementary file, using another backend.
As for displaying those dependencies, it could be done through layers on
the Control flow view. Just like in Google Map, one could select the
layers to display and the corresponding graphs will be drawn over the
control flow view.
The control flow view could indeed be annotated with a red line on top or just over each process interval within the critical path. You could also show a resource view, each interval in the critical path, (just like what is done for each CPU when each process interval on that CPU is shown). You could also highlight the critical path on the multi-CPU resource view.
I'll provide screenshots when I have some available (in the upcoming
days/weeks) for more discussion on this subject.
This is the big idea. I would like to get some feedback on this
proposal. Does that make sense? Any complications ahead? Better
ideas?
Looks good! Brings more questions though:
What is the typical usage scenario for this data? As you proceed to build the state, you uncover depedencies (mostly wake-up actions from one thread to another) which you may write as punctual "events". Other dependencies require more work, for instance matching packets. Thereafter, you need to search the resulting graph to find the critical path: start of A, follow each state interval of A until a packet is sent to B and A blocks, follow state intervals in B until B replies and unblocks A, follow intervals in A until the end of A.
Once you have the critical path, you must be able to use that information to annotate the control flow view. Should it be a property of the state interval? Alternatively, when you are about to draw a state interval, you could check if, at its start time, it is connected to the critical path?
Critical path is one of hopefully many possible dependency analysis. We
cannot assume dependencies start or end with a state interval.
Sometimes an event that creates a dependency is called in the middle of
a state. The generic case would be to display a layer above the control
flow view. The resulting critical path would be a stripped down graph
of the full execution graph containing only the critical path. This way
the graph to display needs have no knowledge of the underlying state
system and vice versa. And each can be displayed independently of the
other.
And now time to implement this!
Geneviève
