高效且性能可移植的向量软件

Highway 是一个提供可移植 SIMD/向量内联函数的 C++ 库。

文档

之前采用 Apache 2 许可，现在双重许可为 Apache 2 / BSD-3。

为什么

我们热衷于高性能软件。我们看到 CPU（服务器、移动设备、桌面）中存在巨大的未开发潜力。Highway 适用于那些希望可靠且经济地突破软件可能性边界的工程师。

如何

CPU 提供 SIMD/向量指令，可以对多个数据项应用相同的操作。这可以将能耗降低约 5 倍，因为执行的指令更少。我们通常还能看到 5-10 倍的速度提升。

Highway 使 SIMD/向量编程变得实用可行，遵循以下指导原则：

符合预期：Highway 是一个 C++ 库，具有精心选择的函数，无需大量编译器转换即可很好地映射到 CPU 指令。与自动向量化相比，生成的代码对代码更改/编译器更新更具可预测性和鲁棒性。

适用于广泛使用的平台：Highway 支持五种架构；相同的应用程序代码可以针对各种指令集，包括那些具有"可扩展"向量（编译时大小未知）的指令集。Highway 仅需要 C++11，并支持四个编译器系列。如果您想在其他平台上使用 Highway，请提出问题。

部署灵活：使用 Highway 的应用程序可以在异构云或客户端设备上运行，在运行时选择最佳可用的指令集。或者，开发人员可以选择针对单一指令集，无任何运行时开销。在这两种情况下，应用程序代码都是相同的，只需将 HWY_STATIC_DISPATCH 替换为 HWY_DYNAMIC_DISPATCH 并添加一行代码。

适用于各种领域：Highway 提供了广泛的操作集，用于图像处理（浮点）、压缩、视频分析、线性代数、密码学、排序和随机生成。我们认识到新的用例可能需要额外的操作，并乐意在合理的情况下添加它们（例如，在某些架构上不会出现性能断崖）。如果您想讨论，请提出问题。

奖励数据并行设计：Highway 提供了 Gather、MaskedLoad 和 FixedTag 等工具，以实现对传统数据结构的加速。然而，最大的收益是通过为可扩展向量设计算法和数据结构来实现的。有用的技术包括批处理、数组结构布局和对齐/填充分配。

我们推荐以下资源作为入门：

• C++ 开发人员的 SIMD
• 现代硬件算法
• C++ 软件优化
• 在三个用例中使用 SIMD 内联函数提高性能

示例

使用 Compiler Explorer 的在线演示：

• 使用动态分派的多个目标 （更复杂，但灵活且使用最佳可用的 SIMD）
• 使用 -m 标志的单一目标 （更简单，但需要/仅使用编译器标志启用的指令集）

我们观察到 Highway 在以下开源项目中被引用，这些项目通过 sourcegraph.com 找到。大多数是 GitHub 仓库。如果您想添加您的项目或直接链接到它，请随时提出问题或通过以下电子邮件与我们联系。

• 音频：Zimtohrli 感知度量
• 浏览器：Chromium（+Vivaldi）、Firefox（+floorp / foxhound / librewolf / Waterfox）
• 计算生物学：RNA 分析
• 计算机图形学：稀疏体素渲染器
• 密码学：google/distributed_point_functions、google/shell-encryption
• 数据结构：bkille/BitLib
• 图像编解码器：eustas/2im、 Grok JPEG 2000、 JPEG XL、 JPEGenc、 Jpegli、OpenHTJ2K
• 图像处理：cloudinary/ssimulacra2、m-ab-s/media-autobuild_suite、 libvips
• 图像查看器：AlienCowEatCake/ImageViewer、diffractor/diffractor、 mirillis/jpegxl-wic、 Lux 全景/图像查看器
• 信息检索： iresearch 数据库索引、 michaeljclark/zvec、 nebula 交互式分析 / OLAP、 ScaNN 可扩展最近邻
• 机器学习：gemma.cpp、 Tensorflow、Numpy、zpye/SimpleInfer
• 机器人学： MIT 基于模型的设计和验证

