Announcing “ftrace”

If you've ever had to understand someone else's largely undocumented code, you may have wished there was some way of narrowing down your search through the source to a simple case or two until you had learned your way around.

I'm in that situation with the Linux “perf tools”, which I'm trying to use in my research. I'm reasonably familiar with strace and ltrace, which trace system and library calls, respectively, but I don't really care about these: I just want to trace the “local” function calls so that I can get a handle on how perf works. That should be easy, right?

Mmm... no. It turns out that I'm not the first person to have this problem.

One of the suggestions on StackOverflow, from Johannes Schaub, is to use readelf to identify all the functions symbols, set breakpoints for all of them in gdb, and retrieve the last frame of the backtrace at each breakpoint. Nice idea. Horribly slow, but a nice idea.

So, since I've been using OpenGrok to browse the kernel tools source, so it would be nice to be able to integrate with it, like this:

OpenGrok with 'ftrace'

It would be really nice to have a callgraph from a particular program invocation, like this:

Callgraph from 'ftrace' via GraphViz 'dot'

So, I wrote a few hundred lines of Python to do what Johannes suggested, plus a bit more. After the pattern of strace and ltrace, I called it ftrace, and you can get it from github:

• Emmet's ftrace on GitHub 

It's horribly slow, it's hacky, but does what I need for the time being.

Arithmetic Intensity Origins

Arithmetic intensity is a key concept in the Roofline Model [Williams et al., 2009], which is important to my own research, and has definitely gone mainstream, making it into the lexicon of computer and computational science and the latest editions of John Hennessey and Dave Patterson's highly-respected books, “Computer Architecture: A Quantitative Approach” and “Computer Organization and Design”. In both books — the former on p.286 et seq., and the latter on p.668 et seq., — the treatment cites the same “Williams et al. 2009”, which inadvertently kinda sorta gives the impression that the idea of arithmetic intensity is due to them (in this case, the “et al.” is Andrew Waterman and Dave Patterson). This seems odd — I would have thought that the term, “arithmetic intensity”, must have been around long before the Roofline Model — but, having been introduced to the term around that time, I couldn't be sure. Where does this term originate?

As it happens, “arithmetic intensity” is a surprisingly new term. Looking back through the literature with Google Scholar and CiteSeerX, it seems that the first occurrence in computer/computational science might have been as early as 1992 [Walter, 1992], but in that case, it seems most likely that it was a rhetorical flourish — synonymous with “containing lots of arithmetic” — rather than a term intended to be coined with any semblance of a consistent technical meaning. It essentially lay dormant for almost 10 years before resurfacing in a Stanford whitepaper by Bill Dally, Pat Hanrahan, and Ron Fedkiw in 2001, where it is loosely defined:

This in turn enables architectures with a high degree of arithmetic intensity, that is applications with a high ratio of arithmetic to memory bandwidth.

In 2002, it appears about half-a-dozen times [Dally, Kapasi et al., Owens et al., Purcell et al., Schröder, Jayasena et al.]. In all but one case in publications (formal or otherwise) about stream computing and GPGPU computing originating at Stanford. In the immediately following years, the term took off, with over 1,000 occurrences in 2012 (see Figure 1).

Figure 1: Occurrences in Search vs. Year

So, it seems that someone in Stanford, perhaps Bill Dally, has a pretty good claim on coining the term “arithmetic intensity” with its current meaning around 2001.