SBCL Internals : Vectorizing

SBCL Internals
The pages on this CLiki-driven site can be edited by anybody at any time. No warranty of any kind can therefore be made; any implied warranties of merchantability or fitness for a particular purpose are expressly disclaimed

[ Home ]

[ Recent Changes ]

[ About CLiki ]

[ Text Formatting ]

Vectorizing compilers exist in several languages, but notably C and FORTRAN, and for various architectures. The basic idea is the same in all cases: take operations that are independent of each other and execute them in parallel. The typical FORTRAN vectorizable loop looks like:

DO I=1..N
  C(I)=A(I)+B(I)
END DO

Now, Common Lisp has map-into, which expresses the vectorizability of an operation perfectly, as it has a well-specified return vector type and a guarantee that the operation is independent of the particular index. The hard part of the operation is figuring out just what to do with the vectors. Currently I (Christophe Rhodes) am looking at transforming map-into at the IR1 stage of the compiler into explicitly vectorized (using the Intel Streaming Single-Instruction Multiple-Data Extensions) x86 code. This is subject to change and real-life(tm) delays.

I'm not sure you can use MAP-INTO for this. The spec for MAP-INTO says "If function [passed to MAP-INTO] has side effects, it can count on being called first on all of the elements with index 0, then on all of those numbered 1, and so on." Don't know if MMX guarantees 'sequential' vectorizing, maybe it does. But if not, then users must pass side-effect-free functions to MAP-INTO. Still, it would be a really cool extension.

Nikodemus: This is a non-issue, I believe: detecting the purity of the function is probably one of the easiest parts of the implementation. ...and if you work hard enough, even impure functions can be partially vectorized:

(let ((y 0))
   (map-into vector (lambda (x) (setf y (foo y (* x 2))) (bar y)) vector))
  ===>
(let ((y 0))
   (vectorized-map-into vector (lambda (x) (* x 2)) vector) vector)
   (map-into vector (lambda (x) (setf y (foo y x)) (bar y)) vector))

Furthermore, we're never going to vectorize full calls anyways -- just things that can be expressed in the SIMD instruction set.

Further thoughts on this subject (some of which are courtesy of Pierre Mai) include noting that

Currently (0.7.4.x) there are almost no loop transformations done on IR1 or IR2. The only exception to this is rotating a loop to encourage sequential flow-of-control over VOPs.
CMUCL has (commented out) the beginnings of an IR1 loop representation, which might prove useful.
Almost certainly, there are easier transformations than vectorization to do; for instance, loop-invariant lifting.

This page is linked from: Christophe Rhodes

CLiki pages can be edited by anyone at any time. Imagine a fearsomely comprehensive disclaimer of liability. Now fear, comprehensively