其他

• C++ SIMD 库评估： "Highway 在多个 SIMD 扩展中表现出色 [..] 。因此，Highway 目前可能是许多软件项目最合适的 SIMD 库。"
• zimt：用于处理 n 维数组的多线程 SIMD 代码的 C++11 模板库
• 向量化快速排序（论文）

如果您想获取 Highway，除了从这个 GitHub 仓库克隆或将其用作 Git 子模块外，您还可以在以下包管理器或仓库中找到它：

• alpinelinux
• conan-io
• conda-forge
• DragonFlyBSD
• fd00/yacp
• freebsd
• getsolus/packages
• ghostbsd
• microsoft/vcpkg
• MidnightBSD
• MSYS2
• NetBSD
• openSUSE
• opnsense
• Xilinx/Vitis_Libraries
• xmake-io/xmake-repo

另请参阅 https://repology.org/project/highway-simd-library/versions 的列表。

当前状态

目标

Highway 支持 24 个目标，按平台字母顺序列出：

• 任意：EMU128、SCALAR；
• Armv7+：NEON_WITHOUT_AES、NEON、NEON_BF16、SVE、SVE2、SVE_256、 SVE2_128；
• IBM Z：Z14、Z15；
• POWER：PPC8（v2.07）、PPC9（v3.0）、PPC10（v3.1B，由于编译器错误尚不支持， 参见 #1207；还需要 QEMU 7.2）；
• RISC-V：RVV（1.0）；
• WebAssembly：WASM、WASM_EMU256（wasm128 的 2 倍展开版本， 如果定义了 HWY_WANT_WASM2 则启用。在可能被未来版本的 WASM 取代之前， 这将继续得到支持。）；
• x86：
  • SSE2
  • SSSE3（~Intel Core）
  • SSE4（~Nehalem，还包括 AES + CLMUL）
  • AVX2（~Haswell，还包括 BMI2 + F16 + FMA）
  • AVX3（~Skylake，AVX-512F/BW/CD/DQ/VL）
  • AVX3_DL（~Icelake，包括 BitAlg + CLMUL + GFNI + VAES + VBMI + VBMI2 + VNNI + VPOPCNT；除非为静态分派编译，否则需要通过定义 HWY_WANT_AVX3_DL 选择加入）
  • AVX3_ZEN4（类似 AVX3_DL，但为 AMD Zen4 优化；如果为静态分派编译， 需要通过定义 HWY_WANT_AVX3_ZEN4 选择加入，但对于运行时分派默认启用）
  • AVX3_SPR（~Sapphire Rapids，包括 AVX-512FP16）

我们的政策是，除非另有说明，只要可以使用当前支持的 Clang 或 GCC（交叉）编译，并使用 QEMU 进行测试，就会继续支持目标。如果目标可以使用 LLVM trunk 编译，并使用我们版本的 QEMU 进行测试而无需额外标志，那么它就有资格纳入我们的持续测试基础设施。否则，目标将在发布前使用选定版本/配置的 Clang 和 GCC 进行手动测试。

SVE 最初使用 farm_sve 进行测试（参见致谢）。

版本控制

Highway 发布旨在遵循 semver.org 系统（主版本号.次版本号.修订号），在向后兼容的添加后递增次版本号，在向后兼容的修复后递增修订号。我们建议使用发布版（而不是 Git 提示），因为它们经过更广泛的测试，详见下文。

当前版本 1.0 表示更加注重向后兼容性。使用文档化功能的应用程序将与具有相同主版本号的未来更新保持兼容。

测试

持续集成测试使用最新版本的 Clang（在原生 x86 上运行，或在 RISC-V 和 Arm 上使用 QEMU）和 MSVC 2019（v19.28，在原生 x86 上运行）进行构建。

