Elamur Research⌕
☰
home / papers / 2009 / Roofline: An Insightful Visual Performance Model for Multicore Architectures

Roofline: An Insightful Visual Performance Model for Multicore Architectures

Paper · 2009 · Samuel Williams, Andrew Waterman and David Patterson

Summary

Multicore chips are diverging in design: many simple cores versus a few complex ones, multithreading, and local stores in place of caches. This makes it harder for programmers, compiler writers and architects to reason about performance. The authors propose Roofline, a bound-and-bottleneck model that aims to give insight rather than exact predictions. It uses a log-log chart that plots attainable floating-point throughput against operational intensity, defined as flops per byte of DRAM traffic after the cache hierarchy has filtered accesses.

A kernel's speed is capped by whichever is lower: peak compute, or sustainable memory bandwidth multiplied by intensity. This produces a flat roof and a slanted roof that meet at a "ridge point". Bandwidth comes from the authors' own optimized microbenchmarks, not from DRAM pin specifications.

The model is then extended with "ceilings", which show the limit reached when a specific optimization is missing. These indicate which optimizations to apply and in what order. The approach is demonstrated on four diverse multicore machines (AMD Opteron X4, Intel Xeon Clovertown, IBM Cell, Sun UltraSPARC T2+) using floating-point kernels such as sparse matrix, stencil/structured grid and FFT codes. One chart per machine can be reused for any kernel.

Key points

  • Core bound: attainable GFlops/s = min(peak FP performance, peak memory bandwidth × operational intensity). Both lines are measured once per computer, not once per kernel.
  • The dual-socket 2.2 GHz AMD Opteron X2 (model 2214) has a peak of 17.6 GFlops/s and 15 GB/s of measured sustainable bandwidth, which puts its ridge point at about 1 flop/byte.
  • The Opteron X4 uses the same socket and therefore has the same DRAM bandwidth, but its peak compute is roughly 4× higher. Its ridge point moves to 4.4, so kernels need higher intensity to gain anything from it.
  • Opteron X2 compute ceilings: 8.8 GFlops/s with an unbalanced add/multiply mix, and 2.2 GFlops/s when ILP/SIMD optimizations are also missing.
  • Opteron X2 memory ceilings: 11 GB/s without software prefetching, 4.8 GB/s without NUMA memory affinity as well, and 2.7 GB/s with only unit-stride optimization.

Interesting ideas

  • I1. Aim for insight over accuracy. The authors deliberately build an imperfect but intuitive model, as the 3Cs cache model did. Simple bounding charts can guide decisions better than precise but opaque predictors, for example when explaining throughput of NLP inference or data pipelines.
  • I2. Measure traffic at the real bottleneck. Counting bytes between caches and DRAM, rather than between CPU and cache, lets memory optimizations show up in the model. More generally, define the ratio at whichever interface actually limits throughput, such as disk, network or GPU memory.
  • I3. Treat ceilings as an ordered optimization checklist. Each missing optimization lowers the reachable limit, and the kernel's intensity indicates which group of fixes (compute or memory) matters. This turns profiling into a prioritized to-do list.
  • I4. Use the ridge point as a one-number difficulty score. Its x-coordinate summarizes how hard it is to reach a machine's peak, which helps compare hardware for a given workload before writing any code.
  • I5. Use measured, sustainable limits rather than spec-sheet numbers. Benchmarking achievable bandwidth gives honest roofs. The authors also suggest the model can extend to non-arithmetic operations, which makes it reusable outside floating-point work.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of California, BerkeleyBerkeley · United States209 works · 244,782 citations🔬Lawrence Berkeley National LaboratoryBerkeley · United States4 works · 41,948 citations

 Fields, topics and concepts

📚 Shelves 3The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksHardware and Architecture · 167 worksComputer Networks and Communications · 100 works

🧭 Topics 1Research subjects and languages the work is about.GPU & parallel computing · 41 works

Cite

Cite as Samuel Williams, Andrew Waterman and David Patterson. 2009. Roofline: An Insightful Visual Performance Model for Multicore Architectures. Communications of the ACM 52(4).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1145/1498765.1498785

