TOC »
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
- crunch
- array-morphisms 3.0 or later
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:
Body Formed 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:
- In CHICKEN 6 an SRFI-4 vector is a two-slot structure, and crunch's converters for numeric-vector arguments do not follow it to the element storage. The egg replaces them for s32, s64, f32 and f64 vectors.
- float arguments and results cross the generated wrapper as C float, so double-precision scalars are passed through one-element f64vectors.
- abs on a float is compiled to C's integer abs(); the kernels use fpabs.
Author
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