Anders Persson

17 years at Ericsson
7 years ASIC development
10 years embedded software

Industrial Ph.D student at Chalmers

Background

• Embedded systems need fast programs

• Fast programs means highly optimized

• Optimization means target specific

• Target specific means non-portable

• Non-portable means increased maintenence

• Increased maintenence means less time to optimize programs

What we want

• High performance, easily maintained code that runs on many platforms

• Write programs that write programs, instead of writing programs

Feldspar
A Domain Specific Language for High-Performance DSP

Developed in collaboration between

• Chalmers

• Ericsson

Open source

Installation:

cabal install feldspar-language
cabal install feldspar-compiler

Feldspar

A functional language embedded in Haskell

• Reuse syntax

• Reuse type checker

A Feldspar program is a Haskell program written using Feldspar libraries

Generates code that can run on the target architecture

Feldspar Architecture

Example: distance between two points

type Point = (Data Float, Data Float)

dist :: Point -> Point -> Data Float
dist (x1,y1) (x2,y2) = sqrt (square (x1-x2) + square (y1-y2))
  where
    square x = x*x

• Removing the word Data gives the same definition in ordinary Haskell

*Main> eval dist (5,10) (8,6)
5.0

Functional DSP

Typical DSP operations

• Element-wise multiplication:   
• Moving average:                     
• Scalar product:                       

elemMult  :: [Float] -> [Float] -> [Float]
movingAvg :: [Float] -> [Float]
sProd     :: [Float] -> [Float] -> Float

Functional DSP in
Haskell and Feldspar

Haskell:

elemMult  :: [Float] -> [Float] -> [Float]
movingAvg :: [Float] -> [Float]
sProd     :: [Float] -> [Float] -> Float

elemMult as bs =
movingAvg as   =
sProd as bs    =

Functional DSP in
Haskell and Feldspar

Haskell:

elemMult  :: [Float] -> [Float] -> [Float]
movingAvg :: [Float] -> [Float]
sProd     :: [Float] -> [Float] -> Float

elemMult as bs = zipWith (*) as bs
movingAvg as   =
sProd as bs    =

Functional DSP in
Haskell and Feldspar

Haskell:

elemMult  :: [Float] -> [Float] -> [Float]
movingAvg :: [Float] -> [Float]
sProd     :: [Float] -> [Float] -> Float

elemMult as bs = zipWith (*) as bs
movingAvg as   = zipWith (\a a' -> (a+a')/2) (tail as) as
sProd as bs    =

Functional DSP in
Haskell and Feldspar

Haskell:

elemMult  :: [Float] -> [Float] -> [Float]
movingAvg :: [Float] -> [Float]
sProd     :: [Float] -> [Float] -> Float

elemMult as bs = zipWith (*) as bs
movingAvg as   = zipWith (\a a' -> (a+a')/2) (tail as) as
sProd as bs    = sum $ zipWith (*) as bs

elemMult  :: Vector1 Float -> Vector1 Float -> Vector1 Float
movingAvg :: Vector1 Float -> Vector1 Float
sProd     :: Vector1 Float -> Vector1 Float -> Data Float

elemMult as bs = zipWith (*) as bs
movingAvg as   = zipWith (\a a' -> (a+a')/2) (tail as) as
sProd as bs    = sum $ zipWith (*) as bs

Generating C code

Haskell code not suitable for running directly in a base station

• Very limited memory
• Top speed needed

But Feldspar produces efficient C code:

*Main> icompile elemMult
...
void test(struct array * v0, struct array * v1, struct array * out)
{
    uint32_t len0;

    len0 = min(getLength(v0), getLength(v1));
    initArray(out, sizeof(float), len0);
    for(uint32_t v2 = 0; v2 < len0; v2 += 1)
    {
        at(float,out,v2) = (at(float,v0,v2) * at(float,v1,v2));
    }
}

Modularity

Which one is most readable?

movingAvg :: Vector1 Float -> Vector1 Float
movingAvg as = zipWith (\a a' -> (a+a')/2) (tail as) as

movingAvg2 :: Vector1 Float -> Vector1 Float
movingAvg2 as = map (/2) $ zipWith (+) (tail as) as

Loop fusion

Which one is most efficient?

movingAvg :: Vector1 Float -> Vector1 Float
movingAvg as = zipWith (\a a' -> (a+a')/2) (tail as) as

movingAvg2 :: Vector1 Float -> Vector1 Float
movingAvg2 as = map (/2) $ zipWith (+) (tail as) as

Loop fusion

