Kernels for boolean matrices

[daphne-eu]

In GitLab by @pdamme on May 10, 2021, 22:29

Motivation

Matrices of boolean values are promising because they

1. allow a compact representation using only a single bit per value, thereby saving space at any level of the memory hierarchy
2. allow a highly efficient processing using full-word scalar (or even SIMD) instructions to process multiple values at once

At the same time, boolean matrices do occur in typical ML algorithms and DB processing models, e.g., as the result of elementwise comparisons, which must also be further processed.

While our current implementations of data structures and kernels are mostly generic w.r.t. the value type by means of a template parameter, they can hardly treat bool efficiently, because they implicitly assume byte-aligned types. Thus, support for boolean matrices must be implemented explicitly.

Supporting boolean matrices has two aspects:

1. data structures (issue Data structures for boolean matrices #39)
2. algorithms/kernels (this issue).

Kernels for boolean matrices

Once our matrix data structures have been specialized for the value type bool, we can start adapting the kernels for those, ideally again by implementing specializations of the kernels for bool as the value type.

Initially, it would suffice to do this only for a couple of relevant kernels, e.g.:

• elementwise comparisons (returning a boolean matrix)
• all/row/column aggregation (taking a boolean matrix as input)
• (random) matrix generation (to be able to play around with such boolean matrices)
• potentially more depending on the algorithms we want to use them for

These kernels should not process each boolean value individually, but rather process several of them at once using full-word scalar or SIMD instructions. For instance, in a dense representation, the sum over 64 boolean values could be calculated by a single popcount instruction. There is generally much room for ideas here.

[daphne-eu]

In GitLab by @pdamme on Jan 27, 2022, 19:34

We might handle this feature via the mechanisms for value type extensibility we plan to develop anyway.