在发布之前，我们还会在 x86 上使用 Clang 和 GCC 进行测试，并通过 GCC 交叉编译在 Armv7/8 上进行测试。有关详细信息，请参阅测试流程。

相关模块

contrib 目录包含SIMD相关的实用工具:一个带对齐行的图像类、一个数学库(已实现16个函数,主要是三角函数),以及用于计算点积和排序的函数。

其他库

如果您只需要x86支持,也可以使用Agner Fog的 VCL向量类库。它包含许多函数,包括一个完整的数学库。

如果您有使用x86/NEON内部函数的现有代码,您可能会对 SIMDe 感兴趣,它使用其他平台的内部函数或自动向量化来模拟这些内部函数。

安装

本项目使用CMake来生成和构建。在基于Debian的系统中,您可以通过以下方式安装:

sudo apt install cmake

Highway的单元测试使用 googletest。 默认情况下,Highway的CMake会在配置时下载这个依赖项。 您可以通过将HWY_SYSTEM_GTEST CMake变量设置为ON并单独安装gtest来避免这种情况:

sudo apt install libgtest-dev

或者,您可以定义HWY_TEST_STANDALONE=1并删除每个BUILD文件中所有出现的gtest_main,然后测试就可以避免对GUnit的依赖。

运行交叉编译的测试需要操作系统的支持,在Debian上由qemu-user-binfmt包提供。

要将Highway构建为共享或静态库(取决于BUILD_SHARED_LIBS),可以使用标准的CMake工作流:

mkdir -p build && cd build
cmake ..
make -j && make test

或者您可以运行run_tests.sh(Windows上为run_tests.bat)。

Bazel也支持构建,但使用和测试不如CMake广泛。

在为Armv7构建时,当前编译器的限制要求您在CMake命令行中添加-DHWY_CMAKE_ARM7:BOOL=ON;参见 #834 和 #1032。据了解,正在进行消除这一限制的工作。

不官方支持在32位x86上构建,默认情况下AVX2/3在那里被禁用。注意johnplatts已经成功地在32位x86上构建并运行了Highway测试,包括AVX2/3,在GCC 7/8和Clang 8/11/12上。在Ubuntu 22.04上,Clang 11和12(但不是更高版本)需要额外的编译器标志-m32 -isystem /usr/i686-linux-gnu/include。Clang 10及更早版本除上述标志外还需要-isystem /usr/i686-linux-gnu/include/c++/12/i686-linux-gnu。参见 #1279。

使用vcpkg构建highway

highway现在可以在vcpkg中使用

vcpkg install highway

vcpkg中的highway端口由Microsoft团队成员和社区贡献者保持最新。如果版本过时,请在vcpkg仓库上创建一个问题或拉取请求。

快速开始

您可以使用examples/中的benchmark作为起点。

快速参考页面简要列出了所有操作及其参数,而指令矩阵指示了每个操作的指令数量。

FAQ回答了关于可移植性、API设计以及在哪里可以找到更多信息的问题。

我们建议尽可能使用完整的SIMD向量以获得最大的性能可移植性。要获得它们,请将ScalableTag<float>(或等效的HWY_FULL(float))标签传递给Zero/Set/Load等函数。对于需要对车道数量设置上限的用例,有两种替代方案:

• 对于最多N个车道,指定CappedTag<T, N>或等效的HWY_CAPPED(T, N)。实际车道数将是N向下舍入到最接近的2的幂,例如如果N是5则为4,如果N是8则为8。这对于窄矩阵等数据结构很有用。仍然需要一个循环,因为向量实际上可能少于N个车道。

• 对于恰好2的幂N个车道,指定FixedTag<T, N>。支持的最大N取决于目标,但保证至少为16/sizeof(T)。

由于ADL限制,调用Highway操作的用户代码必须:

