View source for Roofline model

{{Short description|Visual performance model}}
[[File:Example of a Roofline model.svg|thumb|275px|An example of a roofline model in its basic form. As the image shows, the curve consists of two platform-specific performance ceilings: the processor's peak performance and a ceiling derived from the memory bandwidth. Both [[Cartesian coordinate system|axes]] are in [[Logarithmic scale|logarithmic scale]]]]
The '''roofline model''' is an intuitive visual [[Analytical Performance Modeling|performance model]] used to provide [[Computer performance|performance]] estimates of a given [[Compute kernel|compute kernel]] or application running on [[Multi-core processor|multi-core]], many-core, or [[Hardware acceleration|accelerator]] [[Microarchitecture|processor architectures]], by showing inherent hardware limitations, and potential benefit and priority of [[Program optimization|optimizations]]. By combining [[Locality of reference|locality]], [[Bandwidth (computing)|bandwidth]], and different [[Parallel computing|parallelization]] paradigms into a single performance figure, the model can be an effective alternative to assess the quality of attained performance instead of using simple percent-of-peak estimates, as it provides insights on both the implementation and inherent performance limitations.

The most basic roofline model can be visualized by plotting [[FLOPS|floating-point performance]] as a function of machine peak performance{{vague|date=January 2018}}{{clarify|date=January 2018}}, machine peak bandwidth, and arithmetic intensity. The resultant curve is effectively a performance bound under which kernel or application performance exists, and includes two platform-specific performance ceilings{{clarify|reason=What is a ceiling in this context?|date=January 2018}}: a ceiling derived from the memory bandwidth and one derived from the processor's peak performance (see figure on the right).

== Related terms and performance metrics ==

=== Work ===
The ''work'' <math>W</math> denotes the number of operations performed by a given [[Compute kernel|kernel]] or application.<ref name=":0" /> This metric may refer to any type of operation, from number of [[Array data structure|array]] points updated, to number of [[Integer (computer science)|integer]] operations, to number of floating point operations (FLOPs),<ref>{{Cite book|title=Computer Organisation and Design|author=David A.Patterson, John L. Hennessy|page=543}}</ref> and the choice of one or another is driven by convenience. In the majority of the cases however, <math>W</math> is expressed as ''FLOPs''.<ref name=":0" /><ref name="WilliamsPhD" /><ref name=":1" /><ref name=":2">{{Cite journal|last1=Ilic|first1=A.|last2=Pratas|first2=F.|last3=Sousa|first3=L.|date=2014-01-01|title=Cache-aware Roofline model: Upgrading the loft|journal=IEEE Computer Architecture Letters|volume=13|issue=1|pages=21–24|doi=10.1109/L-CA.2013.6|s2cid=9208032|issn=1556-6056}}</ref><ref name=":3">{{Cite journal|last1=Lorenzo|first1=Oscar G.|last2=Pena|first2=Tomás F.|last3=Cabaleiro|first3=José C.|last4=Pichel|first4=Juan C.|last5=Rivera|first5=Francisco F.|date=2014-03-31|title=Using an extended Roofline Model to understand data and thread affinities on NUMA systems|url=http://revistaseug.ugr.es/index.php/amgp/article/view/1992|journal=Annals of Multicore and GPU Programming|language=en|volume=1|issue=1|pages=56–67|issn=2341-3158}}</ref>

Note that the ''work'' <math>W</math> is a property of the given kernel or application and thus depend just partially on the platform characteristics.

=== Memory traffic ===
The ''memory traffic'' <math>Q</math> denotes the number of [[Byte|byte]]s of memory transfers incurred during the execution of the kernel or application.<ref name=":0" /> In contrast to <math>W</math>, <math>Q</math> is heavily dependent on the properties of the chosen platform, such as for instance the structure of the [[Cache (computing)|cache]] hierarchy.<ref name=":0" />

=== Arithmetic intensity ===
The ''arithmetic intensity'' <math>I</math>, also referred to as ''operational intensity'',<ref name="WilliamsPhD" /><ref>{{Cite web|url=https://crd.lbl.gov/departments/computer-science/PAR/research/roofline/|title=Roofline Performance Model|last=|first=|date=|website=|publisher=Lawrence Berkeley National Laboratory|access-date=19 June 2016}}</ref> is the ratio of the work <math>W</math> to the memory traffic <math>Q</math>:<ref name=":0" /><math display="block">I = {W \over Q}</math>and denotes the number of operations per byte of memory traffic. When the work <math>W</math> is expressed as ''FLOPs'', the resulting arithmetic intensity <math>I</math> will be the ratio of floating point operations to total data movement (''FLOPs/byte'').

== Naive Roofline ==
[[File:Example of a naive Roofline model.svg|thumb|275px|Example of a naïve roofline plot where two [[Compute kernel|kernels]] are reported. The first (vertical dashed red line) has an ''arithmetic intensity'' <math>O_1</math> that is underneath the ''peak bandwidth'' ceiling (diagonal solid black line), and is then ''[[Memory bound function|memory-bound]]''. Instead, the second (corresponding to the rightmost vertical dashed red line) has an ''arithmetic intensity'' <math>O_2</math> that is underneath the ''peak performance'' ceiling (horizontal solid black line), and thus is ''[[CPU-bound|compute-bound]]''.]]
The ''naïve roofline''<ref name="WilliamsPhD">{{cite thesis |type=Ph.D. |last=Williams |first=Samuel W. |date=2008 |title=Auto-tuning Performance on Multicore Computers |publisher=University of California at Berkeley}}</ref> is obtained by applying simple bound and bottleneck analysis.<ref>{{Cite book|last1=Kourtis|first1=Kornilios|last2=Goumas|first2=Georgios|last3=Koziris|first3=Nectarios|title=Proceedings of the 5th conference on Computing frontiers |chapter=Optimizing sparse matrix-vector multiplication using index and value compression |date=2008-01-01|series=CF '08|location=New York, NY, USA|publisher=ACM|pages=87–96|doi=10.1145/1366230.1366244|isbn=9781605580777|citeseerx=10.1.1.140.9391|s2cid=8038147}}</ref> In this formulation of the roofline model, there are only two parameters, the ''peak [[Computer performance|performance]]'' and the ''peak [[Bandwidth (computing)|bandwidth]]'' of the specific [[Microarchitecture|architecture]], and one variable, the ''arithmetic intensity''. The peak performance, in general expressed as [[FLOPS|GFLOPS]], can be usually derived from [[Benchmark (computing)|benchmarking]], while the peak bandwidth, that references to peak [[Dynamic random-access memory|DRAM]] bandwidth to be specific, is instead obtained via architectural manuals.<ref name=":0" /><ref name="WilliamsPhD" /> The resulting plot, in general with both [[Cartesian coordinate system|axes]] in [[Logarithmic scale|logarithmic scale]], is then derived by the following formula:<ref name=":0">{{Cite book|last1=Ofenbeck|first1=G.|last2=Steinmann|first2=R.|last3=Caparros|first3=V.|last4=Spampinato|first4=D. G.|last5=Püschel|first5=M.|title=2014 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS) |chapter=Applying the roofline model |date=2014-03-01|pages=76–85|doi=10.1109/ISPASS.2014.6844463|isbn=978-1-4799-3606-9|s2cid=206992177}}</ref><math display="block">P = \min \begin{cases} \pi\\ \beta \times I \end{cases}</math>where <math>P</math> is the ''attainable performance,'' <math>\pi</math> is the ''peak performance'', <math>\beta</math> is the ''peak bandwidth'' and <math>I</math> is the ''arithmetic intensity.'' The point at which the performance saturates at the peak performance level <math>\pi</math>, that is where the diagonal and horizontal roof meet, is defined as ''ridge point.''<ref name=":1">{{Cite journal|last1=Williams|first1=Samuel|last2=Waterman|first2=Andrew|last3=Patterson|first3=David|date=2009-04-01|title=Roofline: An Insightful Visual Performance Model for Multicore Architectures|journal=Commun. ACM|volume=52|issue=4|pages=65–76|doi=10.1145/1498765.1498785|s2cid=7766361|issn=0001-0782|url=https://zenodo.org/record/1236156}}</ref> The ridge point offers insight on the machine's overall performance, by providing the minimum arithmetic intensity required to be able to achieve peak performance, and by suggesting at a glance the amount of effort required by the programmer to achieve peak performance.<ref name=":1" />

A given [[Compute kernel|kernel]] or application is then characterized by a point given by its arithmetic intensity <math>I</math> (on the x-axis). The attainable performance <math>P</math> is then computed by drawing a vertical line that hits the roofline curve. Hence. the kernel or application is said to be ''[[Memory bound function|memory-bound]]'' if <math>I \leq \pi/\beta</math>. Conversely, if <math>I \geq \pi/\beta</math>, the  [[Computation|computation]] is said to be [[CPU-bound|''compute-bound'']].<ref name=":0" />

== Adding ceilings to the model ==
The ''naive roofline'' provides just an upper bound (the theoretical maximum) to [[Computer performance|performance]]. Although it can still give useful insights on the attainable performance, it does not provide a complete picture of what is actually limiting it. If, for instance, the considered [[Compute kernel|kernel]] or application performs far below the roofline, it might be useful to capture other performance ceilings, other than simple peak [[Bandwidth (computing)|bandwidth]] and performance, to better guide the programmer on which [[Program optimization|optimization]] to implement, or even to assess the suitability of the [[Microarchitecture|architecture]] used with respect to the analyzed kernel or application.<ref name="WilliamsPhD" /> The added ceilings impose then a limit on the attainable performance that is below the actual roofline, and indicate that the kernel or application cannot break through anyone of these ceilings without first performing the associated optimization.<ref name="WilliamsPhD" /><ref name=":1" />

The roofline plot can be expanded upon three different aspects:  [[Data transmission|communication]], adding the ''bandwidth ceilings''; [[Computation|computation]], adding the so-called ''in-core ceilings''; and [[Locality of reference|locality]], adding the ''locality walls''.

<gallery mode="packed" heights="160px" style="text-align:left">
Roofline model bandwidth ceilings.png|An example of a roofline model with added ''[[Bandwidth (computing)|bandwidth]] ceilings''. In this model, the two additional ceilings represent the absence of [[Instruction prefetch|software prefetching]] and [[Non-uniform memory access|NUMA]] organization of [[Computer memory|memory]].
Roofline model in-core ceilings.png|An example roofline model with added ''in-core ceilings'', where the two added ceilings represent the lack of [[Instruction-level parallelism|instruction level parallelism]] and [[Task parallelism|task level parallelism]].
Roofline model locality walls.png|An example roofline model with ''locality walls''. The wall labeled as 3 C's denotes the presence all three types of [[CPU cache|cache misses]]: compulsory, capacity and conflict misses. The wall labeled as 2 C's represent the presence of either compulsory and capacity or compulsory and conflict misses. The last wall denotes the presence of just compulsory misses.
</gallery>

=== Bandwidth ceilings ===

The ''bandwidth ceilings'' are bandwidth diagonals placed below the idealized peak bandwidth diagonal. Their existence is due to the lack of some kind of memory related architectural optimization, such as [[Cache coherence|cache coherence]], or software optimization, such as poor exposure of [[Concurrency (computer science)|concurrency]] (that in turn limit bandwidth usage).<ref name="WilliamsPhD" /><ref name=":1" />

=== In-core ceilings ===

The ''in-core ceilings'' are roofline-like curve beneath the actual roofline that may be present due to the lack of some form of [[Parallel computing|parallelism]]. These ceilings effectively limit how high performance can reach. Performance cannot exceed an in-core ceiling until the underlying lack of parallelism is expressed and exploited. The ceilings can be also derived from architectural optimization manuals other than benchmarks.<ref name="WilliamsPhD" /><ref name=":1" />

=== Locality walls ===

If the ideal assumption that arithmetic intensity is solely a function of the kernel is removed, and the cache topology - and therefore [[CPU cache#Cache miss|cache misses]] - is taken into account, the arithmetic intensity clearly becomes dependent on a combination of kernel and architecture. This may result in a degradation in performance depending on the balance between the resultant arithmetic intensity and the ''ridge point''. Unlike "proper" ceilings, the resulting lines on the roofline plot are vertical barriers through which arithmetic intensity cannot pass without optimization. For this reason, they are referenced to as ''locality walls'' or ''arithmetic intensity'' ''walls.''<ref name="WilliamsPhD" /><ref name=":1" />

== Extension of the model ==
Since its introduction,<ref name="WilliamsPhD" /><ref name=":1" /> the model has been further extended to account for a broader set of metrics and hardware-related bottlenecks. Already available in literature there are extensions that take into account the impact of [[Non-uniform memory access|NUMA]] organization of [[Computer memory|memory]],<ref name=":3" /> of [[Out-of-order execution|out-of-order execution]],<ref name=":4">{{Cite book|last1=Cabezas|first1=V. C.|last2=Püschel|first2=M.|title=2014 IEEE International Symposium on Workload Characterization (IISWC) |chapter=Extending the roofline model: Bottleneck analysis with microarchitectural constraints |date=2014-10-01|pages=222–231|doi=10.1109/IISWC.2014.6983061|isbn=978-1-4799-6454-3|s2cid=33023605}}</ref> of [[Computer memory|memory]] [[Engineering:Latency (engineering)|latencies]],<ref name=":4" /><ref name=":5">{{Cite journal|last1=Lorenzo|first1=O. G.|last2=Pena|first2=T. F.|last3=Cabaleiro|first3=J. C.|last4=Pichel|first4=J. C.|last5=Rivera|first5=F. F.|date=2014-03-26|title=3DyRM: a dynamic roofline model including memory latency information|journal=The Journal of Supercomputing|language=en|volume=70|issue=2|pages=696–708|doi=10.1007/s11227-014-1163-4|s2cid=5318695|issn=0920-8542}}</ref> and to model at a finer grain the [[Cache (computing)|cache]] hierarchy<ref name=":2" /><ref name=":4" /> in order to better understand what is actually limiting performance and drive the [[Program optimization|optimization]] process.

Also, the model has been extended to better suit specific [[Microarchitecture|architectures]] and the related characteristics, such as [[Engineering:Field-programmable gate array|FPGAs]].<ref name=":6">{{Cite journal|last1=da Silva|first1=Bruno|last2=Braeken|first2=An|last3=D'Hollander|first3=Erik H.|last4=Touhafi|first4=Abdellah|date=2013-01-01|title=Performance Modeling for FPGAs: Extending the Roofline Model with High-level Synthesis Tools|journal= International Journal of Reconfigurable Computing|volume=2013|pages=1–10|doi=10.1155/2013/428078|issn=1687-7195|doi-access=free|hdl=1854/LU-4226966|hdl-access=free}}</ref>

==See also==

* [[Software performance testing]]
* [[Benchmark (computing)]]

== References ==

{{reflist}}

== External links ==
*[https://crd.lbl.gov/assets/pubs_presos/hotchips08-roofline-talk.pdf The Roofline Model: A Pedagogical Tool for Auto-tuning Kernels on Multicore Architectures]
* [http://www.spiral.net/software/roofline.html Applying the Roofline model]
*[http://www.spiral.net/software/bottleneck.html Extending the Roofline Model: Bottleneck Analysis with Microarchitectural Constraints]
* [https://bitbucket.org/berkeleylab/cs-roofline-toolkit Roofline Model Toolkit]
** [https://link.springer.com/chapter/10.1007/978-3-319-17248-4_7 Roofline Model Toolkit: A Practical Tool for Architectural and Program Analysis] - publication related to the tool.
* [https://github.com/GeorgOfenbeck/perfplot Perfplot]
* [https://github.com/caparrov/ERM Extended Roofline Model]
* [https://software.intel.com/en-us/articles/intel-advisor-roofline Intel Advisor - Roofline model automation]
* [https://www.youtube.com/watch?v=h2QEM1HpFgg Youtube Video on how to use Intel Advisor Roofline]

[[Category:Software testing]]
[[Category:Software optimization]]

{{Sourceattribution|Roofline model}}