PLDI'2009 | Petabricks: A Language and Compiler for Algorithmic Choice

[ganler]

Paper: https://groups.csail.mit.edu/commit/papers/2009/ansel-pldi09.pdf Slides:

• http://groups.csail.mit.edu/commit/papers/2009/ansel-pldi09-slides.pdf
• https://people.cs.rutgers.edu/~uli/cs673/papers/PetaBricks-pldi09-Slides.pdf
• https://pdfs.semanticscholar.org/6890/4ce3ec9c832b9f0d1ae83293968a7ede0777.pdf

[ganler]

Paper Summary

General solutions are usually not optimal for a specific domain. Taking sorting, for example, the performance of the different algorithms is always related to data distribution, vector length, etc. Since existing compilers are optimizing codes for general performance, Petabrick is motivated to be a compiler optimized for specialized performance by tuning the best configuration for a specific scenario. To tackle this challenge, Petabrick first needs to model the search space of algorithmic choices. It then requires users to specify the accuracy of the algorithm for even better performance given the desired speed-accuracy tradeoff. Petabrick is also a parallel compiler that generates codes that can be executed in parallel using its multi-thread scheduler. Petabrick is also a language extending standard C++. It leverages the concept of transform to identify the input and output data layout, and the term rules to model the search space and strategies. Petabricks then compiles the codes into C++ and use its runtime library to schedule the execution and choices (but the tuning happens at compilation time). During tuning, it follows the dependency graph of algorithmic choices to tune everything from bottom to up. The threading scheduler is also implemented with a work-stealing mechanism to adapt dynamic workloads.

Strength

• Tuning approach is elegant and general for most cases;
• Achieving great performance speedup compared with single-choice approaches;
• Able to handle parallel processing and the results show that the optimized codes are scalable in terms of performance;
• Automatic consistency checking improves the reliability of codes;

Weakness

• No mention of compilation time. Since it is PGO and based on C++, compilation time might be extremely costly especially it needs to be compiled many times;
• Petabrick did not compare its approach with other hybrid algorithm implementations. For example, the sorting algorithm in C++ STL is also a hybrid one, but it did not compare with it.

How to extend

• Conduct benchmark with other hand-crafted hybrid algorithms;
• Optimize the compilation time to make it practical;

---

Valuable discussion from course

• think about 1) transformation space; 2) tuning strategy; & 3) cost model;
• 1: data structure choices;
• 2: learning-based;
• 3: cost model:
• brainstorm: how to model different input data structure automatically?