提问者:小点点

在 AVX2 中高效实现 log2(__m256d)


SVML的__m256d_mm256_log2_pd(__m256d)在英特尔以外的其他编译器上不可用,他们说它的性能在AMD处理器上受到阻碍。互联网上有一些在AVX log intrinsics(_mm256_log_ps)中提到的实现,在g-4.8中丢失了一些?和SSE和AVX的SIMD数学库,但是它们似乎比AVX2更SSE。还有Agner Fog的向量库,但是它是一个很大的库,只有向量log2,所以从它的实现中很难找出向量log2操作的基本部分。

有人能解释一下如何高效地对一个4 double数的向量实现< code>log2()运算吗?即类似于< code > _ _ m256d _ mm 256 _ log2 _ PD(_ _ m256d a)所做的,但可用于其他编译器,并且对于AMD和英特尔处理器都相当有效。

编辑:在我目前的特定情况下,数字是0到1之间的概率,对数用于熵计算:对P[i]*log(P[i])的所有i的总和的否定。P[i] 的浮点指数范围很大,因此数字可以接近 0。我不确定准确性,因此会考虑任何以 30 位尾数开头的解决方案,尤其是首选可调解决方案。

EDIT2:这是我到目前为止的实现,基于https://en.wikipedia.org/wiki/Logarithm#Power_series的“更高效系列”。如何改进它?(性能和精度都需要改进)

namespace {
  const __m256i gDoubleExpMask = _mm256_set1_epi64x(0x7ffULL << 52);
  const __m256i gDoubleExp0 = _mm256_set1_epi64x(1023ULL << 52);
  const __m256i gTo32bitExp = _mm256_set_epi32(0, 0, 0, 0, 6, 4, 2, 0);
  const __m128i gExpNormalizer = _mm_set1_epi32(1023);
  //TODO: some 128-bit variable or two 64-bit variables here?
  const __m256d gCommMul = _mm256_set1_pd(2.0 / 0.693147180559945309417); // 2.0/ln(2)
  const __m256d gCoeff1 = _mm256_set1_pd(1.0 / 3);
  const __m256d gCoeff2 = _mm256_set1_pd(1.0 / 5);
  const __m256d gCoeff3 = _mm256_set1_pd(1.0 / 7);
  const __m256d gCoeff4 = _mm256_set1_pd(1.0 / 9);
  const __m256d gVect1 = _mm256_set1_pd(1.0);
}

__m256d __vectorcall Log2(__m256d x) {
  const __m256i exps64 = _mm256_srli_epi64(_mm256_and_si256(gDoubleExpMask, _mm256_castpd_si256(x)), 52);
  const __m256i exps32_avx = _mm256_permutevar8x32_epi32(exps64, gTo32bitExp);
  const __m128i exps32_sse = _mm256_castsi256_si128(exps32_avx);
  const __m128i normExps = _mm_sub_epi32(exps32_sse, gExpNormalizer);
  const __m256d expsPD = _mm256_cvtepi32_pd(normExps);
  const __m256d y = _mm256_or_pd(_mm256_castsi256_pd(gDoubleExp0),
    _mm256_andnot_pd(_mm256_castsi256_pd(gDoubleExpMask), x));

  // Calculate t=(y-1)/(y+1) and t**2
  const __m256d tNum = _mm256_sub_pd(y, gVect1);
  const __m256d tDen = _mm256_add_pd(y, gVect1);
  const __m256d t = _mm256_div_pd(tNum, tDen);
  const __m256d t2 = _mm256_mul_pd(t, t); // t**2

  const __m256d t3 = _mm256_mul_pd(t, t2); // t**3
  const __m256d terms01 = _mm256_fmadd_pd(gCoeff1, t3, t);
  const __m256d t5 = _mm256_mul_pd(t3, t2); // t**5
  const __m256d terms012 = _mm256_fmadd_pd(gCoeff2, t5, terms01);
  const __m256d t7 = _mm256_mul_pd(t5, t2); // t**7
  const __m256d terms0123 = _mm256_fmadd_pd(gCoeff3, t7, terms012);
  const __m256d t9 = _mm256_mul_pd(t7, t2); // t**9
  const __m256d terms01234 = _mm256_fmadd_pd(gCoeff4, t9, terms0123);

  const __m256d log2_y = _mm256_mul_pd(terms01234, gCommMul);
  const __m256d log2_x = _mm256_add_pd(log2_y, expsPD);

  return log2_x;
}

