| Copyright | [2008..2017] Manuel M T Chakravarty Gabriele Keller [2009..2017] Trevor L. McDonell [2013..2017] Robert Clifton-Everest [2014..2014] Frederik M. Madsen |
|---|---|
| License | BSD3 |
| Maintainer | Trevor L. McDonell <tmcdonell@cse.unsw.edu.au> |
| Stability | experimental |
| Portability | non-portable (GHC extensions) |
| Safe Haskell | None |
| Language | Haskell98 |
Data.Array.Accelerate
Contents
Description
Data.Array.Accelerate defines an embedded language of array computations
for high-performance computing in Haskell. Computations on multi-dimensional,
regular arrays are expressed in the form of parameterised collective
operations such as maps, reductions, and permutations. These computations are
online compiled and can be executed on a range of architectures.
- Abstract interface:
The types representing array computations are only exported abstractly; client code can generate array computations and submit them for execution, but it cannot inspect these computations. This is to allow for more flexibility for future extensions of this library.
- Stratified language:
Accelerate distinguishes the types of collective operations Acc from the
type of scalar operations Exp to achieve a stratified language. Collective
operations comprise many scalar computations that are executed in parallel,
but scalar computations can not contain collective operations. This
separation excludes nested, irregular data-parallelism statically; instead,
Accelerate is limited to flat data-parallelism involving only regular,
multi-dimensional arrays.
- Optimisations:
Accelerate uses a number of scalar and array optimisations, including array fusion, in order to improve the performance of programs. Fusing a program entails combining successive traversals (loops) over an array into a single traversal, which reduces memory traffic and eliminates intermediate arrays.
- Code execution:
Several backends are available which can be used to evaluate accelerate programs:
- Data.Array.Accelerate.Interpreter: simple interpreter in Haskell as a reference implementation defining the semantics of the Accelerate language
- accelerate-llvm-native: implementation supporting parallel execution on multicore CPUs (e.g. x86).
- accelerate-llvm-ptx: implementation supporting parallel execution on CUDA-capable NVIDIA GPUs.
- accelerate-cuda:
an older implementation supporting parallel execution on CUDA-capable
NVIDIA GPUs. NOTE: This backend is being deprecated in favour of
accelerate-llvm-ptx.
- Examples:
The accelerate-examples package demonstrates a range of computational kernels and several complete applications:
- Implementation of the canny edge detector
- Interactive Mandelbrot set generator
- N-body simulation of gravitational attraction between large bodies
- Implementation of the PageRank algorithm
- A simple, real-time, interactive ray tracer.
- A particle based simulation of stable fluid flows
- A cellular automaton simulation
- A "password recovery" tool, for dictionary attacks on MD5 hashes.
lulesh-accelerate is an implementation of the Livermore Unstructured Lagrangian Explicit Shock Hydrodynamics (LULESH) application. LULESH is representative of typical hydrodynamics codes, although simplified and hard-coded to solve the Sedov blast problem on an unstructured hexahedron mesh.
- For more information on LULESH: https://codesign.llnl.gov/lulesh.php.
- Additional components:
- accelerate-io: Fast conversion between Accelerate arrays and other formats (e.g. Repa, Vector).
- accelerate-fft: Fast Fourier transform, with FFI bindings to optimised implementations.
- accelerate-bignum: Fixed-width large integer arithmetic.
- colour-accelerate: Colour representations in Accelerate (RGB, sRGB, HSV, and HSL).
- gloss-accelerate: Generate gloss pictures from Accelerate.
- gloss-raster-accelerate: Parallel rendering of raster images and animations.
- lens-accelerate: Lens operators for Accelerate types.
- linear-accelerate: Linear vector space types for Accelerate.
- mwc-random-accelerate: Generate Accelerate arrays filled with high-quality pseudorandom numbers.
- Contact:
Mailing list for both use and development discussion:
- Bug reports: https://github.com/AccelerateHS/accelerate/issues
Maintainers:
- Trevor L. McDonell: mailto:tmcdonell@cse.unsw.edu.au
- Manuel M T Chakravarty: mailto:chak@cse.unsw.edu.au
- Tip:
Accelerate tends to stress GHC's garbage collector, so it helps to increase the default GC allocation sizes. This can be done when running an executable by specifying RTS options on the command line, for example:
./foo +RTS -A64M -n2M -RTS
You can make these settings the default by adding the following ghc-options
to your .cabal file or similar:
ghc-options: -with-rtsopts=-n2M -with-rtsopts=-A64M
To specify RTS options you will also need to compile your program with -rtsopts.
- data Acc a
- data Array sh e
- class (Typeable a, Typeable (ArrRepr a)) => Arrays a
- type Scalar e = Array DIM0 e
- type Vector e = Array DIM1 e
- type Segments i = Vector i
- class (Show a, Typeable a, Typeable (EltRepr a), ArrayElt (EltRepr a)) => Elt a
- data Z = Z
- data tail :. head = tail :. head
- type DIM0 = Z
- type DIM1 = DIM0 :. Int
- type DIM2 = DIM1 :. Int
- type DIM3 = DIM2 :. Int
- type DIM4 = DIM3 :. Int
- type DIM5 = DIM4 :. Int
- type DIM6 = DIM5 :. Int
- type DIM7 = DIM6 :. Int
- type DIM8 = DIM7 :. Int
- type DIM9 = DIM8 :. Int
- class (Elt sh, Elt (Any sh), Shape (EltRepr sh), FullShape sh ~ sh, CoSliceShape sh ~ sh, SliceShape sh ~ Z) => Shape sh
- class (Elt sl, Shape (SliceShape sl), Shape (CoSliceShape sl), Shape (FullShape sl)) => Slice sl where
- type SliceShape sl :: *
- type CoSliceShape sl :: *
- type FullShape sl :: *
- data All = All
- data Any sh = Any
- (!) :: (Shape sh, Elt e) => Acc (Array sh e) -> Exp sh -> Exp e
- (!!) :: (Shape sh, Elt e) => Acc (Array sh e) -> Exp Int -> Exp e
- the :: Elt e => Acc (Scalar e) -> Exp e
- null :: (Shape sh, Elt e) => Acc (Array sh e) -> Exp Bool
- length :: Elt e => Acc (Vector e) -> Exp Int
- shape :: (Shape sh, Elt e) => Acc (Array sh e) -> Exp sh
- size :: (Shape sh, Elt e) => Acc (Array sh e) -> Exp Int
- shapeSize :: Shape sh => Exp sh -> Exp Int
- use :: Arrays arrays => arrays -> Acc arrays
- unit :: Elt e => Exp e -> Acc (Scalar e)
- generate :: (Shape sh, Elt a) => Exp sh -> (Exp sh -> Exp a) -> Acc (Array sh a)
- fill :: (Shape sh, Elt e) => Exp sh -> Exp e -> Acc (Array sh e)
- enumFromN :: (Shape sh, Num e, FromIntegral Int e) => Exp sh -> Exp e -> Acc (Array sh e)
- enumFromStepN :: (Shape sh, Num e, FromIntegral Int e) => Exp sh -> Exp e -> Exp e -> Acc (Array sh e)
- (++) :: forall sh e. (Slice sh, Shape sh, Elt e) => Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e)
- (?|) :: Arrays a => Exp Bool -> (Acc a, Acc a) -> Acc a
- acond :: Arrays a => Exp Bool -> Acc a -> Acc a -> Acc a
- awhile :: Arrays a => (Acc a -> Acc (Scalar Bool)) -> (Acc a -> Acc a) -> Acc a -> Acc a
- class IfThenElse t where
- type EltT t a :: Constraint
- (>->) :: (Arrays a, Arrays b, Arrays c) => (Acc a -> Acc b) -> (Acc b -> Acc c) -> Acc a -> Acc c
- compute :: Arrays a => Acc a -> Acc a
- indexed :: (Shape sh, Elt a) => Acc (Array sh a) -> Acc (Array sh (sh, a))
- map :: (Shape sh, Elt a, Elt b) => (Exp a -> Exp b) -> Acc (Array sh a) -> Acc (Array sh b)
- imap :: (Shape sh, Elt a, Elt b) => (Exp sh -> Exp a -> Exp b) -> Acc (Array sh a) -> Acc (Array sh b)
- zipWith :: (Shape sh, Elt a, Elt b, Elt c) => (Exp a -> Exp b -> Exp c) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c)
- zipWith3 :: (Shape sh, Elt a, Elt b, Elt c, Elt d) => (Exp a -> Exp b -> Exp c -> Exp d) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d)
- zipWith4 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e) => (Exp a -> Exp b -> Exp c -> Exp d -> Exp e) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e)
- zipWith5 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f) => (Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f)
- zipWith6 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g) => (Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g)
- zipWith7 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h) => (Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g -> Exp h) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h)
- zipWith8 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i) => (Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g -> Exp h -> Exp i) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) -> Acc (Array sh i)
- zipWith9 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i, Elt j) => (Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g -> Exp h -> Exp i -> Exp j) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) -> Acc (Array sh i) -> Acc (Array sh j)
- izipWith :: (Shape sh, Elt a, Elt b, Elt c) => (Exp sh -> Exp a -> Exp b -> Exp c) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c)
- izipWith3 :: (Shape sh, Elt a, Elt b, Elt c, Elt d) => (Exp sh -> Exp a -> Exp b -> Exp c -> Exp d) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d)
- izipWith4 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e) => (Exp sh -> Exp a -> Exp b -> Exp c -> Exp d -> Exp e) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e)
- izipWith5 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f) => (Exp sh -> Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f)
- izipWith6 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g) => (Exp sh -> Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g)
- izipWith7 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h) => (Exp sh -> Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g -> Exp h) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h)
- izipWith8 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i) => (Exp sh -> Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g -> Exp h -> Exp i) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) -> Acc (Array sh i)
- izipWith9 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i, Elt j) => (Exp sh -> Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g -> Exp h -> Exp i -> Exp j) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) -> Acc (Array sh i) -> Acc (Array sh j)
- zip :: (Shape sh, Elt a, Elt b) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh (a, b))
- zip3 :: (Shape sh, Elt a, Elt b, Elt c) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh (a, b, c))
- zip4 :: (Shape sh, Elt a, Elt b, Elt c, Elt d) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh (a, b, c, d))
- zip5 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh (a, b, c, d, e))
- zip6 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh (a, b, c, d, e, f))
- zip7 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh (a, b, c, d, e, f, g))
- zip8 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) -> Acc (Array sh (a, b, c, d, e, f, g, h))
- zip9 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) -> Acc (Array sh i) -> Acc (Array sh (a, b, c, d, e, f, g, h, i))
- unzip :: (Shape sh, Elt a, Elt b) => Acc (Array sh (a, b)) -> (Acc (Array sh a), Acc (Array sh b))
- unzip3 :: (Shape sh, Elt a, Elt b, Elt c) => Acc (Array sh (a, b, c)) -> (Acc (Array sh a), Acc (Array sh b), Acc (Array sh c))
- unzip4 :: (Shape sh, Elt a, Elt b, Elt c, Elt d) => Acc (Array sh (a, b, c, d)) -> (Acc (Array sh a), Acc (Array sh b), Acc (Array sh c), Acc (Array sh d))
- unzip5 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e) => Acc (Array sh (a, b, c, d, e)) -> (Acc (Array sh a), Acc (Array sh b), Acc (Array sh c), Acc (Array sh d), Acc (Array sh e))
- unzip6 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f) => Acc (Array sh (a, b, c, d, e, f)) -> (Acc (Array sh a), Acc (Array sh b), Acc (Array sh c), Acc (Array sh d), Acc (Array sh e), Acc (Array sh f))
- unzip7 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g) => Acc (Array sh (a, b, c, d, e, f, g)) -> (Acc (Array sh a), Acc (Array sh b), Acc (Array sh c), Acc (Array sh d), Acc (Array sh e), Acc (Array sh f), Acc (Array sh g))
- unzip8 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h) => Acc (Array sh (a, b, c, d, e, f, g, h)) -> (Acc (Array sh a), Acc (Array sh b), Acc (Array sh c), Acc (Array sh d), Acc (Array sh e), Acc (Array sh f), Acc (Array sh g), Acc (Array sh h))
- unzip9 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i) => Acc (Array sh (a, b, c, d, e, f, g, h, i)) -> (Acc (Array sh a), Acc (Array sh b), Acc (Array sh c), Acc (Array sh d), Acc (Array sh e), Acc (Array sh f), Acc (Array sh g), Acc (Array sh h), Acc (Array sh i))
- reshape :: (Shape sh, Shape sh', Elt e) => Exp sh -> Acc (Array sh' e) -> Acc (Array sh e)
- flatten :: forall sh e. (Shape sh, Elt e) => Acc (Array sh e) -> Acc (Vector e)
- replicate :: (Slice slix, Elt e) => Exp slix -> Acc (Array (SliceShape slix) e) -> Acc (Array (FullShape slix) e)
- slice :: (Slice slix, Elt e) => Acc (Array (FullShape slix) e) -> Exp slix -> Acc (Array (SliceShape slix) e)
- init :: forall sh e. (Slice sh, Shape sh, Elt e) => Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e)
- tail :: forall sh e. (Slice sh, Shape sh, Elt e) => Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e)
- take :: forall sh e. (Slice sh, Shape sh, Elt e) => Exp Int -> Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e)
- drop :: forall sh e. (Slice sh, Shape sh, Elt e) => Exp Int -> Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e)
- slit :: forall sh e. (Slice sh, Shape sh, Elt e) => Exp Int -> Exp Int -> Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e)
- permute :: (Shape sh, Shape sh', Elt a) => (Exp a -> Exp a -> Exp a) -> Acc (Array sh' a) -> (Exp sh -> Exp sh') -> Acc (Array sh a) -> Acc (Array sh' a)
- ignore :: Shape sh => Exp sh
- scatter :: Elt e => Acc (Vector Int) -> Acc (Vector e) -> Acc (Vector e) -> Acc (Vector e)
- backpermute :: (Shape sh, Shape sh', Elt a) => Exp sh' -> (Exp sh' -> Exp sh) -> Acc (Array sh a) -> Acc (Array sh' a)
- gather :: (Shape sh, Elt e) => Acc (Array sh Int) -> Acc (Vector e) -> Acc (Array sh e)
- reverse :: Elt e => Acc (Vector e) -> Acc (Vector e)
- transpose :: Elt e => Acc (Array DIM2 e) -> Acc (Array DIM2 e)
- filter :: forall sh e. (Shape sh, Slice sh, Elt e) => (Exp e -> Exp Bool) -> Acc (Array (sh :. Int) e) -> Acc (Vector e, Array sh Int)
- fold :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array sh a)
- fold1 :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Acc (Array (sh :. Int) a) -> Acc (Array sh a)
- foldAll :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array sh a) -> Acc (Scalar a)
- fold1All :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Acc (Array sh a) -> Acc (Scalar a)
- foldSeg :: (Shape sh, Elt a, Elt i, IsIntegral i) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Segments i) -> Acc (Array (sh :. Int) a)
- fold1Seg :: (Shape sh, Elt a, Elt i, IsIntegral i) => (Exp a -> Exp a -> Exp a) -> Acc (Array (sh :. Int) a) -> Acc (Segments i) -> Acc (Array (sh :. Int) a)
- all :: (Shape sh, Elt e) => (Exp e -> Exp Bool) -> Acc (Array sh e) -> Acc (Scalar Bool)
- any :: (Shape sh, Elt e) => (Exp e -> Exp Bool) -> Acc (Array sh e) -> Acc (Scalar Bool)
- and :: Shape sh => Acc (Array sh Bool) -> Acc (Scalar Bool)
- or :: Shape sh => Acc (Array sh Bool) -> Acc (Scalar Bool)
- sum :: (Shape sh, Num e) => Acc (Array sh e) -> Acc (Scalar e)
- product :: (Shape sh, Num e) => Acc (Array sh e) -> Acc (Scalar e)
- minimum :: (Shape sh, Ord e) => Acc (Array sh e) -> Acc (Scalar e)
- maximum :: (Shape sh, Ord e) => Acc (Array sh e) -> Acc (Scalar e)
- scanl :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a)
- scanl1 :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a)
- scanl' :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> (Acc (Array (sh :. Int) a), Acc (Array sh a))
- scanr :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a)
- scanr1 :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a)
- scanr' :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> (Acc (Array (sh :. Int) a), Acc (Array sh a))
- prescanl :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a)
- postscanl :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a)
- prescanr :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a)
- postscanr :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a)
- scanlSeg :: forall sh e i. (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e)
- scanl1Seg :: (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e)
- scanl'Seg :: forall sh e i. (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e, Array (sh :. Int) e)
- prescanlSeg :: (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e)
- postscanlSeg :: (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e)
- scanrSeg :: forall sh e i. (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e)
- scanr1Seg :: (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e)
- scanr'Seg :: forall sh e i. (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e, Array (sh :. Int) e)
- prescanrSeg :: (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e)
- postscanrSeg :: (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e)
- stencil :: (Stencil sh a stencil, Elt b) => (stencil -> Exp b) -> Boundary a -> Acc (Array sh a) -> Acc (Array sh b)
- stencil2 :: (Stencil sh a stencil1, Stencil sh b stencil2, Elt c) => (stencil1 -> stencil2 -> Exp c) -> Boundary a -> Acc (Array sh a) -> Boundary b -> Acc (Array sh b) -> Acc (Array sh c)
- class (Elt (StencilRepr sh stencil), Stencil sh a (StencilRepr sh stencil)) => Stencil sh a stencil
- data Boundary a
- type Stencil3 a = (Exp a, Exp a, Exp a)
- type Stencil5 a = (Exp a, Exp a, Exp a, Exp a, Exp a)
- type Stencil7 a = (Exp a, Exp a, Exp a, Exp a, Exp a, Exp a, Exp a)
- type Stencil9 a = (Exp a, Exp a, Exp a, Exp a, Exp a, Exp a, Exp a, Exp a, Exp a)
- type Stencil3x3 a = (Stencil3 a, Stencil3 a, Stencil3 a)
- type Stencil5x3 a = (Stencil5 a, Stencil5 a, Stencil5 a)
- type Stencil3x5 a = (Stencil3 a, Stencil3 a, Stencil3 a, Stencil3 a, Stencil3 a)
- type Stencil5x5 a = (Stencil5 a, Stencil5 a, Stencil5 a, Stencil5 a, Stencil5 a)
- type Stencil3x3x3 a = (Stencil3x3 a, Stencil3x3 a, Stencil3x3 a)
- type Stencil5x3x3 a = (Stencil5x3 a, Stencil5x3 a, Stencil5x3 a)
- type Stencil3x5x3 a = (Stencil3x5 a, Stencil3x5 a, Stencil3x5 a)
- type Stencil3x3x5 a = (Stencil3x3 a, Stencil3x3 a, Stencil3x3 a, Stencil3x3 a, Stencil3x3 a)
- type Stencil5x5x3 a = (Stencil5x5 a, Stencil5x5 a, Stencil5x5 a)
- type Stencil5x3x5 a = (Stencil5x3 a, Stencil5x3 a, Stencil5x3 a, Stencil5x3 a, Stencil5x3 a)
- type Stencil3x5x5 a = (Stencil3x5 a, Stencil3x5 a, Stencil3x5 a, Stencil3x5 a, Stencil3x5 a)
- type Stencil5x5x5 a = (Stencil5x5 a, Stencil5x5 a, Stencil5x5 a, Stencil5x5 a, Stencil5x5 a)
- data Exp t
- class Elt a => Eq a where
- class Eq a => Ord a where
- type Bounded a = (Elt a, Bounded (Exp a))
- minBound :: Bounded a => a
- maxBound :: Bounded a => a
- type Num a = (Elt a, Num (Exp a))
- (+) :: Num a => a -> a -> a
- (-) :: Num a => a -> a -> a
- (*) :: Num a => a -> a -> a
- negate :: Num a => a -> a
- abs :: Num a => a -> a
- signum :: Num a => a -> a
- fromInteger :: Num a => Integer -> a
- type Integral a = (Enum a, Real a, Integral (Exp a))
- quot :: Integral a => a -> a -> a
- rem :: Integral a => a -> a -> a
- div :: Integral a => a -> a -> a
- mod :: Integral a => a -> a -> a
- quotRem :: Integral a => a -> a -> (a, a)
- divMod :: Integral a => a -> a -> (a, a)
- type Fractional a = (Num a, Fractional (Exp a))
- (/) :: Fractional a => a -> a -> a
- recip :: Fractional a => a -> a
- fromRational :: Fractional a => Rational -> a
- type Floating a = (Fractional a, Floating (Exp a))
- pi :: Floating a => a
- sin :: Floating a => a -> a
- cos :: Floating a => a -> a
- tan :: Floating a => a -> a
- asin :: Floating a => a -> a
- acos :: Floating a => a -> a
- atan :: Floating a => a -> a
- sinh :: Floating a => a -> a
- cosh :: Floating a => a -> a
- tanh :: Floating a => a -> a
- asinh :: Floating a => a -> a
- acosh :: Floating a => a -> a
- atanh :: Floating a => a -> a
- exp :: Floating a => a -> a
- sqrt :: Floating a => a -> a
- log :: Floating a => a -> a
- (**) :: Floating a => a -> a -> a
- logBase :: Floating a => a -> a -> a
- class (Real a, Fractional a) => RealFrac a where
- div' :: (RealFrac a, Elt b, IsIntegral b) => Exp a -> Exp a -> Exp b
- mod' :: (Floating a, RealFrac a, ToFloating Int a) => Exp a -> Exp a -> Exp a
- divMod' :: (Floating a, RealFrac a, Num b, IsIntegral b, ToFloating b a) => Exp a -> Exp a -> (Exp b, Exp a)
- class (RealFrac a, Floating a) => RealFloat a where
- class FromIntegral a b where
- class ToFloating a b where
- class Lift c e where
- type Plain e
- class Lift c e => Unlift c e where
- lift1 :: (Unlift Exp a, Lift Exp b) => (a -> b) -> Exp (Plain a) -> Exp (Plain b)
- lift2 :: (Unlift Exp a, Unlift Exp b, Lift Exp c) => (a -> b -> c) -> Exp (Plain a) -> Exp (Plain b) -> Exp (Plain c)
- lift3 :: (Unlift Exp a, Unlift Exp b, Unlift Exp c, Lift Exp d) => (a -> b -> c -> d) -> Exp (Plain a) -> Exp (Plain b) -> Exp (Plain c) -> Exp (Plain d)
- ilift1 :: (Exp Int -> Exp Int) -> Exp DIM1 -> Exp DIM1
- ilift2 :: (Exp Int -> Exp Int -> Exp Int) -> Exp DIM1 -> Exp DIM1 -> Exp DIM1
- ilift3 :: (Exp Int -> Exp Int -> Exp Int -> Exp Int) -> Exp DIM1 -> Exp DIM1 -> Exp DIM1 -> Exp DIM1
- constant :: Elt t => t -> Exp t
- fst :: forall a b. (Elt a, Elt b) => Exp (a, b) -> Exp a
- afst :: forall a b. (Arrays a, Arrays b) => Acc (a, b) -> Acc a
- snd :: forall a b. (Elt a, Elt b) => Exp (a, b) -> Exp b
- asnd :: forall a b. (Arrays a, Arrays b) => Acc (a, b) -> Acc b
- curry :: Lift f (f a, f b) => (f (Plain (f a), Plain (f b)) -> f c) -> f a -> f b -> f c
- uncurry :: Unlift f (f a, f b) => (f a -> f b -> f c) -> f (Plain (f a), Plain (f b)) -> f c
- (?) :: Elt t => Exp Bool -> (Exp t, Exp t) -> Exp t
- caseof :: (Elt a, Elt b) => Exp a -> [(Exp a -> Exp Bool, Exp b)] -> Exp b -> Exp b
- cond :: Elt t => Exp Bool -> Exp t -> Exp t -> Exp t
- while :: Elt e => (Exp e -> Exp Bool) -> (Exp e -> Exp e) -> Exp e -> Exp e
- iterate :: forall a. Elt a => Exp Int -> (Exp a -> Exp a) -> Exp a -> Exp a
- sfoldl :: forall sh a b. (Shape sh, Slice sh, Elt a, Elt b) => (Exp a -> Exp b -> Exp a) -> Exp a -> Exp sh -> Acc (Array (sh :. Int) b) -> Exp a
- (&&) :: Exp Bool -> Exp Bool -> Exp Bool
- (||) :: Exp Bool -> Exp Bool -> Exp Bool
- not :: Exp Bool -> Exp Bool
- subtract :: Num a => Exp a -> Exp a -> Exp a
- even :: Integral a => Exp a -> Exp Bool
- odd :: Integral a => Exp a -> Exp Bool
- gcd :: Integral a => Exp a -> Exp a -> Exp a
- lcm :: Integral a => Exp a -> Exp a -> Exp a
- (^) :: forall a b. (Num a, Integral b) => Exp a -> Exp b -> Exp a
- (^^) :: (Fractional a, Integral b) => Exp a -> Exp b -> Exp a
- index0 :: Exp Z
- index1 :: Elt i => Exp i -> Exp (Z :. i)
- unindex1 :: Elt i => Exp (Z :. i) -> Exp i
- index2 :: (Elt i, Slice (Z :. i)) => Exp i -> Exp i -> Exp ((Z :. i) :. i)
- unindex2 :: forall i. (Elt i, Slice (Z :. i)) => Exp ((Z :. i) :. i) -> Exp (i, i)
- index3 :: (Elt i, Slice (Z :. i), Slice ((Z :. i) :. i)) => Exp i -> Exp i -> Exp i -> Exp (((Z :. i) :. i) :. i)
- unindex3 :: forall i. (Elt i, Slice (Z :. i), Slice ((Z :. i) :. i)) => Exp (((Z :. i) :. i) :. i) -> Exp (i, i, i)
- indexHead :: (Slice sh, Elt a) => Exp (sh :. a) -> Exp a
- indexTail :: (Slice sh, Elt a) => Exp (sh :. a) -> Exp sh
- toIndex :: Shape sh => Exp sh -> Exp sh -> Exp Int
- fromIndex :: Shape sh => Exp sh -> Exp Int -> Exp sh
- intersect :: Shape sh => Exp sh -> Exp sh -> Exp sh
- ord :: Exp Char -> Exp Int
- chr :: Exp Int -> Exp Char
- boolToInt :: Exp Bool -> Exp Int
- bitcast :: (Elt a, Elt b, IsScalar a, IsScalar b, BitSizeEq a b) => Exp a -> Exp b
- foreignAcc :: (Arrays as, Arrays bs, Foreign asm) => asm (as -> bs) -> (Acc as -> Acc bs) -> Acc as -> Acc bs
- foreignExp :: (Elt x, Elt y, Foreign asm) => asm (x -> y) -> (Exp x -> Exp y) -> Exp x -> Exp y
- arrayRank :: Shape sh => sh -> Int
- arrayShape :: Shape sh => Array sh e -> sh
- arraySize :: Shape sh => sh -> Int
- indexArray :: Array sh e -> sh -> e
- fromFunction :: (Shape sh, Elt e) => sh -> (sh -> e) -> Array sh e
- fromList :: (Shape sh, Elt e) => sh -> [e] -> Array sh e
- toList :: forall sh e. Array sh e -> [e]
- (.) :: (b -> c) -> (a -> b) -> a -> c
- ($) :: (a -> b) -> a -> b
- error :: HasCallStack => [Char] -> a
- undefined :: HasCallStack => a
- const :: a -> b -> a
- data Int :: *
- data Int8 :: *
- data Int16 :: *
- data Int32 :: *
- data Int64 :: *
- data Word :: *
- data Word8 :: *
- data Word16 :: *
- data Word32 :: *
- data Word64 :: *
- data Float :: *
- data Double :: *
- data Bool :: *
- data Char :: *
- data CFloat :: *
- data CDouble :: *
- data CShort :: *
- data CUShort :: *
- data CInt :: *
- data CUInt :: *
- data CLong :: *
- data CULong :: *
- data CLLong :: *
- data CULLong :: *
- data CChar :: *
- data CSChar :: *
- data CUChar :: *
- class Typeable a => IsScalar a
- class (Num a, IsScalar a) => IsNum a
- class IsBounded a
- class (IsScalar a, IsNum a, IsBounded a) => IsIntegral a
- class (Floating a, IsScalar a, IsNum a) => IsFloating a
- class IsNonNum a
The Accelerate Array Language
Embedded array computations
Accelerate is an embedded language that distinguishes between vanilla arrays (e.g. in Haskell memory on the CPU) and embedded arrays (e.g. in device memory on a GPU), as well as the computations on both of these. Since Accelerate is an embedded language, programs written in Accelerate are not compiled by the Haskell compiler (GHC). Rather, each Accelerate backend is a runtime compiler which generates and executes parallel SIMD code of the target language at application runtime.
The type constructor Acc represents embedded collective array operations.
A term of type Acc a is an Accelerate program which, once executed, will
produce a value of type a (an Array or a tuple of Arrays). Collective
operations of type Acc a comprise many scalar expressions, wrapped in
type constructor Exp, which will be executed in parallel. Although
collective operations comprise many scalar operations executed in parallel,
scalar operations cannot initiate new collective operations: this
stratification between scalar operations in Exp and array operations in
Acc helps statically exclude nested data parallelism, which is difficult
to execute efficiently on constrained hardware such as GPUs.
For example, to compute a vector dot product we could write:
dotp :: Num a => Vector a -> Vector a -> Acc (Scalar a)
dotp xs ys =
let
xs' = use xs
ys' = use ys
in
fold (+) 0 ( zipWith (*) xs' ys' )The function dotp consumes two one-dimensional arrays (Vectors) of
values, and produces a single (Scalar) result as output. As the return type
is wrapped in the type Acc, we see that it is an embedded Accelerate
computation - it will be evaluated in the object language of dynamically
generated parallel code, rather than the meta language of vanilla Haskell.
As the arguments to dotp are plain Haskell arrays, to make these available
to Accelerate computations they must be embedded with the
use function.
An Accelerate backend is used to evaluate the embedded computation and return
the result back to vanilla Haskell. Calling the run function of a backend
will generate code for the target architecture, compile, and execute it. For
example, the following backends are available:
- accelerate-llvm-native: for execution on multicore CPUs
- accelerate-llvm-ptx: for execution on NVIDIA CUDA-capable GPUs
See also Exp, which encapsulates embedded scalar computations.
- Fusion:
Array computations of type Acc will be subject to array fusion;
Accelerate will combine individual Acc computations into a single
computation, which reduces the number of traversals over the input data and
thus improves performance. As such, it is often useful to have some intuition
on when fusion should occur.
The main idea is to first partition array operations into two categories:
- Element-wise operations, such as
map,generate, andbackpermute. Each element of these operations can be computed independently of all others. - Collective operations such as
fold,scanl, andstencil. To compute each output element of these operations requires reading multiple elements from the input array(s).
Element-wise operations fuse together whenever the consumer operation uses a single element of the input array. Element-wise operations can both fuse their inputs into themselves, as well be fused into later operations. Both these examples should fuse into a single loop:
map -> reverse -> reshape -> map -> map
map -> backpermute ->
zipWith -> map
generate ->If the consumer operation uses more than one element of the input array
(typically, via generate indexing an array multiple
times), then the input array will be completely evaluated first; no fusion
occurs in this case, because fusing the first operation into the second
implies duplicating work.
On the other hand, collective operations can fuse their input arrays into themselves, but on output always evaluate to an array; collective operations will not be fused into a later step. For example:
use ->
zipWith -> fold |-> map
generate ->Here the element-wise sequence (use
+ generate + zipWith) will
fuse into a single operation, which then fuses into the collective
fold operation. At this point in the program the
fold must now be evaluated. In the final step the
map reads in the array produced by
fold. As there is no fusion between the
fold and map steps, this
program consists of two "loops"; one for the use
+ generate + zipWith
+ fold step, and one for the final
map step.
You can see how many operations will be executed in the fused program by
Show-ing the Acc program, or by using the debugging option -ddump-dot
to save the program as a graphviz DOT file.
As a special note, the operations unzip and
reshape, when applied to a real array, are executed
in constant time, so in this situation these operations will not be fused.
- Tips:
- Since
Accrepresents embedded computations that will only be executed when evaluated by a backend, we can programatically generate these computations using the meta language Haskell; for example, unrolling loops or embedding input values into the generated code. - It is usually best to keep all intermediate computations in
Acc, and onlyrunthe computation at the very end to produce the final result. This enables optimisations between intermediate results (e.g. array fusion) and, if the target architecture has a separate memory space as is the case of GPUs, to prevent excessive data transfers.
Instances
Arrays
Dense, regular, multi-dimensional arrays.
The Array is the core computational unit of Accelerate; all programs in
Accelerate take zero or more arrays as input and produce one or more arrays
as output. The Array type has two type parameters:
- sh: is the shape of the array, tracking the dimensionality and extent of
each dimension of the array; for example,
DIM1for one-dimensionalVectors,DIM2for two-dimensional matrices, and so on. - e: represents the type of each element of the array; for example,
Int,Float, et cetera.
Array data is store unboxed in an unzipped struct-of-array representation.
Elements are laid out in row-major order (the right-most index of a Shape
is the fastest varying). The allowable array element types are members of the
Elt class, which roughly consists of:
- Signed and unsigned integers (8, 16, 32, and 64-bits wide).
- Floating point numbers (single and double precision)
CharBool- ()
- Shapes formed from
Zand (:.) - Nested tuples of all of these, currently up to 15-elements wide.
Note that Array itself is not an allowable element type---there are no
nested arrays in Accelerate, regular arrays only!
If device and host memory are separate, arrays will be transferred to the
device when necessary (possibly asynchronously and in parallel with other
tasks) and cached on the device if sufficient memory is available. Arrays are
made available to embedded language computations via
use.
Section "Getting data in" lists functions for getting data into and out of
the Array type.
Instances
| (Shape sh, Elt e) => Lift Acc (Array sh e) # | |
| Elt e => IsList (Vector e) # | |
| Show (Vector e) # | |
| Show (Scalar e) # | |
| (Eq sh, Eq e) => Eq (Array sh e) # | |
| Show (Array sh e) # | |
| Show (Array DIM2 e) # | |
| NFData (Array sh e) # | |
| (Shape sh, Elt e) => Arrays (Array sh e) # | |
| type Item (Vector e) # | |
| type Plain (Array sh e) # | |
class (Typeable a, Typeable (ArrRepr a)) => Arrays a #
Arrays consists of nested tuples of individual Arrays, currently up to
15-elements wide. Accelerate computations can thereby return multiple
results.
Minimal complete definition
arrays, flavour, toArr, fromArr
Instances
| Arrays () # | |
| (Arrays a, Arrays b) => Arrays (a, b) # | |
| (Shape sh, Elt e) => Arrays (Array sh e) # | |
| (Arrays a, Arrays b, Arrays c) => Arrays (a, b, c) # | |
| (Arrays a, Arrays b, Arrays c, Arrays d) => Arrays (a, b, c, d) # | |
| (Arrays a, Arrays b, Arrays c, Arrays d, Arrays e) => Arrays (a, b, c, d, e) # | |
| (Arrays a, Arrays b, Arrays c, Arrays d, Arrays e, Arrays f) => Arrays (a, b, c, d, e, f) # | |
| (Arrays a, Arrays b, Arrays c, Arrays d, Arrays e, Arrays f, Arrays g) => Arrays (a, b, c, d, e, f, g) # | |
| (Arrays a, Arrays b, Arrays c, Arrays d, Arrays e, Arrays f, Arrays g, Arrays h) => Arrays (a, b, c, d, e, f, g, h) # | |
| (Arrays a, Arrays b, Arrays c, Arrays d, Arrays e, Arrays f, Arrays g, Arrays h, Arrays i) => Arrays (a, b, c, d, e, f, g, h, i) # | |
| (Arrays a, Arrays b, Arrays c, Arrays d, Arrays e, Arrays f, Arrays g, Arrays h, Arrays i, Arrays j) => Arrays (a, b, c, d, e, f, g, h, i, j) # | |
| (Arrays a, Arrays b, Arrays c, Arrays d, Arrays e, Arrays f, Arrays g, Arrays h, Arrays i, Arrays j, Arrays k) => Arrays (a, b, c, d, e, f, g, h, i, j, k) # | |
| (Arrays a, Arrays b, Arrays c, Arrays d, Arrays e, Arrays f, Arrays g, Arrays h, Arrays i, Arrays j, Arrays k, Arrays l) => Arrays (a, b, c, d, e, f, g, h, i, j, k, l) # | |
| (Arrays a, Arrays b, Arrays c, Arrays d, Arrays e, Arrays f, Arrays g, Arrays h, Arrays i, Arrays j, Arrays k, Arrays l, Arrays m) => Arrays (a, b, c, d, e, f, g, h, i, j, k, l, m) # | |
| (Arrays a, Arrays b, Arrays c, Arrays d, Arrays e, Arrays f, Arrays g, Arrays h, Arrays i, Arrays j, Arrays k, Arrays l, Arrays m, Arrays n) => Arrays (a, b, c, d, e, f, g, h, i, j, k, l, m, n) # | |
| (Arrays a, Arrays b, Arrays c, Arrays d, Arrays e, Arrays f, Arrays g, Arrays h, Arrays i, Arrays j, Arrays k, Arrays l, Arrays m, Arrays n, Arrays o) => Arrays (a, b, c, d, e, f, g, h, i, j, k, l, m, n, o) # | |
Segment descriptor (vector of segment lengths).
To represent nested one-dimensional arrays, we use a flat array of data values in conjunction with a segment descriptor, which stores the lengths of the subarrays.
Array elements
class (Show a, Typeable a, Typeable (EltRepr a), ArrayElt (EltRepr a)) => Elt a #
The Elt class characterises the allowable array element types, and hence
the types which can appear in scalar Accelerate expressions.
Accelerate arrays consist of simple atomic types as well as nested tuples thereof, stored efficiently in memory as consecutive unpacked elements without pointers. It roughly consists of:
- Signed and unsigned integers (8, 16, 32, and 64-bits wide)
- Floating point numbers (single and double precision)
CharBool- ()
- Shapes formed from
Zand (:.) - Nested tuples of all of these, currently up to 15-elements wide
Adding new instances for Elt consists of explaining to Accelerate how to
map between your data type and a (tuple of) primitive values. For examples
see:
Minimal complete definition
eltType, fromElt, toElt
Instances
| Elt Bool # | |
| Elt Char # | |
| Elt Double # | |
| Elt Float # | |
| Elt Int # | |
| Elt Int8 # | |
| Elt Int16 # | |
| Elt Int32 # | |
| Elt Int64 # | |
| Elt Word # | |
| Elt Word8 # | |
| Elt Word16 # | |
| Elt Word32 # | |
| Elt Word64 # | |
| Elt () # | |
| Elt CChar # | |
| Elt CSChar # | |
| Elt CUChar # | |
| Elt CShort # | |
| Elt CUShort # | |
| Elt CInt # | |
| Elt CUInt # | |
| Elt CLong # | |
| Elt CULong # | |
| Elt CLLong # | |
| Elt CULLong # | |
| Elt CFloat # | |
| Elt CDouble # | |
| Elt All # | |
| Elt Z # | |
| Shape sh => Elt (Any ((:.) sh Int)) # | |
| Elt (Any Z) # | |
| (Elt a, Elt b) => Elt (a, b) # | |
| (Elt t, Elt h) => Elt ((:.) t h) # | |
| (Elt a, Elt b, Elt c) => Elt (a, b, c) # | |
| (Elt a, Elt b, Elt c, Elt d) => Elt (a, b, c, d) # | |
| (Elt a, Elt b, Elt c, Elt d, Elt e) => Elt (a, b, c, d, e) # | |
| (Elt a, Elt b, Elt c, Elt d, Elt e, Elt f) => Elt (a, b, c, d, e, f) # | |
| (Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g) => Elt (a, b, c, d, e, f, g) # | |
| (Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h) => Elt (a, b, c, d, e, f, g, h) # | |
| (Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i) => Elt (a, b, c, d, e, f, g, h, i) # | |
| (Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i, Elt j) => Elt (a, b, c, d, e, f, g, h, i, j) # | |
| (Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i, Elt j, Elt k) => Elt (a, b, c, d, e, f, g, h, i, j, k) # | |
| (Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i, Elt j, Elt k, Elt l) => Elt (a, b, c, d, e, f, g, h, i, j, k, l) # | |
| (Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i, Elt j, Elt k, Elt l, Elt m) => Elt (a, b, c, d, e, f, g, h, i, j, k, l, m) # | |
| (Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i, Elt j, Elt k, Elt l, Elt m, Elt n) => Elt (a, b, c, d, e, f, g, h, i, j, k, l, m, n) # | |
| (Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i, Elt j, Elt k, Elt l, Elt m, Elt n, Elt o) => Elt (a, b, c, d, e, f, g, h, i, j, k, l, m, n, o) # | |
Array shapes & indices
Operations in Accelerate take the form of collective operations over arrays
of the type Array sh e
Shape types, and multidimensional array indices, are built like lists
(technically; a heterogeneous snoc-list) using Z and (:.):
data Z = Z data tail :. head = tail :. head
Here, the constructor Z corresponds to a shape with zero dimension (or
a Scalar array, with one element) and is used to mark the end of the list.
The constructor (:.) adds additional dimensions to the shape on the
right. For example:
Z :. Int
is the type of the shape of a one-dimensional array (Vector) indexed by an
Int, while:
Z :. Int :. Int
is the type of the shape of a two-dimensional array (a matrix) indexed by an
Int in each dimension.
This style is used to construct both the type and value of the shape. For example, to define the shape of a vector of ten elements:
sh :: Z :. Int sh = Z :. 10
Note that the right-most index is the innermost dimension. This is the fastest-varying index, and corresponds to the elements of the array which are adjacent in memory.
Rank-0 index
Constructors
| Z |
Instances
| Eq Z # | |
| Show Z # | |
| Slice Z # | |
| Shape Z # | |
| Elt Z # | |
| Unlift Exp Z # | |
| Lift Exp Z # | |
| Elt e => Stencil DIM1 e (Exp e, Exp e, Exp e) # | |
| Elt e => Stencil DIM1 e (Exp e, Exp e, Exp e, Exp e, Exp e) # | |
| Elt e => Stencil DIM1 e (Exp e, Exp e, Exp e, Exp e, Exp e, Exp e, Exp e) # | |
| Elt e => Stencil DIM1 e (Exp e, Exp e, Exp e, Exp e, Exp e, Exp e, Exp e, Exp e, Exp e) # | |
| Elt e => IsList (Vector e) # | |
| Show (Vector e) # | |
| Show (Scalar e) # | |
| Elt (Any Z) # | |
| Show (Array DIM2 e) # | |
| type SliceShape Z # | |
| type CoSliceShape Z # | |
| type FullShape Z # | |
| type Plain Z # | |
| type Item (Vector e) # | |
Increase an index rank by one dimension. The :. operator is
used to construct both values and types.
Constructors
| tail :. head infixl 3 |
Instances
| Elt e => Stencil DIM1 e (Exp e, Exp e, Exp e) # | |
| Elt e => Stencil DIM1 e (Exp e, Exp e, Exp e, Exp e, Exp e) # | |
| Elt e => Stencil DIM1 e (Exp e, Exp e, Exp e, Exp e, Exp e, Exp e, Exp e) # | |
| Elt e => Stencil DIM1 e (Exp e, Exp e, Exp e, Exp e, Exp e, Exp e, Exp e, Exp e, Exp e) # | |
| (Elt e, Slice (Plain ix), Unlift Exp ix) => Unlift Exp ((:.) ix (Exp e)) # | |
| (Elt e, Slice ix) => Unlift Exp ((:.) (Exp ix) (Exp e)) # | |
| (Elt e, Slice (Plain ix), Lift Exp ix) => Lift Exp ((:.) ix (Exp e)) # | |
| (Slice (Plain ix), Lift Exp ix) => Lift Exp ((:.) ix All) # | |
| (Slice (Plain ix), Lift Exp ix) => Lift Exp ((:.) ix Int) # | |
| Elt e => IsList (Vector e) # | |
| Show (Vector e) # | |
| Shape sh => Elt (Any ((:.) sh Int)) # | |
| (Eq head, Eq tail) => Eq ((:.) tail head) # | |
| Show (Array DIM2 e) # | |
| (Show sh, Show sz) => Show ((:.) sh sz) # | |
| Slice sl => Slice ((:.) sl Int) # | |
| Slice sl => Slice ((:.) sl All) # | |
| Shape sh => Shape ((:.) sh Int) # | |
| (Elt t, Elt h) => Elt ((:.) t h) # | |
| (Stencil ((:.) sh Int) a row2, Stencil ((:.) sh Int) a row1, Stencil ((:.) sh Int) a row0) => Stencil ((:.) ((:.) sh Int) Int) a (row2, row1, row0) # | |
| (Stencil ((:.) sh Int) a row1, Stencil ((:.) sh Int) a row2, Stencil ((:.) sh Int) a row3, Stencil ((:.) sh Int) a row4, Stencil ((:.) sh Int) a row5) => Stencil ((:.) ((:.) sh Int) Int) a (row1, row2, row3, row4, row5) # | |
| (Stencil ((:.) sh Int) a row1, Stencil ((:.) sh Int) a row2, Stencil ((:.) sh Int) a row3, Stencil ((:.) sh Int) a row4, Stencil ((:.) sh Int) a row5, Stencil ((:.) sh Int) a row6, Stencil ((:.) sh Int) a row7) => Stencil ((:.) ((:.) sh Int) Int) a (row1, row2, row3, row4, row5, row6, row7) # | |
| (Stencil ((:.) sh Int) a row1, Stencil ((:.) sh Int) a row2, Stencil ((:.) sh Int) a row3, Stencil ((:.) sh Int) a row4, Stencil ((:.) sh Int) a row5, Stencil ((:.) sh Int) a row6, Stencil ((:.) sh Int) a row7, Stencil ((:.) sh Int) a row8, Stencil ((:.) sh Int) a row9) => Stencil ((:.) ((:.) sh Int) Int) a (row1, row2, row3, row4, row5, row6, row7, row8, row9) # | |
| type Item (Vector e) # | |
| type SliceShape ((:.) sl Int) # | |
| type SliceShape ((:.) sl All) # | |
| type CoSliceShape ((:.) sl Int) # | |
| type CoSliceShape ((:.) sl All) # | |
| type FullShape ((:.) sl Int) # | |
| type FullShape ((:.) sl All) # | |
| type Plain ((:.) ix (Exp e)) # | |
| type Plain ((:.) ix All) # | |
| type Plain ((:.) ix Int) # | |
class (Elt sh, Elt (Any sh), Shape (EltRepr sh), FullShape sh ~ sh, CoSliceShape sh ~ sh, SliceShape sh ~ Z) => Shape sh #
Shapes and indices of multi-dimensional arrays
Minimal complete definition
sliceAnyIndex, sliceNoneIndex
class (Elt sl, Shape (SliceShape sl), Shape (CoSliceShape sl), Shape (FullShape sl)) => Slice sl where #
Slices, aka generalised indices, as n-tuples and mappings of slice indices to slices, co-slices, and slice dimensions
Minimal complete definition
Methods
sliceIndex :: sl -> SliceIndex (EltRepr sl) (EltRepr (SliceShape sl)) (EltRepr (CoSliceShape sl)) (EltRepr (FullShape sl)) #
Marker for entire dimensions in slice and
replicate descriptors.
Occurrences of All indicate the dimensions into which the array's existing
extent will be placed unchanged.
Constructors
| All |
Marker for arbitrary dimensions in slice
and replicate descriptors.
Any can be used in the leftmost position of a slice instead of Z,
indicating that any dimensionality is admissible in that position.
Constructors
| Any |
Array access
Element indexing
(!) :: (Shape sh, Elt e) => Acc (Array sh e) -> Exp sh -> Exp e infixl 9 #
Multidimensional array indexing. Extract the value from an array at the specified zero-based index.
>>>let mat = fromList (Z:.5:.10) [0..]>>>matMatrix (Z :. 5 :. 10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
>>>mat ! Z:.1:.212
(!!) :: (Shape sh, Elt e) => Acc (Array sh e) -> Exp Int -> Exp e infixl 9 #
Extract the value from an array at the specified linear index. Multidimensional arrays in Accelerate are stored in row-major order with zero-based indexing.
>>>let mat = fromList (Z:.5:.10) [0..]>>>matMatrix (Z :. 5 :. 10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
>>>mat !! 1212
Shape information
shapeSize :: Shape sh => Exp sh -> Exp Int #
The number of elements that would be held by an array of the given shape.
Construction
Introduction
use :: Arrays arrays => arrays -> Acc arrays #
Make an array from vanilla Haskell available for processing within embedded Accelerate computations.
Depending upon which backend is used to eventually execute array
computations, use may entail data transfer (e.g. to a GPU).
use is overloaded so that it can accept tuples of Arrays:
>>>let vec = fromList (Z:.10) [0..] :: Array DIM1 IntVector (Z :. 10) [0,1,2,3,4,5,6,7,8,9]
>>>let mat = fromList (Z:.5:.10) [0..] :: Array DIM2 Int>>>matMatrix (Z :. 5 :. 10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
>>>let vec' = use vec :: Acc (Array DIM1 Int)>>>let mat' = use mat :: Acc (Array DIM2 Int)>>>let tup = use (vec, mat) :: Acc (Array DIM1 Int, Array DIM2 Int)
unit :: Elt e => Exp e -> Acc (Scalar e) #
Construct a singleton (one element) array from a scalar value (or tuple of scalar values).
Initialisation
generate :: (Shape sh, Elt a) => Exp sh -> (Exp sh -> Exp a) -> Acc (Array sh a) #
Construct a new array by applying a function to each index.
For example, the following will generate a one-dimensional array
(Vector) of three floating point numbers:
>>>generate (index1 3) (\_ -> 1.2)Vector (Z :. 3) [1.2,1.2,1.2]
Or equivalently:
>>>fill (constant (Z :. 3)) 1.2Vector (Z :. 3) [1.2,1.2,1.2]
The following will create a vector with the elements [1..10]:
>>>generate (index1 10) (\ix -> unindex1 ix + 1)Vector (Z :. 10) [1,2,3,4,5,6,7,8,9,10]
- NOTE:
Using generate, it is possible to introduce nested data parallelism, which
will cause the program to fail.
If the index given by the scalar function is then used to dispatch further
parallel work, whose result is returned into Exp terms by array indexing
operations such as (!) or the, the program
will fail with the error:
'./Data/Array/Accelerate/Trafo/Sharing.hs:447 (convertSharingExp): inconsistent valuation @ shared 'Exp' tree ...'.
fill :: (Shape sh, Elt e) => Exp sh -> Exp e -> Acc (Array sh e) #
Create an array where all elements are the same value.
Enumeration
enumFromN :: (Shape sh, Num e, FromIntegral Int e) => Exp sh -> Exp e -> Acc (Array sh e) #
Create an array of the given shape containing the values x, x+1, etc.
(in row-major order).
>>>enumFromN (constant (Z:.5:.10)) 0 :: Array DIM2 IntMatrix (Z :. 5 :. 10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
Arguments
| :: (Shape sh, Num e, FromIntegral Int e) | |
| => Exp sh | |
| -> Exp e | x: start |
| -> Exp e | y: step |
| -> Acc (Array sh e) |
Create an array of the given shape containing the values x, x+y,
x+y+y etc. (in row-major order).
>>>enumFromStepN (constant (Z:.5:.10)) 0 0.5 :: Array DIM2 FloatMatrix (Z :. 5 :. 10) [ 0.0, 0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 4.5, 5.0, 5.5, 6.0, 6.5, 7.0, 7.5, 8.0, 8.5, 9.0, 9.5, 10.0, 10.5, 11.0, 11.5, 12.0, 12.5, 13.0, 13.5, 14.0, 14.5, 15.0, 15.5, 16.0, 16.5, 17.0, 17.5, 18.0, 18.5, 19.0, 19.5, 20.0, 20.5, 21.0, 21.5, 22.0, 22.5, 23.0, 23.5, 24.0, 24.5]
Concatenation
(++) :: forall sh e. (Slice sh, Shape sh, Elt e) => Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e) infixr 5 #
Concatenate innermost component of two arrays. The extent of the lower dimensional component is the intersection of the two arrays.
>>>let m1 = fromList (Z:.5:.10) [0..]>>>m1Matrix (Z :. 5 :. 10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
>>>let m2 = fromList (Z:.10:.3) [0..]>>>m2Matrix (Z :. 10 :. 3) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
>>>use m1 ++ use m2Matrix (Z :. 5 :. 13) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 3, 4, 5, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 6, 7, 8, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 9, 10, 11, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 12, 13, 14]
Composition
Flow control
(?|) :: Arrays a => Exp Bool -> (Acc a, Acc a) -> Acc a infix 0 #
Infix version of acond. If the predicate evaluates to True, the first
component of the tuple is returned, else the second.
See also: ifThenElse.
An array-level if-then-else construct.
class IfThenElse t where #
For use with -XRebindableSyntax, this class provides ifThenElse lifted
to both scalar and array types.
Minimal complete definition
Associated Types
type EltT t a :: Constraint #
Methods
ifThenElse :: EltT t a => Exp Bool -> t a -> t a -> t a #
Instances
Controlling execution
(>->) :: (Arrays a, Arrays b, Arrays c) => (Acc a -> Acc b) -> (Acc b -> Acc c) -> Acc a -> Acc c infixl 1 #
Pipelining of two array computations. The first argument will be fully evaluated before being passed to the second computation. This can be used to prevent the argument being fused into the function, for example.
Denotationally, we have
(acc1 >-> acc2) arrs = let tmp = acc1 arrs
in tmp `seq` acc2 tmpcompute :: Arrays a => Acc a -> Acc a #
Force an array expression to be evaluated, preventing it from fusing with
other operations. Forcing operations to be computed to memory, rather than
being fused into their consuming function, can sometimes improve performance.
For example, computing a matrix transpose could provide better memory
locality for the subsequent operation. Preventing fusion to split large
operations into several simpler steps could also help by reducing register
pressure.
Preventing fusion also means that the individual operations are available to be executed concurrently with other kernels. In particular, consider using this if you have a series of operations that are compute bound rather than memory bound.
Here is the synthetic example:
loop :: Exp Int -> Exp Int
loop ticks =
let clockRate = 900000 -- kHz
in while (\i -> i < clockRate * ticks) (+1) 0
test :: Acc (Vector Int)
test =
zip3
(compute $ map loop (use $ fromList (Z:.1) [10]))
(compute $ map loop (use $ fromList (Z:.1) [10]))
(compute $ map loop (use $ fromList (Z:.1) [10]))
Without the use of compute, the operations are fused together and the three
long-running loops are executed sequentially in a single kernel. Instead, the
individual operations can now be executed concurrently, potentially reducing
overall runtime.
Element-wise operations
Indexing
indexed :: (Shape sh, Elt a) => Acc (Array sh a) -> Acc (Array sh (sh, a)) #
Pair each element with its index
Mapping
map :: (Shape sh, Elt a, Elt b) => (Exp a -> Exp b) -> Acc (Array sh a) -> Acc (Array sh b) #
Apply the given function element-wise to an array.
map f [x1, x2, ... xn] = [f x1, f x2, ... f xn]
imap :: (Shape sh, Elt a, Elt b) => (Exp sh -> Exp a -> Exp b) -> Acc (Array sh a) -> Acc (Array sh b) #
Apply a function to every element of an array and its index
Zipping
zipWith :: (Shape sh, Elt a, Elt b, Elt c) => (Exp a -> Exp b -> Exp c) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) #
Apply the given binary function element-wise to the two arrays. The extent of the resulting array is the intersection of the extents of the two source arrays.
zipWith3 :: (Shape sh, Elt a, Elt b, Elt c, Elt d) => (Exp a -> Exp b -> Exp c -> Exp d) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) #
Zip three arrays with the given function, analogous to zipWith.
zipWith4 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e) => (Exp a -> Exp b -> Exp c -> Exp d -> Exp e) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) #
Zip four arrays with the given function, analogous to zipWith.
zipWith5 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f) => (Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) #
Zip five arrays with the given function, analogous to zipWith.
zipWith6 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g) => (Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) #
Zip six arrays with the given function, analogous to zipWith.
zipWith7 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h) => (Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g -> Exp h) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) #
Zip seven arrays with the given function, analogous to zipWith.
zipWith8 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i) => (Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g -> Exp h -> Exp i) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) -> Acc (Array sh i) #
Zip eight arrays with the given function, analogous to zipWith.
zipWith9 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i, Elt j) => (Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g -> Exp h -> Exp i -> Exp j) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) -> Acc (Array sh i) -> Acc (Array sh j) #
Zip nine arrays with the given function, analogous to zipWith.
izipWith :: (Shape sh, Elt a, Elt b, Elt c) => (Exp sh -> Exp a -> Exp b -> Exp c) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) #
Zip two arrays with a function that also takes the element index
izipWith3 :: (Shape sh, Elt a, Elt b, Elt c, Elt d) => (Exp sh -> Exp a -> Exp b -> Exp c -> Exp d) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) #
Zip three arrays with a function that also takes the element index,
analogous to izipWith.
izipWith4 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e) => (Exp sh -> Exp a -> Exp b -> Exp c -> Exp d -> Exp e) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) #
Zip four arrays with the given function that also takes the element index,
analogous to zipWith.
izipWith5 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f) => (Exp sh -> Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) #
Zip five arrays with the given function that also takes the element index,
analogous to zipWith.
izipWith6 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g) => (Exp sh -> Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) #
Zip six arrays with the given function that also takes the element index,
analogous to zipWith.
izipWith7 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h) => (Exp sh -> Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g -> Exp h) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) #
Zip seven arrays with the given function that also takes the element
index, analogous to zipWith.
izipWith8 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i) => (Exp sh -> Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g -> Exp h -> Exp i) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) -> Acc (Array sh i) #
Zip eight arrays with the given function that also takes the element
index, analogous to zipWith.
izipWith9 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i, Elt j) => (Exp sh -> Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g -> Exp h -> Exp i -> Exp j) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) -> Acc (Array sh i) -> Acc (Array sh j) #
Zip nine arrays with the given function that also takes the element index,
analogous to zipWith.
zip :: (Shape sh, Elt a, Elt b) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh (a, b)) #
Combine the elements of two arrays pairwise. The shape of the result is the intersection of the two argument shapes.
zip3 :: (Shape sh, Elt a, Elt b, Elt c) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh (a, b, c)) #
Take three arrays and return an array of triples, analogous to zip.
zip4 :: (Shape sh, Elt a, Elt b, Elt c, Elt d) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh (a, b, c, d)) #
Take four arrays and return an array of quadruples, analogous to zip.
zip5 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh (a, b, c, d, e)) #
Take five arrays and return an array of five-tuples, analogous to zip.
zip6 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh (a, b, c, d, e, f)) #
Take six arrays and return an array of six-tuples, analogous to zip.
zip7 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh (a, b, c, d, e, f, g)) #
Take seven arrays and return an array of seven-tuples, analogous to zip.
zip8 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) -> Acc (Array sh (a, b, c, d, e, f, g, h)) #
Take seven arrays and return an array of seven-tuples, analogous to zip.
zip9 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) -> Acc (Array sh i) -> Acc (Array sh (a, b, c, d, e, f, g, h, i)) #
Take seven arrays and return an array of seven-tuples, analogous to zip.
Unzipping
unzip :: (Shape sh, Elt a, Elt b) => Acc (Array sh (a, b)) -> (Acc (Array sh a), Acc (Array sh b)) #
unzip3 :: (Shape sh, Elt a, Elt b, Elt c) => Acc (Array sh (a, b, c)) -> (Acc (Array sh a), Acc (Array sh b), Acc (Array sh c)) #
Take an array of triples and return three arrays, analogous to unzip.
unzip4 :: (Shape sh, Elt a, Elt b, Elt c, Elt d) => Acc (Array sh (a, b, c, d)) -> (Acc (Array sh a), Acc (Array sh b), Acc (Array sh c), Acc (Array sh d)) #
Take an array of quadruples and return four arrays, analogous to unzip.
unzip5 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e) => Acc (Array sh (a, b, c, d, e)) -> (Acc (Array sh a), Acc (Array sh b), Acc (Array sh c), Acc (Array sh d), Acc (Array sh e)) #
Take an array of 5-tuples and return five arrays, analogous to unzip.
unzip6 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f) => Acc (Array sh (a, b, c, d, e, f)) -> (Acc (Array sh a), Acc (Array sh b), Acc (Array sh c), Acc (Array sh d), Acc (Array sh e), Acc (Array sh f)) #
Take an array of 6-tuples and return six arrays, analogous to unzip.
unzip7 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g) => Acc (Array sh (a, b, c, d, e, f, g)) -> (Acc (Array sh a), Acc (Array sh b), Acc (Array sh c), Acc (Array sh d), Acc (Array sh e), Acc (Array sh f), Acc (Array sh g)) #
Take an array of 7-tuples and return seven arrays, analogous to unzip.
unzip8 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h) => Acc (Array sh (a, b, c, d, e, f, g, h)) -> (Acc (Array sh a), Acc (Array sh b), Acc (Array sh c), Acc (Array sh d), Acc (Array sh e), Acc (Array sh f), Acc (Array sh g), Acc (Array sh h)) #
Take an array of 8-tuples and return eight arrays, analogous to unzip.
unzip9 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i) => Acc (Array sh (a, b, c, d, e, f, g, h, i)) -> (Acc (Array sh a), Acc (Array sh b), Acc (Array sh c), Acc (Array sh d), Acc (Array sh e), Acc (Array sh f), Acc (Array sh g), Acc (Array sh h), Acc (Array sh i)) #
Take an array of 8-tuples and return eight arrays, analogous to unzip.
Modifying Arrays
Shape manipulation
reshape :: (Shape sh, Shape sh', Elt e) => Exp sh -> Acc (Array sh' e) -> Acc (Array sh e) #
Change the shape of an array without altering its contents. The size of
the source and result arrays must be identical.
precondition: shapeSize sh == shapeSize sh'
If the argument array is manifest in memory, reshape is a NOP. If the
argument is to be fused into a subsequent operation, reshape corresponds to
an index transformation in the fused code.
flatten :: forall sh e. (Shape sh, Elt e) => Acc (Array sh e) -> Acc (Vector e) #
Flatten the given array of arbitrary dimension into a one-dimensional
vector. As with reshape, this operation performs no work.
Replication
replicate :: (Slice slix, Elt e) => Exp slix -> Acc (Array (SliceShape slix) e) -> Acc (Array (FullShape slix) e) #
Replicate an array across one or more dimensions as specified by the generalised array index provided as the first argument.
For example, given the following vector:
>>>let vec = fromList (Z:.10) [0..]Vector (Z :. 10) [0,1,2,3,4,5,6,7,8,9]
...we can replicate these elements to form a two-dimensional array either by replicating those elements as new rows:
>>>replicate (lift (Z :. 4 :. All)) (use vec)Matrix (Z :. 4 :. 10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
...or as columns:
>>>replicate (lift (Z :. All :. 4)) (use vec)Matrix (Z :. 10 :. 4) [ 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9]
Replication along more than one dimension is also possible. Here we replicate twice across the first dimension and three times across the third dimension:
>>>replicate (lift (Z :. 2 :. All :. 3)) (use vec)Array (Z :. 2 :. 10 :. 3) [0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8,8,8,9,9,9,0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8,8,8,9,9,9]
The marker Any can be used in the slice specification to match against some
arbitrary dimension. For example, here Any matches against whatever shape
type variable sh takes.
rep0 :: (Shape sh, Elt e) => Exp Int -> Acc (Array sh e) -> Acc (Array (sh :. Int) e) rep0 n a = replicate (lift (Any :. n)) a
>>>let x = unit 42 :: Acc (Scalar Int)>>>rep0 10 xVector (Z :. 10) [42,42,42,42,42,42,42,42,42,42]
>>>rep0 5 (use vec)Matrix (Z :. 10 :. 5) [ 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9]
Of course, Any and All can be used together.
rep1 :: (Shape sh, Elt e) => Exp Int -> Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int :. Int) e) rep1 n a = A.replicate (lift (Any :. n :. All)) a
>>>rep1 5 (use vec)Matrix (Z :. 5 :. 10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Extracting sub-arrays
slice :: (Slice slix, Elt e) => Acc (Array (FullShape slix) e) -> Exp slix -> Acc (Array (SliceShape slix) e) #
Index an array with a generalised array index, supplied as the
second argument. The result is a new array (possibly a singleton)
containing the selected dimensions (Alls) in their entirety.
slice is the opposite of replicate, and can be used to cut out entire
dimensions. For example, for the two dimensional array mat:
>>>let mat = fromList (Z:.5:.10) [0..]>>>matMatrix (Z :. 5 :. 10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
...will can select a specific row to yield a one dimensional result by fixing
the row index (2) while allowing the column index to vary (via All):
>>>slice (use mat) (lift (Z :. 2 :. All))Vector (Z :. 10) [20,21,22,23,24,25,26,27,28,29]
A fully specified index (with no Alls) returns a single element (zero
dimensional array).
>>>slice (use mat) (lift (Z :. 4 :. 2))Scalar Z [42]
The marker Any can be used in the slice specification to match against some
arbitrary (lower) dimension. Here Any matches whatever shape type variable
sh takes:
sl0 :: (Shape sh, Elt e) => Acc (Array (sh:.Int) e) -> Exp Int -> Acc (Array sh e) sl0 a n = A.slice a (lift (Any :. n))
>>>let vec = fromList (Z:.10) [0..]>>>sl0 (use vec) 4Scalar Z [4]
>>>sl0 (use mat) 4Vector (Z :. 5) [4,14,24,34,44]
Of course, Any and All can be used together.
sl1 :: (Shape sh, Elt e) => Acc (Array (sh:.Int:.Int) e) -> Exp Int -> Acc (Array (sh:.Int) e) sl1 a n = A.slice a (lift (Any :. n :. All))
>>>sl1 (use mat) 4Vector (Z :. 10) [40,41,42,43,44,45,46,47,48,49]
>>>let cube = fromList (Z:.3:.4:.5) [0..]>>>cubeArray (Z :. 3 :. 4 :. 5) [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59]
>>>sl1 (use cube) 2Matrix (Z :. 3 :. 5) [ 10, 11, 12, 13, 14, 30, 31, 32, 33, 34, 50, 51, 52, 53, 54]
init :: forall sh e. (Slice sh, Shape sh, Elt e) => Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e) #
Yield all but the elements in the last index of the innermost dimension.
>>>let mat = fromList (Z:.5:.10) [0..]>>>matMatrix (Z :. 5 :. 10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
>>>init (use mat)Matrix (Z :. 5 :. 9) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 31, 32, 33, 34, 35, 36, 37, 38, 40, 41, 42, 43, 44, 45, 46, 47, 48]
tail :: forall sh e. (Slice sh, Shape sh, Elt e) => Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e) #
Yield all but the first element along the innermost dimension of an array. The innermost dimension must not be empty.
>>>let mat = fromList (Z:.5:.10) [0..]>>>matMatrix (Z :. 5 :. 10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
>>>tail (use mat)Matrix (Z :. 5 :. 9) [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 31, 32, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 48, 49]
take :: forall sh e. (Slice sh, Shape sh, Elt e) => Exp Int -> Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e) #
Yield the first n elements in the innermost dimension of the array (plus
all lower dimensional elements).
>>>let mat = fromList (Z:.5:.10) [0..]>>>matMatrix (Z :. 5 :. 10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
>>>take 5 (use mat)Matrix (Z :. 5 :. 5) [ 0, 1, 2, 3, 4, 10, 11, 12, 13, 14, 20, 21, 22, 23, 24, 30, 31, 32, 33, 34, 40, 41, 42, 43, 44]
drop :: forall sh e. (Slice sh, Shape sh, Elt e) => Exp Int -> Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e) #
Yield all but the first n elements along the innermost dimension of the
array (plus all lower dimensional elements).
>>>let mat = fromList (Z:.5:.10) [0..]>>>matMatrix (Z :. 5 :. 10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
>>>drop 7 (use mat)Matrix (Z :. 5 :. 3) [ 7, 8, 9, 17, 18, 19, 27, 28, 29, 37, 38, 39, 47, 48, 49]
slit :: forall sh e. (Slice sh, Shape sh, Elt e) => Exp Int -> Exp Int -> Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e) #
Yield a slit (slice) of the innermost indices of an array. Denotationally, we have:
slit i n = take n . drop i
Permutations
Forward permutation (scatter)
Arguments
| :: (Shape sh, Shape sh', Elt a) | |
| => (Exp a -> Exp a -> Exp a) | combination function |
| -> Acc (Array sh' a) | array of default values |
| -> (Exp sh -> Exp sh') | index permutation function |
| -> Acc (Array sh a) | array of source values to be permuted |
| -> Acc (Array sh' a) |
Generalised forward permutation operation (array scatter).
Forward permutation specified by a function mapping indices from the source array to indices in the result array. The result array is initialised with the given defaults and any further values that are permuted into the result array are added to the current value using the given combination function.
The combination function must be associative and commutative. Elements
that are mapped to the magic value ignore by the permutation function are
dropped.
For example, we can use permute to compute the occurrence count (histogram)
for an array of values in the range [0,10):
histogram :: Acc (Vector Int) -> Acc (Vector Int)
histogram xs =
let zeros = fill (constant (Z:.10)) 0
ones = fill (shape xs) 1
in
permute (+) zeros (\ix -> index1 (xs!ix)) ones>>>let xs = fromList (Z :. 20) [0,0,1,2,1,1,2,4,8,3,4,9,8,3,2,5,5,3,1,2]>>>histogram (use xs)Vector (Z :. 10) [2,4,4,3,2,2,0,0,2,1]
- Note:
Regarding array fusion:
- The
permuteoperation will always be evaluated; it can not be fused into a later step. - Since the index permutation function might not cover all positions in the output array (the function is not surjective), the array of default values must be evaluated. However, other operations may fuse into this.
- The array of source values can fuse into the permutation operation.
ignore :: Shape sh => Exp sh #
Magic value identifying elements that are ignored in a forward permutation.
Arguments
| :: Elt e | |
| => Acc (Vector Int) | destination indices to scatter into |
| -> Acc (Vector e) | default values |
| -> Acc (Vector e) | source values |
| -> Acc (Vector e) |
Overwrite elements of the destination by scattering the values of the source array according to the given index mapping.
Note that if the destination index appears more than once in the mapping the result is undefined.
>>>let to = fromList (Z :. 6) [1,3,7,2,5,8]>>>let input = fromList (Z :. 7) [1,9,6,4,4,2,5]>>>scatter (use to) (fill (constant (Z:.10)) 0) (use input)Vector (Z :. 10) [0,1,4,9,0,4,0,6,2,0]
Backward permutation (gather)
Arguments
| :: (Shape sh, Shape sh', Elt a) | |
| => Exp sh' | shape of the result array |
| -> (Exp sh' -> Exp sh) | index permutation function |
| -> Acc (Array sh a) | source array |
| -> Acc (Array sh' a) |
Generalised backward permutation operation (array gather).
Backward permutation specified by a function mapping indices in the destination array to indices in the source array. Elements of the output array are thus generated by reading from the corresponding index in the source array.
For example, backpermute can be used to
transpose a matrix; at every index Z:.y:.x
in the result array, we get the value at that index by reading from the
source array at index Z:.x:.y:
swap :: Exp DIM2 -> Exp DIM2 swap = lift1 $ \(Z:.y:.x) -> Z:.x:.y
>>>let mat = fromList (Z:.5:.10) [0..]>>>matMatrix (Z :. 5 :. 10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
>>>let mat' = use mat>>>backpermute (swap (shape mat')) swap mat'Matrix (Z :. 10 :. 5) [ 0, 10, 20, 30, 40, 1, 11, 21, 31, 41, 2, 12, 22, 32, 42, 3, 13, 23, 33, 43, 4, 14, 24, 34, 44, 5, 15, 25, 35, 45, 6, 16, 26, 36, 46, 7, 17, 27, 37, 47, 8, 18, 28, 38, 48, 9, 19, 29, 39, 49]
Arguments
| :: (Shape sh, Elt e) | |
| => Acc (Array sh Int) | index of source at each index to gather |
| -> Acc (Vector e) | source values |
| -> Acc (Array sh e) |
Gather elements from a source array by reading values at the given indices.
>>>let input = fromList (Z:.9) [1,9,6,4,4,2,0,1,2]>>>let from = fromList (Z:.6) [1,3,7,2,5,3]>>>gather (use from) (use input)Vector (Z :. 6) [9,4,1,6,2,4]
Specialised permutations
transpose :: Elt e => Acc (Array DIM2 e) -> Acc (Array DIM2 e) #
Transpose the rows and columns of a matrix.
Filtering
filter :: forall sh e. (Shape sh, Slice sh, Elt e) => (Exp e -> Exp Bool) -> Acc (Array (sh :. Int) e) -> Acc (Vector e, Array sh Int) #
Drop elements that do not satisfy the predicate. Returns the elements which pass the predicate, together with a segment descriptor indicating how many elements along each outer dimension were valid.
>>>let vec = fromList (Z :. 10) [1..10] :: Vector Int>>>vecVector (Z :. 10) [1,2,3,4,5,6,7,8,9,10]
>>>filter even (use vec)(Vector (Z :. 5) [2,4,6,8,10], Scalar Z [5])
>>>let mat = fromList (Z :. 4 :. 10) [1,2,3,4,5,6,7,8,9,10,1,1,1,1,1,2,2,2,2,2,2,4,6,8,10,12,14,16,18,20,1,3,5,7,9,11,13,15,17,19] :: Array DIM2 Int>>>matMatrix (Z :. 4 :. 10) [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
>>>filter odd (use mat)(Vector (Z :. 20) [1,3,5,7,9,1,1,1,1,1,1,3,5,7,9,11,13,15,17,19], Vector (Z :. 4) [5,5,0,10])
Folding
fold :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array sh a) #
Reduction of the innermost dimension of an array of arbitrary rank. The first argument needs to be an associative function to enable an efficient parallel implementation. The initial element does not need to be an identity element of the combination function.
>>>let mat = fromList (Z:.5:.10) [0..]>>>matMatrix (Z :. 5 :. 10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
>>>fold (+) 42 (use mat)Vector (Z :. 5) [87,187,287,387,487]
Reductions with non-commutative operators are supported. For example, the following computes the maximum segment sum problem along each innermost dimension of the array.
https://en.wikipedia.org/wiki/Maximum_subarray_problem
maximumSegmentSum
:: forall sh e. (Shape sh, Num e, Ord e)
=> Acc (Array (sh :. Int) e)
-> Acc (Array sh e)
maximumSegmentSum
= map (\v -> let (x,_,_,_) = unlift v :: (Exp e, Exp e, Exp e, Exp e) in x)
. fold1 f
. map g
where
f :: (Num a, Ord a) => Exp (a,a,a,a) -> Exp (a,a,a,a) -> Exp (a,a,a,a)
f x y =
let (mssx, misx, mcsx, tsx) = unlift x
(mssy, misy, mcsy, tsy) = unlift y
in
lift ( mssx `max` (mssy `max` (mcsx+misy))
, misx `max` (tsx+misy)
, mcsy `max` (mcsx+tsy)
, tsx+tsy
)
g :: (Num a, Ord a) => Exp a -> Exp (a,a,a,a)
g x = let y = max x 0
in lift (y,y,y,x)>>>let vec = fromList (Z:.10) [-2,1,-3,4,-1,2,1,-5,4,0]>>>maximumSegmentSum (use vec)Scalar Z [6]
See also Fold, which can be a useful way to
compute multiple results from a single reduction.
fold1 :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Acc (Array (sh :. Int) a) -> Acc (Array sh a) #
Variant of fold that requires the reduced array to be non-empty and
doesn't need an default value. The first argument needs to be an
associative function to enable an efficient parallel implementation. The
initial element does not need to be an identity element.
foldAll :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array sh a) -> Acc (Scalar a) #
Reduction of an array of arbitrary rank to a single scalar value. The first argument needs to be an associative function to enable efficient parallel implementation. The initial element does not need to be an identity element.
>>>let vec = fromList (Z:.10) [0..]>>>foldAll (+) 42 (use vec)Scalar Z [87]
>>>let mat = fromList (Z:.5:.10) [0..]>>>foldAll (+) 0 (use mat)Scalar Z [1225]
fold1All :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Acc (Array sh a) -> Acc (Scalar a) #
Variant of foldAll that requires the reduced array to be non-empty and
doesn't need an default value. The first argument must be an associative
function.
Segmented reductions
foldSeg :: (Shape sh, Elt a, Elt i, IsIntegral i) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Segments i) -> Acc (Array (sh :. Int) a) #
Segmented reduction along the innermost dimension of an array. The segment descriptor specifies the lengths of the logical sub-arrays, each of which is reduced independently. The innermost dimension must contain at least as many elements as required by the segment descriptor (sum thereof).
>>>let seg = fromList (Z:.4) [1,4,0,3]>>>segVector (Z :. 4) [1,4,0,3]
>>>let mat = fromList (Z:.5:.10) [0..]>>>matMatrix (Z :. 5 :. 10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
>>>foldSeg (+) 0 (use mat) (use seg)Matrix (Z :. 5 :. 4) [ 0, 10, 0, 18, 10, 50, 0, 48, 20, 90, 0, 78, 30, 130, 0, 108, 40, 170, 0, 138]
fold1Seg :: (Shape sh, Elt a, Elt i, IsIntegral i) => (Exp a -> Exp a -> Exp a) -> Acc (Array (sh :. Int) a) -> Acc (Segments i) -> Acc (Array (sh :. Int) a) #
Variant of foldSeg that requires all segments of the reduced array to
be non-empty and doesn't need a default value. The segment descriptor
specifies the length of each of the logical sub-arrays.
Specialised reductions
all :: (Shape sh, Elt e) => (Exp e -> Exp Bool) -> Acc (Array sh e) -> Acc (Scalar Bool) #
Check if all elements satisfy a predicate
any :: (Shape sh, Elt e) => (Exp e -> Exp Bool) -> Acc (Array sh e) -> Acc (Scalar Bool) #
Check if any element satisfies the predicate
product :: (Shape sh, Num e) => Acc (Array sh e) -> Acc (Scalar e) #
Compute the product of the elements
minimum :: (Shape sh, Ord e) => Acc (Array sh e) -> Acc (Scalar e) #
Yield the minimum element of an array. The array must not be empty.
maximum :: (Shape sh, Ord e) => Acc (Array sh e) -> Acc (Scalar e) #
Yield the maximum element of an array. The array must not be empty.
Scans (prefix sums)
scanl :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a) #
Data.List style left-to-right scan along the innermost dimension of an arbitrary rank array. The first argument needs to be an associative function to enable efficient parallel implementation. The initial value (second argument) may be arbitrary.
>>>scanl (+) 10 (use $ fromList (Z :. 10) [0..])Array (Z :. 11) [10,10,11,13,16,20,25,31,38,46,55]
>>>scanl (+) 0 (use $ fromList (Z :. 4 :. 10) [0..])Matrix (Z :. 4 :. 11) [ 0, 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 0, 10, 21, 33, 46, 60, 75, 91, 108, 126, 145, 0, 20, 41, 63, 86, 110, 135, 161, 188, 216, 245, 0, 30, 61, 93, 126, 160, 195, 231, 268, 306, 345]
scanl1 :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a) #
Data.List style left-to-right scan along the innermost dimension without an initial value (aka inclusive scan). The array must not be empty. The first argument needs to be an associative function. Denotationally, we have:
scanl1 f e arr = tail (scanl f e arr)
>>>scanl (+) (use $ fromList (Z:.4:.10) [0..])Matrix (Z :. 4 :. 10) [ 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 10, 21, 33, 46, 60, 75, 91, 108, 126, 145, 20, 41, 63, 86, 110, 135, 161, 188, 216, 245, 30, 61, 93, 126, 160, 195, 231, 268, 306, 345]
scanl' :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> (Acc (Array (sh :. Int) a), Acc (Array sh a)) #
Variant of scanl, where the last element (final reduction result) along
each dimension is returned separately. Denotationally we have:
scanl' f e arr = (init res, unit (res!len))
where
len = shape arr
res = scanl f e arr>>>let (res,sum) = scanl' (+) 0 (use $ fromList (Z:.10) [0..])>>>resVector (Z :. 10) [0,0,1,3,6,10,15,21,28,36]>>>sumScalar Z [45]
>>>let (res,sums) = scanl' (+) 0 (use $ fromList (Z:.4:.10) [0..])>>>resMatrix (Z :. 4 :. 10) [ 0, 0, 1, 3, 6, 10, 15, 21, 28, 36, 0, 10, 21, 33, 46, 60, 75, 91, 108, 126, 0, 20, 41, 63, 86, 110, 135, 161, 188, 216, 0, 30, 61, 93, 126, 160, 195, 231, 268, 306]>>>sumsVector (Z :. 4) [45,145,245,345]
scanr :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a) #
Right-to-left variant of scanl.
scanr1 :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a) #
Right-to-left variant of scanl1.
scanr' :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> (Acc (Array (sh :. Int) a), Acc (Array sh a)) #
Right-to-left variant of scanl'.
prescanl :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a) #
Left-to-right prescan (aka exclusive scan). As for scan, the first
argument must be an associative function. Denotationally, we have
prescanl f e = Prelude.fst . scanl' f e
>>>let vec = fromList (Z:.10) [1..10]>>>prescanl (+) 0 (use vec)Vector (Z :. 10) [0,0,1,3,6,10,15,21,28,36]
postscanl :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a) #
prescanr :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a) #
Right-to-left prescan (aka exclusive scan). As for scan, the first argument must be an
associative function. Denotationally, we have
prescanr f e = Prelude.fst . scanr' f e
postscanr :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a) #
Right-to-left postscan, a variant of scanr1 with an initial value. Denotationally, we have
postscanr f e = map (e `f`) . scanr1 f
Segmented scans
scanlSeg :: forall sh e i. (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e) #
Segmented version of scanl along the innermost dimension of an array. The
innermost dimension must have at least as many elements as the sum of the
segment descriptor.
>>>let seg = fromList (Z:.4) [1,4,0,3]>>>segVector (Z :. 4) [1,4,0,3]
>>>let mat = fromList (Z:.5:.10) [0..]>>>matMatrix (Z :. 5 :. 10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
>>>scanlSeg (+) 0 (use mat) (use seg)Matrix (Z :. 5 :. 12) [ 0, 0, 0, 1, 3, 6, 10, 0, 0, 5, 11, 18, 0, 10, 0, 11, 23, 36, 50, 0, 0, 15, 31, 48, 0, 20, 0, 21, 43, 66, 90, 0, 0, 25, 51, 78, 0, 30, 0, 31, 63, 96, 130, 0, 0, 35, 71, 108, 0, 40, 0, 41, 83, 126, 170, 0, 0, 45, 91, 138]
scanl1Seg :: (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e) #
Segmented version of scanl1 along the innermost dimension.
As with scanl1, the total number of elements considered, in this case given
by the sum of segment descriptor, must not be zero. The input vector must
contain at least this many elements.
Zero length segments are allowed, and the behaviour is as if those entries were not present in the segment descriptor; that is:
scanl1Seg f xs [n,0,0] == scanl1Seg f xs [n] where n /= 0
>>>let seg = fromList (Z:.4) [1,4,0,3]>>>segVector (Z :. 4) [1,4,0,3]
>>>let mat = fromList (Z:.5:.10) [0..]>>>matMatrix (Z :. 5 :. 10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
>>>scanl1Seg (+) (use mat) (use seg)Matrix (Z :. 5 :. 8) [ 0, 1, 3, 6, 10, 5, 11, 18, 10, 11, 23, 36, 50, 15, 31, 48, 20, 21, 43, 66, 90, 25, 51, 78, 30, 31, 63, 96, 130, 35, 71, 108, 40, 41, 83, 126, 170, 45, 91, 138]
scanl'Seg :: forall sh e i. (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e, Array (sh :. Int) e) #
Segmented version of scanl' along the innermost dimension of an array. The
innermost dimension must have at least as many elements as the sum of the
segment descriptor.
The first element of the resulting tuple is a vector of scanned values. The second element is a vector of segment scan totals and has the same size as the segment vector.
>>>let seg = fromList (Z:.4) [1,4,0,3]>>>segVector (Z :. 4) [1,4,0,3]
>>>let mat = fromList (Z:.5:.10) [0..]>>>matMatrix (Z :. 5 :. 10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
>>>let (res,sums) = scanl'Seg (+) 0 (use mat) (use seg)>>>resMatrix (Z :. 5 :. 8) [ 0, 0, 1, 3, 6, 0, 5, 11, 0, 0, 11, 23, 36, 0, 15, 31, 0, 0, 21, 43, 66, 0, 25, 51, 0, 0, 31, 63, 96, 0, 35, 71, 0, 0, 41, 83, 126, 0, 45, 91]>>>sumsMatrix (Z :. 5 :. 4) [ 0, 10, 0, 18, 10, 50, 0, 48, 20, 90, 0, 78, 30, 130, 0, 108, 40, 170, 0, 138]
prescanlSeg :: (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e) #
Segmented version of prescanl.
postscanlSeg :: (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e) #
Segmented version of postscanl.
scanrSeg :: forall sh e i. (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e) #
Segmented version of scanr along the innermost dimension of an array. The
innermost dimension must have at least as many elements as the sum of the
segment descriptor.
>>>let seg = fromList (Z:.4) [1,4,0,3]>>>segVector (Z :. 4) [1,4,0,3]
>>>let mat = fromList (Z:.5:.10) [0..]>>>matMatrix (Z :. 5 :. 10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
>>>scanrSeg (+) 0 (use mat) (use seg)Matrix (Z :. 5 :. 12) [ 2, 0, 18, 15, 11, 6, 0, 0, 24, 17, 9, 0, 12, 0, 58, 45, 31, 16, 0, 0, 54, 37, 19, 0, 22, 0, 98, 75, 51, 26, 0, 0, 84, 57, 29, 0, 32, 0, 138, 105, 71, 36, 0, 0, 114, 77, 39, 0, 42, 0, 178, 135, 91, 46, 0, 0, 144, 97, 49, 0]
scanr1Seg :: (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e) #
Segmented version of scanr1.
>>>let seg = fromList (Z:.4) [1,4,0,3]>>>segVector (Z :. 4) [1,4,0,3]
>>>let mat = fromList (Z:.5:.10) [0..]>>>matMatrix (Z :. 5 :. 10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
>>>scanr1Seg (+) (use mat) (use seg)Matrix (Z :. 5 :. 8) [ 0, 10, 9, 7, 4, 18, 13, 7, 10, 50, 39, 27, 14, 48, 33, 17, 20, 90, 69, 47, 24, 78, 53, 27, 30, 130, 99, 67, 34, 108, 73, 37, 40, 170, 129, 87, 44, 138, 93, 47]
scanr'Seg :: forall sh e i. (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e, Array (sh :. Int) e) #
Segmented version of scanr'.
>>>let seg = fromList (Z:.4) [1,4,0,3]>>>segVector (Z :. 4) [1,4,0,3]
>>>let mat = fromList (Z:.5:.10) [0..]>>>matMatrix (Z :. 5 :. 10) [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
>>>let (res,sums) = scanr'Seg (+) 0 (use mat) (use seg)>>>resMatrix (Z :. 5 :. 8) [ 0, 15, 11, 6, 0, 17, 9, 0, 0, 45, 31, 16, 0, 37, 19, 0, 0, 75, 51, 26, 0, 57, 29, 0, 0, 105, 71, 36, 0, 77, 39, 0, 0, 135, 91, 46, 0, 97, 49, 0]>>>sumsMatrix (Z :. 5 :. 4) [ 2, 18, 0, 24, 12, 58, 0, 54, 22, 98, 0, 84, 32, 138, 0, 114, 42, 178, 0, 144]
prescanrSeg :: (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e) #
Segmented version of prescanr.
postscanrSeg :: (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e) #
Segmented version of postscanr.
Stencils
Arguments
| :: (Stencil sh a stencil, Elt b) | |
| => (stencil -> Exp b) | stencil function |
| -> Boundary a | boundary condition |
| -> Acc (Array sh a) | source array |
| -> Acc (Array sh b) | destination array |
Map a stencil over an array. In contrast to map, the domain of a stencil
function is an entire neighbourhood of each array element. Neighbourhoods
are sub-arrays centred around a focal point. They are not necessarily
rectangular, but they are symmetric and have an extent of at least three
along each axis. Due to the symmetry requirement the extent is necessarily
odd. The focal point is the array position that is determined by the stencil.
For those array positions where the neighbourhood extends past the boundaries of the source array, a boundary condition determines the contents of the out-of-bounds neighbourhood positions.
Stencil neighbourhoods are specified via nested tuples, where the nesting depth is equal to the dimensionality of the array. For example, a 3x1 stencil for a one-dimensional array:
s31 :: Stencil3 a -> Exp a s31 (l,c,r) = ...
...where c is the focal point of the stencil, and l and r represent the
elements to the left and right of the focal point, respectively. Similarly,
a 3x3 stencil for a two-dimensional array:
s33 :: Stencil3x3 a -> Exp a s33 ((_,t,_)
,(l,c,r) ,(_,b,_)) = ...
...where c is again the focal point and t, b, l and r are the
elements to the top, bottom, left, and right of the focal point, respectively
(the diagonal elements have been elided).
For example, the following computes a 5x5 Gaussian blur as a separable 2-pass operation.
type Stencil5x1 a = (Stencil3 a, Stencil5 a, Stencil3 a)
type Stencil1x5 a = (Stencil3 a, Stencil3 a, Stencil3 a, Stencil3 a, Stencil3 a)
convolve5x1 :: Num a => [Exp a] -> Stencil5x1 a -> Exp a
convolve5x1 kernel (_, (a,b,c,d,e), _)
= Prelude.sum $ Prelude.zipWith (*) kernel [a,b,c,d,e]
convolve1x5 :: Num a => [Exp a] -> Stencil1x5 a -> Exp a
convolve1x5 kernel ((_,a,_), (_,b,_), (_,c,_), (_,d,_), (_,e,_))
= Prelude.sum $ Prelude.zipWith (*) kernel [a,b,c,d,e]
gaussian = [0.06136,0.24477,0.38774,0.24477,0.06136]
blur :: Num a => Acc (Array DIM2 a) -> Acc (Array DIM2 a)
blur = stencil (convolve5x1 gaussian) Clamp
. stencil (convolve1x5 gaussian) ClampArguments
| :: (Stencil sh a stencil1, Stencil sh b stencil2, Elt c) | |
| => (stencil1 -> stencil2 -> Exp c) | binary stencil function |
| -> Boundary a | boundary condition #1 |
| -> Acc (Array sh a) | source array #1 |
| -> Boundary b | boundary condition #2 |
| -> Acc (Array sh b) | source array #2 |
| -> Acc (Array sh c) | destination array |
Map a binary stencil of an array. The extent of the resulting array is the
intersection of the extents of the two source arrays. This is the stencil
equivalent of zipWith.
Stencil specification
class (Elt (StencilRepr sh stencil), Stencil sh a (StencilRepr sh stencil)) => Stencil sh a stencil #
Minimal complete definition
stencilPrj
Instances
| Elt e => Stencil DIM1 e (Exp e, Exp e, Exp e) # | |
| Elt e => Stencil DIM1 e (Exp e, Exp e, Exp e, Exp e, Exp e) # | |
| Elt e => Stencil DIM1 e (Exp e, Exp e, Exp e, Exp e, Exp e, Exp e, Exp e) # | |
| Elt e => Stencil DIM1 e (Exp e, Exp e, Exp e, Exp e, Exp e, Exp e, Exp e, Exp e, Exp e) # | |
| (Stencil ((:.) sh Int) a row2, Stencil ((:.) sh Int) a row1, Stencil ((:.) sh Int) a row0) => Stencil ((:.) ((:.) sh Int) Int) a (row2, row1, row0) # | |
| (Stencil ((:.) sh Int) a row1, Stencil ((:.) sh Int) a row2, Stencil ((:.) sh Int) a row3, Stencil ((:.) sh Int) a row4, Stencil ((:.) sh Int) a row5) => Stencil ((:.) ((:.) sh Int) Int) a (row1, row2, row3, row4, row5) # | |
| (Stencil ((:.) sh Int) a row1, Stencil ((:.) sh Int) a row2, Stencil ((:.) sh Int) a row3, Stencil ((:.) sh Int) a row4, Stencil ((:.) sh Int) a row5, Stencil ((:.) sh Int) a row6, Stencil ((:.) sh Int) a row7) => Stencil ((:.) ((:.) sh Int) Int) a (row1, row2, row3, row4, row5, row6, row7) # | |
| (Stencil ((:.) sh Int) a row1, Stencil ((:.) sh Int) a row2, Stencil ((:.) sh Int) a row3, Stencil ((:.) sh Int) a row4, Stencil ((:.) sh Int) a row5, Stencil ((:.) sh Int) a row6, Stencil ((:.) sh Int) a row7, Stencil ((:.) sh Int) a row8, Stencil ((:.) sh Int) a row9) => Stencil ((:.) ((:.) sh Int) Int) a (row1, row2, row3, row4, row5, row6, row7, row8, row9) # | |
Boundary condition specification for stencil operations.
Common stencil patterns
type Stencil3x3 a = (Stencil3 a, Stencil3 a, Stencil3 a) #
type Stencil5x3 a = (Stencil5 a, Stencil5 a, Stencil5 a) #
type Stencil3x3x3 a = (Stencil3x3 a, Stencil3x3 a, Stencil3x3 a) #
type Stencil5x3x3 a = (Stencil5x3 a, Stencil5x3 a, Stencil5x3 a) #
type Stencil3x5x3 a = (Stencil3x5 a, Stencil3x5 a, Stencil3x5 a) #
type Stencil3x3x5 a = (Stencil3x3 a, Stencil3x3 a, Stencil3x3 a, Stencil3x3 a, Stencil3x3 a) #
type Stencil5x5x3 a = (Stencil5x5 a, Stencil5x5 a, Stencil5x5 a) #
type Stencil5x3x5 a = (Stencil5x3 a, Stencil5x3 a, Stencil5x3 a, Stencil5x3 a, Stencil5x3 a) #
type Stencil3x5x5 a = (Stencil3x5 a, Stencil3x5 a, Stencil3x5 a, Stencil3x5 a, Stencil3x5 a) #
type Stencil5x5x5 a = (Stencil5x5 a, Stencil5x5 a, Stencil5x5 a, Stencil5x5 a, Stencil5x5 a) #
The Accelerate Expression Language
Scalar data types
The type Exp represents embedded scalar expressions. The collective
operations of Accelerate Acc consist of many scalar expressions executed in
data-parallel.
Note that scalar expressions can not initiate new collective operations: doing so introduces nested data parallelism, which is difficult to execute efficiently on constrained hardware such as GPUs, and is thus currently unsupported.
Instances
Type classes
Basic type classes
The Eq class defines equality == and inequality /= for scalar
Accelerate expressions.
For convenience, we include Elt as a superclass.
Instances
| Eq Bool # | |
| Eq Char # | |
| Eq Double # | |
| Eq Float # | |
| Eq Int # | |
| Eq Int8 # | |
| Eq Int16 # | |
| Eq Int32 # | |
| Eq Int64 # | |
| Eq Word # | |
| Eq Word8 # | |
| Eq Word16 # | |
| Eq Word32 # | |
| Eq Word64 # | |
| Eq () # | |
| Eq CChar # | |
| Eq CSChar # | |
| Eq CUChar # | |
| Eq CShort # | |
| Eq CUShort # | |
| Eq CInt # | |
| Eq CUInt # | |
| Eq CLong # | |
| Eq CULong # | |
| Eq CLLong # | |
| Eq CULLong # | |
| Eq CFloat # | |
| Eq CDouble # | |
| (Eq a, Eq b) => Eq (a, b) # | |
| (Eq a, Eq b, Eq c) => Eq (a, b, c) # | |
| (Eq a, Eq b, Eq c, Eq d) => Eq (a, b, c, d) # | |
| (Eq a, Eq b, Eq c, Eq d, Eq e) => Eq (a, b, c, d, e) # | |
| (Eq a, Eq b, Eq c, Eq d, Eq e, Eq f) => Eq (a, b, c, d, e, f) # | |
| (Eq a, Eq b, Eq c, Eq d, Eq e, Eq f, Eq g) => Eq (a, b, c, d, e, f, g) # | |
| (Eq a, Eq b, Eq c, Eq d, Eq e, Eq f, Eq g, Eq h) => Eq (a, b, c, d, e, f, g, h) # | |
| (Eq a, Eq b, Eq c, Eq d, Eq e, Eq f, Eq g, Eq h, Eq i) => Eq (a, b, c, d, e, f, g, h, i) # | |
| (Eq a, Eq b, Eq c, Eq d, Eq e, Eq f, Eq g, Eq h, Eq i, Eq j) => Eq (a, b, c, d, e, f, g, h, i, j) # | |
| (Eq a, Eq b, Eq c, Eq d, Eq e, Eq f, Eq g, Eq h, Eq i, Eq j, Eq k) => Eq (a, b, c, d, e, f, g, h, i, j, k) # | |
| (Eq a, Eq b, Eq c, Eq d, Eq e, Eq f, Eq g, Eq h, Eq i, Eq j, Eq k, Eq l) => Eq (a, b, c, d, e, f, g, h, i, j, k, l) # | |
| (Eq a, Eq b, Eq c, Eq d, Eq e, Eq f, Eq g, Eq h, Eq i, Eq j, Eq k, Eq l, Eq m) => Eq (a, b, c, d, e, f, g, h, i, j, k, l, m) # | |
| (Eq a, Eq b, Eq c, Eq d, Eq e, Eq f, Eq g, Eq h, Eq i, Eq j, Eq k, Eq l, Eq m, Eq n) => Eq (a, b, c, d, e, f, g, h, i, j, k, l, m, n) # | |
| (Eq a, Eq b, Eq c, Eq d, Eq e, Eq f, Eq g, Eq h, Eq i, Eq j, Eq k, Eq l, Eq m, Eq n, Eq o) => Eq (a, b, c, d, e, f, g, h, i, j, k, l, m, n, o) # | |