How is a Google Summer of Code in Graphite ?
During your Summer of Code you will be part of an international team working on Graphite. We meet once a week on the phone and stay the rest of the week in touch using the gcc-graphite mailing list. Once in a while we meet up at important conferences like the GCC Summit, the GROW workshop or have our own small meetings at INRIA or at AMD Austin/TX.
There have already been many successful summer of code students in Graphite. Tobias did the Summer of Code 2008 working on SCoP detection (Blog), Li Feng (Blog) worked in 2009 on automatic parallelization, Riyadh Baghdadi (page) worked in 2010 on adding SCoPLib support to Graphite (Page).
As a student you should know that working on GCC seems to be difficult, but it is not. Or at least not as difficult as you think. Just jump into the code - some well written, some a little ugly - related to your project and you will get all the support you need to be successful. The best way to find out if you could work on Graphite is to fix a small bug. We will glade to point you to a simple one and support you to get it fixed.
The following advices will help you prepare your Google summer of code proposal : 5 advices to get your Google Summer of Code proposal accepted.
Graphite Google Summer of Code ideas
Graphite has a long TODO list with open ideas. So we extracted some self contained project ideas for Summer of Code students. But you can also look at the open projects on the Graphite TODO list or propose your own idea
GCC has even more Summer of Code Projects in other areas of the Compiler.
Region based SCoP detection (2010)
Replace the ugly SCoP detection with a modern Region based approach. The SCoP detection finds the subgraphs of the CFG that Graphite is able to optimize. At the moment this algorithm is very specific and hard to extend, so we would like to split it in two general parts. The first one just detects all possible regions that could be optimized. The second part finds the largest regions that fit in the polytope model. 1. There are two possible approaches for the first part. Approach one is to follow up on a patchset already available. Approach two is to implement a region detection pass as it was currently developed for llvm http://wiki.llvm.org/RegionInfo
The advantage of approach one is that a patchset for step 1 is already available, so it is probably easier to finish. However there are some advantages with the second approach. It does not have to change the CFG upfront and is therefore probably less invasive. Furthermore the algorithm to detect the regions is really short. You should have a look at both approaches and decide which one is better suited for Graphite. You might also reason about the coverage the different approaches will achieve.
See also: http://gcc.gnu.org/wiki/Graphite/SCoP_detection_on_sese_regions Patchset: http://groups.google.com/group/gcc-graphite/browse_frm/thread/28c8db4b90ae7d43#
TODO
- Find all possible regions in the CFG of a function.
- Extend the scalar evolution so that it can be run on a region.
- Find the maximal regions that can be extracted by graphite
- Fix all bugs that show up on your way.
- Add statistics how much coverage we get.
- Add debug output that show why some regions cannot be found by graphite
Contact: Sebastian Pop, TobiasGrosser
Port Graphite to the current CLooG version (2010)
Graphite uses its own version of CLooG since it was merged into trunk two years ago. The reasons why we created our own fork were mainly license restriction with the old polylib backend. However today there are two new backends for CLooG that are both compatible with the current GCC license. CLooG-ISL and CLooG-Parma.
CLooG-Parma is a rewrite of CLooG-PPL, the CLooG fork Graphite uses at the moment. CLooG-PPL and CLooG-Parma use both the Parma Polyhedra Library, however CLooG-Parma is based on the most recent CLooG version, whereas CLooG-PPL uses a CLooG version from two years ago. Moving to CLooG-Parma will give us better and faster code generation and allows us to take advantage of further CLooG development.
CLooG-ISL is based on the newly developed integer set library (ISL). It often able to generate even better code than CLooG-Parma, as it takes advantage of the integrity of the polyhedron (all numbers are integers). This enables further optimizations.
TODO
- Port Graphite to the current CLooG HEAD version
- Test Graphite with the cloog isl backend
- Test Graphite with the cloog parma backend
- Port the old cloog-ppl backend to the new interface for backward compatibility
- Compare all three backends in terms of runtime e.g. using the SPEC benchmarks or polyhedron.com benchmarks.
Contact: TobiasGrosser
Add SCoPLib support to Graphite (2010)
Besides of Graphite there are several polyhedral optimization frameworks. Most of them are developed at universities like Pluto, LooPo and several others. It would be great if Graphite could to take advantage of the algorithms implemented in these projects.
Therefore it is necessary to exchange the data using a common representation. An already established standard is the SCoPlib (OpenScop git repository). SCoPLib is a library to read/write polyhedral descriptions of programs. It is implemented in Pluto, CLAN, and CLooG and will soon be implemented in LooPo. Enable Graphite to read write SCoPLib will allow us and all researches to try their new optimizations easily. Either in established tools or new ideas, that do not need to worry about gcc internals.
TODO
- Write SCoPLib Import/Export
- Write test cases using the SCoPLib Import/Export
Connect with at least one tool that can optimize SCoPlib (e.g. Pluto)
Contact: Sebastian Pop, TobiasGrosser
Polyhedral transformations/optimizations in GRAPHITE (2010)
Beside the set of traditional loop transformations, which always work on loops, we might do optimizations in Graphite just by trying to get array accesses close by. These optimizations are a lot closer to the polyhedral model, as we do not think any more about loops but just statements and the point in time, when they are executed. So instead of applying some loop interchange to some loops, we just try to change the schedule of the statements in a way that accesses to the same array are as close as possible in time. The effect might be a normal loop interchange, but also some transformations that can not be expressed easily by traditional transformations.
This project is actually not well defined, as we only had some ideas. So you will jump in the darkness. But we hope there might be some interesting optimization opportunities for you.
Contact: Sebastian Pop, TobiasGrosser
TODO
- Think about what you want to optimize
- Find some test cases where your optimization brings performance by just changing the C code.
- Implement your optimization in graphite.
- Find heuristics that allow to automatically apply them.
Traditional loop transformations in GRAPHITE (2010)
There are a set of traditional loop transformations like interchange, strip-mining, blocking, fusion and splitting that compilers implement. Currently Graphite does a little blocking and interchange, but there are still some missing ones and for the implemented ones the heuristics have to be improved.
Contact: Sebastian Pop Info: Part of it is already implemented. Probably there is still enough to be done.
TODO
- Find testcases where traditional loop transformations improve performance.
- Implement some of the traditional loop transformations.
- Find heuristics that allow to automatically apply them.
Improve Parallel code generation (2010)
Graphite can - thanks to Li - parallelize simple loops. It would be great to investigate the improvements because of this. Which loops can be parallelized? In which benchmarks are parallelization opportunities? And does Graphite parallelize them. Afterwords the runtime should be measured and improvements/regressions should be analyzed. During this analysis the basic implementation Li contributed should be improved such that at the end GCC is able to parallelize a reasonable number of Loops in well known benchmarks. This should be provable with numbers that either show Graphite does well, or that shows that more advanced algorithms are necessary to handle them, but graphite is able to extract these loops and could pass them e.g. to Pluto.
Contact: Sebastian Pop, TobiasGrosser
TODO
- Analyye several benchmarks and find interesting loops.
- Check if they can be found by Graphite
- Fix bugs that stopped Graphite from analyzing them
- Analyze performance and fix performance limitations in Graphite