@inproceedings{williams2009roofline,
  title = {{Roofline: An Insightful Visual Performance Model for Multicore Architectures}},
  author = {Samuel Williams, Andrew Waterman and David Patterson},
  booktitle = {Communications of the ACM 52(4)},
  year = {2009},
  doi = {10.1145/1498765.1498785},
  url = {https://doi.org/10.1145/1498765.1498785}
}

References

30 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. V. Adve, Analyzing the Behavior and Performance of Parallel Programs, PhD thesis, Univ. of Wisconsin, 1993. find
  2. AMD, Software Optimization Guide for AMD Family 10h Processors, Publication 40546, April 2008. find
  3. G. Amdahl, “Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities,” AFIPS Conference Proceedings 30(1967), 483-485. find
  4. K. Asanovic, R. Bodik, B. Catanzaro, J. Gebis, K. Keutzer, D. Patterson, W. Plishker, J. Shalf, S. Williams, K. Yelick. “The landscape of parallel computing research: A view from Berkeley.” Tech. Rep. UCB/EECS-2006-183, EECS, U.C. Berkeley, Dec 2006. find
  5. C. Bienia,. S. Kumar, J. Singh, and K. Li. “The PARSEC Benchmark Suite: Characterization and Architectural Implications,” Princeton University Technical Report TR-81 1-008, January 2008. find
  6. S. Bird et al, “A Case for Sensible Performance Counters,” submitted to the First USENIX Workshop on Hot Topics in Parallelism (HotPar ’09), Berkeley CA, March 2009. find
  7. E. Boyd, W. Azeem, H. Lee, T. Shih, S. Hung, and E. Davidson, “A Hierarchical Approach to Modeling and Improving the Performance of Scientific Applications on the KSR1,” Proc. 1994 Int’l Conf. on Parallel Processing, vol. 3, pp. 188-192, 1994. find
  8. D. Callahan, J. Cocke, and K. Kennedy. “Estimating interlock and improving balance for pipelined machines,” J. Parallel Distrb. Comput. 5, 334-358. 1988. find
  9. J. Chong, Private Communication, 2008. find
  10. P. Colella, “Defining Software Requirements for Scientific Computing,” presentation, 2004. find
  11. S. Carr and K. Kennedy, “Improving the Ratio of Memory Operations to Floating-Point Operations in Loops,” ACM TOPLAS 16(4) (Nov. 1994). find
  12. K. Datta, M. Murphy, V. Volkov, S. Williams, J. Carter, L. Oliker, D. Patterson, J Shalf, K. Yelick, “Stencil Computation Optimization and Autotuning on State-of-the-Art Multicore Architectures,” Supercomputing (SC08), 2008. find
  13. J. Demmel, J. Dongarra, V. Eijkhout, E. Fuentes, A. Petitet, R. Vuduc, R. Whaley, and K. Yelick, “Self Adapting Linear Algebra Algorithms and Software,” Proc. IEEE: Special Issue on Program Generation, Optimization, and Adaptation, 93 (2) 2005. find
  14. M. Dubois and F. A. Briggs, “Performance of Synchronized Iterative Processes in Multiprocessor Systems,” IEEE Trans. on Software Engineering SE-8, 4 (July 1982), 419-431. find
  15. M. Frigo and S. Johnson, "The Design and Implementation of FFTW3," Proc. IEEE: Special Issue on Program Generation, Optimization, and Platform Adaptation. 93 (2) 2005. find
  16. M. Harris, "Mapping Computational Concepts to GPUs," ACM SIGGRAPH Tutorials, Chapter 31, 2005. find
  17. J. Hennessy and D. Patterson, Computer Architecture: A Quantitative Approach, 4th ed., Boston, MA: Morgan Kaufmann Publishers, 2007. find
  18. M. Hill and M. Marty, “Amdahl's Law in the Multicore Era,” IEEE Computer, July 2008. find
  19. M. Hill and A. Smith, "Evaluating Associativity in CPU Caches," IEEE Trans. on Computers, 38(12), pp. 1612-1630, Dec. 1989. find
  20. E. Lazowska, J. Zahorjan, S. Graham, and K. Sevcik, Quantitative System Performance: Computer System Analysis Using Queueing Network Models, Prentice Hail, Upper Saddle River, NJ, 1984. find
  21. J. D. C. Little, "A Proof of the Queueing Formula L = λ W" Operations Research, 9, 383-387 (1961). find
  22. J. McCalpin, “STREAM: Sustainable Memory Bandwidth in High Performance Computers,” www.cs.virginia.edu/stream, 1995. find
  23. D. Patterson, “Latency Lags Bandwidth,” 47:10, CACM, Oct. 2004. find
  24. S. Williams, Autotuning Performance on Multicore Computers, PhD thesis, U.C. Berkeley, 2008. find
  25. S. Williams, J. Carter, L. Oliker, J. Shalf, K. Yelick, "Lattice Boltzmann Simulation Optimization on Leading Multicore Platforms," Int’l Parallel & Distributed Processing Symposium (IPDPS), 2008. find
  26. S. Williams, L. Oliker, R. Vuduc, J. Shalf, K. Yelick, J. Demmel, "Optimization of Sparse Matrix-Vector Multiplication on Emerging Multicore Platforms," Supercomputing (SC07), 2007. find
  27. M. Tikir, L. Carrington, E. Strohmaier, A. Snavely, "A Genetic Algorithms Approach to Modeling the Performance of Memory-bound Computations," Supercomputing (SC07), 2007. find
  28. A. Thomasian and P. Bay, “Analytic Queueing Network Models for Parallel Processing of Task Systems,” IEEE Trans. on Computers C-35, 12 (December 1986), 1045-1054. find
  29. R. Vuduc, J. Demmel, K. Yelick, S. Kamil, R. Nishtala, and B. Lee. “Performance Optimizations and Bounds for Sparse Matrix-Vector Multiply,” Supercomputing (SC02), Nov. 2002. find
  30. S. Woo, M. Ohara, E. Torrie, J-P Singh, and A. Gupta. “The SPLASH-2 programs: characterization and methodological considerations,” Proc. 22nd annual Int’l Symp. on Computer Architecture (ISCA '95), May 1995, 24 - 36. Categories and Subject Descriptors B.8.2 [Performance And Reliability]: Performance… find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/williams-2009-roofline-insightful-visual-performance-model/