Algorithmic Species: A Classification of Program Code for Parallel Programming
By Cedric NugterenTool
Overview of Algorithmic Species
Algorithmic species is an algorithm classification technique targeted at parallel programming. Species are classes of algorithms, capturing among others the amount and structure of parallelism and data re-use in nested for-loops. Algorithmic species are derived from a polyhedral representation of code, but provide a more intuitive description of classes, similar to skeletons or pattern languages.
ASET (algorithmic species extraction tool) is a tool to automatically annotate C program code with algorithmic species information. It is based on pet (Polyhedral Extraction Tool)
. A-DARWIN (automatic Darwin) is a newer tool to automatically extract algorithmic species. The main differences are that it is no longer based on the polyhedral tools but on static analysis of the AST. Additionally, it can extract the new SPECIES+ classification.
Obtain A-DARWIN, ASET, examples, documentation and references:
Bones: A Parallelizing Source-to-Source Compiler Based on Algorithmic Skeletons
By Cedric Nugteren and Gert-Jan van den BraakTool
Overview of Bones
Recent advances in multi-core and many-core processors requires programmers to exploit an increasing amount of parallelism from their applications. Data parallel languages such as CUDA and OpenCL make it possible to take advantage of such processors, but still require a large amount of effort from programmers. To address the challenge of parallel programming, we introduce Bones.
Bones is a source-to-source compiler based on algorithmic skeletons and a new algorithm classification. The compiler takes C-code annotated with class information as input and generates parallelized target code. Targets include NVIDIA GPUs (through CUDA), AMD GPUs (through OpenCL) and x86 CPUs (through OpenCL and OpenMP). Bones is open-source, written in the Ruby programming language, and is available through our website. The compiler is based on the C-parser CAST, which is used to parse the input code into an abstract syntax tree (AST) and to generate the target code from a transformed AST.
Obtain the source code and documentation
Installation of Bones is a simple matter of extracting the Bones package to a directory of your choice or installing the gem 'gem install bones-compiler
'. However, there are a number of prerequisites. Bones requires the installation of Ruby, the Rubygems gem package manager and two gems:
- Any version of Ruby 1.8 or 1.9. Information on Ruby is found at ruby-lang.org.
- [OS X]: Ruby is pre-installed on any OS X system since Tiger (10.4).
- [Linux]: Ruby is pre-installed on some Linux based systems. Most Linux package managers (yum, apt-get) will be able to provide a Ruby installation. Make sure that the ruby development package ('ruby-devel') is also installed, as it is required by one of the gems.
- [Windows]: Ruby for Windows can be obtained from rubyinstaller.org.
- The Rubygems gem package manager. Information on Rubygems can be found at rubygems.org.
- [OS X]: Rubygems is pre-installed on any OS X system since Tiger (10.4).
- [Linux]: Most Linux package managers will be able to provide a Rubygems installation by installing the package 'rubygems'.
- [Windows]: Rubygems for Windows is obtained automatically when installing from rubyinstaller.org.
- Bones requires three gems, trollop, cast, and symbolic. These gems can be installed by calling Rubygems from the command line, i.e.: 'gem install trollop cast symbolic'.
For example, all prerequisites can be installed as follows on a Fedora, Red-Hat or CentOS system:
yum install ruby ruby-devel rubygems
gem install trollop cast symbolic
For an Ubuntu, Debian or Mint system, the equivalent commands are:
apt-get install ruby ruby-devel rubygems
gem install trollop cast symbolic
To install the compiler, simply extract the 'bones_x.x.x.tar.gz
' package to a directory of your choice. The Bones executable is found in the 'bin
' subdirectory. Including the path to the 'bin
' directory to your environmental variable 'PATH
' will make Bones available from any directory on your machine. You can also install the gem: 'gem install bones-compiler
The usage is as follows:
bones --application <input> --target <target> [OPTIONS]
With the following flags:
--application, -a <s>: Input application file
--target, -t <s>: Target processor (choose from: GPU-CUDA, GPU-OPENCL-AMD,
CPU-OPENCL-INTEL, CPU-OPENCL-AMD, CPU-OPENMP, CPU-C)
--measurements, -m: Enable/disable timers
--verify, -c: Verify correctness of the generated code
--version, -v: Print version and exit
--help, -h: Show this message
Bones can be invoked from the command-line. Two arguments (-a and -t) are mandatory, others are optional. This is an example of the usage of Bones assuming the file 'example.c
' to be present:
bones -a example.c -t GPU-CUDA -c