SCoPing SNAP

This post describes my (ultimately failed) attempts to run Tadashi (missing reference) on SNAP.

TL;DR

Detecting SCoPs
The new error
Running the pre-processor and lessons learned (aka PET uses ~clang~)
Product of parameters error
Macros simulating fortran arrays
Ultimate failure and examples of non-SCoPs

SCoP finding utilities: `scop_detector` and `scops_in_dir`

Tadashi relies on ISL and more accurately PET (Verdoolaege & Grosser, 2012) to extract the SCoP from a source file. It is not hard to write a utility which exclusively does this and instead of any serious polyhedral compilation it just gives a rough (or complete if time/space allows it)

Old stuff

In the search for realistic apps I wrote scop_detector, a very simple program which would run PET’s automatic scop detection algorithm on any given .c file, and print out the found schedule trees along with a summary (number of SCoPs, max depth of SCoPs, filename, etc.). Since this worked only on single files, a natural course of action was to add support for multiple files. This was achieved by wrapping it in a Bash script (scops_in_dir) which iterated (recursively) through all .c file in a directory and invoked scop_detector with them. This made “probing” projects for SCoPs trivial: clone/download the source code, run scops_in_dir and keep an eye out for a big/deep schedule tree. SNAP was one of the first apps which looked promising to extract SCoPs from!

scop_detector showed a deep schedule tree indicating multiple nested loops, which was promising, but it also printed an error which I saw for the first time saying “data dependent conditions not supported”. The error message was coming from code copied from PPCG (Verdoolaege et al., 2013), which was copied as part of the dead code elimination algorithm. The code revealed a loop with a boundary being a product of two parameters. It seemed that product can be calculated as a new SCoP parameter (before the SCoP). However, after the attempt to fix this issue the error still persisted.

References

Polyhedral Extraction Tool

Sven Verdoolaege and Tobias Grosser

May 2012

Abs

We present a new library for extracting a polyhedral model from C source. The library is based on clang, the LLVM C frontend, and isl, a library for manipulating quasi-affine sets and relations. The use of clang for parsing the C code brings advanced diagnostics and full support for C99. The use of isl allows for an easy construction and a powerful and compact representation of the polyhedral model. Besides allowing arbitrary piecewise quasi-affine index expressions and conditions, the library also supports some data dependent constructs and has special treatment for unsigned integers. The library has been successfully used to obtain polyhedral models for use in an equivalence checker, a tool for constructing polyhedral process networks, a parallelizer targeting GPUs and an interactive polyhedral environment.
Polyhedral Parallel Code Generation for CUDA

Sven Verdoolaege, Juan Carlos Juega, Albert Cohen, and 3 more authors

ACM Transactions on Architecture and Code Optimization, Jan 2013

Abs DOI

This article addresses the compilation of a sequential program for parallel execution on a modern GPU. To this end, we present a novel source-to-source compiler called PPCG. PPCG singles out for its ability to accelerate computations from any static control loop nest, generating multiple CUDA kernels when necessary. We introduce a multilevel tiling strategy and a code generation scheme for the parallelization and locality optimization of imperfectly nested loops, managing memory and exposing concurrency according to the constraints of modern GPUs. We evaluate our algorithms and tool on the entire PolyBench suite.

Enjoy Reading This Article?

Here are some more articles you might like to read next: