CODEWITHSUNDEEP
haskellgpgpuaccelerate-haskell
mszep
mszep

Reputation: 420

Look-up table in haskell accelerate

I'm doing a fun side project using Haskell's accelerate library. I have a function that I need to write, which in pure Haskell would look like this:

oddfac :: Int -> Int
oddfac n = product [1,3...n]

i.e. similar to the factorial function, but only multiplying the odd numbers. I'd like to execute this function on the accelerate backend, so if I understand things correctly, it needs to become of type Exp Int -> Exp Int. However, the library doesn't allow arbitrary expressions to be evaluated in Exp, for performance reasons. Fortunately, I only ever need to evaluate this function for small values, e.g. n<=7. I had the idea to define a list (or array) of precalculated return values so that simply indexing it would return the appropriate value, and each evaluation would take the same amount of time, which is not the case for the naive version. However, I have not been able to find a way to do this. I now have two questions:

1) Is there a way to do this, i.e. to define a hardcoded array which is then indexed to retrieve the appropriate value within a function of type Exp a -> Exp b?

2) Am I going about things in an efficient way? Are there any obvious flaws in how I am thinking about this prolem?

UPDATE

The following works, based on @ErikR's answer and subsequent comment:

module Test where

import Data.Array.Accelerate as A
import Prelude as P

oddfac :: Exp Int -> Exp Int
oddfac n = (use $ A.fromList (Z :. 6) [1, 1, 3, 3, 15, 15]) A.! (index1 n)

alloddfac :: Acc (Vector Int)
alloddfac = A.map oddfac $ use $ A.fromList (Z :. 3) [1, 3, 5]

Upvotes: 1

Views: 631

Answers (2)

Cactus
Cactus

Reputation: 27636

You can "throw over the fence" from Haskell into Exp arbitrary arrays via to the (Shape sh, Elt e) => Lift Acc (Array sh e) instance. So you can create your lookup table in Haskell and then just lift it:

import Data.Array.Accelerate as A hiding (product)

oddfac :: Int -> Int
oddfac n = product [1,3..n]

oddfacs :: Vector Int
oddfacs = A.fromFunction (Z :. 7) (\(Z :. i) -> oddfac i)

lut :: Acc (Vector Int)
lut = A.lift oddfacs

The rest is then doable a la @ErikR's answer, by indexing into the lookup table lut.

Upvotes: 1

ErikR
ErikR

Reputation: 52049

It would seem to me that you could create an Acc (Array DIM1 Int) using one of several methods and then use Accelerate's (!) with the index1 function to index into the array.

Note that Vector a is an alias for Array DIM1 a.

Here's how to create an Acc (Vector Int) of the odd factorials (7 elements):

oddfacts :: Acc (Vector Int)
-- analogous to: take 7 $ scanl (*) 1 [3,5..]
oddfacts = A.scanl (*) (constant (1::Int)) $ A.enumFromStepN (A.index1 (constant (7::Int))) (constant (3::Int)) (constant (2::Int))

and here's how to index into it:

foo :: Exp Int -> Exp Int
foo n = oddfacts A.! (A.index1 n)

and how you might use it with a conditional:

bar :: Exp Int-> Exp Int
bar n = (n <=* (constant (7::Int))) ?
           ( oddfacts A.! (A.index1 n)
           , constant (0::Int)           -- return 0 if n > 7
           )

Caveat - I haven't actually run this code, but it type checks.

The examples in the accelerate-examples package has a lot of code that uses the array generation functions (A.generate, A.scanl, etc.) and the indexing functions (A.index1, A.index2, etc.)

Upvotes: 2

Related Questions