chickadee » array-morphisms-crunch

array-morphisms-crunch

Kernels for array-morphisms compiled to C by the crunch compiler: activations, element-wise arithmetic, reductions, scans, BLAS, convolution and the Adam optimizer, and a code generator that compiles a kernel for each segmented operation of a replay plan.

Description

crunch compiles a statically typed subset of Scheme to C. The kernels of this egg are written in Scheme, but they run without type dispatch, boxing or allocation in their inner loops.

Every kernel gives the same values as the Scheme code of array-morphisms that it replaces, so registering a backend of this egg changes performance, not results. Large arrays can be split across threads. The results do not depend on the number of threads.

Requirements

The code generator also needs csc and its C compiler at run time.

Usage

(import array-morphisms-activation-exec
        array-morphisms-crunch-activations)
(register-activation-backend! (make-crunch-threaded-activation-backend))

(import array-morphisms-blas-exec
        array-morphisms-crunch-conv-backend)
(register-blas-backend! (make-crunch-blas-backend))

(import array-morphisms-crunch-codegen)
(register-crunch-codegen-backend!)

The three registrations are independent. The activation backend can be combined with any BLAS backend, including the built-in microBLAS backend and the system-BLAS backend of array-morphisms-blas.

nanograd's Adam optimizer uses the Adam kernel once it is registered:

(import nanograd-optimizer array-morphisms-crunch-optimizers)
(register-optimizer-kernel! 'adam 'f32 crunch-adam-f32)
(register-optimizer-kernel! 'adam 'f64 crunch-adam-f64)

Activation backends

Module array-morphisms-crunch-activations.

make-crunch-activation-backendprocedure
make-crunch-threaded-activation-backendprocedure

Return an activation backend for register-activation-backend!. The threaded backend splits large arrays across threads. Its results are the same as those of the unthreaded one. Both register the binary ops add, sub, mul and div with register-binary-op!.

A backend holds f32 and f64 kernels for:

  • the activations relu, sigmoid and tanh and their derivative ops relu-deriv, sigmoid-deriv and tanh-deriv;
  • exp, log, sqrt, negate and abs;
  • the binary ops add, sub, mul and div, also broadcast by row, column or scalar;
  • sums, means, maxima and minima of row-major 2-D arrays over axis 0 or 1, rounded exactly as the Scheme loops round them;
  • scans (sum, prod, max, min) of row-major arrays along any axis; a scan along the last axis runs 8 lines together;
  • copies of strided views of rank at most 4 into row-major order;
  • fused kernels for the bodies that the fusion pass of array-morphisms forms most often (below).

The kernels are generated from the scalar-op table of array-morphisms, which also supplies the Scheme combiners, so each kernel uses the same formula. log and sqrt of a negative number give NaN, where Scheme gives a complex number.

Each kernel is also exported on its own, as crunch-<op>-f32 and crunch-<op>-f64, a procedure (size in out).

crunch-activation-opsprocedure

The op names of the activation table.

crunch-fused-bodiesprocedure

The canonical bodies of the fused kernels:

BodyFormed by the fusion pass for
(mul (in 0) (cast f32 (relu-deriv (in 1))))gradient times relu derivative
(mul (in 0) (cast f32 (sigmoid-deriv (in 1))))gradient times sigmoid derivative
(mul (in 0) (cast f32 (tanh-deriv (in 1))))gradient times tanh derivative
(add (in 0) (cast f32 (mul (in 1) (in 2))))x*y + z
(negate (cast f32 (mul (in 0) (in 1))))negated product
(exp (cast f32 (negate (in 0))))exp(-x)
(mul (in 0) (cast f32 (sigmoid (in 0))))silu(a)
(mul (in 0) (cast f32 (mul (in 1) (cast f32 (sigmoid (in 1))))))b * silu(a), the Llama feed-forward block

The f32 kernel rounds where the body says (cast f32 ...), as storing the intermediate value would; the f64 kernel is the same body without casts.

crunch-colsum-bodiesprocedure

The bodies of the column-sum kernels. The list is currently empty.

crunch-softmax-rows-f32 rows cols src outprocedure
crunch-softmax-rows-f64 rows cols src outprocedure

Replace each row of the row-major rows x cols array src by its softmax, stored in out, which may be src. The row maximum is subtracted before exp, and the sum is accumulated in double precision.

crunch-rope-f32 n head-size base cos sin xprocedure
crunch-rope-f64 n head-size base cos sin xprocedure

