Learning about Optimizing for Parallelism and Locality


(Robert Bigelow) #1

Hello Everyone,

I’m a grad student trying to put together an independent study to follow up my Compilers class and would like to explore the material in chapter 11 of the “Dragon book” which covers optimizations for parallelism and locality. I find that I learn best when I implement something in code, and so would like to have a project for this independent study. For this project, I was thinking of using an existing compiler that I could write some analyses for and then use those to implement one or more optimizations that employ the affine transform theory developed in that chapter. The ultimate goal would be to output vectorized code given some (relatively simple) array-intensive sequential program. To that end, I have a few questions for the Swift compiler experts.

  1. Would the Swift compiler be an appropriate choice for this endeavor, or should I go straight to Clang/LLVM?
  2. Is there currently work in progress (or completed) for vectorizing loops by emitting SIMD instructions?
  3. Does this seem like a reasonable goal for a 1 semester course?

I’m sure I’ll have some followup questions based on the responses to the above questions, but that’s it for now. Thank you for taking the time to read this post!

Rob Bigelow


(Andrew Trick) #2

I suggest writing your analysis based on LLVM's mid-level IR. That will work with both Swift and C code. It would be great if you could, as extra credit, evaluate cases in which the equivalent Swift code isn't being vectorized.


(Andrew Trick) #3

The answer to this question is "yes". See http://llvm.org/docs/Vectorizers.html.
And if you want more details, the llvm-dev mailing list is the place to go. You can also take a look at the source in llvm/lib/Transforms/Vectorize.


(Robert Bigelow) #4

Thanks for your response, Andrew. That makes sense to do the work in LLVM's IR. I'll include your suggestion for extra credit in my plan. I was just reading about cases like this in a blog post about numeric programming in Swift that @Chris_Lattner3 linked. The author pointed out some opportunities for vectorizing reductions.

If all goes well I'll be starting this project in mid-May (I still have to get approval from my professor.)