05-futhark.md

Introduction to the language Futhark

\cimg{figs/futhark.png}{scale=0.60}{Futhark}{Source: Taken from https://commons.wikimedia.org/, ref. URL03}

Futhark is a purely functional programming language for producing parallelizable code on (+CPU) or (+GPU). It was designed by Troels Henriksen, Cosmin Oancea and Martin Elsman at the University of Copenhagen. The main goal of Futhark is to write generic code that can compile into either:

• (+OpenCL),
• (+CUDA),
• multi-threaded (+POSIX) C,
• sequential C,
• sequential Python.

Although a Futhark code can compile into an executable, this feature reserves for testing purposes because there is no (+IO). Thus, the main interest is to write particular functions that you would like to speed up thanks to parallel programming and compile in library mode. In this mode, the compiler convert our Futhark code in sequential C, multi-threaded (+POSIX) C, (+OpenCL), or (+CUDA) code depending on which backend we want.

\pagebreak

Example in pure Futhark

To better understand Futhark, here is a simple example: calculating the factorial of a number [@henriksen_basic_2021].

let fact (n: i32): i32 = reduce (*) 1 (1...n)
let main (n: i32): i32 = fact n

As we can see, the function fact defines the factorial of a number as the successive multiplication of numbers from one to n through the function reduce. The program's entry point, main, takes as parameter a number n and calls the function fact with this number.

futhark opencl fact.fut
echo 12 | ./fact

To compile the Futhark code, we have to specify a backend; Here we compile in (+OpenCL) to run the program on the graphics card, and we run the program with the number 12 as the parameter.

479001600i32

The program calculates the factorial of 12 and therefore returns 479 001 600.

Example using Futhark C API

In this other example, we use Futhark in a C program to perform a very specific operation, in this case to calculate the factorial of a number. We use the library mode of the Futhark compiler, and we use the (+OpenCL) backend to convert the Futhark code.

entry fact (n: i32): i32 = reduce (*) 1 (1...n)

In a Futhark file (fact.fut), we define the function fact like the previous example. In library mode, the compiler convert all functions preceded with the keyword entry. Thus, the fact function is respecting this rule in order to use it in a C code.

futhark opencl --lib fact.fut

Then you have to convert the Futhark code in library mode and specify the backend. Here, the factorial program is converted in (+OpenCL). Finally, it generates a fact.h and fact.c file, which can be included in a C program.

#include <stdio.h>
#include <stdlib.h>
#include "fact.h"

int main(int argc, char **argv) {
    int number = atoi(argv[1]);
    
    /* Futhark Init */
    struct futhark_context_config *futcfg = futhark_context_config_new();
    struct futhark_context *futctx = futhark_context_new(futcfg);
    
    /* Main Code */
    int result;
    futhark_entry_fact(futctx, &result, number);
    printf("%d\n", result);

    /* Futhark Free */
    futhark_context_config_free(futcfg);
    futhark_context_free(futctx);
    return 0;
}

The program initializes a Futhark configuration and a Futhark context (futhark_context_config_new, futhark_context_new); then, the program calls the fact function, which has been converted in (+OpenCL). It is called via the function futhark_entry_fact, which takes as arguments the Futhark context, an integer pointer to store the result, and the number whose factorial desire.

futhark opencl --library fact.fut
gcc fact.c -c
gcc main.c -o fact fact.o -lOpenCL -lm

./fact 12
479001600

After compiling in library mode our Futhark code, we compile the generated code with our main code via (+GCC). The program's execution with the factorial of 12 returns the correct value, i.e. 479 001 600.

\pagebreak