Intel Tip: If you can’t break a memory roof, try to rework your algorithm for higher arithmetic intensity. This will move you to the right and give you more room to increase performance before hitting the memory bandwidth roof.
For algorithms in the memory-bound region of a roofline plot, Intel suggests increasing the arithmetic intensity so that they move to the right (compute-bound region) hence providing room to improve the performance, since the performance roof would be higher.
I'm unable to understand how increasing the arithmetic intensity (say, increasing the no. of operations in the algorithm) can possibly improve a performance metric like the wall-clock time taken for the algorithm to run. Wouldn't you need to do more no. of computations even for a higher performance (in FLOPS)? Could someone explain how this is possible?
Increasing the arithmetic alone is not sufficient to make the algorithm faster. The idea is if you have a choice between multiple algorithm and one of them is memory bound, then it is probably better to pick the other one assuming it is not much slower in practice since you can hardly optimize memory-bound algorithm while this is often much easier for compute-bound one. The memory latency did almost not improve much over the last decade and the bandwidth is only slowly increasing (much less than the number of FLOPS of processors). This is known as the Memory Wall (stated several decades ago). Moving data becomes so expensive nowadays that it is sometimes better to recompute operations rather than storing the previous results. This is especially true for very large data since the bigger the data structure the slower it is. This situation is expected to become worse over the next decades. Thus, a slower compute-bound algorithm can become faster than a memory-bound one in a near future (especially if it can-be/is parallelized).