Like 2017, Polly Labs participates as a mentoring organizations at Google Summer of Code 2018. Even before 2017 we participated indirectly through the LLVM Foundation and Julia.
This page is meant as a starting point for students interested in submitting a project proposal to our organization.
First and foremost, please contact us before applying. You can reach us for enquiries related to any of our projects through the Polly Labs mailinglist. We can help you deciding which project you want to work on and review your proposal. In our experience, the proposals submitted by students who contacted us first are vastly better than those who did not.
The detailed guide is available at the How-to-apply page.
In summary:
We will ask you to do a minor contribution to your project of choice, for instance, fix a small bug. This helps you to get familiar with our patch workflow and gives us an idea about your skills.
Chose one of the project suggestions below or propose you own.
Write a proposal using the template found at the How-to-apply page.
Let use review your proposal before submitting the final version.
These people have agreed to potentially mentor a project:
Here are some ideas for projects
These are some projects students can apply for. The list is not exhaustive, we are open to more project suggestions.
PRL is a runtime library for PPCG-generated code. Its main advantages over ocl_utilities.c used by default by PPCG are that it reuses the OpenCL objects (context, command queue, etc) and the programs compiled by the OpenCL driver so it does not have to be recompiled every time a PPCG-optimized region starts execution. It also allows reusing memory buffers allocated on the GPU, with fine-grained control over when they have to be transferred between host and accelerator.
This library currently only exists for OpenCL. In CUDA the program compilation and persistent objects are managed by CUDA and its runtime. However, there is currently no control over data transfers when using CUDA. The goal for this GSoC project is to add CUDA-support to PRL.
Things to do in this project:
Required knowledge: C, Low-level CUDA
Estimated difficulty: Moderate
Possible mentor(s): Michael Kruse and/or Chandan Reddy
Fuzzy-testing could be a useful tool for finding bugs in the existing implementation. Unfortunately for both projects it is not as easy as launching libFuzzer or American Fuzzy Lop.
In case of Polly, this merely tests the bitcode parser which has not been fortified against fuzzing itself yet. Also, the probability to hit something that just remotely looks like a SCoP is rather low. That probability is not much higher when using llvm-stress which also has the problem that it can only generate certain categories of nested loop structures. A tool that can find whether some condition can occur and produce reduced test cases that are otherwise difficult to find would be very valuable.
For isl simple fuzzing would just test the parser. More interesting would be if it could test the library’s other public functions as well. For instance, some error conditions can get hit only in unusual circumstances.
This project is more about developing tools for fuzzing and finding bugs than to fix them. The community would try to fix the bugs on the majority of cases. Possible strategies are:
Required knowledge: LLVM bitcode, Fuzzing
Estimated difficulty: Easy
Possible mentor: Michael Kruse
Last year, Sebastian Pop and Aditya Kumar published the article "SCoP Detection: A Fast Algorithm for Industrial Compilers >". It presents a more compile-time efficient algorithm to find SCoPs on the IR-Level which they implemented in GCC Graphite.
This project’s idea is to either implement a similar algorithm in Polly or improve the detection in other ways, e.g., currently the same IR is checked multiple times. Polly’s ScopDetection pass is currently based on LLVM’s RegionInfo. which in turn uses LLVM’s DominanceFrontier analysis. The latter is considered deprecated and has quadratic worst-case behavior. Not least the current ScopDetection does a lot of redundant computation.
Required knowledge: Polyhedral model
Estimated difficulty: Very difficult
Possible mentors: Tobias Grosser, Andreas Simbürger
Transformation passes in LLVM can chose to either preserve an analysis’ result by adapting it to the changes it made or let the pass manager throw the analysis away to force it being recomputed when needed again. Due to Polly’s current pass structure, Polly must preserve all analyses it uses or the pass manager will throw away Polly’s SCoP analysis themselves.
Currently Polly does not preserve all analysis as well as it could do. Most of the time it preserves just enough information such that other SCoPs in the same function can still be processed correctly. There is an ugly workaround to ensure that the analyses are recomputed for add other passes.
The following analyses must be preserved.
The main goal of this project is to ensure that all analysis are preserved correctly such that they pass their verifyAnalysis function and no miscompilation occurs with the barrier disabled. Stretch goals are to improve the quality of analysis preservation, for instance that loops in the generated code are added to LoopInfo.
Required knowledge: LLVM pass manager (old and new)
Difficulty: Moderate
Possible mentors: Michael Kruse
Even though Polly’s compile time is today not a lot higher than other non-trial IR passes, the need to version code in many situations and the lack of static knowledge about loop iteration counts, hotness of functions, and parameter requires Polly to be significantly more conservative than it would need to be. The goal of this project is to connect Polly with the LLVM profiling infrastructure to exploit profiling information to decide: 1) when to run Polly, 2) how aggressive to version the code, 3) which code version to emit, and 4) which assumptions to take. As a result, Polly should can in profile guided builds become more aggressive, while still having a lower compile time and code size impact.
Required knowledge: PGO in LLVM
Possible mentors: Tobias Grosser
The Chapel compiler supports an LLVM backend and early experiments with Polly integration indicated that Polly was not identifying loops from Chapel kernels an analyzable. This goal of this project is to figure out what is going wrong and address the issue. Addressing the issue might require patching Polly or Chapel and the student will be expected to work with the appropriate developers to make that happen. Once Polly is recognizing loops from Chapel, the next step in this project is to demonstrate some simple Chapel loops running on a GPU through Polly integration.
Wanted knowledge: Polly, Chapel
Estimated difficulty: moderate
Possible mentors: Michael Kruse, Michael Ferguson
The Polyhedral Playground is an interactive Jupyter worksheet for trying out the Integer Set Library and polyhedral compilation.
Here are some ideas on what can be worked on:
Required knowledge: Jupyter, JavaScript, EmScripten
Estimated difficulty: moderate; easy if you have experience with those technologies
Possible mentors: Tobias Grosser, Oleksandr Zinenko
We have two (competing) implementations that optimize schedules for spatial locality. Polly’s rescheduler currently only optimize for temporal locality.
The task is to evaluate these spatial optimzers and implement at least one of them in Polly. Individal features of both implementations might even be combined. In addtion, Tensor Comprehensions has functionality that we might also be interested in.
Required knowledge: C, C++, understanding of the underlying polyhedral theory is a plus
Estimated difficulty: harder
Possible mentors: Sven Verdoolaege, Oleksandr Zinenko
Our ability to optimize programs depends on how we measure them. At the moment we mostly use Polybench. The project is to assemble more benchmarks that a polyhedral optimizer should be able to transform. The benchmark program should only contain the performance-relevant kernel, with no obstacles which could make transformation illegal (e.g. indirect arrays, aliasing, overflows, function calls, etc.) The goal is to add these benchmarks to LLVM’s test-suite.
Fields which we think are underrepresented in our current benchmark set:
Required knowledge: C, C++
Estimated difficulty: Easy