Hacker News Reader

Comment by misnome | Hacker News Reader

This sounds interesting, but the documentation is really sparse, basically only how to turn it on. Am I supposed to be thinking of this a bit like Intel’s Parallel Studio’s Advisor tools for analysing threading and vectorisation? How do I tell what it’s doing with e.g. adding OpenMP calls since it seems to insert them between parsing and object code without oversight?

Basically, how easy is it, and how do I approach using this, as a non domain-expert?

View on HN

The best resources on understanding Polly are probably various LLVM developer conference talks (it’s come up at nearly every one since at least 2010 or so).

But just like not needing to worry too much about how GCC does this unless you’re a compiler engineer, I’d say just either let it try or not.

Edit: Here's the 2011 talk (http://llvm.org/devmtg/2011-11/Grosser_PollyOptimizations.pd...) that I think is a good yet old intro. Tobias's more recent work (say http://www.grosser.es/bibliography/doerfert2017optimistic.ht...) is a good "what's possible now-ish". But again, these are both compiler-researcher papers.

> The best resources on understanding Polly are probably various LLVM developer conference talks

I don't suppose there are videos available?

There are!

https://m.youtube.com/channel/UCv2_41bSAa5Y_8BacJUZfjQ

https://youtu.be/A8E5KgzZPMM

https://llvm.org/devmtg/

these are great! thanks

My understanding is that this is only about memory access patterns, and has nothing to do with multithreading. The basic example being matrix multiplications C=A∙B. If the matrices are too big to fit in the L2/L3 cache, you have to think about how to optimize memory access. So instead of having the compiler just generate instructions to read/write memory, you want it to interleave instructions to prefetch memory, ahead of time. But how do you do that? What is the best point in time to prefetch?

Another optimization is locality: The basic algorithm is to loop over i and j, then multiply A's row i with B's column j. You do that with another loop over k to compute the sum over Aᵢₖ∙Bₖⱼ, then store the result in Cᵢⱼ. But what if one row or column is already too big for the cache? Also, once you invested into loading the data into the cache, you want to make the best use of it. You don't want to load it again if you can avoid it. So what you do is you limit the loop ranges for i, j, and k such that the overall memory accessed fits into the cache. But what are the optimal loop sizes?

The answers depends on the CPU architecture (cache sizes) and probably also the memory that you're using.

I don't know about this specific example, but polyhedral optimization generally, at least, is useful for parallelization of such loops, e.g. http://pluto-compiler.sourceforge.net/. However, serial GEMM is typically most important in HPC, with parallelization at a higher level.

(GEMM shouldn't be main memory limited, if that's what you mean.)

Reply on news.ycombinator.com