1

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]
2
  • 1
    Can you do pattern matching on Exp Int? Then you could do away with lists/indexing altogether.
    – crockeea
    Nov 5, 2015 at 20:08
  • No, that results in a runtime exception. Even if it did work, I think it would compile down to highly branched code, which is not what you want in an Exp computation, because the execution time then depends on the input.
    – mszep
    Nov 5, 2015 at 20:39

2 Answers 2

2

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.)

4
  • I don't think this will work, since the library does not allow the programmer to spawn Acc computations within an Exp expression. It will typecheck, but will cause a runtime error. The reason the library writers have done this I believe is to prevent the execution of nested data parallel expressions, which would be very hard to run efficiently on e.g. a GPU.
    – mszep
    Nov 6, 2015 at 0:37
  • 1
    hmmm... could you just hard code the values using A.use $ A.fromList ... like the nofib example does? e.g. this code
    – ErikR
    Nov 6, 2015 at 0:55
  • Looks like you get the same problem, because A.fromList returns an Acc Array, which you're not allowed to embed in an Exp computation...
    – mszep
    Nov 6, 2015 at 1:11
  • You can clearly use A.! in an Acc computation. See for instance the pagerank example. Note that the ranks ! ... expression is a Exp Float. Perhaps a more detailed example of what you want to do would help so we can actually try to write the code and run it.
    – ErikR
    Nov 6, 2015 at 1:43
1

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.

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.