Tuesday, May 14, 2013

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.