Rotate the first n elements of x in place as consecutive pairs. Pair p of each head of head-size elements is rotated by the angle with cosine cos[base + p] and sine sin[base + p]: the interleaved rotary position embedding of Llama, with base selecting the row of the token position.

These two kernels have no morphism op. They are meant for code that works outside compiled SSA programs, such as attention over a growing key/value cache.

BLAS and convolution backend

Module array-morphisms-crunch-blas-backend.

crunch-sgemm M N K alpha A B beta Cprocedure
crunch-dgemm M N K alpha A B beta Cprocedure
crunch-sgemm-strided M N K alpha A lda transa B ldb transb beta Cprocedure
crunch-dgemm-strided M N K alpha A lda transa B ldb transb beta Cprocedure
crunch-sgemm-offset M N K alpha A off-A lda transa B off-B ldb transb beta C off-Cprocedure
crunch-dgemm-offset M N K alpha A off-A lda transa B off-B ldb transb beta C off-Cprocedure
crunch-sgemv M N alpha A x beta yprocedure
crunch-dgemv M N alpha A x beta yprocedure
crunch-sdot N x yprocedure
crunch-ddot N x yprocedure
crunch-sdot-offset N x off-x y off-yprocedure
crunch-ddot-offset N x off-x y off-yprocedure
crunch-saxpy N alpha x yprocedure
crunch-daxpy N alpha x yprocedure

The BLAS kernels, with the normalized signatures of array-morphisms-blas-exec.

  • Each element of C is a sum over k in increasing order, in double precision for f32 as well as f64, so the result does not depend on the number of threads.
  • An operand that is not plain row-major is first packed into a row-major copy. Packing buffers are kept and reused.
  • The rows of C are shared among up to (crunch-thread-count) threads, with at least 65536 multiply-adds per thread.
  • As in reference BLAS, C is not read when beta is 0.
  • The offset kernels take matrices and vectors that start at an offset into their vectors, as array-morphisms needs for the cells of a batched product. They compute exactly as the strided GEMM and the DOT kernel.
crunch-native-build?procedure

Whether the installed egg was built for the CPU of the build machine (see Building).

Module array-morphisms-crunch-conv-backend.

make-crunch-blas-backendprocedure

Return the complete BLAS backend record: the kernels above, and the convolution hooks for NCHW and NHWC images.

The module also exports the convolution kernels themselves: crunch-im2col-nchw-f32, crunch-im2col-nhwc-f32, crunch-col2im-nchw-f32, crunch-col2im-nhwc-f32, crunch-bias-add-f32, and the six hooks crunch-conv-fwd-im2col-f32, crunch-conv-bwd-data-im2col-f32, crunch-conv-bwd-weights-im2col-f32 and their -nhwc- versions.

Code generation

Module array-morphisms-crunch-codegen.

The fused kernels above form a fixed catalog. The code generator instead writes a kernel for each segop of a replay plan, from the segop's body and index maps, and compiles it with crunch.

register-crunch-codegen-backend!procedure

Add the code generator to the segop backends of array-morphisms, after the registry backend, so that the BLAS and catalogue kernels keep the segops they run, and before the scheme backend.

unregister-crunch-codegen-backend!procedure

Remove the registered backend.

The code generator runs:

  • element-wise maps, with one or several outputs, over spaces of up to rank 6, whose operands are read through identities, broadcasts, transposes and other strided views;
  • reductions over spaces of up to rank 8 that combine with add, mul, max or min, with the map fused into them and the final step fused after them;
  • matrix products with an epilogue: the BLAS backend computes the product, and the epilogue runs as a generated kernel;
  • scans over spaces of up to rank 8 that the catalogue scan kernels do not run: scans with a combining expression or aux arrays, scans of strided arrays, and integer scans.

The operands may be f32, f64, s32, s64 or u32. A body may contain (if (rel x y) a b), with rel one of <, >, <=, >= and =; the kernel computes both branches and picks one.

Results. A generated kernel computes the same values as the Scheme code it replaces, bit for bit: it rounds where the body says so, adds in the same order, and follows Scheme's arithmetic on mixed integers and floats. When an integer result would leave the range of its dtype, the kernel stops and the segop runs on the host for that call.

When kernels are compiled. The kernels of a plan are compiled together, as one module, when the plan is compiled, at the second step of a program run through ssa-realize/ctx. Compiled modules are kept in a cache directory, so later processes load them instead of compiling them again. If a module cannot be compiled, its segops run on the backends after the code generator, and a warning is written.

