basis/math/vectors/simd/simd-docs.factor

   1 USING: help.markup help.syntax sequences math math.vectors
   2 kernel.private classes.tuple.private
   3 math.vectors.simd.intrinsics cpu.architecture ;
   4 IN: math.vectors.simd
   5
   6 ARTICLE: "math.vectors.simd.intro" "Introduction to SIMD support"
   7 "Modern CPUs support a form of data-level parallelism, where arithmetic operations on fixed-size short vectors can be done on all components in parallel. This is known as single-instruction-multiple-data (SIMD)."
   8 $nl
   9 "SIMD support in the processor takes the form of instruction sets which operate on vector registers. By operating on multiple scalar values at the same time, code which operates on points, colors, and other vector data can be sped up."
  10 $nl
  11 "In Factor, SIMD support is exposed in the form of special-purpose SIMD " { $link "sequence-protocol" } " implementations. These are fixed-length, homogeneous sequences. They are referred to as vectors, but should not be confused with Factor's " { $link "vectors" } ", which can hold any type of object and can be resized.)."
  12 $nl
  13 "The words in the " { $vocab-link "math.vectors" } " vocabulary, which can be used with any sequence of numbers, are special-cased by the compiler. If the compiler can prove that only SIMD vectors are used, it expands " { $link "math-vectors" } " into " { $link "math.vectors.simd.intrinsics" } ". While in the general case, SIMD intrinsics operate on heap-allocated SIMD vectors, that too can be optimized since in many cases the compiler unbox SIMD vectors, storing them directly in registers."
  14 $nl
  15 "Since the only difference between ordinary code and SIMD-accelerated code is that the latter uses special fixed-length SIMD sequences, the SIMD library is very easy to use. To ensure your code compiles to use vector instructions without boxing and unboxing overhead, follow the guidelines for " { $link "math.vectors.simd.efficiency" } "."
  16 $nl
  17 "There should never be any reason to use " { $link "math.vectors.simd.intrinsics" } " directly, but they too have a straightforward, but lower-level, interface." ;
  18
  19 ARTICLE: "math.vectors.simd.support" "Supported SIMD instruction sets and operations"
  20 "At present, the SIMD support makes use of SSE2 and a few SSE3 instructions on x86 CPUs."
  21 $nl
  22 "SSE3 introduces horizontal adds (summing all components of a single vector register), which is useful for computing dot products. Where available, SSE3 operations are used to speed up " { $link sum } ", " { $link v. } ", " { $link norm-sq } ", " { $link norm } ", and " { $link distance } ". If SSE3 is not available, software fallbacks are used for " { $link sum } " and related words, decreasing performance."
  23 $nl
  24 "On PowerPC, or older x86 chips without SSE2, software fallbacks are used for all high-level vector operations. SIMD code can run with no loss in functionality, just decreased performance."
  25 $nl
  26 "The primities in the " { $vocab-link "math.vectors.simd.intrinsics" } " vocabulary do not have software fallbacks, but they should not be called directly in any case." ;
  27
  28 ARTICLE: "math.vectors.simd.types" "SIMD vector types"
  29 "Each SIMD vector type is named " { $snippet "scalar-count" } ", where " { $snippet "scalar" } " is a scalar C type such as " { $snippet "float" } " or " { $snippet "double" } ", and " { $snippet "count" } " is a vector dimension, such as 2, 4, or 8."
  30 $nl
  31 "The following vector types are defined:"
  32 { $subsection float-4 }
  33 { $subsection double-2 }
  34 { $subsection float-8 }
  35 { $subsection double-4 }
  36 "For each vector type, several words are defined:"
  37 { $table
  38     { "Word" "Stack effect" "Description" }
  39     { { $snippet "type-with" } { $snippet "( x -- simd-array )" } "creates a new instance where all components are set to a single scalar" }
  40     { { $snippet "type-boa" } { $snippet "( ... -- simd-array )" } "creates a new instance where components are read from the stack" }
  41     { { $snippet ">type" } { $snippet "( seq -- simd-array )" } "creates a new instance initialized with the elements of an existing sequence, which must have the correct length" }
  42     { { $snippet "type{" } { $snippet "type{ elements... }" } "parsing word defining literal syntax for an SIMD vector; the correct number of elements must be given" }
  43 }
  44 "The " { $link float-4 } " and " { $link double-2 } " types correspond to 128-bit vector registers. The " { $link float-8 } " and " { $link double-4 } " types are not directly supported in hardware, and instead unbox to a pair of 128-bit vector registers."
  45 $nl
  46 "Operations on " { $link float-4 } " instances:"
  47 { $subsection float-4-with }
  48 { $subsection float-4-boa }
  49 { $subsection POSTPONE: float-4{ }
  50 "Operations on " { $link double-2 } " instances:"
  51 { $subsection double-2-with }
  52 { $subsection double-2-boa }
  53 { $subsection POSTPONE: double-2{ }
  54 "Operations on " { $link float-8 } " instances:"
  55 { $subsection float-8-with }
  56 { $subsection float-8-boa }
  57 { $subsection POSTPONE: float-8{ }
  58 "Operations on " { $link double-4 } " instances:"
  59 { $subsection double-4-with }
  60 { $subsection double-4-boa }
  61 { $subsection POSTPONE: double-4{ }
  62 "To actually perform vector arithmetic on SIMD vectors, use " { $link "math-vectors" } " words."
  63 { $see-also "c-types-specs" } ;
  64
  65 ARTICLE: "math.vectors.simd.efficiency" "Writing efficient SIMD code"
  66 "Since SIMD vectors are heap-allocated objects, it is important to write code in a style which is conducive to the compiler being able to inline generic dispatch and eliminate allocation."
  67 $nl
  68 "If the inputs to a " { $vocab-link "math.vectors" } " word are statically known to be SIMD vectors, the call is converted into an SIMD primitive, and the output is then also known to be an SIMD vector (or scalar, depending on the operation); this information propagates forward within a single word (together with any inlined words and macro expansions). Any intermediate values which are not stored into collections, or returned from the word, are furthermore unboxed."
  69 $nl
  70 "To check if optimizations are being performed, pass a quotation to the " { $snippet "optimizer-report." } " and " { $snippet "optimized." } " words in the " { $vocab-link "compiler.tree.debugger" } " vocabulary, and look for calls to " { $link "math.vectors.simd.intrinsics" } " as opposed to high-level " { $link "math-vectors" } "."
  71 $nl
  72 "For example, in the following, no SIMD operations are used at all, because the compiler's propagation pass does not consider dynamic variable usage:"
  73 { $code
  74 """USING: compiler.tree.debugger math.vectors
  75 math.vectors.simd ;
  76 SYMBOLS: x y ;
  77
  78 [
  79     double-4{ 1.5 2.0 3.7 0.4 } x set
  80     double-4{ 1.5 2.0 3.7 0.4 } y set
  81     x get y get v+
  82 ] optimizer-report.""" }
  83 "The following word benefits from SIMD optimization, because it begins with an unsafe declaration:"
  84 { $code
  85 """USING: compiler.tree.debugger kernel.private
  86 math.vectors math.vectors.simd ;
  87
  88 : interpolate ( v a b -- w )
  89     { float-4 float-4 float-4 } declare
  90     [ v* ] [ [ 1.0 ] dip n-v v* ] bi-curry* bi v+ ;
  91
  92 \ interpolate optimizer-report.""" }
  93 "Note that using " { $link declare } " is not recommended. Safer ways of getting type information for the input parameters to a word include defining methods on a generic word (the value being dispatched upon has a statically known type in the method body), as well as using " { $link "hints" } " and " { $link POSTPONE: inline } " declarations."
  94 $nl
  95 "Here is a better version of the " { $snippet "interpolate" } " words above that uses hints:"
  96 { $code
  97 """USING: compiler.tree.debugger hints
  98 math.vectors math.vectors.simd ;
  99
 100 : interpolate ( v a b -- w )
 101     [ v* ] [ [ 1.0 ] dip n-v v* ] bi-curry* bi v+ ;
 102
 103 HINTS: interpolate float-4 float-4 float-4 ;
 104
 105 \ interpolate optimizer-report. """ }
 106 "This time, the optimizer report lists calls to both SIMD primitives and high-level vector words, because hints cause two code paths to be generated. The " { $snippet "optimized." } " word can be used to make sure that the fast code path consists entirely of calls to primitives."
 107 $nl
 108 "If the " { $snippet "interpolate" } " word was to be used in several places with different types of vectors, it would be best to declare it " { $link POSTPONE: inline } "."
 109 $nl
 110 "In the " { $snippet "interpolate" } " word, there is still a call to the " { $link <tuple-boa> } " primitive, because the return value at the end is being boxed on the heap. In the next example, no memory allocation occurs at all because the SIMD vectors are stored inside a struct class (see " { $link "classes.struct" } "); also note the use of inlining:"
 111 { $code
 112 """USING: compiler.tree.debugger math.vectors math.vectors.simd ;
 113 IN: simd-demo
 114
 115 STRUCT: actor
 116 { id int }
 117 { position float-4 }
 118 { velocity float-4 }
 119 { acceleration float-4 } ;
 120
 121 GENERIC: advance ( dt object -- )
 122
 123 : update-velocity ( dt actor -- )
 124     [ acceleration>> n*v ] [ velocity>> v+ ] [ ] tri
 125     (>>velocity) ; inline
 126
 127 : update-position ( dt actor -- )
 128     [ velocity>> n*v ] [ position>> v+ ] [ ] tri
 129     (>>position) ; inline
 130
 131 M: actor advance ( dt actor -- )
 132     [ >float ] dip
 133     [ update-velocity ] [ update-position ] 2bi ;
 134
 135 M\ actor advance optimized."""
 136 }
 137 "The " { $vocab-link "compiler.cfg.debugger" } " vocabulary can give a lower-level picture of the generated code, that includes register assignments and other low-level details. To look at low-level optimizer output, call " { $snippet "test-mr mr." } " on a word or quotation:"
 138 { $code
 139 """USE: compiler.tree.debugger
 140
 141 M\ actor advance test-mr mr.""" }
 142 "An example of a high-performance algorithm that uses SIMD primitives can be found in the " { $vocab-link "benchmark.nbody-simd" } " vocabulary." ;
 143
 144 ARTICLE: "math.vectors.simd.intrinsics" "Low-level SIMD primitives"
 145 "The words in the " { $vocab-link "math.vectors.simd.intrinsics" } " vocabulary are used to implement SIMD support. These words have three disadvantages compared to the higher-level " { $link "math-vectors" } " words:"
 146 { $list
 147     "They operate on raw byte arrays, with a separate “representation” parameter passed in to determine the type of the operands and result."
 148     "They are unsafe; passing values which are not byte arrays, or byte arrays with the wrong size, will dereference invalid memory and possibly crash Factor."
 149     { "They do not have software fallbacks; if the current CPU does not have SIMD support, a " { $link bad-simd-call } " error will be thrown." }
 150 }
 151 "The compiler converts " { $link "math-vectors" } " into SIMD primitives automatically in cases where it is safe; this means that the input types are known to be SIMD vectors, and the CPU supports SIMD."
 152 $nl
 153 "It is best to avoid calling these primitives directly. To write efficient high-level code that compiles down to primitives and avoids memory allocation, see " { $link "math.vectors.simd.efficiency" } "."
 154 { $subsection (simd-v+) }
 155 { $subsection (simd-v-) }
 156 { $subsection (simd-v/) }
 157 { $subsection (simd-vmin) }
 158 { $subsection (simd-vmax) }
 159 { $subsection (simd-vsqrt) }
 160 { $subsection (simd-sum) }
 161 { $subsection (simd-broadcast) }
 162 { $subsection (simd-gather-2) }
 163 { $subsection (simd-gather-4) }
 164 "There are two primitives which are used to implement accessing SIMD vector fields of " { $link "classes.struct" } ":"
 165 { $subsection alien-vector }
 166 { $subsection set-alien-vector }
 167 "For the most part, the above primitives correspond directly to vector arithmetic words. They take a representation parameter, which is one of the singleton members of the " { $link vector-rep } " union in the " { $vocab-link "cpu.architecture" } " vocabulary." ;
 168
 169 ARTICLE: "math.vectors.simd.alien" "SIMD data in struct classes"
 170 "Struct classes may contain fields which store SIMD data; use one of the following C type names:"
 171 { $code
 172 """float-4
 173 double-2
 174 float-8
 175 double-4""" }
 176 "Passing SIMD data as function parameters is not yet supported." ;
 177
 178 ARTICLE: "math.vectors.simd" "Hardware vector arithmetic (SIMD)"
 179 "The " { $vocab-link "math.vectors.simd" } " vocabulary extends the " { $vocab-link "math.vectors" } " vocabulary to support efficient vector arithmetic on small, fixed-size vectors."
 180 { $subsection "math.vectors.simd.intro" }
 181 { $subsection "math.vectors.simd.types" }
 182 { $subsection "math.vectors.simd.support" }
 183 { $subsection "math.vectors.simd.efficiency" }
 184 { $subsection "math.vectors.simd.alien" }
 185 { $subsection "math.vectors.simd.intrinsics" } ;
 186
 187 ! ! ! float-4
 188
 189 HELP: float-4
 190 { $class-description "A sequence of four single-precision floating point values. New instances can be created with " { $link float-4-with } " or " { $link float-4-boa } "." } ;
 191
 192 HELP: float-4-with
 193 { $values { "x" float } { "simd-array" float-4 } }
 194 { $description "Creates a new vector with all four components equal to a scalar." } ;
 195
 196 HELP: float-4-boa
 197 { $values { "a" float } { "b" float } { "c" float } { "d" float } { "simd-array" float-4 } }
 198 { $description "Creates a new vector from four scalar components." } ;
 199
 200 HELP: float-4{
 201 { $syntax "float-4{ a b c d }" }
 202 { $description "Literal syntax for a " { $link float-4 } "." } ;
 203
 204 ! ! ! double-2
 205
 206 HELP: double-2
 207 { $class-description "A sequence of two double-precision floating point values. New instances can be created with " { $link double-2-with } " or " { $link double-2-boa } "." } ;
 208
 209 HELP: double-2-with
 210 { $values { "x" float } { "simd-array" double-2 } }
 211 { $description "Creates a new vector with both components equal to a scalar." } ;
 212
 213 HELP: double-2-boa
 214 { $values { "a" float } { "b" float } { "simd-array" double-2 } }
 215 { $description "Creates a new vector from two scalar components." } ;
 216
 217 HELP: double-2{
 218 { $syntax "double-2{ a b }" }
 219 { $description "Literal syntax for a " { $link double-2 } "." } ;
 220
 221 ! ! ! float-8
 222
 223 HELP: float-8
 224 { $class-description "A sequence of eight single-precision floating point values. New instances can be created with " { $link float-8-with } " or " { $link float-8-boa } "." } ;
 225
 226 HELP: float-8-with
 227 { $values { "x" float } { "simd-array" float-8 } }
 228 { $description "Creates a new vector with all eight components equal to a scalar." } ;
 229
 230 HELP: float-8-boa
 231 { $values { "a" float } { "b" float } { "c" float } { "d" float } { "e" float } { "f" float } { "g" float } { "h" float } { "simd-array" float-8 } }
 232 { $description "Creates a new vector from eight scalar components." } ;
 233
 234 HELP: float-8{
 235 { $syntax "float-8{ a b c d e f g h }" }
 236 { $description "Literal syntax for a " { $link float-8 } "." } ;
 237
 238 ! ! ! double-4
 239
 240 HELP: double-4
 241 { $class-description "A sequence of four double-precision floating point values. New instances can be created with " { $link double-4-with } " or " { $link double-4-boa } "." } ;
 242
 243 HELP: double-4-with
 244 { $values { "x" float } { "simd-array" double-4 } }
 245 { $description "Creates a new vector with all four components equal to a scalar." } ;
 246
 247 HELP: double-4-boa
 248 { $values { "a" float } { "b" float } { "c" float } { "d" float } { "simd-array" double-4 } }
 249 { $description "Creates a new vector from four scalar components." } ;
 250
 251 HELP: double-4{
 252 { $syntax "double-4{ a b c d }" }
 253 { $description "Literal syntax for a " { $link double-4 } "." } ;
 254
 255 ABOUT: "math.vectors.simd"