Crate diskann_wide

Expand description

§Wide - Cross Architecture SIMD

This crate attempts to provide (mostly) Miri-compatible, cross-platform SIMD with support for light-weight architecture dispatching.

§Traits

SIMD vectors are weird types as they behave both like scalars and containers. Primary traits exposed by wide are:

SIMDVector: General trait for working with a SIMD vector, including creation and data access.
SIMDMask: Basically a SIMD boolean. Comparisons between SIMDVectors are done lanewise, with the mask containing the results for each lane. Each SIMDVector has an associated mask.
Architecture: SIMD instructions are architecture specific. Some server CPUs like new(ish) x86 models support AVX512, while most consumer CPUs do not yet support that instruction set extension.

To allow compilation of single binaries that support multiple architectures, wide has taken the position that the Architecture is largely explicit when it comes to SIMD types.

Generic, cross-architecture algorithms are still supported by using an Architectures associated SIMD types.

A host of secondary SIMD related traits are also exported, all prefixed with SIMD. Refer to the documentation on each trait for more information.

§Structs

Types implementing SIMDMask can take a variety of architecture specific shapes. To that end, each architecture-specific SIMDMask is associated with a BitMask, where bit i is set to 1 if the corresponding lane in the full mask representation evaluates to a logic true, and 0 otherwise.

Masks can be converted to and from their corresponding BitMask as needed.

§Safety

One source of unsafety in SIMD is the accidental use of an intrinsic that is not supported by the current runtime CPU. This is made safe in wide by using the following strategy:

Each SIMDVector and SIMDMask type is uniquely associated with an Architecture.
Construction of a new SIMDVector or SIMDMask requires either an instance of its associated architecture, or a SIMDVector/SIMDMask of the same Architecture.
Architecture instances can only be obtained:
- From an instance of a SIMDVector/SIMDMask associated with that Architecture.
- From one of the safe constructors like arch::dispatch or new_checked which perform runtime checks necessary to ensure the compatibility.
- Through an unsafe constructor, on which case all bets are off.

So an Architecture is needed to bootstrap the use of SIMD, but from then on, the existence of SIMD types for a given Architecture serve as proof-of-safety.

§Special Architectures

Some Architectures are special and always available to use safely:

arch::Scalar: An architecture that uses emulation via loops to implement SIMD-like operations. This architecture is safe because no special hardware intrinsics are invoked.
arch::Current: The Architecture that is the closest fit to the current compilation target. This is not always arch::Scalar. For example, if compiling for x86-64-v3, then the arch::Current will be arch::x86_64::V3. This is safe because it only uses intrinsics that are already available for the compiler to use.

The current architecture can be obtained using with arch::current() or the constant crate::ARCH.

§Dev Docs

§Adding a new `TxN` vector type.

Implement the type for the backends in arch (you can usually follow and slightly modify the existing examples).
Implement for Emulated for the implementations that require macro instantiation.
Add the type to the Architecture trait.

At each step, be sure to include tests, which should be fairly straight forward.

§Adding a New Implementation to an Existing Trait

Basically do steps 2-4 of the above list.

§Adding a New Trait

If needed, provide a reference implementation in the reference module.
If it’s a relatively simple op, adding a new macro in test_utils/ops.rs that invokes the reference implementation may be all that’s needed.

More complicated operations may require their own test harness (see test_utils/dot_product.rs).

Tests should go through the utilities in test_utils::driver to ensure adequate coverage and low compile time.
Implement the trait for the needed types, implementing for Emulated, architecture-specific types, Architecture.

§Testing and Architectural Levels

By default, wide will only run tests supported by the current runtime hardware. This allows the tests to pass on a wide variety of machines during development.

However, this can mean that tests targeting architecture not supported by the runtime hardware will silently succeed.

To ensure all tests either run, or generate an error if the runtime hardware does not support a test, set the environment variable

WIDE_TEST_MIN_ARCH="all"

Various back-end specific values are supported. Note that this variable sets the minimum level of tests that are required to run. Tests for higher architecture levels will still be run if supported by the runtime hardware.

§x86_64

x86-64-v4: Target Wide’s arch::x86_64::V4 architecture.
x86-64-v3: Target Wide’s arch::x86_64::V3 architecture.
scalar: Target the scalar architecture.

Re-exports§

pub use arch::Architecture;

Modules§

arch: Traits and functions supporting multi-architecture applications.
lifetime: Tools to pass objects with lifetimes across the function pointer API.

Macros§

alias: Convenience aliases for aliasing SIMD types.

Structs§

BitMask: A lane-wise mask represented as a bit-mask.
Const: Move a const-generic into the type domain to work around issues with the use and compile-time computation involving const-generic parameters.
Emulated: An emulated SIMD vector.
LoHi: Representation of the low and high halves associated with an implementation of SplitJoin or crate::ZipUnzip.

Constants§

ARCH: The current architecture that is the closest fit for the current compilation target.

Traits§

AsSIMD: Convert Self to the SIMD type T. This is mainly useful when implementing fallback operations through crate::Emulated to restore the original SIMD type.
Constant: A trait to model compile-time constants.
FromInt: Perform a potentially lossy conversion from a raw integer.
SIMDAbs: Take the absolute value of each lane.
SIMDCast: Perform a numeric cast on the scalar type.
SIMDDotProduct: Optimized dot-product style accumulation.
SIMDFloat: A roll-up of traits required for SIMD floating point types.
SIMDMask: A logical mask for SIMD operations.
SIMDMinMax: Efficiently retrieve the pairwise minimum or maximum for the two arguments.
SIMDMulAdd: Efficiently perform the operation
SIMDPartialEq: A SIMD equivalent of std::cmp::PartialEq.
SIMDPartialOrd: A SIMD equivalent of std::cmp::PartialOrd.
SIMDReinterpret: Perform a bit-cast from one SIMD type to another.
SIMDSelect: A vectorized “if else”.
SIMDSigned
SIMDSumTree: Perform a pairwise reducing sum of all lanes in the vector and return the result as a scalar.
SIMDUnsigned: A roll-up of traits required for SIMD integer types.
SIMDVector: A trait representing minimal behavior for a SIMD-like vector.
SplitJoin: Split a type into or join from two halves.
SupportedLaneCount: Mapping from a number of lanes to the underlying type for a bitmask.
ZipUnzip: Element-wise zip and unzip of two half-width SIMD vectors.

Functions§

cast_f16_to_f32: Perform a Miri-safe conversion from f16 to f32.
cast_f32_to_f16: Perform a Miri-safe cast from f32 to f16.