到目前为止,我的实现给出了每秒405 268 490次运算,并且看起来精确到第8位。使用以下函数测量性能:

#include <chrono>
#include <cmath>
#include <cstdio>
#include <immintrin.h>

// ... Log2() implementation here

const int64_t cnLogs = 100 * 1000 * 1000;

void BenchmarkLog2Vect() {
  __m256d sums = _mm256_setzero_pd();
  auto start = std::chrono::high_resolution_clock::now();
  for (int64_t i = 1; i <= cnLogs; i += 4) {
    const __m256d x = _mm256_set_pd(double(i+3), double(i+2), double(i+1), double(i));
    const __m256d logs = Log2(x);
    sums = _mm256_add_pd(sums, logs);
  }
  auto elapsed = std::chrono::high_resolution_clock::now() - start;
  double nSec = 1e-6 * std::chrono::duration_cast<std::chrono::microseconds>(elapsed).count();
  double sum = sums.m256d_f64[0] + sums.m256d_f64[1] + sums.m256d_f64[2] + sums.m256d_f64[3];
  printf("Vect Log2: %.3lf Ops/sec calculated %.3lf\n", cnLogs / nSec, sum);
}

与C语言和汇编语言中对数的结果相比,当前的矢量实现比std::log2()快4倍,比std::log()快2.5倍。


共2个答案

匿名用户

通常的策略是基于身份log(a*b)=log(a)log(b),或者在这种情况下log2(2^指数*尾数))=log2(2*指数)log2(尾数)。或者简化,指数log2(尾数)。尾数的范围非常有限,从1.0到2.0,所以<code>log2(尾数)</code>的多项式只需要在非常有限的范围内拟合。(或等效地,尾数=0.5到1.0,并将指数偏差校正常数更改1)。

泰勒级数展开是系数的一个很好的起点,但是您通常希望在该特定范围内最小化最大绝对误差(或相对误差),并且泰勒级数系数可能在该范围内具有较低或较高的异常值,而不是具有与最大负误差几乎匹配的最大正误差。因此,您可以对系数进行所谓的极小极大拟合。

如果您的函数将< code>log2(1.0)精确地计算为< code>0.0很重要,您可以通过实际使用< code >尾数-1.0作为您的多项式,而不是常数系数来实现这一点。0.0 ^ n = 0.0。这也极大地改善了接近1.0的输入的相对误差,即使绝对误差仍然很小。

你需要它有多精确,以及在什么范围内输入?像往常一样,在准确性和速度之间有一个权衡,但幸运的是,通过增加一个多项式项(并重新拟合系数),或者通过放弃一些舍入误差避免,沿着这个尺度移动是很容易的。

Agner Fog的log_d()的VCL实现旨在实现非常高的精度,使用技巧通过避免可能导致添加小数和大数的东西来避免舍入误差。这在一定程度上模糊了基本设计。

有关更快更近似的浮点数 log(),请参阅 http://jrfonseca.blogspot.ca/2008/09/fast-sse2-pow-tables-or-polynomials.html 上的多项式实现。它省略了VCL使用的许多额外的精度增益技巧,因此更容易理解。它使用1.0到2.0范围内的尾数的多项式近似。

(这就是log()实现的真正技巧:您只需要一个在小范围内工作的多项式。)

它已经只执行log2而不是log,不像VCL的log-base-e被烘焙到常量中以及它如何使用它们。阅读它可能是理解log()的指数多项式(尾数)实现的一个很好的起点。

即使是它的最高精度版本也不是完全float精度,更不用说double了,但是可以用更多的项来拟合多项式。或者很明显,两个多项式的比例很好;这就是VCL对<code>double</code>的使用。

我在将JRF的SSE2函数移植到AVX2 FMA(尤其是AVX512与< code>_mm512_getexp_ps和< code>_mm512_getmant_ps)时获得了出色的结果,一旦我仔细调整它。(这是一个商业项目的一部分,所以我不认为我可以发布代码。)对于< code>float的快速近似实现正是我想要的。

