Datenparallele Datentypen in C++26: Reduktion eines SIMD-Vektors

Nach der Vorstellung der datenparallelen Datentypen in C++26 und einem praktischen Beispiel behandle ich in diesem Artikel die Reduktion und Maskenreduktion für datenparallele Datentypen.

Funktionen zur Reduktion

Eine Reduktion reduziert den SIMD-Vektor auf ein einzelnes Element. Die Bibliothek stellt drei Funktionen für diesen Zweck zur Verfügung: reduce, hmin und hmax.

Das folgende Programm zeigt, wie diese Funktionen verwendet werden:

// reduction.cpp

#include 
#include 
#include 
#include 
#include 

namespace stdx = std::experimental;
 
void println(std::string_view name, auto const& a) {
  std::cout << name << ": ";
  for (std::size_t i{}; i != std::size(a); ++i)
    std::cout << a[i] << ' ';
  std::cout << '\n';
}

 
int main() {

  const stdx::fixed_size_simd a([](int i) { return i; });    
  println("a", a);

  auto sum = stdx::reduce(a);
  std::cout << "sum: " << sum << "\n\n";

  const stdx::fixed_size_simd b([](int i) { return i + 1; });    
  println("b", b);

  auto product = stdx::reduce(b, std::multiplies<>());
  std::cout << "product: " << product <<  "\n\n";

  auto maximum = stdx::hmax(b);
  std::cout << "maximum: " << maximum <<  "\n\n";

  auto minimum = stdx::hmin(b);
  std::cout << "minimum: " << minimum <<  "\n\n";
    
}

Zunächst kommt die Funktion reduce zum Einsatz. Standardmäßig wird der Operator + wie gewohnt angewendet. Diese Funktion kann jedoch auch mit einem beliebigen binären Operator parametrisiert werden. Der Ausdruck stdx::reduce(b, std::multiplies<>()) wendet das Funktionsobjekt std::multiplies aus dem Header functional an. Die Funktionen hmax und hmin bestimmen das Maximum und Minimum des SIMD-Vektors b.

Maskenreduktion auf true oder false

Bei der Reduktion einer Maske wird die SIMD-Maske entweder auf den Wert true oder auf den Wert false reduziert.

Hier begegnen wir einigen alten Bekannten aus C++: all_of, any_of, none_of und some_of.

• all_of: Gibt true zurück, wenn alle Werte in der SIMD-Maske true
• any_of: Gibt true zurück, wenn mindestens ein Wert in der SIMD-Maske true
• none_of: Gibt true zurück, wenn alle Werte in der SIMD-Maske false
• some_of: Gibt true zurück, wenn mindestens ein Wert in der SIMD-Maske true ist, aber nicht alle Werte darin true

cppreference.com enthält ein schönes Beispiel für diese Funktionen:

// reductionWithMask.cpp

#include 
#include 
 
namespace stq = std::experimental;
 
int main()
{
  using mask = stq::fixed_size_simd_mask;
 
  mask mask1{false}; // = {0, 0, 0, 0}
  assert
  (
    stq::none_of(mask1) == true &&
    stq::any_of(mask1) == false &&
    stq::some_of(mask1) == false &&
    stq::all_of(mask1) == false
  );
 
  mask mask2{true}; // = {1, 1, 1, 1}
  assert
  (
    stq::none_of(mask2) == false &&
    stq::any_of(mask2) == true &&
    stq::some_of(mask2) == false &&
    stq::all_of(mask2) == true
  );
 
  mask mask3{true};
  mask3[0] = mask3[1] = false; // mask3 = {0, 0, 1, 1}
  assert
  (
    stq::none_of(mask3) == false &&
    stq::any_of(mask3) == true &&
    stq::some_of(mask3) == true &&
    stq::all_of(mask3) == false
  );
}

popcount bestimmt, wie viele Werte in einer SIMD-Maske true sind. Ein Programm, das dies ausführt, lässt sich schnell schreiben:

// popcount.cpp

#include 
#include 
#include 

namespace stdx = std::experimental;
 
void println(std::string_view name, auto const& a) {
  std::cout << std::boolalpha << name << ": ";
  for (std::size_t i{}; i != std::size(a); ++i)
    std::cout << a[i] << ' ';
  std::cout << '\n';
}

 
int main() {

  const stdx::native_simd a = 1;
  println("a", a);

  const stdx::native_simd b([](int i) { return i - 2; });
  println("b", b);

  const auto c = a + b;
  println("c", c);

  const stdx::native_simd_mask x = c < 0; 
  println("x", x);

  auto cnt = popcount(x);
  std::cout << "cnt: " << cnt << '\n';

}

Darüber hinaus gibt es zwei weitere weitere Funktionen:

• find_first_set: Gibt den niedrigsten Index i zurück, bei dem die SIMD-Maske true ist.
• find_last_set: Gibt den größten Index i zurück, bei dem die SIMD-Maske true ist.

Das folgende Programm demonstriert die Verwendung der beiden Funktionen:

// find_first_set.cpp
#include  
#include 
#include 
namespace stdx = std::experimental;

void println(std::string_view name, auto const& a) { 
 std::cout << std::boolalpha << name << ": ";
for (std::size_t i{}; i != std::size(a); ++i)
 std::cout << a[i] << ' '; 
std::cout << '\n';
}

int main() {
  stdx::simd_mask x{0}; 
  println("x", x);
  x[1] = true;
  x[x.size() - 1] = true; 
  println("x", x);

  auto first = stdx::find_first_set(x);
  std::cout << "find_first_set(x): " << first << '\n';

  auto last = stdx::find_last_set(x);
  std::cout << "find_last_set(x): " << last<< '\n';
}

Wie geht‘s weiter?

In meinem nächsten Artikel werde ich mich auf die Algorithmen datenparalleler Datentypen konzentrieren.

(rme)