*Main> icompile movingAvg
...
void test(struct array * v0, struct array * out)
{
    uint32_t v2;
    uint32_t len0;

    v2 = getLength(v0);
    len0 = min((v2 - min(v2, 1)), v2);
    initArray(out, sizeof(float), len0);
    for(uint32_t v1 = 0; v1 < len0; v1 += 1)
    {
        at(float,out,v1) = ((at(float,v0,(v1 + 1))
                           + at(float,v0,v1)) / 2.0f);
    }
}

Loop fusion

*Main> icompile movingAvg2
...
void test(struct array * v0, struct array * out)
{
    uint32_t v2;
    uint32_t len0;

    v2 = getLength(v0);
    len0 = min((v2 - min(v2, 1)), v2);
    initArray(out, sizeof(float), len0);
    for(uint32_t v1 = 0; v1 < len0; v1 += 1)
    {
        at(float,out,v1) = ((at(float,v0,(v1 + 1))
                           + at(float,v0,v1)) / 2.0f);
    }
}

Loop fusion

Feldspar’s vector library guarantees fusion!

• Predictable compilation
• Encourages modular data-centric programming

Representing embedded languages

Haskell makes it very convenient to represent expressions as recursive data types. For example:

-- Arithmetic expressions
data Expr = Num Int
          | Add Expr Expr
          | Mul Expr Expr

-- Evaluation
eval :: Expr -> Int
eval (Num n)     = n
eval (Add e1 e2) = eval e1 + eval e2
eval (Mul e1 e2) = eval e1 * eval e2

Embedded language API

num :: Int -> Expr
num = Num

(<+>) :: Expr -> Expr -> Expr
(<+>) = Add

(<*>) :: Expr -> Expr -> Expr
(<*>) = Mul

prog = (num 10 <*> num 4) <+> (num 34 <+> num 6)

*Main> eval prog
80

Improved API

instance Num Expr
  where
    fromInteger = Num . fromInteger
    (+)         = (<+>)
    (*)         = (<*>)

prog2 :: Expr
prog2 = 10*4 + 34 + 6

Simple code generation

Convert an expression to a sequence of variable assignments:

*Main> compile (10*4 + 34 + 6)
v0 = 10
v1 = 4
v2 = v0*v1
v3 = 34
v4 = v2+v3
v5 = 6
v6 = v4+v5

Simple code generation

var v = "v" ++ show v

assign v expr = var v ++ " = " ++ expr ++ "\n"

matchOp (Add e1 e2) = ("+",e1,e2)
matchOp (Mul e1 e2) = ("*",e1,e2)

compile' :: Int -> Expr -> (String,Int)
compile' v (Num n) = (assign v (show n), v)
compile' v0 e      = (code1 ++ code2 ++ code3, v3)
  where
    (op,e1,e2) = matchOp e
    (code1,v1) = compile' v0     e1
    (code2,v2) = compile' (v1+1) e2
    v3         = v2+1
    code3      = assign v3 (var v1 ++ op ++ var v2)

compile :: Expr -> IO ()
compile = putStrLn . fst . compile' 0

Simple code generation

prog2 :: Expr
prog2 = 10*4 + 34 + 6

*Main> compile prog2
v0 = 10
v1 = 4
v2 = v0*v1
v3 = 34
v4 = v2+v3
v5 = 6
v6 = v4+v5

• The user writes Haskell-like code
• The compiler works on a much simpler language
• Embedded languages are powerful!

High-level sugar

The language API can be extended without changing the Expr type

Simple example, loop construct:

loop :: Int -> (Expr -> Expr) -> (Expr -> Expr)
loop 0 f = id
loop n f = f . loop (n-1) f

• Using Haskell to generate embedded programs
• Advantage: Can give advanced constructs (like loop) to the user, while keeping the expressions simple

Example

*Main> compile (loop 5 (*2) 30)
v0 = 30
v1 = 2
v2 = v0*v1
v3 = 2
v4 = v2*v3
v5 = 2
v6 = v4*v5
v7 = 2
v8 = v6*v7
v9 = 2
v10 = v8*v9

Feldspar implementation

• Same basic idea as the simple Expr language
• A recursive data type to represent programs
• An evaluator and a C code generator
• Lots of high-level sugar!
  • Most constructs are based on sugar
  • E.g. the Vector type only exists as sugar

Summary

Functional programming suitable for numeric processing and DSP

• Encourages data-centric programming instead of loops
• Absence of side-effects enables high-level optimizations such as fusion

Embedding is a powerful implementation technique

• Reuse type system, etc.
• Rich language to the user, simple language to the compiler

Summary

Feldspar allows you to use high-level functional programming for performance-critical software

Some work remains

• Better memory usage
• Deployment on multi-core architectures
• Debugging
• Etc.