在我的用例中,每个 jrf_fastlog() 都是独立的,因此 OOO 执行很好地隐藏了 FMA 延迟,甚至不值得使用 VCL 的 polynomial_5() 函数使用的更高 ILP 短延迟多项式评估方法(“Estrin's 方案”,它在 FMA 之前执行一些非 FMA 乘法,导致更多的总指令)。

Agner Fog的VCL现在是Apache许可的,所以任何项目都可以直接包含它。如果你想要高精度,你应该直接使用VCL。它只是标头,只是内联函数,所以它不会膨胀你的二进制文件。

VCL的< code>log float和double函数在< code>vectormath_exp.h中。该算法有两个主要部分:

>

  • 提取指数位并将该整数转换回浮点数(在调整IEEE FP使用的偏差之后)。

    提取一些指数位中的尾数和OR,以获得[0.5,1.0)范围内的值的向量。(或者(0.5,1.0],我忘了)。

    进一步调整这个 if(尾数)

    使用多项式近似来 log(x),该近似在 x=1.0 左右准确。(对于双精度,VCL 的 log_d() 使用两个 5 阶多项式的比率。 @harold说这通常有利于精度。一个与大量 FMA 混合的分区通常不会损害吞吐量,但它确实比 FMA 具有更高的延迟。使用 vrcpps 进行 Newton-Raphson 迭代通常比在现代硬件上使用 vdivps 慢。使用比率还可以通过并行评估两个低阶多项式而不是一个高阶多项式来创建更多的 ILP,并且与高阶多项式的一个长 dep 链相比,可以降低总体延迟(这也会在该长链上累积显着的舍入误差)。

    然后添加指数polynomial_approx_log(尾数)以获得最终的log()结果。VCL 分多个步骤执行此操作,以减少舍入误差。ln2_lo ln2_hi = ln(2)。它分为一个小常量和一个大常量,以减少舍入误差。

    // res is the polynomial(adjusted_mantissa) result
    // fe is the float exponent
    // x is the adjusted_mantissa.  x2 = x*x;
    res  = mul_add(fe, ln2_lo, res);             // res += fe * ln2_lo;
    res += nmul_add(x2, 0.5, x);                 // res += x  - 0.5 * x2;
    res  = mul_add(fe, ln2_hi, res);             // res += fe * ln2_hi;
    

    如果您的目标不是0.5或1 ulp精度(或此函数实际提供的任何内容;IDK),您可以放弃2步ln2的东西,只使用VM_LN2。)

    x-0.5*x2部分实际上是一个额外的多项式项,我想。这就是我所说的对数基数e被嵌入的意思:你需要一个关于这些项的系数,或者去掉那条线,重新拟合log2的多项式系数。你不能只是把所有的多项式系数乘以一个常数。

    之后,它检查下溢、溢出或反规范,如果向量中的任何元素需要特殊处理以产生适当的NaN或-Inf,而不是我们从多项式指数中获得的任何垃圾,则进行分支。如果已知您的值是有限的和正的,您可以注释掉这一部分并获得显著的加速(甚至在分支执行几个指令之前的检查)。

    >

  • http://gallium.inria.fr/blog/fast-vectorizable-math-approx/ 一些关于如何评估多项式近似中的相对误差和绝对误差的内容,并对系数进行最小极大修复,而不仅仅是使用泰勒级数展开。

    http://www.machinedlearnings.com/2011/06/fast-approximate-logarithm-exponential.html一个有趣的方法:它键入双关语将浮点数转换为uint32_t,并将该整数转换为浮点数。由于IEEE的二进制32浮点数将指数存储在比尾数更高的位上,因此生成的浮点数主要表示指数的值,缩放为1

    然后它使用一个带有几个系数的表达式来修复问题并获得 log() 近似值。它包括除以(常数尾数),以校正将浮点位模式转换为浮点数时尾数污染。我发现在 HSW 和 SKL 上使用 AVX2 的矢量化版本比使用 4 阶多项式的 JRF 快速日志更慢、更不准确。(特别是当将其用作快速 arcsinh 的一部分时,它也使用 vsqrtps 的除法单元。

  • 匿名用户

    最后,这是我的最佳结果,在Ryzen 1800X@3.6GHz上,它在单个线程中给出了每秒8亿对数(每个线程中2亿4个对数的向量),并且精确到尾数的最后几位。剧透:看看最后如何将性能提高到每秒8.7亿对数。

    特殊情况:负数、负无穷大和带有负号位的NaNs被视为非常接近0(导致一些垃圾大的负“对数”值)。正无穷大和带有正符号位的<code>NaN</code>s会导致1024左右的对数。如果您不喜欢如何处理特殊情况,可以选择添加代码来检查它们,并做更适合您的事情。这将使计算速度变慢。

    namespace {
      // The limit is 19 because we process only high 32 bits of doubles, and out of
      //   20 bits of mantissa there, 1 bit is used for rounding.
      constexpr uint8_t cnLog2TblBits = 10; // 1024 numbers times 8 bytes = 8KB.
      constexpr uint16_t cZeroExp = 1023;
      const __m256i gDoubleNotExp = _mm256_set1_epi64x(~(0x7ffULL << 52));
      const __m256d gDoubleExp0 = _mm256_castsi256_pd(_mm256_set1_epi64x(1023ULL << 52));
      const __m256i cAvxExp2YMask = _mm256_set1_epi64x(
        ~((1ULL << (52-cnLog2TblBits)) - 1) );
      const __m256d cPlusBit = _mm256_castsi256_pd(_mm256_set1_epi64x(
        1ULL << (52 - cnLog2TblBits - 1)));
      const __m256d gCommMul1 = _mm256_set1_pd(2.0 / 0.693147180559945309417); // 2.0/ln(2)
      const __m256i gHigh32Permute = _mm256_set_epi32(0, 0, 0, 0, 7, 5, 3, 1);
      const __m128i cSseMantTblMask = _mm_set1_epi32((1 << cnLog2TblBits) - 1);
      const __m128i gExpNorm0 = _mm_set1_epi32(1023);
      // plus |cnLog2TblBits|th highest mantissa bit
      double gPlusLog2Table[1 << cnLog2TblBits];
    } // anonymous namespace
    
    void InitLog2Table() {
      for(uint32_t i=0; i<(1<<cnLog2TblBits); i++) {
        const uint64_t iZp = (uint64_t(cZeroExp) << 52)
          | (uint64_t(i) << (52 - cnLog2TblBits)) | (1ULL << (52 - cnLog2TblBits - 1));
        const double zp = *reinterpret_cast<const double*>(&iZp);
        const double l2zp = std::log2(zp);
        gPlusLog2Table[i] = l2zp;
      }
    }
    
    __m256d __vectorcall Log2TblPlus(__m256d x) {
      const __m256d zClearExp = _mm256_and_pd(_mm256_castsi256_pd(gDoubleNotExp), x);
      const __m256d z = _mm256_or_pd(zClearExp, gDoubleExp0);
    
      const __m128i high32 = _mm256_castsi256_si128(_mm256_permutevar8x32_epi32(
        _mm256_castpd_si256(x), gHigh32Permute));
      // This requires that x is non-negative, because the sign bit is not cleared before
      //   computing the exponent.
      const __m128i exps32 = _mm_srai_epi32(high32, 20);
      const __m128i normExps = _mm_sub_epi32(exps32, gExpNorm0);
    
      // Compute y as approximately equal to log2(z)
      const __m128i indexes = _mm_and_si128(cSseMantTblMask,
        _mm_srai_epi32(high32, 20 - cnLog2TblBits));
      const __m256d y = _mm256_i32gather_pd(gPlusLog2Table, indexes,
        /*number of bytes per item*/ 8);
      // Compute A as z/exp2(y)
      const __m256d exp2_Y = _mm256_or_pd(
        cPlusBit, _mm256_and_pd(z, _mm256_castsi256_pd(cAvxExp2YMask)));
    
      // Calculate t=(A-1)/(A+1). Both numerator and denominator would be divided by exp2_Y
      const __m256d tNum = _mm256_sub_pd(z, exp2_Y);
      const __m256d tDen = _mm256_add_pd(z, exp2_Y);
    
      // Compute the first polynomial term from "More efficient series" of https://en.wikipedia.org/wiki/Logarithm#Power_series
      const __m256d t = _mm256_div_pd(tNum, tDen);
    
      const __m256d log2_z = _mm256_fmadd_pd(t, gCommMul1, y);
    
      // Leading integer part for the logarithm
      const __m256d leading = _mm256_cvtepi32_pd(normExps);
    
      const __m256d log2_x = _mm256_add_pd(log2_z, leading);
      return log2_x;
    }
    

    它使用了查找表方法和一级多项式的组合,主要在维基百科上描述(链接在代码注释中)。我可以在这里分配8KB的L1缓存(这是每个逻辑核可用的16KB L1缓存的一半),因为对数计算对我来说确实是瓶颈,并且没有更多需要L1缓存的东西。

    但是,如果您需要更多的L1缓存来满足其他需求,您可以通过将cnLog2TblBits减少到例如5来减少对数算法使用的缓存量,以降低对数计算的准确性为代价。

    或者为了保持较高的精度,您可以通过添加以下内容来增加多项式项的数量:

    namespace {
      // ...
      const __m256d gCoeff1 = _mm256_set1_pd(1.0 / 3);
      const __m256d gCoeff2 = _mm256_set1_pd(1.0 / 5);
      const __m256d gCoeff3 = _mm256_set1_pd(1.0 / 7);
      const __m256d gCoeff4 = _mm256_set1_pd(1.0 / 9);
      const __m256d gCoeff5 = _mm256_set1_pd(1.0 / 11);
    }
    

    然后更改行const__m256d t=_mm256_div_pd(tNum,tDen)之后的Log2TblPlus()的尾部

      const __m256d t2 = _mm256_mul_pd(t, t); // t**2
    
      const __m256d t3 = _mm256_mul_pd(t, t2); // t**3
      const __m256d terms01 = _mm256_fmadd_pd(gCoeff1, t3, t);
      const __m256d t5 = _mm256_mul_pd(t3, t2); // t**5
      const __m256d terms012 = _mm256_fmadd_pd(gCoeff2, t5, terms01);
      const __m256d t7 = _mm256_mul_pd(t5, t2); // t**7
      const __m256d terms0123 = _mm256_fmadd_pd(gCoeff3, t7, terms012);
      const __m256d t9 = _mm256_mul_pd(t7, t2); // t**9
      const __m256d terms01234 = _mm256_fmadd_pd(gCoeff4, t9, terms0123);
      const __m256d t11 = _mm256_mul_pd(t9, t2); // t**11
      const __m256d terms012345 = _mm256_fmadd_pd(gCoeff5, t11, terms01234);
    
      const __m256d log2_z = _mm256_fmadd_pd(terms012345, gCommMul1, y);
    

    然后注释//对数的前导整数部分,其余部分不变。

    通常你不需要那么多的术语,即使是几比特的表,我只是提供了系数和计算供参考。如果< code>cnLog2TblBits==5,除了< code>terms012之外,您可能不需要任何东西。但是我没有做过这样的测量,你需要实验一下什么适合你的需求。

    显然,计算的多项式次数越少,计算速度就越快。

    编辑:这个问题在什么情况下AVX2收集指令会比单独加载数据更快?表明如果满足以下条件,您可能会获得性能提升

    const __m256d y = _mm256_i32gather_pd(gPlusLog2Table, indexes,
      /*number of bytes per item*/ 8);
    

    替换为

    const __m256d y = _mm256_set_pd(gPlusLog2Table[indexes.m128i_u32[3]],
      gPlusLog2Table[indexes.m128i_u32[2]],
      gPlusLog2Table[indexes.m128i_u32[1]],
      gPlusLog2Table[indexes.m128i_u32[0]]);
    

    对于我的实现,它节省了大约1.5个周期,将总周期计数减少到计算4个对数,从18减少到16.5,因此性能上升到每秒8.7亿对数。我保留当前的实现,因为它更惯用,一旦CPU开始正确执行收集操作(像GPU那样合并),它就会更快。

    EDIT2:在锐龙CPU(但不是在英特尔上)上,您可以通过更换来获得更多的加速(大约0.5个周期)

    const __m128i high32 = _mm256_castsi256_si128(_mm256_permutevar8x32_epi32(
      _mm256_castpd_si256(x), gHigh32Permute));
    

      const __m128 hiLane = _mm_castpd_ps(_mm256_extractf128_pd(x, 1));
      const __m128 loLane = _mm_castpd_ps(_mm256_castpd256_pd128(x));
      const __m128i high32 = _mm_castps_si128(_mm_shuffle_ps(loLane, hiLane,
        _MM_SHUFFLE(3, 1, 3, 1)));