crunch-codegen #!optional boolparameter

#t (the default) to use the backend. The environment variable AM_CRUNCH_CODEGEN=0 makes the default #f.

crunch-codegen-fusions #!optional classesparameter

The fusion classes whose fused segops the backend reports as native to the fusion pass of array-morphisms. Default (redomap epilogue), or the classes named in AM_CRUNCH_CODEGEN_FUSIONS.

crunch-codegen-threads #!optional nparameter

The number of threads a kernel runs on. #f (the default) follows the activation backend: the crunch thread count with the threaded backend, otherwise one.

crunch-codegen-cache-directory #!optional dirparameter

The cache directory. Default AM_CRUNCH_CODEGEN_CACHE, else $XDG_CACHE_HOME/array-morphisms/kernels, else ~/.cache/array-morphisms/kernels; #f keeps no cache.

crunch-codegen-csc #!optional pathparameter

The csc program used to compile.

crunch-codegen-statsprocedure

For the whole process: how many segops became kernels, and how many kernels were compiled, loaded from the cache, or could not be compiled. replay-plan-stats gives the same counts for one plan.

crunch-codegen-forget-kernels!procedure

Make the next plan load or compile its kernels again.

The module array-morphisms-crunch-translate holds the translation of segop bodies into crunch Scheme, shared by the generated kernels.

Threads

Module array-morphisms-crunch-threads.

The threaded kernels split [0, n) into nearly equal contiguous chunks. The calling thread runs the first chunk, and workers of a persistent POSIX thread pool run the others. The workers never touch the CHICKEN heap or call into the CHICKEN runtime, all signals are blocked in them, and the calling thread stays inside one foreign call until every chunk has finished, so the vectors cannot move. If a worker cannot be created, its chunk runs on the calling thread.

crunch-thread-count #!optional nparameter

The number of threads requested. Default: the environment variable AM_CRUNCH_THREADS, or the number of online processors, at most 8.

crunch-thread-min-chunk #!optional nparameter

The smallest number of elements given to one thread. Default 4096.

crunch-thread-pool-spin-usprocedure
crunch-thread-pool-spin-us-set! usprocedure

The number of microseconds a waiting thread spins before it sleeps. Default: AM_CRUNCH_SPIN_US, or 20; 0 disables spinning.

crunch-thread-pool-sizeprocedure
crunch-thread-pool-statsprocedure
crunch-thread-pool-shutdown!procedure

The number of workers, counters for tuning, and stopping the pool. The pool is created again at the next threaded call.

The dispatchers crunch-dispatch-f32, crunch-dispatch-f64, crunch-dispatch4-f32, crunch-dispatch4-f64 and crunch-dispatch-n run C chunk kernels; see the source for their calling conventions.

Optimizer kernels

Module array-morphisms-crunch-optimizers.

crunch-adam-f32 n hyper param grad m vprocedure
crunch-adam-f64 n hyper param grad m vprocedure

One Adam update of the first n elements of param, grad, m and v, in place. hyper is an f64vector holding the learning rate, beta1, beta2, epsilon, the bias corrections 1 - beta1^t and 1 - beta2^t, and the weight decay. This is the calling convention of nanograd's optimizer-kernel registry.

Building

The C code is compiled with -O3 -DNDEBUG. NDEBUG removes crunch's per-element index assertions; the Scheme wrappers check vector lengths before every call instead.

Setting AM_CRUNCH_NATIVE=1 while building compiles the kernels for the CPU of the build machine, as with -march=native:

rm -f *.so *.o *.link *.import.scm
AM_CRUNCH_NATIVE=1 chicken-install -test

Such a build runs only on CPUs with the same instructions. It may use fused multiply-add, so its results can differ from those of a portable build in the last bits; they still do not depend on the number of threads.

Notes on crunch

The egg works around these properties of crunch's embedded mode without modifying crunch:

Author

Ivan Raikov

Repository

https://github.com/iraikov/array-morphisms-crunch

License

LGPL-3

Version History

2.0
Code generator for segops (array-morphisms-crunch-codegen, array-morphisms-crunch-translate); fused kernels; scan kernels; offset GEMM and DOT kernels; persistent thread pool; crunch.h is found when eggs are installed under a non-default prefix; requires array-morphisms 3.0
1.1
Kernels for exp, log, sqrt, negate and abs; crunch-softmax-rows and crunch-rope; threaded broadcast binary kernels
1.0
Initial release

Contents »