In Treadmarks, processors may become idle while performing any one of four operations: (1) lock acquire, (ii) barrier entry, (iii) diff/page requests, and (iv) garbage collection.
We implemented waiting time analysis in Carnival
using a pipeline of three independent tools.
The first tool in the pipeline
takes in trace file information and
produces as output a pair of execution paths
for every instance of waiting time in the execution.
Each pair of matching events (such as the beginning and end of a
Treadmarks library call) becomes a execution step that is
identified by the processor where the events happened, the profiling
category and location in the source code, and has a duration associated
with it. An execution path is a set of execution steps,
so the size is bounded by the product
.
Another tool takes as input the list of waiting time steps and the pair of paths representing each such step, and creates a set of equivalence classes of execution paths (i.e., merges equivalent paths). The output of this tool is a list of waiting time steps expressed in terms of the representative path for an equivalence class. The waiting time step defines the duration of waiting; the representative path defines the percentage of that duration associated with each execution step on the path.
Finally, for each instance of waiting time, another tool removes any redundant steps between the pair of paths that characterizes it. This tool also acts as a filter on the set of characterizations, allowing the user to select individual execution steps for analysis.