• 位于namespace hwy { namespace HWY_NAMESPACE {内;或
• 为每个操作添加前缀,如namespace hn = hwy::HWY_NAMESPACE; hn::Add();或
• 为每个使用的操作添加using声明:using hwy::HWY_NAMESPACE::Add;。

此外,调用Highway操作(如Load)的每个函数必须以HWY_ATTR为前缀,或者位于HWY_BEFORE_NAMESPACE()和HWY_AFTER_NAMESPACE()之间。Lambda函数目前需要在开头大括号前加上HWY_ATTR。

不要对SIMD向量使用命名空间作用域或static初始化器,因为在使用运行时调度时,如果编译器选择了为不受当前CPU支持的目标编译的初始化器,这可能导致SIGILL。相反,通过Set初始化的常量通常应该是局部(const)变量。

使用Highway的代码的入口点根据它们使用静态还是动态调度略有不同。在这两种情况下,我们建议顶层函数接收一个或多个指向数组的指针,而不是特定目标的向量类型。

• 对于静态调度,HWY_TARGET将是HWY_BASELINE_TARGETS中可用的最佳目标,即编译器允许使用的目标(参见快速参考)。HWY_NAMESPACE内的函数可以在定义它们的同一模块中使用HWY_STATIC_DISPATCH(func)(args)调用。您可以通过将函数包装在常规函数中并在头文件中声明常规函数来从其他模块调用该函数。

• 对于动态调度,通过HWY_EXPORT宏生成一个函数指针表,HWY_DYNAMIC_DISPATCH(func)(args)使用它来调用当前CPU支持的目标的最佳函数指针。如果定义了HWY_TARGET_INCLUDE并包含了foreach_target.h,则会自动为HWY_TARGETS中的每个目标编译一个模块(参见快速参考)。请注意,HWY_DYNAMIC_DISPATCH的第一次调用,或对第一次调用HWY_DYNAMIC_POINTER返回的指针的每次调用,都涉及一些CPU检测开销。您可以通过在任何HWY_DYNAMIC_*调用之前调用以下内容来防止这种情况:hwy::GetChosenTarget().Update(hwy::SupportedTargets());。

使用动态调度时,foreach_target.h从翻译单元(.cc文件)包含,而不是头文件。包含在几个翻译单元之间共享的向量代码的头文件需要一个特殊的包含保护,例如从examples/skeleton-inl.h摘取的以下内容:

#if defined(HIGHWAY_HWY_EXAMPLES_SKELETON_INL_H_) == defined(HWY_TARGET_TOGGLE)
#ifdef HIGHWAY_HWY_EXAMPLES_SKELETON_INL_H_
#undef HIGHWAY_HWY_EXAMPLES_SKELETON_INL_H_
#else
#define HIGHWAY_HWY_EXAMPLES_SKELETON_INL_H_
#endif

#include "hwy/highway.h"
// 您的向量代码
#endif

按照惯例,我们将这些头文件命名为-inl.h,因为它们的内容(通常是函数模板)通常是内联的。

编译器标志

应用程序应该在启用优化的情况下编译。没有内联,SIMD代码可能会慢10到100倍。对于clang和GCC,-O2通常就足够了。

对于MSVC,我们建议使用/Gv编译,以允许非内联函数在寄存器中传递向量参数。如果打算将AVX2目标与半宽向量一起使用(例如用于PromoteTo),那么使用/arch:AVX2编译也很重要。这似乎是在MSVC上可靠生成VEX编码的SSE指令的唯一方法。有时MSVC会生成VEX编码的SSE指令,如果它们与AVX混合,但并非总是如此,参见DevCom-10618264。否则,混合VEX编码的AVX2指令和非VEX SSE可能会导致严重的性能下降。不幸的是,使用/arch:AVX2选项,生成的二进制文件将需要AVX2。请注意,clang和GCC不需要这样的标志,因为它们支持特定目标的属性,我们使用这些属性来确保为AVX2目标正确生成VEX代码。

条带化循环

在向量化循环时,一个重要的问题是如何处理不能被向量大小N = Lanes(d)整除的迭代次数('行程计数',表示为count)。例如,可能需要避免写入数组末尾之外。

在本节中,让T表示元素类型,d = ScalableTag<T>。假设循环体作为函数template<bool partial, class D> void LoopBody(D d, size_t index, size_t max_n)给出。

"条带化"是一种通过将循环转换为外循环和内循环来向量化循环的技术,使得内循环中的迭代次数与向量宽度匹配。然后,内循环被替换为向量操作。

Highway提供了几种循环向量化策略:

• 确保所有输入/输出都经过填充。然后(外)循环简单地为

for (size_t i = 0; i < count; i += N) LoopBody<false>(d, i, 0);

在这里,模板参数和第二个函数参数是不需要的。 这是首选方案，除非 N 达到上千且向量操作存在长延迟的流水线处理。这种情况在90年代的超级计算机中存在，但现今ALU成本低廉，大多数实现将向量分为1、2或4部分，因此即使不需要所有通道，处理整个向量的成本也很小。事实上，这避免了在较旧目标上谓词或部分加载/存储的（可能较大的）成本，且不会重复代码。

• 处理整个向量，并在最后一个向量中包含先前处理过的元素：

  for (size_t i = 0; i < count; i += N) LoopBody<false>(d, HWY_MIN(i, count - N), 0);
  

  如果 count >= N 且 LoopBody 是幂等的，这是第二个首选方案。某些元素可能会被处理两次，但单一代码路径和完全向量化通常是值得的。即使 count < N，将输入/输出填充到 N 通常也是有意义的。

• 使用 hwy/contrib/algo/transform-inl.h 中的 Transform* 函数。这处理了循环和余数处理，你只需定义一个泛型 lambda 函数（C++14）或函子，它接收来自输入/输出数组的当前向量，以及可选的来自最多两个额外输入数组的向量，并返回要写入输入/输出数组的值。

  这里是一个实现 BLAS 函数 SAXPY（alpha * x + y）的示例：

  Transform1(d, x, n, y, [](auto d, const auto v, const auto v1) HWY_ATTR {
    return MulAdd(Set(d, alpha), v, v1);
  });
  

• 如上处理整个向量，然后进行标量循环：

  size_t i = 0;
  for (; i + N <= count; i += N) LoopBody<false>(d, i, 0);
  for (; i < count; ++i) LoopBody<false>(CappedTag<T, 1>(), i, 0);
  

  模板参数和第二个函数参数同样不需要。

  这避免了代码重复，对于大的 count 值是合理的。 如果 count 很小，第二个循环可能比下一个选项慢。

• 如上处理整个向量，然后对修改后的 LoopBody 进行一次带掩码的调用：

  size_t i = 0;
  for (; i + N <= count; i += N) {
    LoopBody<false>(d, i, 0);
  }
  if (i < count) {
    LoopBody<true>(d, i, count - i);
  }
  

  现在模板参数和第三个函数参数可以在 LoopBody 内部使用，以非原子方式'混合'v 的前 num_remaining 个通道与后续位置内存中的先前内容： BlendedStore(v, FirstN(d, num_remaining), d, pointer);。类似地， MaskedLoad(FirstN(d, num_remaining), d, pointer) 加载前 num_remaining 个元素，并在其他通道返回零。

  当无法确保向量已填充时，这是一个很好的默认选择，但仅在 #if !HWY_MEM_OPS_MIGHT_FAULT 时安全！ 与标量循环相比，只需要一次最终迭代。 两个循环体增加的代码大小预计是值得的，因为它避免了除最后一次迭代外所有迭代中的掩码成本。

其他资源

• Highway 介绍（幻灯片）
• 不同架构上每操作指令概览
• 设计理念和比较
• 实现细节

致谢

我们使用了 Berenger Bramas 的 farm-sve；它在 x86 开发机上检查 SVE 移植时证明很有用。

这不是 Google 官方支持的产品。 联系方式：janwas@google.com