SIMD優化應用
SIMD 介紹
費林分類法(Flynn’s Taxonomy)
? 單一指令流單一數據流（SISD）
? 單一指令流多數據流（SIMD）
? 多指令流單一數據流（MISD）
? 多指令流多數據流（MIMD）

SIMD(Single Instruction Multiple Data) 是一種處理器指令類型，即單個指令可以同時處理多個數據。這里的多個，一般指的就是就是多個 CPU 寄存器。
例如，以下為加法的標量(Scalar)與SIMD(Vector)兩種執行方式:

現代大多數處理器指令為 SISD / SIMD, 而多核計算方式被認為是 MIMD。
處理器如何實現 SIMD

有一段經典SIMD應用代碼 ClickHouse: Columns/ColumnsCommon.cpp, filterArraysImplGeneric()，這段代碼的注釋是這樣形容的:
/** A slightly more optimized version.

• Based on the assumption that often pieces of consecutive values

• completely pass or do not pass the filter.

• Therefore, we will optimistically check the parts of SIMD_BYTES values.
  */
  在這段代碼中，filterArraysImplGeneric 函數需要完成下面一段 SQL Where 子句的部分邏輯:
  ? 有一個數組 data, 里面存放了數據
  ? 有一個 int8 類型數組 filter，size等于 data，存放了一些布爾值，用于標識 data 里面的數據是否應該被篩選出來
  ? 生成一個新的數組 res，根據 filter 數組，對 data 數組進行篩選
  這個邏輯正常實現很簡單，偽碼如:
  let res = []
  for (let i = 0; i < data.size(); i ++) {
  if (filter[i] != 0) {
  res.append(data[i])
  }
  }
  有什么優化點呢 ？如果考慮到 data 的長度很長的話 (在 ClickHouse 的應用場景，這個 Array 的長度，在一次查詢中，所有執行累加在一起，通常在億級以上)
  ClickHouse 的實現思路如下:
  ? 上述代碼耗時因素在于循環次數非常多，等于 data 數組的長度
  ? 如果可以降低循環次數，同時保證單次循環耗時變化不大，總體執行效率更高
  ? 要滿足上述條件，需要在同一個指令周期做更多運算，SIMD 指令可以滿足訴求
  ? 考慮到目前 SIMD 指令最大支持 512 比特數據，filter 本身是 8 比特，單循環處理數據量可為 512 / 8 = 64 個 (考慮到當前大多數計算機處理器為 64 位)
  ? 每次取 64 個 filter 數組項，組合為一個 64 位無符號整型值 mask，這樣每個 filter 數組項占用一個比特位
  ? 考慮兩種特殊情況: 如果 mask 64 位比特均為 1，那么這個循環中，64 個 data 項都應該拷貝到 res，反之如果 mask 64 位比特均為 0，可以直接跳過循環。這兩種特殊情況在業務場景中都經常發生
  ? 如果沒有命中特殊情況，需要循環 64 次嘛 ？有沒有進一步優化方法 ？
  ? 有多少項需要復制到新的數組，取決于 mask 中比特位為 1 的個數
  ? __builtin_ctzll 編譯器內置函數，可以獲取最低比特位為 1 的 index，以此可知道哪項數據應該復制
  ? 最低置1比特位的項已經復制后，需要將其比特位置 0，這里有兩個都比較高效的方法: _blsr_u64 指令 及 mask = mask & (mask-1)，_blsr_u64 可以查指令集，但是 mask & (mask-1) 具體怎么才可以想出來，需要深厚的編程功底了。
  ? 循環設置最低置1比特位，直到 mask 中所有比特位均為 0
  ? 完成
  分析一下每個 64項 Loop 性能可以提升多少 ？
  這里為了方便，每個指令的指令周期相等，現實情況中并非如此
  下面的分析，更多是定性而非定量
  ? 如果按照最基礎實現，需要經歷 64 個循環，每個循環需要一次條件判斷，以及可能的一次數據讀取與寫入，大約 3 個指令周期，大約 194 指令周期
  ? 下面考慮 ClickHouse 的 SIMD 優化實現
  ? Bytes64MaskToBits64Mask 需要 3 個指令周期
  ? 最佳情況, filter 不命中: 無額外指令周期，性能顯著高于標量版本
  ? 次佳情況, filter 全部命中: 需要大約 10 個指令周期復制數據，性能顯著高于標量版本
  ? 其余情況，指令周期與 mask 中 1 比特位個數相關
  ? 在最差情況下，SIMD 優化版本耗時可能略高于普通實現
  代碼如下:
  static constexpr size_t SIMD_BYTES = 64;

  while (filt_pos < filt_end_aligned)
  {
  // 將 64 字節的 filter 數組，轉變為 64 比特的無符號整數
  uint64_t mask = Bytes64MaskToBits64Mask(filt_pos);

    // 是否為邊界情況: filter 全部命中if (0xffffffffffffffff == mask){// copy all ...}else{while (mask){// 找出最低位置1比特的 indexsize_t index = __builtin_ctzll(mask);copy_array(offsets_pos + index);#ifdef __BMI__// _blsr_u64 將最低置一比特位置 0mask = _blsr_u64(mask);#else// 一種不依賴原生指令支持的方案mask = mask & (mask-1);#endif}}filt_pos += SIMD_BYTES;offsets_pos += SIMD_BYTES;
  

  }
  其中，Bytes64MaskToBits64Mask 的實現同樣很講究:
  /// Transform 64-byte mask to 64-bit mask
  inline UInt64 Bytes64MaskToBits64Mask(const UInt8 * bytes64)
  {
  #if defined(AVX512F) && defined(AVX512BW)
  static const __m512i zero64 = _mm512_setzero_epi32();
  UInt64 res = _mm512_cmp_epi8_mask(_mm512_loadu_si512(reinterpret_cast<const __m512i *>(bytes64)), zero64, _MM_CMPINT_EQ);
  #elif defined(AVX) && defined(AVX2)
  static const __m256i zero32 = _mm256_setzero_si256();
  UInt64 res =
  (static_cast(_mm256_movemask_epi8(_mm256_cmpeq_epi8(
  _mm256_loadu_si256(reinterpret_cast<const __m256i *>(bytes64)), zero32))) & 0xffffffff)
  | (static_cast(_mm256_movemask_epi8(_mm256_cmpeq_epi8(
  _mm256_loadu_si256(reinterpret_cast<const __m256i *>(bytes64+32)), zero32))) << 32);
  #elif defined(SSE2) && defined(POPCNT)
  static const __m128i zero16 = _mm_setzero_si128();
  UInt64 res =
  (static_cast(_mm_movemask_epi8(_mm_cmpeq_epi8(
  _mm_loadu_si128(reinterpret_cast<const __m128i *>(bytes64)), zero16))) & 0xffff)
  | ((static_cast(_mm_movemask_epi8(_mm_cmpeq_epi8(
  _mm_loadu_si128(reinterpret_cast<const __m128i *>(bytes64 + 16)), zero16))) << 16) & 0xffff0000)
  | ((static_cast(_mm_movemask_epi8(_mm_cmpeq_epi8(
  _mm_loadu_si128(reinterpret_cast<const __m128i *>(bytes64 + 32)), zero16))) << 32) & 0xffff00000000)
  | ((static_cast(_mm_movemask_epi8(_mm_cmpeq_epi8(
  _mm_loadu_si128(reinterpret_cast<const __m128i *>(bytes64 + 48)), zero16))) << 48) & 0xffff000000000000);
  #else
  UInt64 res = 0;
  const UInt8 * pos = bytes64;
  const UInt8 * end = pos + 64;
  for (; pos < end; ++pos)
  res |= ((*pos == 0)<<(pos-bytes64));
  #endif
  return ~res;
  }
  按照優先級盡可能利用位數多的指令集進行計算，同時在所有指令集都不可用及未64字節對齊(align)的部分進行了保底處理。利用了以下指令集:
  ? AVX512F / AVX512BW
  ? AVX/AVX2
  ? SSE2

參考鏈接：
https://zhuanlan.zhihu.com/p/449154820

總結

以上是生活随笔為你收集整理的SIMD优化应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。