VVenc 命令行参数解析方式

关于C++命令行参数解析的基础分析可以参考文章C++ 中使用 argc 和 argv 的命令行参数

VVenc中的命令行参数解析的过程相对于上面这篇文章有种羊了个羊第一关到第二关的感觉,这篇文章我们逐一的去分析VVenc命令行参数的解析方式。

VVenc命令行参数相关的结构体和类

首先需要介绍VVenc中几个相关的结构体和类。C++中的struct与class的区别:

  • Class中默认的成员访问权限是private的,而Struct中则是public的;
  • 从Class继承默认是private继承,而从Struct继承默认是public继承。
  • 除此之外C++的结构体和类没有太大的区别。

struct OptionBase

/** OptionBase: Virtual base class for storing information relating to a
 * specific option This base class describes common elements.  Type specific
 * information should be stored in a derived class. */
struct OptionBase
{
  OptionBase(const std::string& name, const std::string& desc, const bool bool_switch )
  : opt_string(name), opt_desc(desc), is_bool_switch(bool_switch)
  {};

  virtual ~OptionBase() {}

  /* parse argument arg, to obtain a value for the option */
  virtual void parse(const std::string& arg, ErrorReporter&) = 0;
  /* set the argument to the default value */
  virtual void setDefault() = 0;
  virtual const std::string getDefault( ) { return std::string(); }
  virtual const std::string getValue( ) { return std::string(); }

  std::string opt_string;
  std::string opt_desc;
  bool        is_bool_switch = false;
};

OptionBase:用于存储与特定参数相关的信息的虚拟基类。这个基类描述了常见元素opt_string和opt_desc。类型特定信息应存储在派生类中。

struct Options


struct Names{
  Names() : opt(0) {};
  ~Names()
  {
    if (opt)
    {
      delete opt;
    }
  }
  std::list<std::string> opt_long;
  std::list<std::string> opt_short;
  OptionBase* opt;
};

typedef std::list<Names*> NamesPtrList;
NamesPtrList opt_list;

typedef std::map<std::string, NamesPtrList> NamesMap;
NamesMap opt_long_map;
NamesMap opt_short_map;

typedef std::list<std::string> subSectionsPtrList;
subSectionsPtrList subSections_list;
std::string curSubSection;
  
typedef std::map<std::string, std::list<std::string> > SubSectionNamesListMap;
SubSectionNamesListMap sub_section_namelist_map;

struct Options定义了以上成员变量,默认都是public类型。

  • Names是一个结构体,结构体内包含了opt_longopt_short两个string型的list;
  • opt_list是Names*类型的list;
  • opt_long_mapopt_short_map是hash map,方便对长短命令行参数的查找;

void addOption(OptionBase *opt)

void addOption(OptionBase *opt)
  {
    Names* names = new Names();
    names->opt = opt;
    std::string& opt_string = opt->opt_string;

    if( useLowerNamesOnly ) // 如果只使用小写字母,则将所有大写字母转换成小写字母
    {
      std::transform( opt_string.begin(), opt_string.end(), opt_string.begin(), ::tolower );
    }

    size_t opt_start = 0;
    for (size_t opt_end = 0; opt_end != std::string::npos;)
    {
      opt_end = opt_string.find_first_of(',', opt_start); // 先找到当前开始位置后第一个逗号的位置
      bool force_short = 0;
      if (opt_string[opt_start] == '-') // 如果以'-'开始,强制为短命令
      {
        opt_start++;
        force_short = 1;
      }
      std::string opt_name = opt_string.substr(opt_start, opt_end - opt_start); // 获取命令
      if (force_short || opt_name.size() == 1) // 如果强制为短命令 或者命令长度是1
      {
        names->opt_short.push_back(opt_name); // push到opt_short list里
        opt_short_map[opt_name].push_back(names); // push到hash表里
      }
      else // 如果不是短命令push到长命令里
      {
        names->opt_long.push_back(opt_name);

        std::string optLongLower = opt_name;
        std::transform( optLongLower.begin(), optLongLower.end(), optLongLower.begin(), ::tolower );
        opt_long_map[optLongLower].push_back(names);
      }
      opt_start += opt_end + 1; // 跳到下一个逗号的位置
    }

    if( !subSections_list.empty() )
    {
      if( curSubSection.empty() ){ curSubSection = subSections_list.back(); }
      sub_section_namelist_map[curSubSection].push_back(opt_string);
    }

    opt_list.push_back(names); // 将长命令和对应的短命令push到opt_list里
  }

函数addOption用存储命令行参数,包括短命令和长命令,其派生类OptionSpecific中对函数调用符进行了重载,并在重载函数中调用了addOption。关于函数调用符的重载可以参考重载函数调用运算符。函数的细节已经在代码里注释了,这里就不再说了。

class OptionSpecific

/* Class with templated overloaded operator(), for use by Options::addOptions() */
class OptionSpecific
{
public:
  OptionSpecific(Options& parent_) : parent(parent_) {}

  /**
   * Add option described by name to the parent Options list,
   *   with storage for the option's value
   *   with default_val as the default value
   *   with desc as an optional help description
   */
  template<typename T>
  OptionSpecific&
  operator()(const std::string& name, T& storage, T default_val, const std::string& desc = "", bool bool_switch = false)
  {
    parent.addOption(new Option<T>(name, storage, default_val, desc, bool_switch));
    return *this;
  }

  /**
   * Add option described by name to the parent Options list,
   *   without separate default value
   */
  template<typename T>
  OptionSpecific&
  operator()(const std::string& name, T& storage, const std::string& desc = "", bool bool_switch = false )
  {
    parent.addOption(new Option<T>(name, storage, storage, desc, bool_switch));
    return *this;
  }

  /**
   * Add option described by name to the parent Options list,
   *   with desc as an optional help description
   * instead of storing the value somewhere, a function of type
   * OptionFunc::Func is called.  It is upto this function to correctly
   * handle evaluating the option's value.
   */
  OptionSpecific&
  operator()(const std::string& name, OptionFunc::Func *func, const std::string& desc = "")
  {
    parent.addOption(new OptionFunc(name, parent, func, desc));
    return *this;
  }
private:
  Options& parent;
};

OptionSpecific对函数调用运算符进行了三次重载,分别是:

  • 将按名称描述的命令行参数添加到父选项列表中,并存命令行参数的值,默认值为default_val,可选帮助描述为desc
  • 将按名称描述的命令行参数添加到父选项列表中,不使用单独的默认值
  • 将按名称描述的命令行参数添加到父选项列表中,使用desc作为可选的帮助描述,而不是将值存储在某处,将调用OptionFunc::Func类型的函数。正确处理命令行参数值的评估取决于此函数

重载函数调用运算符

C++允许重载函数调用运算符,写作operator()。如果在自定义的类中编写一个operator(),那么这个类的对象就可以当成函数指针使用。包含函数调用运算符的类对象成为函数对象,或简称为仿函数。只能将这个运算符重载为类的非静态方法。

下面是一个简单的类,它带有一个重载的operator()以及一个具有相同行为的类方法:

class FuncO {
    public:
    FuncO operator () (int param); // Function call operator
    int doSquare (int param);
};

// Impelementation of overloaded function call operator
FuncO FuncO::operator () (int param) {
    cout << doSquare (param) << endl;
    return FuncO (*this);
}

// Implementation of nomal method
int FuncO::doSquare (int param) {
    return param * param;
}

int main ()
{
    FuncO square;
    square (2) (3) (4);
    cout << square.doSquare(5) <<endl;
}

这个代码示例里重载的函数调用运算符比较有趣,它的返回类型是一个FuncO对象,这个对象也是函数对象,也可以直接当成函数指针来使用,所以我们看到下面在出现了square (2) (3) (4),连续调用了3次,第一次square (2) 返回了一个函数对象,接着这个函数对象调用square (2)(3),然后又返回一个函数对象,接着调用square (2) (3) (4)。

运行结果如下:

$ ./FuncO 
4
9
16
25

这个例子在VTM代码中的参数解析中有用到。

C++ 中使用 argc 和 argv 的命令行参数

命令行参数在 DOS 或 Linux 等命令行操作系统中的程序名称之后给出,并从操作系统传递给程序。要在程序中使用命令行参数,必须首先了解 main 函数的完整声明,main 函数实际上可以接受两个参数:一个参数是命令行参数的数量,另一个参数是所有命令行参数的完整列表。

main 的完整声明如下所示:

int main ( int argc, char *argv[] )
  • int型 argc 是 ARGument Count(因此为 argc)。它是从命令行传递给程序的参数数量,包括程序的名称。
  • argv数组是所有参数的列表。argv[0] 是程序的名称,如果名称不可用,则为空字符串。每个小于 argc 的元素编号都是命令行参数。可以像使用字符串一样使用每个 argv 元素,也可以将 argv 用作二维数组。argv[argc] 是一个空指针。
  • 参数由空格分隔,也可以是制表符。

下面给出了C++的实例,可以将所有命令行参数打印出来。

#include <iostream>
using namespace std;
 
int main ( int argc, char *argv[] )
{
    for (int i = 0; i < argc; i++) {
        cout << "argv[" << i << ']' << ": " << argv[i] << endl;
    }
    return 0;
}

运行结果如下:

$ ./arg -a 123 -bcd 4\"5 ef ghj
argv[0]: ./arg
argv[1]: -a
argv[2]: 123
argv[3]: -bcd
argv[4]: 4"5
argv[5]: ef
argv[6]: ghj

视频编码器多次运行不一致问题及解决方案

以为我自己的经验来说,编码器开发和优化过程中的不一致主要包括:CABAC 状态不一致、编解码不一致、debug/release 不一致、多次运行不一致。本文主要总结编码器多次运行不一致问题及解决方案。

多次运行不一致一般来说经常出现在多线程中。可能的原因是某些状态没有初始化,导致在多线程的时候每次运行拿到的值不一样;也可能是一个线程用到了另外一个还没有执行完的线程,导致拿到了空的或者错误的值。

多线程/单线程不一致

通常设置多线程时会保证单线程和多线程的结果时一致的,有时候更改某些代码后会出现多线程和单线程的结果不一致,如果多线程运行每次出现的结果是一样的,只是和单线程的结果不一样,那这是比较好解决的一个问题。

首先对多线程和单线程分别进行编码,尽量关闭deblock和sao。然后把多线程和单线程的码流使用码流分析仪打开,或者用VTM打开dtrace的宏解码再用YUView打开。这个目的是为了找到第一个出现不一致的块,同时可以确定两个不同的块选择的模式,找到第一个不同的块后后面就好办了,就不停的打log,来确定最初问题出现的地方,修掉就可以了。

多线程多次运行不一致

多线程多次运行不一致比较难的一点是难以复现,很难出现重复的编码结果,这就会导致我们无法方便定位问题的原因。所以需要通过几种方法来将不一致的可能情况给缩小,让不一致的结果尽量在一个结果上出现频率较高。我们先使用单线程编码一遍来得到一个anchor的编码结果。然后可以尝试以下办法:

一种方法是尽量关闭编码工具,现尝试把编码工具关闭之后是否还有不一致的情况。如果没有了,就去定位具体是哪个编码工具导致的。如果还有不一致,那就看出现不一致的结果复现的概率大不大,如果一个结果出现的概率比较大,这样就可以方便定位了。

定位方法和多线程/单线程不一致的方法一样,就不断的打log来找到问题所在的地方,但是要保证多线程编码的结果是一样的,比如多线程编出来码率是34.56kb的结果概率比较大,那只有在这个结果下的log才有意义,其他结果是没有意义的。

如果不一致的结果仍然难以复现,第二种方法就是尽量减少编码帧数。比如5帧10帧这种,先看看是不是可以稳定浮现。如果不行,可以随便将一个不一致的结果和anchor对比,找到编码顺序第一个不一样的帧的poc值,在编码时就编这么多帧,然后不断的缩小帧数,直到可以一种编码结果可以多次出现,然后按照上面的方法定位即可。

目前我遇到的问题基本上可以用这两个方法解决,这是我自己的解决方案,可能还有其它更好的方案。

Combined inter and intra prediction (CIIP)

Megre模式是HEVC编码标准引入的一项帧间预测编码技术,在VVC编码标准中对Merge模式进行了扩展。包括对候选列表的扩展,增加了HMVP和 Pair-wise average candidates。编码工具新增CIIP (combined inter-intra prediction)、MMVD(merge mode with MV difference)、GEO(geometric partitioning mode)。VVC新提出的affine也存在merge模式,不过affine merge的候选推导和上面几个编码工具是不一样的。本文主要讨论CIIP技术。

1 原理

在VVC中,当一个CU在merge模式下编码时,如果CU包含至少64个亮度样本(即CU宽度乘以CU高度等于或大于64),并且如果CU宽度和CU高度都小于 128 ,可以选择使用CIIP模式,当前CU是否使用CIIP会被写入码流中。

图1

顾名思义,CIIP 就是将将帧间预测信号与帧内预测信号相结合。 CIIP模式下的帧间预测信号\(P_{inter}\)是使用与Nomal Megre模式(不是MMVD和Affine merge)相同的帧间预测过程导出的;并且帧内预测信号\(P_{intra}\)是按照Planar模式的常规帧内预测过程导出的。然后,使用加权平均来组合帧内和帧间预测信号,其中根据上方和左侧相邻块的编码模式(如图1所示)计算权重值,如下所示:

  • 如果上方相邻CU可用且预测模式为帧内预测,则将 isIntraTop 设置为 1,否则将 isIntraTop 设置为 0;
  • 如果左侧相邻CU可用且预测模式为帧内预测,则将 isIntraLeft 设置为 1,否则将 isIntraLeft 设置为 0;
  • 如果 (isIntraLeft + isIntraTop) = 2,则 wt = 3;
  • 否则,如果 (isIntraLeft + isIntraTop) = 1,则 wt = 2;
  • 否则,将 wt = 1。

CIIP加权预测公式如下:

\(P_{CIIP}=((4-wt)*P_{inter}+wt*P_{intra}+2)>>2\)

一般来说,Nomal merge有最多有6个候选,CIIP也最多有6个候选,MMVD最多有64个候选,Affine merge最多有5个候选,如果这些merge模式每个都做RDO的话,时间复杂度肯定极高,所以一般编码器的解决方案是和Intra预测类似,先使用SATD cost进行一遍粗选,选择几个最优的候选最后才做RDO,这样可以节省很多的时间。CIIP的粗选过程可以放在Nomal merge粗选的后面,只选择其中几个比较好的候选来check CIIP的候选,也可以节省一定的时间。

值得注意的是,在编码标准中,CIIP的merge是不可以判断为skip模式的,也就是说选择CIIP模式,残差系数一定不为0,遇到CIIP模式且cbf = 0可以根据需求决定是否要丢掉这个CIIP候选。

2 VTM代码

2.1 CIIP粗选

if (isIntrainterEnabled)
{
  // prepare for Intra bits calculation
  pu.ciipFlag = true;  // 先将ciip flage设置成true,用来计算bits

  // save the to-be-tested merge candidates
  uint32_t CiipMergeCand[NUM_MRG_SATD_CAND];
  for (uint32_t mergeCnt = 0; mergeCnt < std::min(NUM_MRG_SATD_CAND, (const int)mergeCtx.numValidMergeCand); mergeCnt++)
  {
    CiipMergeCand[mergeCnt] = RdModeList[mergeCnt].mergeCand;
  }
  for (uint32_t mergeCnt = 0; mergeCnt < std::min(std::min(NUM_MRG_SATD_CAND, (const int)mergeCtx.numValidMergeCand), 4); mergeCnt++)
  {
    uint32_t mergeCand = CiipMergeCand[mergeCnt];
    acMergeTmpBuffer[mergeCand] = m_acMergeTmpBuffer[mergeCand].getBuf(localUnitArea); // 复用nomal merge的插值buffer

    // estimate merge bits
    mergeCtx.setMergeInfo(pu, mergeCand); 

    // first round
    pu.intraDir[0] = PLANAR_IDX;
    uint32_t intraCnt = 0;
    // generate intrainter Y prediction
    if (mergeCnt == 0)
    {
      m_pcIntraSearch->initIntraPatternChType(*pu.cu, pu.Y()); // 获取参考像素
      m_pcIntraSearch->predIntraAng(COMPONENT_Y, pu.cs->getPredBuf(pu).Y(), pu); // Planar预测
      m_pcIntraSearch->switchBuffer(pu, COMPONENT_Y, pu.cs->getPredBuf(pu).Y(), m_pcIntraSearch->getPredictorPtr2(COMPONENT_Y, intraCnt));
    }
    pu.cs->getPredBuf(pu).copyFrom(acMergeTmpBuffer[mergeCand]);
    if (pu.cs->slice->getLmcsEnabledFlag() && m_pcReshape->getCTUFlag())
    {
      pu.cs->getPredBuf(pu).Y().rspSignal(m_pcReshape->getFwdLUT());
    }
    m_pcIntraSearch->geneWeightedPred(COMPONENT_Y, pu.cs->getPredBuf(pu).Y(), pu, m_pcIntraSearch->getPredictorPtr2(COMPONENT_Y, intraCnt)); //加权组合

    // calculate cost
    if (pu.cs->slice->getLmcsEnabledFlag() && m_pcReshape->getCTUFlag())
    {
      pu.cs->getPredBuf(pu).Y().rspSignal(m_pcReshape->getInvLUT());
    }
    distParam.cur = pu.cs->getPredBuf(pu).Y();
    Distortion sadValue = distParam.distFunc(distParam); // 计算 dist
    if (pu.cs->slice->getLmcsEnabledFlag() && m_pcReshape->getCTUFlag())
    {
      pu.cs->getPredBuf(pu).Y().rspSignal(m_pcReshape->getFwdLUT());
    }
    m_CABACEstimator->getCtx() = ctxStart;
    pu.regularMergeFlag = false;
    uint64_t fracBits = m_pcInterSearch->xCalcPuMeBits(pu); //计算 bits
    double cost = (double)sadValue + (double)fracBits * sqrtLambdaForFirstPassIntra; // 计算 cost

    insertPos = -1;
    updateCandList(ModeInfo(mergeCand, false, false, true), cost, RdModeList, candCostList, uiNumMrgSATDCand, &insertPos); // 更新候选排序列表
    if (insertPos != -1)
    {
      for (int i = int(RdModeList.size()) - 1; i > insertPos; i--)
      {
        swap(acMergeTempBuffer[i - 1], acMergeTempBuffer[i]);
      }
      swap(singleMergeTempBuffer, acMergeTempBuffer[insertPos]);
    }
  }
  pu.ciipFlag = false;
}

2.2 组合预测

这一块的代码涉及到像素的加权组合,因此可以使用SIMD来实现,VTM这里是使用C++实现的。

void IntraPrediction::geneWeightedPred(const ComponentID compId, PelBuf &pred, const PredictionUnit &pu, Pel *srcBuf)
{
  const int width = pred.width;
  CHECK(width == 2, "Width of 2 is not supported");
  const int height    = pred.height;
  const int srcStride = width;
  const int dstStride = pred.stride;

  Pel *dstBuf = pred.buf;
  int wIntra, wMerge;

  const Position posBL = pu.Y().bottomLeft();
  const Position posTR = pu.Y().topRight();
  const PredictionUnit *neigh0 = pu.cs->getPURestricted(posBL.offset(-1, 0), pu, CHANNEL_TYPE_LUMA);
  const PredictionUnit *neigh1 = pu.cs->getPURestricted(posTR.offset(0, -1), pu, CHANNEL_TYPE_LUMA);
  bool isNeigh0Intra = neigh0 && (CU::isIntra(*neigh0->cu));
  bool isNeigh1Intra = neigh1 && (CU::isIntra(*neigh1->cu));

  if (isNeigh0Intra && isNeigh1Intra)
  {
    wIntra = 3; wMerge = 1;
  }
  else
  {
    if (!isNeigh0Intra && !isNeigh1Intra)
    {
      wIntra = 1; wMerge = 3;
    }
    else
    {
      wIntra = 2; wMerge = 2;
    }
  }

  for (int y = 0; y < height; y++)
  {
    for (int x = 0; x < width; x++)
    {
      dstBuf[y*dstStride + x] = (wMerge * dstBuf[y*dstStride + x] + wIntra * srcBuf[y*srcStride + x] + 2) >> 2;
    }
  }
}

2.3 encoder

首选判断是否ciipAvailable,CIIP和GEO都不是regular merge,如果有一个是true,则需要编是否为regular merge,如果不是,则还需要编一个flag来判断是CIIP还是GEO。

const bool ciipAvailable = pu.cs->sps->getUseCiip() && !pu.cu->skip && pu.cu->lwidth() < MAX_CU_SIZE && pu.cu->lheight() < MAX_CU_SIZE && pu.cu->lwidth() * pu.cu->lheight() >= 64;
  const bool geoAvailable = pu.cu->cs->slice->getSPS()->getUseGeo() && pu.cu->cs->slice->isInterB() &&
    pu.cs->sps->getMaxNumGeoCand() > 1
                                                                    && pu.cu->lwidth() >= GEO_MIN_CU_SIZE && pu.cu->lheight() >= GEO_MIN_CU_SIZE
                                                                    && pu.cu->lwidth() <= GEO_MAX_CU_SIZE && pu.cu->lheight() <= GEO_MAX_CU_SIZE
                                                                    && pu.cu->lwidth() < 8 * pu.cu->lheight() && pu.cu->lheight() < 8 * pu.cu->lwidth();
  if (geoAvailable || ciipAvailable)
  {
    m_BinEncoder.encodeBin(pu.regularMergeFlag, Ctx::RegularMergeFlag(pu.cu->skip ? 0 : 1));
  }
  if (pu.regularMergeFlag)
  {
    if (pu.cs->sps->getUseMMVD())
    {
      m_BinEncoder.encodeBin(pu.mmvdMergeFlag, Ctx::MmvdFlag(0));
      DTRACE(g_trace_ctx, D_SYNTAX, "mmvd_merge_flag() mmvd_merge=%d pos=(%d,%d) size=%dx%d\n", pu.mmvdMergeFlag ? 1 : 0, pu.lumaPos().x, pu.lumaPos().y, pu.lumaSize().width, pu.lumaSize().height);
    }
    if (pu.mmvdMergeFlag || pu.cu->mmvdSkip)
    {
      mmvd_merge_idx(pu);
    }
    else
    {
      merge_idx(pu);
    }
  }
  else
  {
    if (geoAvailable && ciipAvailable)
    {
      Ciip_flag(pu);
    }
    merge_idx(pu);
  }

Merge模式候选列表构建

Megre模式是HEVC编码标准引入的一项帧间预测编码技术,在VVC编码标准中对Merge模式进行了扩展。包括对候选列表的扩展,增加了HMVP和 Pair-wise average candidates。编码工具新增CIIP (combined inter-intra prediction)、MMVD(merge mode with MV difference)、GEO(geometric partitioning mode)。VVC新提出的affine也存在merge模式,不过affine merge的候选推导和上面几个编码工具是不一样的。本文主要讨论Merge模式候选列表构建。

1 HEVC Merge候选列表构建

HEVC的Merge候选个数最大为5个,构建过程如图1。

图1

为了构建空域Merge候选,在位于图2所示位置的候选中选择最多四个Merge候选。

图2

构建的顺序是A1→B1→B0→A0→B2。仅当位置 A1、B1、B0 和 A0 的任何 PU 不可用(例如它属于另一个Slice或Tile)或者不是inter mode时才考虑位置 B2。

在A1位置的候选加入后,剩余候选的加入会进行冗余校验,确保将具有相同运动信息的候选排除在列表之外,以提高编码效率。为了降低计算复杂度,仅比较下图3的箭头链接的对,并且仅当候选通过冗余检查时才将其添加到列表中。

图3

在 HEVC 中,一个 CU 可能会被划分为多个 PU,这可能会对Merge模式带来冗余。图4描绘了从 CU 中分别按 N × 2N 和 2N × N 模式划分的“第二个 PU”。

图4

当第二个 PU 从一个 CU 划分 N × 2N 时,位置 A1 的候选者不考虑用于列表构建。事实上,通过选择这个候选者,两个 PU 将共享相同的运动信息,这对于 CU 中只有一个 PU 的情况是多余的。 类似地,当第二个 PU 从一个 CU 被分割为 2N × N 时,不考虑位置 B1。

在时域Merge候选的推导中,TMVP 候选是从存储在位置 H 或 C 的 MV 推导出来的,如图 1 所示的并置图片,类似于 AMVP 模式的 TMVP 候选。 对于Merge候选列表中的 TMVP 候选,MV 将被缩放到相应参考帧列表中具有参考索引 0 的参考帧。

除了时空Merge候选之外,还有两种附加类型的Merge候选:组合的双向预测Merge候选和具有 (0, 0) 运动向量的零运动候选。 组合的双向预测Merge候选是通过仅利用 B Slice的时空Merge候选来生成的。 通过组合具有参考列表0的第一Merge候选和具有参考列表1的第二Merge候选来生成组合双向预测候选,其中第一和第二Merge候选根据预定义顺序从Merge候选列表中的可用Merge候选中选择。这两个MV将形成新的双向预测候选。如果未满足Merge候选列表,则将向列表添加零运动候选以填充列表。

2 VVC Merge候选列表构建

2.1 空域候选推导

VVC中空域Merge候选的推导与HEVC相同,只是前两个Merge候选的位置交换了。在位于图 5 所示位置的候选中,最多选择四个Merge候选。推导顺序为 B1、A1、B0、A0 和 B2。仅当位置 B0、A0、B1、A1 的一个或多个 CU 不可用(例如它属于另一个Slice或Tile)或者不是inter mode时,才考虑位置 B2。在A1位置的候选加入后,剩余候选的加入进行冗余校验,保证将具有相同运动信息的候选排除在列表之外,从而提高编码效率。为了降低计算复杂度,在提到的冗余校验中并未考虑所有可能的候选对,与HEVC一样仅考虑与图 3 中的箭头链接的对,并且仅当用于冗余校验的相应候选具有不同的运动信息时,才将候选添加到列表中。

图5

2.2 时域候选推导(TMVP)

在此步骤中,仅将一个候选者添加到列表中。 特别地,在该时域Merge候选的推导中,基于属于并置参考图片的 co-located CU来缩放运动矢量。 用于推导位于同一位置的 CU 的参考帧列表和参考索引会被写入slice header中。 时域Merge候选的缩放运动向量如图 6中的虚线所示,它是从 co-located CU 的运动向量缩放的。

图6

如图 7 所示,在候选 C0 和 C1 之间选择时域候选的位置。如果位置 C0 处的 CU 不可用、被帧内编码或位于当前 CTU 行之外,则使用位置 C1。 否则,在时域Merge候选的推导中使用位置 C0。

图7

2. 3 HMVP候选

在 HEVC 中,有两种类型的 MVP,即时域 MVP 和空域 MVP,它们利用来自空间相邻或时间块的运动信息。在 VVC 中,引入了一种新型 MVP,即 基于历史的 MVP(HMVP)。 HMVP 的基本思想是进一步使用先前编码的 MV 作为 MVP,这些 MV 与相对于当前块的相邻或不相邻块相关联。为了跟踪可用的 HMVP 候选者,在编码器和解码器处都维护了一个 HMVP 候选者表,并动态更新。每当新的 CTU 行开始时,表就会重置以简化并行编码。

HMVP 表中最多有5个候选者。在对一个不处于子块模式(包括仿射模式)或 GPM 的帧间预测块进行编码之后,通过将关联的运动信息附加到表的末尾作为新的 HMVP 候选者来选择性地更新表。应用受限的先进先出 (FIFO) 规则来管理表,其中首先应用冗余检查以查找表中是否存在相同的HMVP。 如果找到,则从表中删除相同的 HMVP,然后将所有 HMVP 候选向前移动,并将相同的 HMVP 插入到表的最后一个条目中。使用 HMVP,即使编码块在空间上不与当前块相邻,先前编码块的运动信息也可以用于更有效的运动矢量预测。

为了减少冗余校验操作的数量,引入了以下简化:

  1. 表中的最后两个条目分别对 A1 和 B1 空域候选进行冗余检查。
  2. 一旦可用Merge候选的总数达到最大允许Merge候选减1,则终止来自HMVP的Merge候选列表构建过程。

2.4 Pair-wise average merge candidates derivation

VVC 中的Pair-wise average Merge候选取代了 HEVC 中的组合双预测Merge候选。Pair-wise average 候选是通过使用前两个Merge候选对现有Merge候选列表中预定义的候选对进行平均来生成的。 第一个Merge候选定义为 p0Cand,第二个Merge候选定义为 p1Cand。 根据 p0Cand 和 p1Cand 的运动向量的可用性分别计算每个参考列表的平均运动向量。 如果两个运动矢量都在一个列表中,则即使它们指向不同的参考帧,这两个运动矢量也会被平均,并将其参考图片设置为p0Cand之一; 如果只有一个运动矢量可用,则直接使用一个; 如果没有可用的运动矢量,则保持此列表无效。 此外,如果 p0Cand 和 p1Cand 的半像素插值滤波器索引不同,则将其设置为 0。

当添加Pair-wise average Merge候选后Merge列表未满时,则将向列表添加零运动候选以填充列表。

2.5 VTM代码分析

删去了代码中和GDR相关的和一些不重要的内容。

空域:代码里的符号和上面图中的符号不一致,但是仔细看顺序还是一样的。

// above
  const PredictionUnit *puAbove = cs.getPURestricted(posRT.offset(0, -1), pu, pu.chType);

  bool isAvailableB1 = puAbove && isDiffMER(pu.lumaPos(), posRT.offset(0, -1), plevel) && pu.cu != puAbove->cu && CU::isInter(*puAbove->cu);

  if (isAvailableB1)
  {
    miAbove = puAbove->getMotionInfo(posRT.offset(0, -1));

    // get Inter Dir
    mrgCtx.interDirNeighbours[cnt] = miAbove.interDir;
    mrgCtx.useAltHpelIf[cnt] = miAbove.useAltHpelIf;
    // get Mv from Above
    mrgCtx.bcwIdx[cnt] = (mrgCtx.interDirNeighbours[cnt] == 3) ? puAbove->cu->bcwIdx : BCW_DEFAULT;
    mrgCtx.mvFieldNeighbours[cnt << 1].setMvField(miAbove.mv[0], miAbove.refIdx[0]);

    if (slice.isInterB())
    {
      mrgCtx.mvFieldNeighbours[(cnt << 1) + 1].setMvField(miAbove.mv[1], miAbove.refIdx[1]);
    }
    cnt++;
  }

  //left
  const PredictionUnit* puLeft = cs.getPURestricted(posLB.offset(-1, 0), pu, pu.chType);

  const bool isAvailableA1 = puLeft && isDiffMER(pu.lumaPos(), posLB.offset(-1, 0), plevel) && pu.cu != puLeft->cu && CU::isInter(*puLeft->cu);

  if (isAvailableA1)
  {
    miLeft = puLeft->getMotionInfo(posLB.offset(-1, 0));

    if (!isAvailableB1 || (miAbove != miLeft))
    {
      // get Inter Dir
      mrgCtx.interDirNeighbours[cnt] = miLeft.interDir;
      mrgCtx.useAltHpelIf[cnt]       = miLeft.useAltHpelIf;
      mrgCtx.bcwIdx[cnt]             = (mrgCtx.interDirNeighbours[cnt] == 3) ? puLeft->cu->bcwIdx : BCW_DEFAULT;
      // get Mv from Left
      mrgCtx.mvFieldNeighbours[cnt << 1].setMvField(miLeft.mv[0], miLeft.refIdx[0]);

      if (slice.isInterB())
      {
        mrgCtx.mvFieldNeighbours[(cnt << 1) + 1].setMvField(miLeft.mv[1], miLeft.refIdx[1]);
      }
      cnt++;
    }
  }

  // above right
  const PredictionUnit *puAboveRight = cs.getPURestricted( posRT.offset( 1, -1 ), pu, pu.chType );

  bool isAvailableB0 = puAboveRight && isDiffMER( pu.lumaPos(), posRT.offset(1, -1), plevel) && CU::isInter( *puAboveRight->cu );

  if( isAvailableB0 )
  {
    miAboveRight = puAboveRight->getMotionInfo( posRT.offset( 1, -1 ) );

    if( !isAvailableB1 || ( miAbove != miAboveRight ) )
    {

      // get Inter Dir
      mrgCtx.interDirNeighbours[cnt] = miAboveRight.interDir;
      mrgCtx.useAltHpelIf[cnt] = miAboveRight.useAltHpelIf;
      // get Mv from Above-right
      mrgCtx.bcwIdx[cnt] = (mrgCtx.interDirNeighbours[cnt] == 3) ? puAboveRight->cu->bcwIdx : BCW_DEFAULT;
      mrgCtx.mvFieldNeighbours[cnt << 1].setMvField( miAboveRight.mv[0], miAboveRight.refIdx[0] );

      if( slice.isInterB() )
      {
        mrgCtx.mvFieldNeighbours[( cnt << 1 ) + 1].setMvField( miAboveRight.mv[1], miAboveRight.refIdx[1] );
      }
      cnt++;
    }
  }

  //left bottom
  const PredictionUnit *puLeftBottom = cs.getPURestricted( posLB.offset( -1, 1 ), pu, pu.chType );

  bool isAvailableA0 = puLeftBottom && isDiffMER( pu.lumaPos(), posLB.offset(-1, 1), plevel) && CU::isInter( *puLeftBottom->cu );

  if( isAvailableA0 )
  {
    miBelowLeft = puLeftBottom->getMotionInfo( posLB.offset( -1, 1 ) );

    if( !isAvailableA1 || ( miBelowLeft != miLeft ) )
    {
      // get Inter Dir
      mrgCtx.interDirNeighbours[cnt] = miBelowLeft.interDir;
      mrgCtx.useAltHpelIf[cnt]       = miBelowLeft.useAltHpelIf;
      mrgCtx.bcwIdx[cnt]             = (mrgCtx.interDirNeighbours[cnt] == 3) ? puLeftBottom->cu->bcwIdx : BCW_DEFAULT;
      // get Mv from Bottom-Left
      mrgCtx.mvFieldNeighbours[cnt << 1].setMvField( miBelowLeft.mv[0], miBelowLeft.refIdx[0] );

      if( slice.isInterB() )
      {
        mrgCtx.mvFieldNeighbours[( cnt << 1 ) + 1].setMvField( miBelowLeft.mv[1], miBelowLeft.refIdx[1] );
      }
      cnt++;
    }
  }

  // above left
  if ( cnt < 4 )
  {
    const PredictionUnit *puAboveLeft = cs.getPURestricted( posLT.offset( -1, -1 ), pu, pu.chType );

    bool isAvailableB2 = puAboveLeft && isDiffMER( pu.lumaPos(), posLT.offset(-1, -1), plevel ) && CU::isInter( *puAboveLeft->cu );

    if( isAvailableB2 )
    {
      miAboveLeft = puAboveLeft->getMotionInfo( posLT.offset( -1, -1 ) );

      if( ( !isAvailableA1 || ( miLeft != miAboveLeft ) ) && ( !isAvailableB1 || ( miAbove != miAboveLeft ) ) )
      {
        // get Inter Dir
        mrgCtx.interDirNeighbours[cnt] = miAboveLeft.interDir;
        mrgCtx.useAltHpelIf[cnt]       = miAboveLeft.useAltHpelIf;
        mrgCtx.bcwIdx[cnt]             = (mrgCtx.interDirNeighbours[cnt] == 3) ? puAboveLeft->cu->bcwIdx : BCW_DEFAULT;
        // get Mv from Above-Left
        mrgCtx.mvFieldNeighbours[cnt << 1].setMvField( miAboveLeft.mv[0], miAboveLeft.refIdx[0] );

        if( slice.isInterB() )
        {
          mrgCtx.mvFieldNeighbours[( cnt << 1 ) + 1].setMvField( miAboveLeft.mv[1], miAboveLeft.refIdx[1] );
        }
        cnt++;
      }
    }
  }

TMVP

  if (slice.getPicHeader()->getEnableTMVPFlag() && (pu.lumaSize().width + pu.lumaSize().height > 12))
  {
    //>> MTK colocated-RightBottom
    // offset the pos to be sure to "point" to the same position the uiAbsPartIdx would've pointed to
    Position posRB = pu.Y().bottomRight().offset( -3, -3 );
    const PreCalcValues& pcv = *cs.pcv;

    Position posC0;
    Position posC1 = pu.Y().center();
    bool C0Avail = false;
    bool boundaryCond = ((posRB.x + pcv.minCUWidth) < pcv.lumaWidth) && ((posRB.y + pcv.minCUHeight) < pcv.lumaHeight);
    const SubPic& curSubPic = pu.cs->slice->getPPS()->getSubPicFromPos(pu.lumaPos());
    if (curSubPic.getTreatedAsPicFlag())
    {
      boundaryCond = ((posRB.x + pcv.minCUWidth) <= curSubPic.getSubPicRight() &&
                      (posRB.y + pcv.minCUHeight) <= curSubPic.getSubPicBottom());
    }
    if (boundaryCond)
    {
      int posYInCtu = posRB.y & pcv.maxCUHeightMask;
      if (posYInCtu + 4 < pcv.maxCUHeight)
      {
        posC0 = posRB.offset(4, 4);
        C0Avail = true;
      }
    }

    Mv        cColMv;
    int       refIdx      = 0;
    int       dir         = 0;
    unsigned  arrayAddr   = cnt;
    bool      existMV     = (C0Avail && getColocatedMVP(pu, REF_PIC_LIST_0, posC0, cColMv, refIdx, false))
                   || getColocatedMVP(pu, REF_PIC_LIST_0, posC1, cColMv, refIdx, false);
    if (existMV)
    {
      dir     |= 1;
      mrgCtx.mvFieldNeighbours[2 * arrayAddr].setMvField(cColMv, refIdx);
    }

    if (slice.isInterB())
    {
      existMV = (C0Avail && getColocatedMVP(pu, REF_PIC_LIST_1, posC0, cColMv, refIdx, false))
                || getColocatedMVP(pu, REF_PIC_LIST_1, posC1, cColMv, refIdx, false);
      if (existMV)
      {
        dir     |= 2;
        mrgCtx.mvFieldNeighbours[2 * arrayAddr + 1].setMvField(cColMv, refIdx);
      }
    }

    if( dir != 0 )
    {
      bool addTMvp = true;
      if( addTMvp )
      {
        mrgCtx.interDirNeighbours[arrayAddr] = dir;
        mrgCtx.bcwIdx[arrayAddr]             = BCW_DEFAULT;
        mrgCtx.useAltHpelIf[arrayAddr]       = false;
        if (mrgCandIdx == cnt)
        {
          return;
        }

        cnt++;
      }
    }
  }

HMVP

bool PU::addMergeHMVPCand(const CodingStructure &cs, MergeCtx &mrgCtx, const int &mrgCandIdx,
                          const uint32_t maxNumMergeCandMin1, int &cnt, const bool isAvailableA1,
                          const MotionInfo miLeft, const bool isAvailableB1, const MotionInfo miAbove,
                          const bool ibcFlag, const bool isGt4x4

)
{
  const Slice& slice = *cs.slice;
  MotionInfo miNeighbor;

  auto &lut = ibcFlag ? cs.motionLut.lutIbc : cs.motionLut.lut;

  const int numAvailCandInLut = (int) lut.size();

  for (int mrgIdx = 1; mrgIdx <= numAvailCandInLut; mrgIdx++)
  {
    miNeighbor = lut[numAvailCandInLut - mrgIdx];

    if ( mrgIdx > 2 || ((mrgIdx > 1 || !isGt4x4) && ibcFlag)
      || ((!isAvailableA1 || (miLeft != miNeighbor)) && (!isAvailableB1 || (miAbove != miNeighbor))) )
    {
      mrgCtx.interDirNeighbours[cnt] = miNeighbor.interDir;
      mrgCtx.useAltHpelIf      [cnt] = !ibcFlag && miNeighbor.useAltHpelIf;
      mrgCtx.bcwIdx[cnt]             = (miNeighbor.interDir == 3) ? miNeighbor.bcwIdx : BCW_DEFAULT;

      mrgCtx.mvFieldNeighbours[cnt << 1].setMvField(miNeighbor.mv[0], miNeighbor.refIdx[0]);
      if (slice.isInterB())
      {
        mrgCtx.mvFieldNeighbours[(cnt << 1) + 1].setMvField(miNeighbor.mv[1], miNeighbor.refIdx[1]);
      }

      if (mrgCandIdx == cnt)
      {
        return true;
      }
      cnt ++;

      if (cnt  == maxNumMergeCandMin1)
      {
        break;
      }
    }
  }

  if (cnt < maxNumMergeCandMin1)
  {
    mrgCtx.useAltHpelIf[cnt] = false;
  }

  return false;
}

pairwise-average candidates

if (cnt > 1 && cnt < maxNumMergeCand)
    {
      mrgCtx.mvFieldNeighbours[cnt * 2].setMvField( Mv( 0, 0 ), NOT_VALID );
      mrgCtx.mvFieldNeighbours[cnt * 2 + 1].setMvField( Mv( 0, 0 ), NOT_VALID );
      // calculate average MV for L0 and L1 seperately
      unsigned char interDir = 0;

      mrgCtx.useAltHpelIf[cnt] = (mrgCtx.useAltHpelIf[0] == mrgCtx.useAltHpelIf[1]) ? mrgCtx.useAltHpelIf[0] : false;
      for( int refListId = 0; refListId < (slice.isInterB() ? 2 : 1); refListId++ )
      {
        const short refIdxI = mrgCtx.mvFieldNeighbours[0 * 2 + refListId].refIdx;
        const short refIdxJ = mrgCtx.mvFieldNeighbours[1 * 2 + refListId].refIdx;

        // both MVs are invalid, skip
        if( (refIdxI == NOT_VALID) && (refIdxJ == NOT_VALID) )
        {
          continue;
        }

        interDir += 1 << refListId;
        // both MVs are valid, average these two MVs
        if( (refIdxI != NOT_VALID) && (refIdxJ != NOT_VALID) )
        {
          const Mv &mvI = mrgCtx.mvFieldNeighbours[0 * 2 + refListId].mv;
          const Mv &mvJ = mrgCtx.mvFieldNeighbours[1 * 2 + refListId].mv;

          // average two MVs
          Mv avgMv = mvI;
          avgMv += mvJ;
          avgMv.roundAffine(1);

          mrgCtx.mvFieldNeighbours[cnt * 2 + refListId].setMvField( avgMv, refIdxI );
        }
        // only one MV is valid, take the only one MV
        else if( refIdxI != NOT_VALID )
        {
          Mv singleMv = mrgCtx.mvFieldNeighbours[0 * 2 + refListId].mv;
          mrgCtx.mvFieldNeighbours[cnt * 2 + refListId].setMvField( singleMv, refIdxI );
        }
        else if( refIdxJ != NOT_VALID )
        {
          Mv singleMv = mrgCtx.mvFieldNeighbours[1 * 2 + refListId].mv;
          mrgCtx.mvFieldNeighbours[cnt * 2 + refListId].setMvField( singleMv, refIdxJ );
        }
      }

      mrgCtx.interDirNeighbours[cnt] = interDir;
      if( interDir > 0 )
      {
        cnt++;
      }
    }

Zero Mv

uint32_t arrayAddr = cnt;

  int numRefIdx = slice.isInterB() ? std::min(slice.getNumRefIdx(REF_PIC_LIST_0), slice.getNumRefIdx(REF_PIC_LIST_1))
                                   : slice.getNumRefIdx(REF_PIC_LIST_0);

  int r = 0;
  int refcnt = 0;
  while (arrayAddr < maxNumMergeCand)
  {
    mrgCtx.interDirNeighbours[arrayAddr] = 1;
    mrgCtx.bcwIdx[arrayAddr]             = BCW_DEFAULT;
    mrgCtx.mvFieldNeighbours[arrayAddr << 1].setMvField(Mv(0, 0), r);
    mrgCtx.useAltHpelIf[arrayAddr] = false;

    if (slice.isInterB())
    {
      mrgCtx.interDirNeighbours[arrayAddr] = 3;
      mrgCtx.mvFieldNeighbours[(arrayAddr << 1) + 1].setMvField(Mv(0, 0), r);
    }

    arrayAddr++;

    if (refcnt == numRefIdx - 1)
    {
      r = 0;
    }
    else
    {
      ++r;
      ++refcnt;
    }
  }
  mrgCtx.numValidMergeCand = arrayAddr;

代码和上文描述的是一致的,代码里包含了更多的细节,这里就不再讨论了。

VTM 快速CTC测试方案

以下内容总结自JVET-T2010、JVET-T0003、JVET-B0036

VTM作为VVC的参考软件,集成了许多编码工具。尽管这些编码工具大大提升了VTM的编码效率,然而编码时间却急速上升。在JVET-T0003中给出了VTM-10.0的性能,相对于HM16.20,AI配置下,码率节省26.85%,编码时间上升2630%;RA配置下,码率节省40.06%,编码时间增加859%。

我们在进行CTC测试时,尽管有足够多的计算资源(例如多核CPU),当我们采用最小的并行工作方式(每个序列、每个QP、每个配置编一次),每个job的编码时间是不一样的,整个测试时间是取决于编码时间最长的那个序列,这样我们需要花超过一周的时间来进行通测,所以一个快速的测试方案是必须的。

JVET-B0036分别为AI和RA配置提出了快速测试方案,并纳入VTM通用测试条件(JVET-2010)中。下面对JVET-B0036做简要的介绍。

1 Parallel encoding for RA configuration

通常,对测试序列的前 1 或 2 秒内的帧进行编码被认为是 RA 配置的快速模拟方法。但是编码结果可能与编码全长序列的结果有很大不同。一方面,不同帧数的预测结构可能不同,这对压缩性能有重要影响;另一方面,全长序列不同部分的运动特性可能会有很大差异。由于存在一些针对特定运动特性的帧间预测编码工具,因此最终的编码结果容易受到影响。通过考虑这些因素,RA配置的简化模拟方法不能改变预测结构,或减少帧数。

现有RA配置中的预测结构示例如图1所示,其中与每个帧相关联的数字代表编码顺序。为了启用随机访问,I 帧被定期插入。两个连续的 I 帧之间的预测结构是相同的。除了第一个 I 帧被编码为 IDR 帧外,所有 I 帧都被编码为非 IDR I 帧(“开放 GOP”)。对于非IDR I帧,虽然有一些编码顺序在其后面的前导图片,但这些前导图片将不会被后续图片引用。以图1中的第5~12帧为例,第6~8帧为第5帧的Leading picture,在解码过程中需要参考第5帧。但是第9~12帧在解码过程中不会参考第6~8帧。这意味着,如果我们根据帧内周期将整个序列划分为一些片段,如图 1 所示,则它们之间没有帧间预测依赖性。这样整个顺序编码过程就可以分为许多子过程,可以并行执行,充分利用计算资源。

考虑到上述分析,在本方案中,根据intra period,将整个顺序编码过程分为几个随机访问段(RAS),每个RAS以一个RAP帧开始和结束(最后一个段除外,可能是以B帧结束,因为帧数可能小于一个intra周期)。这里注意RAP帧必须是Intra帧。以序列Nebuta为例,RA配置的intra period为64,则poc为0~64的帧为第一RAS,64~128的帧为第二RAS,以此类推。由于两个连续的 RAS 之间没有帧间预测相关性,这样,这些 RAS 可以并行编码。

在所有RAS的编码过程完成后,利用每个RAS的编码日志文件(属于同一个整个序列编码过程)提取整个序列编码过程的编码结果。这里请注意,有些帧将被编码两次(作为 RAS 的结束,也是后续 RAS 的开始,如 Nebuta 的第 64 帧)。但它们只会被带入提取过程一次。由于每个 RAS 的第一个 I 帧中都会存在 VPS、SPS 和 PPS 编码位,为了避免重复统计,除了第一个 RAS 之外,只有作为每个 RAS 结尾的那些 I 帧才会被纳入提取过程,因为开始和结束都将被考虑在内。最后,可以通过提出的并行模拟方法获得原始RD数据。

如果两个连续的RAS的编码过程是完全独立的,那么并行RAS编码得到的RD数据应该等于整个顺序编码过程(原始)的RD数据。但实际上,在当前的编码参考软件中,有一些工具带来了依赖性。第一个是“CABAC_INIT_PRESENT_FLAG”,它指定“cabac_init_flag”是否出现在slice header中,“cabac_init_flag”表示当前slice的上下文初始化表项,在现在的编码软件中,前一个slice的slice类型会影响当前slice的表项选择。第二个是“VCEG_AZ07_INIT_PREVFRAME”,它是“VCEG_AZ07_ECABAC”的子宏[4]。如果“VCEG_AZ07_INIT_PREVFRAME”打开,则“可以通过从先前编码的图片复制状态来初始化slice间上下文模型的初始概率状态”。第三个是“COM16_C806_ALF_TEMPPRED_NUM”,它是ALF_HM3_REFACTOR的一个子宏,这个宏表示候选ALF参数集的长度,如果这个宏大于0,可以从参数集中选择当前切片的ALF参数,导出来自先前编码的切片。这3个因素带来的不等是因为RAS的起始I帧后面的slice(例如图1中的frame9或frame17)的前一个slice类型已经改变,在原始方法中,前一个slice类型是inter,但是提出的方法是 Intra。此外,通过我们的测试,如果“SAO”的长度太短,则会将比特率不匹配(仅比特率)带入最后一个 RAS 的第二帧。那是因为“slice级 SAO 开/关决定是由hierarchy level>0层的前一帧决定的。对于具有hierarchy level = N 的当前帧,前一帧被定义为解码顺序中具有hierarchy level = (N-1) 的最后一帧。”。因此,如果最后一个 RAS 很短,则hierarchy level不连续,例如只有 0、2、3。因此,最后一个RAS中hierarchy level = 2的帧的SAO开/关决定将由前一个RAS中hierarchy level = 1的帧决定。

即使存在这些因素,来自 RAS 并行的最终 RD 数据仍然非常接近来自原始整个顺序编码过程的 RD 数据。JEM1.0 与 HM16.6 在不同仿真方法下的性能在表 1~表 3 中给出。由于我们的集群无法提供关于编码时间和解码时间的公平比较,所以下面的“EncT”和“DecT”是不准确的,下同。

从表1~表3可以看出,原始方法的总体结果为-20.01%,而提出方法的结果为-20.00%,而前2个intra period内的结果为-19.37%。因此所提方法的编码结果与原始结果非常接近。

由于序列是按照intra period划分的,近似等于帧率,所以新的RA配置仿真时间仅为原来的1/T(T为序列持续时间,单位为秒)

2 AI simulation using snapshot of full-length sequence

与RA配置不同,AI配置的编码结果不会受预测结构或运动特性的影响,而是受镜头场景的影响。一般来说,对于现有的测试序列,拍摄场景相对稳定。即使在一些测试序列中有一些场景变化,它也很慢。所以,如果将整个场景变化缓慢的测试序列切割成一些均匀的小部分,对于每个部分,仍然可以认为是一个场景稳定的小序列。对于稳定的部分,任何帧的编码结果都可以很好地代表其他帧,因此不需要对所有帧进行编码。

在这个提议中,对于每个序列,选择每个intra period的第一帧(在 RA 配置中)以形成一个新的小得多的序列,如图 3 所示。对选择方法的更直接的解释是为每个序列选择 RA 配置中的 RAP 图片。以序列Nebuta为例,RA配置中其帧内周期为64,poc等于0、64、128、192、256的帧,总共只有5帧,将被选出形成一个新的序列进行AI模拟, 比较原始完整序列的 300 帧。

即使每个序列的帧数显着减少,全长序列的编码性能仍然可以得到很好的体现。为了证实这一点,下面给出了 JEM1.0 与 HM16.6 的 3 种不同测试方法的性能。

从表4~表6,对比前1秒的编码结果(Y:-13.80%),snapshot的编码结果(Y:-13.91%)似乎更接近全长序列(Y:-13.99%), 特别是对于ClassF。

对于每个序列,由于新的较小序列仅由每个帧内周期的第一帧组成,因此新的AI配置模拟时间仅为原始配置的1/IP(IP是RA配置的帧内周期)。

在VTM中的AI配置可以通过设置TemporalSubsampleRatio来直接实现这个方案。

CABAC状态不一致解决方案

以为我自己的经验来说,编码器开发和优化过程中的不一致主要包括:CABAC 状态不一致、编解码不一致、debug/release 不一致、多次运行不一致、多线程/单线程不一致。本文主要总结在编码器中遇到这些不一致时常见的原因和解决方案。

编码器在做RDO时,会选择cost最低的模式作为最优模式,其中

\(cost = D + \lambda R\)

我们在RDO的过程中要准确的估计当前模式产生的码率,为了得到准确的码率,需要保持CABAC状态的更新和最后编码CTU时CABAC的状态一致,因此在最后编码完CTU时可以进行CABAC的状态的检查,以判断估计过程的CABAC和真实的CABAC状态是否一致,如果不一致可以通过ASSERT()来触发断言,这样在Debug模式下就可以发现是否存在不一致,如果出现不一致,那么RDO选择的结果可能会出现错误。

在做RDO时,一般会把初始的CABAC状态先备份一份,然后在check每个候选的时候,拷贝出初始的CABAC状态,保证在check每个候选的时候,CABAC的初始状态是一致的,如果忘记拷贝,使用的时上个候选更新过的CABAC状态,就会出现不一致的情况。

同时也要保存最优候选的CABAC状态,如果没有保存也会出现不一致。

在估计码率时需要对某些flag进行bits估计,估计的过程会更新对应ctxIdx的CABAC状态,如果少估计了或者多估计了一次或者多次,也会导致CABAC状态的不一致。

解决方案

当出现不一致时,在Debug模式下会触发ASSERT,这个时候可以看到当前出错误的CTU index,以及不一致的CABAC状态的ctxIdx(一般可以关闭WPP和SAO,这样比较好定位是哪个CTU index)。这样我们可以在check每个cu模式之前打印state[ctxIdx]的值,再打印出encode每个cu时state[ctxIdx]的值,找到第一个不一致的cu,然后再Debug确定具体哪个地方改变了state[ctxIdx]的值。

多媒体指令集SIMD优化入门

以下内容翻译自:
Practical SIMD Programing–Jacco Bikker 2017
Basics of SIMD Programming

SIMD 操作能够用一条指令处理多个数据,广泛用于多媒体应用中的 3D 图形和音频/视频处理。SIMD全称Single Instruction Multiple Data,单指令多数据流,能够复制多个操作数,并把它们打包在大型寄存器的一组指令集。一条指令操作多个数据.是CPU基本指令集的扩展,也就是说一次运算指令可以执行多个数据流,这样在很多时候可以提高程序的运算速度。

1 SIMD Concepts

SIMD 是 Single Instruction Multiple Data 的缩写,而 SIMD 操作一词是指一种计算方法,可以用一条指令处理多个数据。相比之下,使用一条指令来处理每个单独数据的传统顺序方法称为标量操作。

以一个简单的求和为例,标量和 SIMD 操作之间的区别如下所示。

对于传统的标量运算,必须依次执行四个加法指令才能获得如图  (a) 所示的和。同时,SIMD 仅使用一条加法指令即可达到相同的结果,如图 (b) 所示。SIMD 操作需要更少的指令来处理给定的大量数据,其效率高于标量操作。

SIMD 操作不能用于以不同方式处理多个数据。图 2.3 给出了一个典型的例子,其中一些数据要相加,而另一些数据要减去、相乘或相除。

CPU 使用寄存器来存储要操作的数据。典型的寄存器存储 32 或 64 位,并保存单个标量值。CPU 指令通常对两个操作数进行操作。考虑以下代码片段:

vec3 velocity = GetPlayerSpeed();
float length = velocity.Length();

计算该向量长度需要大量的标量操作:

x2 = velocity.x * velocity.x
y2 = velocity.y * velocity.y
z2 = velocity.z * velocity.z
sum = x2 + y2
sum = sum + z2
length = sqrtf( sum )

矢量寄存器存储 4 个 (SSE) 或 8 个 (AVX) 标量。这意味着 C++ 向量在汇编程序级别仍然是一个向量:我们不是将三个单独的值存储在三个寄存器中,而是将四个值(x、y、z 和一个虚拟值)存储在一个向量寄存器中。而且,我们不是分别对 x、y 和 z 进行平方,而是使用单个 SIMD 指令对三个值(以及虚拟值)进行平方。

这个简单示例说明了我们在编写 SIMD 代码时需要处理的一些问题:

  • 在对三分量向量进行操作时,我们没有使用向量处理器的全部计算潜力:我们浪费了 SIMD 寄存器中 25%(对于 SSE)或 62.5%(对于 AVX)的“槽”。
  • 在向量寄存器中存储三个标量不是免费的:成本取决于我们稍后将讨论的许多因素。这给计算增加了一些开销。
  • 最后一行的平方根仍然对单个值执行。因此,尽管这是最昂贵的线路,但它并没有从矢量硬件中受益,从而限制了我们的收益。

有一种可靠的方法可以减轻这些担忧。假设我们的应用程序实际上是一个四人游戏:

for( int i = 0; i < 4; i++ )
{
   vec3 velocity = GetPlayerSpeed();
   float length = velocity.Length();
}

在这种情况下,我们可以同时对四个向量进行操作:

x4 = GetPlayerXSpeeds();
y4 = GetPlayerYSpeeds();
z4 = GetPlayerZSpeeds();
x4squared = x4 * x4;
y4squared = y4 * y4;
z4squared = z4 * z4;
sum4 = x4squared + y4squared;
sum4 = sum4 + z4squared;
length4 = sqrtf4( sum4 );

请注意,我们已将 C++向量概念与 SIMD 向量完全解耦:我们只需使用 SIMD 向量并行执行原始标量功能四次。现在每一行都使用一条 SIMD 指令,效率为 100%(当然,我们需要 8 名玩家来进行 AVX ……),甚至现在计算平方根也是为了四个数字。

这里需要注意一件重要的事情:为了使前三行有效,玩家速度必须已经以“SIMD-friendly”格式存储,即:xxxx、yyyy、zzzz。像这样组织的数据可以直接复制到向量寄存器中。

这也意味着我们不可能期望编译器自动为我们执行此操作。高效的 SIMD 代码需要高效的数据布局;这必须手动完成。

2 Data Parallelism

具有四个玩家速度的示例将浪费 AVX 机器上 50% 的计算潜力。显然,我们需要更多的工作。高效的 SIMD 代码需要大量数据并行性,其中针对大量输入执行一系列操作。达到 100% 的效率要求输入数组大小是 4 或 8 的倍数;然而,对于任何重要的输入数组大小,我们都非常接近这个最佳值,并且 AVX 性能只是 SSE 性能的两倍。

对于数据并行算法,SIMD 寄存器中的每个标量都保存一个“线程”的数据。我们调用寄存器通道中的插槽。输入数据称为流。

如果您是 C++ 程序员,您可能熟悉基本类型:char、short、int、float 等。它们中的每一个都有特定的大小:char 为 8 位,short 为 16 位,int 和 float 为 32 位。位只是位,因此 float 和 int 之间的区别在于解释。这允许我们做一些讨厌的事情:

int a;
float& b = (float&)a;

这将创建一个整数和一个指向 a 的浮点引用。由于变量 a 和 b 现在占用相同的内存位置,因此更改 a 会更改 b,反之亦然。实现此目的的另一种方法是使用union:

union { int a; float b; };

同样,a 和 b 驻留在同一内存位置。这是另一个例子:

union { unsigned int a4; unsigned char a[4]; };

这一次,一个由四个字符组成的小数组与 32 位整数值 a4 重叠。我们现在可以通过数组 a[4] 访问 a4 中的各个字节。请注意,a4 现在基本上有四个 1 字节的“通道”,这有点类似于我们使用 SIMD 得到的。我们甚至可以将 a4 用作 32 个 1 位值,即存储 32 个布尔值。

SSE 寄存器大小为 128 位,如果用于存储四个浮点数,则命名为 __m128,对于整数,则命名为 __m128i。为方便起见,我们将 __m128 发音为“quadfloat”,将 __m128i 发音为“quadint”。AVX 版本是 __m256(’octfloat’)和 __m256i(’octint’)。为了能够使用 SIMD 类型,我们需要包含一些头文件:

#include "nmmintrin.h" // for SSE4.2
#include "immintrin.h" // for AVX

一个 __m128 变量包含四个浮点数,所以我们可以再次使用union:

union { __m128 a4; float a[4]; };

现在我们可以方便地访问 __m128 向量中的各个浮点数。

我们也可以直接创建 quadfloat:

__m128 a4 = _mm_set_ps( 4.0f, 4.1f, 4.2f, 4.3f );
__m128 b4 = _mm_set_ps( 1.0f, 1.0f, 1.0f, 1.0f );

要将它们加在一起,我们使用 _mm_add_ps:

__m128 sum4 = _mm_add_ps( a4, b4 );

__mm_set_ps 和 _mm_add_ps 关键字为内置函数。SSE 和 AVX 内置函数都编译为一条汇编指令;使用这些意味着我们实际上是直接在我们的程序中编写汇编代码。几乎每个标量操作都有一个内置函数:

_mm_sub_ps( a4, b4 );
_mm_mul_ps( a4, b4 );
_mm_div_ps( a4, b4 );
_mm_sqrt_ps( a4 );
_mm_rcp_ps( a4 ); // reciprocal

对于 AVX,我们使用类似的内在函数:只需在前面加上 _mm256 而不是 _mm,因此:_mm256_add_ps(a4, b4),等等。

SSE 和 AVX 指令的完整概述可以在这里找到:

https://software.intel.com/sites/landingpage/IntrinsicsGuide/

您可以放心地假设 2000 年之后生产的任何 CPU 都支持最高 4.2 的 SSE。AVX,尤其是 AVX2 是较新的技术;查看 Wikipedia 以获取支持处理器的列表:

https://en.wikipedia.org/wiki/Advanced_Vector_Extensions

3 A Practical Example: C++

以下代码呈现了一个 Mandelbrot 分形:

float scale = 1 + cosf( t );
t += 0.01f;
for( int y = 0; y < SCRHEIGHT; y++ )
{
   float yoffs = ((float)y / SCRHEIGHT - 0.5f) * scale;
   float xoffs = -0.5f * scale, dx = scale / SCRWIDTH;
   for( int x = 0; x < SCRWIDTH; x++, xoffs += dx )
   {
      float ox = 0, oy = 0, py;
      for( int i = 0; i < 99; i++ ) px = ox, py = oy,
         oy = -(py * py - px * px - 0.55f + xoffs),
         ox = -(px * py + py * px - 0.55f + yoffs);
      int r = min( 255, max( 0, (int)(ox * 255) ) );
      int g = min( 255, max( 0, (int)(oy * 255) ) );
      screen->Plot( x, y, (r << 16) + (g << 8) );
} }

请注意,此代码经过了很好的优化,并且计算量很大。我们可以很容易地在多核上运行这段代码:像素之间没有依赖关系,所以这个算法是令人尴尬的并行。但为了获得最佳性能,我们还需要使用指令级并行性。这意味着每个标量操作都应该针对四个输入元素执行。繁重的工作发生在内部循环中,所以如果我们只是优化它,我们应该会看到一个不错的加速。让我们考虑一下我们的选择:内部循环中有循环依赖,所以我们不能并行运行迭代。然而,我们可以并行处理四个像素。

我们现在将逐步将现有的标量代码转换为矢量化代码。我将使用 SSE,但稍作修改后,相同的过程也适用于 AVX。

Step 1:备份原代码

最好的方法是使用 #if 1 … #else … #endif 块。这样原始代码触手可及,万一出现问题,或者仅供参考。

Step 2:创建四个流

我们首先模拟四个流的使用。一次处理四个像素意味着 x 以 4 为步长增加。除此之外,我们需要 ox 和 oy 变量的四个副本,因为现在将针对四个像素并行计算这些副本。

for( int x = 0; x < SCRWIDTH; x += 4, xoffs += dx * 4 )
{
  float ox[4] = { 0, 0, 0, 0 }, oy[4] = { 0, 0, 0, 0 }; 
  for( int lane = 0; lane < 4; lane++ )

内部循环的内容几乎没有改变:我们做同样的工作,但是我们现在对数组元素进行操作,而不是对 ox 和 oy 进行操作:

for( int i = 0; i < 99; i++ ) px = ox[lane], py = oy[lane],
    oy[lane] = -(py * py - px * px - 0.55f + xoffs + lane * dx),
    ox[lane] = -(px * py + py * px - 0.55f + yoffs);

最后,我们需要绘制四个像素。让我们在一个单独的循环中执行此操作,因此我们不能将该循环转换为 SIMD,或者单独进行转换:

for( int lane = 0; lane < 4; lane++ )
{
    int r = min( 255, max( 0, (int)(ox[lane] * 255) ) );
    int g = min( 255, max( 0, (int)(oy[lane] * 255) ) );
    screen->Plot( x + lane, y, (r << 16) + (g << 8) );
}

Step 3:创建 SIMD 数据结构

这是一个简单的步骤:我们已经在 ox[4] 和 oy[4] 中有四个通道的数据,这意味着我们有两组四个浮点数,这正是存储在 quadfloat 中的内容。

union { __m128 ox4; float ox[4]; };
union { __m128 oy4; float oy[4]; };
ox4 = oy4 = _mm_setzero_ps();

最后一行使用内部函数将 128 位向量设置为零。

Step 4:检查功能

我们正在对我们的代码进行一些相当侵入性的更改,因此请定期确保一切仍按预期工作!

Step 5:转换内循环

由于已经准备好流转换,所以最终的转换很简单:

for( int i = 0; i < 99; i++ ) px4 = ox4, py4 = oy4,
    oy4 = -(py4 * py4 – px4 * px4 - 0.55f + xoffs4),
    ox4 = -(px4 * py4 + py4 * px4 - 0.55f + yoffs4);

这段代码不起作用,但它确实让我们清楚地知道我们想去哪里。流上的循环消失了,因为我们现在并行执行这些。ox[lane] 和 oy[lane] 的使用被 ox4 和 oy4 取代。变量 px4 和 py4 现在也应该是 quadfloats。一些问题仍然存在:

  • 一个不是简单地使用 * 运算符将两个四元浮点数相乘; 
  • xoffs4 的内容有点复杂。

关于 xoffs4:变量 xoffs 过去每次迭代都会增加 dx。所以,我们正在寻找的是一个由四个浮点数组成的数组,包含 { xoffs, xoffs + dx, xoffs + 2 * dx, xoffs + 3 * dx }:

__m128 xoffs4 = _mm_set_ps( xoffs, xoffs + dx, xoffs + dx * 2, xoffs + dx * 3 );

变量 yoffs4 对四个像素中的每一个都包含相同的值:

__m128 yoffs4 = _mm_set_ps( yoffs, yoffs, yoffs, yoffs );

剩下的就是操作者了。我们需要用 _mm_mul_ps 替换每个乘法,用 _mm_sub_ps 替换每个减法,等等。让我们为 oy4 执行此操作:

oy4 = -(py4 * py4 - px4 * px4 - 0.55f + xoffs4);

变成

oy4 =
_mm_sub_ps(
    _mm_setzero_ps(),
    _mm_add_ps(
       _mm_sub_ps(
          _mm_sub_ps(
             _mm_mul_ps( py4, py4 ),
             _mm_mul_ps( px4, px4 )
          ),
          _mm_set1_ps( 0.55f )
    ),
xoffs4 ) );

把所有东西放在一起,我们得到了最终的矢量化程序:

for( int y = 0; y < SCRHEIGHT; y++ )
{
    float yoffs = ((float)y / SCRHEIGHT - 0.5f) * scale; float xoffs = -0.5f * scale, dx = scale / SCRWIDTH; for( int x = 0; x < SCRWIDTH; x += 4, xoffs += dx * 4 ) {
    union { __m128 ox4; float ox[4]; };
    union { __m128 oy4; float oy[4]; };
    ox4 = oy4 = _mm_setzero_ps();
    __m128 xoffs4 = _mm_setr_ps( xoffs, xoffs + dx,
                    xoffs + dx * 2, xoffs + dx * 3 );
    __m128 yoffs4 = _mm_set_ps1( yoffs );
    for( int i = 0; i < 99; i++ )
    {
        __m128 px4 = ox4, py4 = oy4;
        oy4 = _mm_sub_ps( _mm_setzero_ps(), _mm_add_ps( _mm_sub_ps(
              _mm_sub_ps( _mm_mul_ps( py4, py4 ), _mm_mul_ps( px4, px4 ) ),
              _mm_set_ps1( 0.55f ) ), xoffs4 ) );
        ox4 = _mm_sub_ps( _mm_setzero_ps(), _mm_add_ps( _mm_sub_ps(
              _mm_add_ps( _mm_mul_ps( px4, py4 ), _mm_mul_ps( py4, px4 ) ),
              _mm_set_ps1( 0.55f ) ), yoffs4 ) );
    }
    for( int lane = 0; lane < 4; lane++ )
    {
        int r = min( 255, max( 0, (int)(ox[lane] * 255) ) );
        int g = min( 255, max( 0, (int)(oy[lane] * 255) ) );
        screen->Plot( x + lane, y, (r << 16) + (g << 8) );
    } 
}

正如所承诺的那样,此代码的运行速度几乎是原始代码的四倍。

4 Conditional Code & SIMD

代码向量化是将现有代码转换为可以并行执行的独立标量流的过程,其中每个任务执行相同的指令。这样,可以使用“单指令多数据”指令同时执行四个或八个(或更多)标量流。

到目前为止,我们矢量化的代码相对简单:图像的所有像素都可以独立计算,以任意顺序计算,也可以并行计算,对于每个像素,我们执行完全相同的指令。但是,如果事情没有那么简单呢?最常见的复杂情况是条件代码:任何涉及 if 语句、条件表达式(例如 a=b>a?a:b),但也包括具有可变迭代次数的循环、switch 语句等。显然,任何有条件的东西都可能导致标量流不执行相同的代码。

考虑我们矢量化 Mandelbrot 示例中的第二个循环:

for( int lane = 0; lane < 4; lane++ )
{
    int r = min( 255, max( 0, (int)(ox[lane] * 255) ) );
    int g = min( 255, max( 0, (int)(oy[lane] * 255) ) );
    screen->Plot( x + lane, y, (r << 16) + (g << 8) );
}

这里使用的 min 和 max 函数隐藏了一些条件代码。Min 可以实现为:

int min( a, b ) { if (a < b) return a; else return b; }

或者使用条件表达式:

#define min(a,b) ((a)<(b)?(a):(b));

对于最小值和最大值的特定情况,SSE 和 AVX 提供了一个有效的解决方案:

__m128 c4 = _mm_min_ps( a4, b4 );
__m128 c4 = _mm_max_ps( a4, b4 );

这些指令的存在有时会导致 SSE 代码超过预期的最佳 400% 效率:条件代码会导致 CPU 延迟,但在 SSE 和 AVX 中,min 和 max 根本不是条件的。

我们现在可以矢量化部分像素绘图循环:

__m128 C4 = _mm_set_ps1( 255.0f );
ox4 = _mm_min_ps( C4, _mm_max_ps( _mm_setzero_ps(), _mm_mul_ps( ox4, C4 ) ) );
oy4 = _mm_min_ps( C4, _mm_max_ps( _mm_setzero_ps(), _mm_mul_ps( oy4, C4 ) ) );
for( int lane = 0; lane < 4; lane++ )
{
    int r = (int)ox[lane];
    int g = (int)oy[lane];
    screen->Plot( x + lane, y, (r << 16) + (g << 8) );
}

请注意,常量 255.0f 存储在一个变量中,因此我们不必执行 _mm_set1_ps 指令四次,而只需执行一次。

事实上,我们可以更进一步:从 float 到 int 的转换也可以使用 SSE 指令完成

union { __m128i tmp1; int oxi[4]; }; tmp1 = _mm_cvtps_epi32( ox4 );
union { __m128i tmp2; int oyi[4]; }; tmp2 = _mm_cvtps_epi32( oy4 );

请注意,union现在组合了一个四元组和一个整数数组。

现在在第二个循环中只剩下一条线,用于绘制像素。plot是surface类的一个方法,实现如下:

void Surface::Plot( int x, int y, Pixel c )
{
    if ((x >= 0) && (y >= 0) && (x < m_Width) && (y < m_Height))
        m_Buffer[x + y * m_Pitch] = c;
}

这里,“Pixel”只是一个 32 位无符号整数,m_Width 和 m_Height 是表面的宽度和高度。if 语句防止像素被绘制到屏幕外。在 Mandelbrot 应用程序中,这永远不会发生,但显然其他应用程序可能需要此功能。

Surface::Plot 的 SSE 版本可能如下所示:

void Surface::Plot4( __m128i x4, __m128i y4, __m128i c4 )
{
  if ((x4 >= 0) && (y4 >= 0) && (x4 < m_Width) && (y4 < m_Height))
        ...
}

这次我们遇到了一个问题。SSE和AVX没有与if语句等效的指令,这是有充分理由的:我们在标量代码中看到的布尔表达式将成为“quadbool”表达式,而条件代码(将某些内容存储在像素缓冲区中)可能必须对任何、部分或所有通道执行。

我刚刚写的SSE和AVX没有if语句,但它们实际上有比较指令。它们不会产生“四布尔”,但会返回一些有用的东西:位掩码。以下是一个例子:

__m128 mask = _mm_cmpge_ps( x4, _mm_setzero_ps() ); // if (x4 >= 0)

此行采用 x4 和一个包含零的 quadfloat,并检查第一个操作数是否大于或等于第二个操作数。对于大于 (_mm_cmpgt_ps)、小于 (_mm_cmplt_ps)、小于或等于 (_mm_cmple_ps)、等于 (_mm_cmpeq_ps) 和不等于 (_mm_cmpne_ps) 存在类似的比较指令。

掩码值为 128 位值。比较后,其内容反映了结果:“假”为 32 个零,“真”为 32 个零。

我们还可以结合比较:

__m128 mask1 = _mm_cmpge_ps( x4, _mm_setzero_ps() ); // if (x4 >= 0)
__m128 mask2 = _mm_cmpge_ps( y4, _mm_setzero_ps() ); // if (y4 >= 0)
__m128 mask = _mm_and_ps( mask1, mask2 ); // if (x4 >= 0 && y4 >= 0)

这些实际上都不是有条件的:我们无条件地计算位掩码。生成的位掩码可以两种不同的方式使用。第一种方法是中断向量指令流,并切换到标量代码来处理比较结果。为此,我们使用 _mm_movemask_ps 指令。该指令采用掩码,并返回一个 4 位值,如果通道的 32 位为 1,则每个位设置为 1,否则设置为 0。现在我们可以单独测试这些位:

int  result = _mm_movemask_ps( mask );
if (result & 1) { ... } // result for first lane is true
if (result & 2) { ... } // result for second lane is true
if (result & 4) { ... } // result for third lane is true
if (result & 8) { ... } // result for fourth lane is true

好处是我们现在至少使用矢量代码进行了比较。但是我们并没有解决实际问题:条件代码仍然破坏了我们的向量流。

为了解决这个问题,我们需要以不同的方式使用掩码:禁用通道的功能。考虑实际的条件代码:

m_Buffer[x + y * m_Pitch] = c;

这一行将一个无符号整数写入屏幕缓冲区中的地址。现在,如果我们将该地址替换为其他安全位置,例如虚拟变量的地址,该怎么办?我们仍然会执行写入,但这次它不会产生可见像素。

让我们考虑一个更实用的解决方案:如果一个像素恰好不在屏幕上,我们将其写入位置 (0,0)。当然,这个像素会包含废话,因为它会被所有屏幕外像素覆盖,但为了这个例子,我们认为这是可以接受的。为了实现这一点,我们将像素地址计算 x + y * m_Pitch 替换为 (x + y * m_Pitch) * 0。无论 x、y 和 m_Pitch 的值是什么,这个等式的结果都是 0。而这种操作正是这些掩码设计的目的。

让我们计算绘图语句的完整掩码:

__m128 mask1 = _mm_cmpge_ps( x4, _mm_setzero_ps() );
__m128 mask2 = _mm_cmpge_ps( y4, _mm_setzero_ps() );
__m128 mask3 = _mm_cmplt_ps( x4, _mm_set_ps1( m_Width ) );
__m128 mask4 = _mm_cmplt_ps( y4, _mm_set_ps1( m_Height ) );
__m128 mask = _mm_and_ps( _mm_and_ps( _mm_and_ps( mask1, mask2 ), mask3 ), mask4 );

我们可以如下计算四个像素地址:

__m128i address4 = _mm_add_epi32( _mm_mullo_epi32( y4, m_Pitch4 ), x4 ); 
address4 = _mm_and_si128( address, *(__m128i*)&mask ) );

关于这些行的几点说明:

  • 两个 32 位整数相乘产生一个 64 位整数,它不适合 32 位通道。_mm_mullo_epi32 指令丢弃前 32 位,在这种情况下很好。
  • 没有_mm_and_epi32指令;而是使用 _mm_and_si128 直接对 128 位进行按位和整数运算。
  • 我们的掩码是一个 quadfloat,而 _mm_and_si128 需要一个 quadint 掩码。因此,我们将其即时转换为正确的类型。
  • 第二行使用计算的掩码将所有屏幕外像素地址重置为 0,正如我们计划的那样。

现在还有一件事要做:将四个像素绘制到存储在 quadint address4 中的地址。我们想要进行的写入被称为分散:四个地址可能彼此相邻,但也可能遍布屏幕。没有支持此功能的 SSE 和 AVX 指令,因此我们唯一的选择是使用四个 32 位写入来执行此操作。尽管这破坏了我们的向量流,但这些都不是有条件的。

最终的 Plot4 方法:

void Surface::Plot4( __m128 x4, __m128 y4, __m128i c4 )
{
    __m128 mask1 = _mm_cmpge_ps( x4, _mm_setzero_ps() );
    __m128 mask2 = _mm_cmpge_ps( y4, _mm_setzero_ps() );
    __m128 mask3 = _mm_cmplt_ps( x4, _mm_set_ps1( (float)m_Width ) );
    __m128 mask4 = _mm_cmplt_ps( y4, _mm_set_ps1( (float)m_Height ) );
    __m128 mask = _mm_and_ps( _mm_and_ps( _mm_and_ps( mask1, mask2 ), mask3 ), mask4 ); union { __m128i address4; int address[4]; };
    __m128i m_Pitch4 = _mm_set1_epi32( m_Pitch );
    __m128i x4i = _mm_cvtps_epi32( x4 );
    __m128i y4i = _mm_cvtps_epi32( y4 );
    address4 = _mm_add_epi32( _mm_mullo_epi32( y4i, m_Pitch4 ), x4i );
    for( int i = 0; i < 4; i++ ) 
        m_Buffer[address[i]] = c4.m128i_i32[i];
}

请注意,该函数现在对 x4 和 y4 采用 quadfloats;这是因为 quadints 的 SSE 指令集比 quadfloats 更受限制。特别是缺少 _mm_cmpge_epi32。可以模拟此功能,但这会使代码不太清晰。

5 Fun with Mask

在上一节中,我们使用 128 位掩码来取消计算。我们通过使用 _mm_and_sil128 使用整数“and”来做到这一点。我们将它应用于包含地址的 quadint 变量(实际上是:从屏幕缓冲区开始的偏移量),但同样的技巧适用于浮点数。为此,我们“abuse”了浮点数 0.0f 的一个有趣属性:它的二进制表示是 32 个零。这意味着如果我们“和”一个具有 32 个零的浮点数,我们将重置其所有位,从而使浮点值变为 0.0f。‘And’ing 与 32 个 1 无关:我们只保留原始浮点数。一个例子:

__m128 mask = ...; // some comparison
a4 = _mm_and_ps( a4, mask );

如果掩码中的相应通道为“false”,则第二行将 quadfloat a4 的通道设置为 0.0f。

根据条件,我们可能想在某些通道上放置零以外的东西。考虑以下条件表达式:

float a = b == 0 ? b : c;

…如果其值为零,则将 a 替换为 b,否则将其替换为 c。一种方法是再次使用掩码:

__m128 mask = _mm_cmpeq_ps( a4, _mm_setzero_ps() );
__m128 part1 = _mm_and_ps( mask, b4 );
__m128 part2 = _mm_andnot_ps( mask, c4 );
a4 = _mm_or_ps( part1, part2 );

在这里,part1 将包含掩码为false的每个通道的零,以及掩码为true的 b4 中的值。Quadfloat part2 使用反转掩码,并从 c4 中选择。请注意,part1 和 part2 没有重叠:如果一个通道在 part1 中不为零,那么它在 part2 中将为零,反之亦然。因此,这两个部分可以安全地混合以获得最终结果。

获得此结果的更直接方法是使用 _mm_blendv_ps 指令:

__m128 mask = _mm_cmpeq_ps( a4, _mm_setzero_ps() );
a4 = _mm_blendv_ps( b4, c4, mask );

_mm_blendv_ps 内在函数根据掩码从 b4 和 c4 中选择值:如果掩码中的值设置为 true,则将选择 c4 中的值,否则将选择 b4 中的值。

6 Optimizating and Debugging SIMD Code

在前面的部分中,我们已经了解了如何对代码进行矢量化,以及如何处理条件代码。在本节中,我们将讨论一些提高 SIMD 代码效率的常见机会。

指令计数:原则上,每个内在函数都编译为单个编译器指令。这意味着更短的源代码会产生更小的程序,大多数情况下运行速度会更快。有时,诸如 _mm_blendv_ps 之类的高级指令可以替代一系列更简单的指令。因此,熟悉可用的说明会很有帮助。

浮点与整数: SSE 和 AVX 中的浮点支持比整数支持要好得多。有时临时转换为浮点数可以使您的代码更高效,即使这意味着您需要稍后再转换回来。浮点运算肯定会让您的生活更轻松:许多整数内在函数非常晦涩(参见例如_mm_mullo_epi32)。

减少 _mm_set_ps 的使用: 在向量化代码中经常需要常量,正如我们在 Mandelbrot 示例中看到的那样。在现场为这些创建quadfloat可能很诱人。但是,_mm_set_ps 是一个昂贵的函数,因为它需要四个操作数。考虑缓存结果:计算循环外的 quadfloat,这样您就可以在循环内多次使用它而不会受到惩罚。同样,如果您需要将标量扩展为 quadfloats(如 Plot 方法中的 m_Pitch),请考虑在类中缓存扩展版本。

避免收集操作:与 _mm_set_ps 相关的另一个陷阱是您提供给它的数据来自分散在内存中的位置。从内存中获取数据到 quadfloat 的最快方法是当它已经作为 quadfloat 存储在内存中时,即 16 个连续字节。

数据对齐:要记住的一件事是,内存中的 quadfloat 必须始终存储在 16 的倍数的地址中。否则将导致崩溃。这就是 C# 对 SSE/AVX 数据使用慢速未对齐读取的原因:C# 不能保证数据对齐。在 C++ 中,在堆栈上创建的变量将自动遵守此规则。然而,使用 new 分配的变量可能未对齐,从而导致意外崩溃。如果您确实遇到了崩溃,请检查正在处理的数据是否正确对齐:(十六进制)地址应始终以零结尾。

C++ 调试器:对 SIMD 的支持很好地集成在 Visual Studio 调试器中。你可以例如轻松检查 SIMD 变量中的各个值。

AVX/AVX2 支持: 如果您的处理器恰好是 AMD 和 Intel 必须提供的最新最好的处理器,请注意您生成的某些代码可能无法在您邻居的笔记本电脑上运行。在 C++ 中,完全有可能生成一个无法运行的 .exe,例如AVX2 不可用。确保牢记目标硬件,或为旧硬件提供替代实现。这个问题的一个例子:Metal Gear V 的早期破解需要一些模糊的 SSE 指令,这些指令在某些 AMD 硬件上不可用,即使该硬件完全能够运行游戏本身。

仅向量化瓶颈:在 Mandelbrot 示例中,我们对 Plot 方法进行了向量化,尽管它只消耗了一小部分时间。不要在现实世界中这样做:矢量化很难,您只想将精力集中在瓶颈上。在 Mandelbrot 示例中,更新 ox 和 oy 的大规模循环是一个很好的示例:大量工作集中在一小部分代码中,急需进行接近金属的优化。

避开花哨的 SIMD 库:矢量化很难,当你打算写 a * b 时,写 _mm_mul_ps(a,b) 感觉很不自然。抵制编写自己的运算符的冲动;习惯原始的内在函数。任何更复杂的东西都必然会隐藏效率低下,甚至引入它们。

优化代码内存访问

以下内容总结自《Intel® 64 and IA-32 Architectures Optimization Reference Manual》

本文内容讨论针对Intel处理器优化代码内存访问的相关技术。主要内容如下:

1 加载和存储执行带宽

通常,加载和存储是代码执行中最频繁的操作,高达 40% 的加载和存储指令并不少见。每一代微架构都提供了多个缓冲区来支持在有指令运行时执行加载和存储操作。这些缓冲区由 Sandy Bridge 和 Ivy Bridge 微架构的 128 位组成。 在 Haswell、Broadwell 和 Skylake Client 微架构中,大小增加到 256 位; 以及 Skylake Server、Cascade Lake、Cascade Lake Advanced Performance 和 Ice Lake 客户端微架构中的 512 位。 为了最大限度地提高性能,最好使用平台中可用的最大宽度。

1.1 在 Sandy Bridge 微架构中利用加载带宽

虽然先前的微架构只有一个加载端口(端口 2),但 Sandy Bridge 微架构可以从端口 2 和端口 3 加载。因此,每个周期可以执行两次加载操作,并使代码的加载吞吐量翻倍。 这改进了读取大量数据并且不需要经常将结果写入内存的代码(端口 3 也处理存储地址操作)。 为了利用此带宽,数据必须保留在 L1 数据缓存中,否则应按顺序访问,从而使硬件预取器能够及时将数据带到 L1 数据缓存中。

考虑以下计算数组所有元素和的 C 代码示例:

int buff[BUFF_SIZE];
int sum = 0;

for (i=0;i<BUFF_SIZE;i++){ 
  sum+=buff[i];
}

示例 1-1 是英特尔编译器为此 C 代码生成的汇编代码。 编译器使用英特尔 SSE 指令对执行进行矢量化。 在此代码中,每个 ADD 操作都使用前一个 ADD 操作的结果。 这将吞吐量限制为每个周期一个加载和 ADD 操作。 示例 1-2 针对 Sandy Bridge 微架构进行了优化,使其能够使用额外的加载带宽。 该代码通过使用两个寄存器来对数组值求和,从而消除了 ADD 操作之间的依赖性。 每个周期可以执行两次加载和两次添加操作。

示例 1-1

xor eax, eax
  pxor xmm0, xmm0
  lea rsi, buff

loop_start:
  paddd xmm0, [rsi+4*rax]
  paddd xmm0, [rsi+4*rax+16]
  paddd xmm0, [rsi+4*rax+32]
  paddd xmm0, [rsi+4*rax+48]
  paddd xmm0, [rsi+4*rax+64]
  paddd xmm0, [rsi+4*rax+80]
  paddd xmm0, [rsi+4*rax+96]
  paddd xmm0, [rsi+4*rax+112]
  add eax, 32
  cmp eax, BUFF_SIZE
  jl loop_start
sum_partials:
  movdqa xmm1, xmm0
  psrldq xmm1, 8
  paddd xmm0, xmm1
  movdqa xmm2, xmm0
  psrldq xmm2, 4
  paddd xmm0, xmm2
  movd [sum], xmm0

示例 1-2

  xor eax, eax
  pxor xmm0, xmm0
  pxor xmm1, xmm1
  lea rsi, buff

loop_start:
  paddd xmm0, [rsi+4*rax]
  paddd xmm1, [rsi+4*rax+16]
  paddd xmm0, [rsi+4*rax+32]
  paddd xmm1, [rsi+4*rax+48]
  paddd xmm0, [rsi+4*rax+64]
  paddd xmm1, [rsi+4*rax+80]
  paddd xmm0, [rsi+4*rax+96]
  paddd xmm1, [rsi+4*rax+112]
  add eax, 32
  cmp eax, BUFF_SIZE
  jl loop_start
sum_partials:
  paddd xmm0, xmm1
  movdqa xmm1, xmm0
  psrldq xmm1, 8
  paddd xmm0, xmm1
  movdqa xmm2, xmm0
  psrldq xmm2, 4
  paddd xmm0, xmm2
  movd [sum], xmm0

1.2 Sandy Bridge 微架构中的 L1D 缓存延迟

L1D 缓存的加载延迟可能会有所不同, 最好的情况是 4 个周期,这适用于使用以下方法之一对通用寄存器进行加载操作:

  • 一个寄存器。
  • 一个基址寄存器加上一个小于 2048 的偏移量。

考虑示例中的指针跟踪代码示例。

示例 1-3: Traversing through indexes

// C code example
index = buffer.m_buff[index].next_index; 
// ASM example
loop:
  shl rbx, 6
  mov rbx, 0x20(rbx+rcx) 
  dec rax
  cmp rax, -1
  jne loop

示例 1-4: Traversing through pointers

// C code example
node = node->pNext;
// ASM example 
loop:
  mov rdx, [rdx] 
  dec rax
  cmp rax, -1 
  jne loop

示例 1-3 通过遍历索引实现指针追踪。 然后编译器生成所示的代码,使用带有偏移量的 base+index 寻址内存。 示例 1-4 显示了编译器从指针解引用代码生成的代码,并且仅使用了一个基址寄存器。在 Sandy Bridge 微架构和之前的微架构中,代码 2 比代码 1 要快。

1.3 处理 L1D 缓存库冲突

在 Sandy Bridge 微架构中,L1D 缓存的内部组织会出现两个加载地址,可能存在库冲突的微操作的情况。当两个加载操作之间存在冲突时,最近的一个将被延迟,直到冲突解决。当两个同时加载操作具有相同的线性地址的第 2-5 位但它们不是来自高速缓存中的同一组(第 6-12 位)时,就会发生库冲突。

只有当代码受加载带宽约束时,才应处理库冲突。一些库冲突不会导致任何性能下降,因为它们被其他性能限制隐藏,消除这种库冲突并不能提高性能。

以下示例演示了库冲突以及如何修改代码并避免它们。它使用两个源数组,其大小是缓存行大小的倍数。当从 A 加载一个元素并从 B 加载对应元素时,这些元素在它们的缓存行中具有相同的偏移量,因此可能会发生存储库冲突。 L1D 缓存库冲突不适用于 Haswell 微架构。

示例 1-5:C Code

int A[128];
int B[128];
int C[128];
for (i=0;i<128;i+=4){
  C[i]=A[i]+B[i]; // the loads from A[i] and B[i] collide
  C[i+1]=A[i+1]+B[i+1];
  C[i+2]=A[i+2]+B[i+2];
  C[i+3]=A[i+3]+B[i+3];
}

示例 1-6: Code with Bank Conflicts

  xor rcx, rcx
  lea r11, A
  lea r12, B
  lea r13, C
loop:
  lea esi, [rcx*4]
  movsxd rsi, esi
  mov edi, [r11+rsi*4]
  add edi, [r12+rsi*4]
  mov r8d, [r11+rsi*4+4]
  add r8d, [r12+rsi*4+4]
  mov r9d, [r11+rsi*4+8]
  add r9d, [r12+rsi*4+8]
  mov r10d, [r11+rsi*4+12]
  add r10d, [r12+rsi*4+12]

  mov [r13+rsi*4], edi
  inc ecx
  mov [r13+rsi*4+4], r8d
  mov [r13+rsi*4+8], r9d
  mov [r13+rsi*4+12], r10d
  cmp ecx, LEN
  jb loop

示例 1-7: Code without Bank Conflicts

 xor rcx, rcx
  lea r11, A
  lea r12, B
  lea r13, C
loop:
  lea esi, [rcx*4]
  movsxd rsi, esi
  mov edi, [r11+rsi*4]
  mov r8d, [r11+rsi*4+4]
  add edi, [r12+rsi*4]
  add r8d, [r12+rsi*4+4]
  mov r9d, [r11+rsi*4+8]
  mov r10d, [r11+rsi*4+12]
  add r9d, [r12+rsi*4+8]
  add r10d, [r12+rsi*4+12]
  
  inc ecx
  mov [r13+rsi*4], edi
  mov [r13+rsi*4+4], r8d
  mov [r13+rsi*4+8], r9d
  mov [r13+rsi*4+12], r10d
  cmp ecx, LEN
  jb loop

2 尽量减少寄存器溢出

当一段代码的实时变量多于处理器可以保存在通用寄存器中的数量时,一种常见的方法是将一些变量保存在内存中。 这种方法称为寄存器溢出。 L1D 缓存延迟的影响会对该代码的性能产生负面影响。 如果寄存器溢出的地址使用较慢的寻址模式,效果会更加明显。

一种选择是将通用寄存器溢出到 XMM 寄存器。 这种方法也可能提高前几代处理器的性能。 以下示例显示如何将寄存器溢出到 XMM 寄存器而不是内存。

示例 2-1:Register spills into memory

loop:
  mov rdx, [rsp+0x18]
  movdqa xmm0, [rdx]
  movdqa xmm1, [rsp+0x20]
  pcmpeqd xmm1, xmm0
  pmovmskb eax, xmm1
  test eax, eax
  jne end_loop
  movzx rcx, [rbx+0x60]

  add qword ptr[rsp+0x18], 0x10
  add rdi, 0x4
  movzx rdx, di
  sub rcx, 0x4
  add rsi, 0x1d0
  cmp rdx, rcx
  jle loop

Register spills into XMM

  movq xmm4, [rsp+0x18]
  mov rcx, 0x10
  movq xmm5, rcx
loop:
  movq rdx, xmm4
  movdqa xmm0, [rdx]
  movdqa xmm1, [rsp+0x20]
  pcmpeqd xmm1, xmm0
  pmovmskb eax, xmm1
  test eax, eax
  jne end_loop
  movzx rcx, [rbx+0x60]

  padd xmm4, xmm5
  add rdi, 0x4
  movzx rdx, di
  sub rcx, 0x4
  add rsi, 0x1d0
  cmp rdx, rcx
  jle loop

3 增强推测执行和内存消歧

在 Intel Core 微架构之前,当代码同时包含存储和加载时,在知道旧存储的地址之前无法发出加载。此规则确保正确处理对先前存储的加载依赖关系。

Intel Core 微架构包含一种机制,允许在存在较旧的未知存储的情况下推测性地执行某些加载。处理器稍后检查加载地址是否与执行加载时地址未知的旧存储重叠。如果地址确实重叠,则处理器重新执行加载和所有后续指令。

示例代码说明了编译器无法确定”Ptr->Array”在循环期间不会改变的情况。因此,编译器不能将”Ptr->Array”作为不变量保存在寄存器中,并且必须在每次迭代中再次读取它。虽然这种情况可以通过重写代码以要求指针地址不变在软件中修复,但内存消歧在不重写代码的情况下提高了性能。

示例 3-1:Loads Blocked by Stores of Unknown Address

// C code
struct AA {
  AA ** Array;
};
void nullify_array ( AA *Ptr, DWORD Index, AA *ThisPtr)
{
  while ( Ptr->Array[--Index] != ThisPtr )
  {
    Ptr->Array[Index] = NULL ;
  } ;
} ;

// Assembly sequence
  nullify_loop:
  mov dword ptr [eax], 0
  mov edx, dword ptr [edi]
  sub ecx, 4
  cmp dword ptr [ecx+edx], esi
  lea eax, [ecx+edx]
  jne nullify_loop

4 存储转发

处理器的内存系统仅在存储失效后将存储发送到内存(包括缓存)。但是,存储数据可以从同一地址从存储转发到后续加载,以缩短存储加载延迟。

存储转发有两种要求。如果违反了这些要求,存储转发将无法发生,加载必须从缓存中获取数据(因此存储必须先将其数据写回缓存)。这会带来很大程度上与底层微架构的管道深度有关的惩罚。

第一个要求与存储转发数据的大小和对齐方式有关。 此限制可能会对整体应用程序性能产生很大影响。 通常,可以防止因违反此限制而导致的性能损失。 存储到加载转发限制因一种微架构而异。 第 4.1 节“存储到加载转发对大小和对齐的限制”中详细讨论了几个导致存储转发停滞的编码缺陷示例以及这些缺陷的解决方案。 第二个要求是数据的可用性,在第 4.2 节“数据可用性的存储转发限制”中进行了讨论。 一个好的做法是消除冗余的加载操作。

可以将临时标量变量保存在寄存器中,而永远不要将其写入内存。 通常,这样的变量不能使用间接指针访问。 将变量移动到寄存器会消除该变量的所有加载和存储,并消除与存储转发相关的潜在问题。 然而,它也增加了套准压力。

加载指令倾向于启动计算链。 由于乱序引擎是基于数据依赖的,因此加载指令对引擎的高速执行能力起着重要作用。 消除加载指令应该是高度优先的。

如果一个变量从存储到再次使用之间没有变化,则可以复制或直接使用之前存储的寄存器。 如果寄存器压力太大,或者在存储和第二次加载之前调用了一个看不见的函数,则可能无法消除第二次加载。

尽可能在寄存器中而不是在堆栈中传递参数。 在堆栈上传递参数需要存储然后重新加载。 虽然此序列在硬件中通过直接从内存顺序缓冲区向加载提供值而在硬件中进行了优化,如果存储转发限制允许,则无需访问数据缓存,但浮点值会在转发过程中产生显着延迟。 在(最好是 XMM)寄存器中传递浮点参数应该可以节省这种长延迟操作。

参数传递约定可能会限制哪些参数在堆栈上传递,哪些参数在寄存器中传递。 但是,如果编译器可以控制整个二进制文件的编译(使用整个程序优化),则可以克服这些限制。

4.1 Store-to-Load-Forwarding 大小和对齐限制

存储转发的数据大小和对齐限制适用于基于 Intel Core 微架构、Intel Core 2 Duo、Intel Core Solo 和 Pentium M 处理器的处理器。 对于较短的流水线机器,违反存储转发限制的性能损失较小。

存储转发限制因每个微架构而异。 以下规则有助于满足存储转发的大小和对齐限制:

  • 规则1:从存储转发的加载必须具有相同的地址起点,因此与存储数据具有相同的对齐方式。
  • 规则2:从存储转发的加载数据必须完全包含在存储数据中。

从存储转发的加载必须等待存储的数据写入存储缓冲区才能继续,但其他不相关的加载不需要等待。

  • 规则3:如果需要提取存储数据的未对齐部分,请读出完全包含数据的最小对齐部分,并根据需要 shift/mask 数据。 这比招致存储转发失败的惩罚要好。
  • 规则4:通过根据需要使用单个大型读取和注册副本,避免在将大型存储到同一内存区域之后进行几次小型加载。

示例 4-1 描述了几种存储转发情况,其中小加载跟随大存储。 前三个加载操作说明了规则 4 中描述的情况。但是,最后一个加载操作从存储转发中获取数据没有问题。

示例 4-1:Situations Showing Small Loads After Large Store

mov [EBP],‘abcd’
mov AL, [EBP] ; Not blocked - same alignment
mov BL, [EBP + 1] ; Blocked
mov CL, [EBP + 2] ; Blocked
mov DL, [EBP + 3] ; Blocked
mov AL, [EBP] ; Not blocked - same alignment
              ; n.b. passes older blocked loads

示例 4-2 说明了存储转发情况,其中大加载跟随几个小存储。 加载操作所需的数据无法转发,因为需要转发的所有数据都没有包含在存储缓冲区中。 在小存储到同一内存区域后避免大加载。

示例 4-2:Non-forwarding Example of Large Load After Small Store

mov [EBP], ‘a’
mov [EBP + 1], ‘b’
mov [EBP + 2], ‘c’
mov [EBP + 3], ‘d’
mov EAX, [EBP] ; Blocked
    ; The first 4 small store can be consolidated into
    ; a single DWORD store to prevent this non-forwarding
    ; situation.

示例 4-3 说明了可能出现在编译器生成的代码中的停滞存储转发情况。 有时,编译器会生成类似于示例 3 中所示的代码来处理溢出的字节到堆栈并将字节转换为整数值。

示例 4-3:A Non-forwarding Situation in Compiler Generated Code

mov DWORD PTR [esp+10h], 00000000h
mov BYTE PTR [esp+10h], bl
mov eax, DWORD PTR [esp+10h] ; Stall
and eax, 0xff ; Converting back to byte value

示例 4-5 提供了两种替代方案来避免示例 3 中所示的非转发情况。

示例 4-5:Two Ways to Avoid Non-forwarding Situation in Example 3

; A. Use MOVZ instruction to avoid large load after small
; store, when spills are ignored.
movz eax, bl ; Replaces the last three instructions
; B. Use MOVZ instruction and handle spills to the stack
mov DWORD PTR [esp+10h], 00000000h
mov BYTE PTR [esp+10h], bl
movz eax, BYTE PTR [esp+10h] ; Not blocked

在内存位置之间移动小于 64 位的数据时,64 位或 128 位 SIMD 寄存器移动效率更高(如果对齐),可用于避免未对齐的加载。 尽管浮点寄存器允许一次移动 64 位,但浮点指令不应用于此目的,因为数据可能会被无意修改。

示例 4-5:Large and Small Load Stalls

; A. Large load stall
mov mem, eax ; Store dword to address “MEM"
mov mem + 4, ebx ; Store dword to address “MEM + 4"
fld mem ; Load qword at address “MEM", stalls
; B. Small Load stall
fstp mem ; Store qword to address “MEM"
mov bx, mem+2 ; Load word at address “MEM + 2", stalls
mov cx, mem+4 ; Load word at address “MEM + 4", stalls

在第一种情况 (A) 中,在对同一内存区域(从内存地址 MEM 开始)进行一系列小存储之后,会出现大加载。 大加载将停止。

FLD 必须等待存储写入内存,然后才能访问所需的所有数据。 这种停顿也可能发生在其他数据类型中(例如,当存储字节或字,然后从同一内存区域读取字或双字时)。

在第二种情况 (B) 中,在大存储到同一内存区域(从内存地址 MEM 开始)之后,会有一系列小加载。 小加载将停止。

字加载必须等待四字存储写入内存,然后才能访问所需的数据。 这种停顿也可能发生在其他数据类型中(例如,当存储双字或字,然后从同一内存区域读取字或字节时)。 这可以通过将商店尽可能远离加载来避免。

4.2

要存储的值必须在加载操作完成之前可用。 如果违反此限制,加载的执行将被延迟,直到数据可用。 这种延迟会导致一些执行资源被不必要地使用,这可能会导致相当大但不确定的延迟。 然而,这个问题的整体影响远小于违反尺寸和对齐要求的影响。

在现代微架构中,硬件预测加载何时依赖并从之前的存储中获取数据。 这些预测可以显着提高性能。 但是,如果在它所依赖的存储之后过早地安排加载,或者如果要存储的数据的生成被延迟,则可能会产生重大损失。

数据通过内存传递有几种情况,可能需要将存储与加载分开:

  • 溢出、保存和恢复堆栈帧中的寄存器。
  • 参数传递。
  • 全局变量和 volatile 变量。
  • 整数和浮点之间的类型转换。
  • 当编译器不分析内联代码时,强制内联代码接口中涉及的变量位于内存中,从而创建更多内存变量并防止消除冗余负载。

如果可以在不招致其他惩罚的情况下,请优先考虑将变量分配给寄存器,例如在寄存器分配和参数传递中,以最大限度地减少存储转发问题的可能性和影响。 尽量不要存储转发从长延迟指令生成的数据 – 例如,MUL 或 DIV。 避免为具有最短存储加载距离的变量存储转发数据。 避免为具有许多 and/or 长依赖链的变量存储转发数据,尤其是避免在循环携带的依赖链上包含存储转发。示例 4-6 展示了一个循环携带的依赖链的例子。

示例 4-6:Loop-carried Dependence Chain

for ( i = 0; i < MAX; i++ ) {
  a[i] = b[i] * foo;
  foo = a[i] / 3;
} // foo is a loop-carried dependence.

尽早计算存储地址以避免存储块加载。

5 数据布局优化

填充源代码中定义的数据结构,以便每个数据元素都与自然操作数大小的地址边界对齐。如果操作数打包在 SIMD 指令中,则与打包元素大小(64 位或 128 位)对齐。

通过在结构和数组内部提供填充来对齐数据。 程序员可以重新组织结构和数组,以尽量减少填充浪费的内存量。 但是,编译器可能没有这种自由。 例如,C 编程语言指定结构元素在内存中的分配顺序。

示例 5-1 显示了如何重新排列数据结构以减小其大小。

示例 5-1:Rearranging a Data Structure

struct unpacked { /* Fits in 20 bytes due to padding */
  int a;
  char b;
  int c;
  char d;
  int e;
};
struct packed { /* Fits in 16 bytes */
  int a;
  int c;
  int e;
  char b;
  char d;
}

64 字节的高速缓存行大小会影响流应用程序(例如多媒体)。 这些在丢弃数据之前仅引用和使用一次数据。 稀疏地利用高速缓存行内的数据的数据访问会导致系统内存带宽的利用效率降低。 例如,可以将结构数组分解为多个数组以实现更好的打包,如例 5-2 所示。

示例 5-2:Decomposing an Array

struct { /* 1600 bytes */
  int a, c, e;
  char b, d;
} array_of_struct [100];
struct { /* 1400 bytes */
  int a[100], c[100], e[100];
  char b[100], d[100];
} struct_of_array;
struct { /* 1200 bytes */
  int a, c, e;
} hybrid_struct_of_array_ace[100];
struct { /* 200 bytes */
  char b, d;
} hybrid_struct_of_array_bd[100];

这种优化的效率取决于使用模式。 如果结构的元素全部一起访问,但数组的访问模式是随机的,那么 ARRAY_OF_STRUCT 会避免不必要的预取,即使它会浪费内存。

但是,如果数组的访问模式表现出局部性(例如数组索引被扫描),那么具有硬件预取器的处理器将从 STRUCT_OF_ARRAY 预取数据,即使结构的元素被一起访问。

当结构的元素不是以相同的频率访问时,例如当元素 A 的访问频率是其他条目的十倍时,STRUCT_OF_ARRAY 不仅可以节省内存,还可以防止获取不必要的数据项 B、C、D 和E。

使用 STRUCT_OF_ARRAY 还允许程序员和编译器使用 SIMD 数据类型。

请注意,STRUCT_OF_ARRAY 的缺点是需要更多独立的内存流引用。 这可能需要使用更多的预取和额外的地址生成计算。 它还会对 DRAM 页面访问效率产生影响。 另一种方法是 HYBRID_STRUCT_OF_ARRAY 混合了这两种方法。 在这种情况下,仅生成和引用 2 个单独的地址流:1 个用于 HYBRID_STRUCT_OF_ARRAY_ACE,1 个用于 HYBRID_STRUCT_OF_ARRAY_BD。 第二个替代方案还可以防止获取不必要的数据——假设 (1) 变量 A、C 和 E 总是一起使用,以及 (2) 变量 B 和 D 总是一起使用,但与 A、C 和 E 不同时使用 。

混合方法确保:

  • 比 STRUCT_OF_ARRAY 更简单/更少的地址生成。
  • 更少的流,从而减少了 DRAM 页面缺失。
  • 由于流更少,预取更少。
  • 同时使用的数据元素的高效缓存行打包。

尝试安排数据结构,使它们允许顺序访问。如果将数据排列成一组流,则自动硬件预取器可以预取应用程序需要的数据,从而减少有效的内存延迟。 如果以非顺序方式访问数据,则自动硬件预取器无法预取数据。 预取器最多可以识别八个并发流。当心高速缓存行(64 字节)内的错误共享。

6 堆栈对齐

当内存引用拆分缓存线时,会发生对堆栈的未对齐访问的性能损失。这意味着八个空间上连续的未对齐四字访问中有一个总是受到惩罚,类似于四个连续的、未对齐的双四字访问中的一个。

当数据对象超过系统的默认堆栈对齐方式时,对齐堆栈可能是有益的。例如,在32/64位Linux和64位Windows上,默认堆栈对齐为16字节,而32位Windows为4字节。

确保堆栈在与寄存器宽度匹配的最大多字节粒度数据类型边界处对齐。对齐堆栈通常需要使用额外的寄存器来跟踪未知数量的填充区域。在导致跨越缓存线的未对齐内存引用和导致额外的通用寄存器溢出之间存在权衡。实现动态堆栈对齐的汇编级技术可能取决于编译器和特定的操作系统环境。

示例 6-1:Examples of Dynamical Stack Alignment

// 32-bit environment
push ebp ; save ebp
mov  ebp, esp ; ebp now points to incoming parameters
andl esp, $-<N> ;align esp to N byte boundary
sub  esp, $<stack_size>; reserve space for new stack frame
. ; parameters must be referenced off of ebp
mov  esp, ebp ; restore esp
pop  ebp ; restore ebp

// 64-bit environment
sub  esp, $<stack_size +N>
mov  r13, $<offset_of_aligned_section_in_stack>
andl r13, $-<N> ; r13 point to aligned section in stack
. ;use r13 as base for aligned data

如果由于某种原因无法将堆栈对齐64位,则例程应访问该参数并将其保存到寄存器或已知的对齐存储器中,从而只会导致一次惩罚。

7 缓存中的容量限制和别名

在某些情况下,具有给定步幅的地址将竞争内存层次结构中的某些资源。 通常,缓存被实现为具有多种方式的集合关联性,每种方式由多组缓存行(或某些情况下的扇区)组成。 多个内存引用在缓存中竞争同一组的每个方式可能会导致容量问题。 有适用于特定微架构的别名条件。 请注意,一级缓存行是 64 字节。 因此,在别名比较中不考虑最低有效 6 位。

8 混合代码和数据

英特尔处理器对指令的主动预取和预解码有两个相关影响:

  • 根据英特尔体系结构处理器的要求,自修改代码可以正常工作,但会导致严重的性能损失。尽可能避免自我修改代码。
  • 在代码段中放置可写数据可能无法与自修改代码区分开来。代码段中的可写数据可能会受到与自修改代码相同的性能损失。

如果(希望是只读的)数据必须与代码出现在同一页上,请避免将其直接放在间接跳转之后。例如,跟随一个间接跳转及其最可能的目标,并将数据放在一个无条件分支之后。

在极少数情况下,将代码页上的数据作为指令执行可能会导致性能问题。当执行遵循不驻留在跟踪缓存中的间接分支时,很可能会发生这种情况。如果这明显导致性能问题,请尝试将数据移到其他位置,或在间接分支后立即插入非法操作码或暂停指令。请注意,后两种备选方案在某些情况下可能会降低性能。

始终将代码和数据放在单独的页面上。尽可能避免自我修改代码。如果要修改代码,请尝试一次完成所有操作,并确保执行修改的代码和被修改的代码位于单独的4kb页面或单独对齐的1kb子页面上。

8.1 自修改代码(Self-modifying Code)

在 Pentium III 处理器和之前的实现上正确运行的自修改代码(SMC)将在后续实现上正确运行。当需要高性能时,应避免SMC和交叉修改代码(当多处理器系统中的多个处理器写入代码页时)。

软件应避免写入正在执行的同一个1KB子页面中的代码页,或获取正在写入的同一个2KB子页面中的代码。此外,将包含直接或推测执行代码的页面作为数据页面与另一个处理器共享可能会触发SMC条件,从而导致机器的整个管道和跟踪缓存被清除。这是由于自修改代码条件造成的。

如果写入的代码在作为代码访问数据页之前填充了该页,则动态代码不必导致SMC情况。动态修改的代码(例如,来自目标修复)可能会受到SMC条件的影响,应尽可能避免。通过引入间接分支和使用register间接调用在数据页(而不是代码页)上使用数据表来避免这种情况。

8.2 位置无关代码

位置无关的代码通常需要获取指令指针的值。示例8-1a显示了一种通过发出不带匹配RET的调用将IP值放入ECX寄存器的技术。示例8-1b显示了另一种使用匹配的CALL/RET对将IP值放入ECX寄存器的技术。

示例 8-1:Instruction Pointer Query Techniques

a) Using call without return to obtain IP does not corrupt the RSB
    call _label; return address pushed is the IP of next instruction
_label:
    pop ECX; IP of this instruction is now put into ECX
b) Using matched call/ret pair
    call _lblcx;
    ... ; ECX now contains IP of this instruction
    ...
_lblcx
    mov ecx, [esp];
    ret

9 写组合

写组合(WC)通过两种方式提高性能:

  • 在一级缓存的写未命中时,它允许在缓存线从缓存/内存层次结构的更外层读取所有权(RFO)之前,对同一缓存线进行多个存储。然后读取行的其余部分,并将尚未写入的字节与返回行中未修改的字节组合。
  • 写入组合允许在高速缓存层次结构中将多个写入组合并作为一个单元进一步写入。 这节省了端口和总线流量。节省流量对于避免部分写入未缓存的内存尤为重要。

基于英特尔 Core 微架构的处理器在每个内核中有八个写入组合缓冲区。 从 Nehalem 微架构开始,有 10 个缓冲区可用于写入组合。 从 Ice Lake 客户端微架构开始,有 12 个缓冲区可用于写入组合。

如果内部循环写入超过四个数组(四个不同的缓存行),则应用循环分裂来分解循环体,以便在每个结果循环的每次迭代中只写入四个数组。

写组合缓冲区用于所有内存类型的存储。 它们对于对未缓存内存的写入特别重要:对同一缓存行的不同部分的写入可以分组到单个完整的缓存行总线事务中,而不是像多个部分写入那样通过总线(因为它们没有被缓存) . 避免部分写入会对受总线带宽限制的图形应用程序产生重大影响,其中图形缓冲区位于未缓存的内存中。 将对未缓存内存的写入和对回写内存的写入分离到单独的阶段可以确保写入组合缓冲区可以在被其他写入流量驱逐之前填满。 已发现消除部分写入事务对某些应用程序的性能影响约为 20%。 因为高速缓存行是 64 字节,所以写入总线 63 字节将导致部分总线事务。

在编写同时在两个线程上执行的函数时,减少内部循环中允许的写入次数将有助于充分利用写入组合存储缓冲区。

存储顺序和可见性也是写入组合的重要问题。 当对先前未写入的高速缓存行的写入组合缓冲区进行写入时,将发生读取所有权 (RFO)。 如果后续写入发生在另一个写入组合缓冲区,则可能会为该高速缓存行导致单独的 RFO。 对第一个高速缓存行和写入组合缓冲区的后续写入将被延迟,直到第二个 RFO 得到服务,以保证写入的正确排序可见性。 如果写入的内存类型是写入组合,则不会有 RFO,因为该行没有被缓存,并且没有这样的延迟。

10 局部增强

局部性增强可以减少来自缓存/内存层次结构中的外部子系统的数据流量。这是为了解决这样一个事实,即从外部层面的周期计数来看,访问成本将比从内部层面的成本更高。通常,访问给定缓存级别(或内存系统)的周期成本因不同的微体系结构、处理器实现和平台组件而异。按地区识别相对数据访问成本趋势可能就足够了,而不是按照每个地区、每个处理器/平台实施列出的周期成本的大型数值表,等。一般趋势是,假设数据访问并行度相似,从外部子系统访问数据的成本可能比从缓存/内存层次结构中的直接内部级别访问数据的成本大约高3-10倍。

即使最后一级缓存的缓存未命中率相对于缓存引用的数量可能较低,处理器通常会花费相当大一部分执行时间等待缓存未命中得到服务。通过增强程序的局部性来减少缓存未命中是一个关键的优化。这可以采取几种形式:

  • 阻塞以迭代将适合缓存的数组的一部分(目的是对数据块 [或 tile] 的后续引用将成为缓存命中引用)。
  • 循环交换以避免跨越高速缓存行或页面边界。
  • 循环倾斜以使访问连续。

可以通过对数据访问模式进行排序以利用硬件预取来实现对最后一级缓存的局部性增强。 这也可以采取多种形式:

  • 将稀疏填充的多维数组转换为一维数组,以便内存引用以对硬件预取友好的顺序、小步幅模式发生。
  • 最佳切片大小和形状选择可以通过提高最后一级缓存的命中率和减少硬件预取操作导致的内存流量来进一步改善时间数据局部性。

避免对局部性增强技术起作用的操作很重要。 在访问内存时,无论数据是在缓存中还是在系统内存中,大量使用锁定前缀都会导致很大的延迟。

阻塞、循环交换、循环倾斜和打包等优化技术最好由编译器完成。 优化数据结构以适应一级缓存的一半或二级缓存; 在编译器中打开循环优化以增强嵌套循环的局部性。

优化一半的一级缓存将在每次数据访问的周期成本方面带来最大的性能优势。 如果一级缓存的一半太小不实用,则针对二级缓存进行优化。 针对中间的一点进行优化(例如,针对整个一级缓存)可能不会比针对二级缓存的优化带来实质性的改进。

11 非临时存储总线流量

峰值系统总线带宽由几种类型的总线活动共享,包括读取(从内存)、读取所有权(缓存行)和写入。 如果一次将 64 个字节写入总线,则总线写事务的数据传输率会更高。

通常,写入回写 (WB) 内存的总线必须与读取所有权 (RFO) 流量共享系统总线带宽。 非临时存储不需要 RFO 流量; 它们确实需要小心管理访问模式,以确保一次收回 64 个字节(而不是收回多个块)。

尽管由于非临时存储而导致的完整 64 字节总线写入的数据带宽是总线写入 WB 内存的两倍,但传输多个块会浪费总线请求带宽并提供显着降低的数据带宽。 这种差异在示例 11-1 和 11-2 中进行了描述。

示例 11-1:Using Non-temporal Stores and 64-byte Bus Write Transactions

#define STRIDESIZE 256
lea ecx, p64byte_Aligned
mov edx, ARRAY_LEN
xor eax, eax
slloop:
movntps XMMWORD ptr [ecx + eax], xmm0
movntps XMMWORD ptr [ecx + eax+16], xmm0
movntps XMMWORD ptr [ecx + eax+32], xmm0
movntps XMMWORD ptr [ecx + eax+48], xmm0

; 64 bytes is written in one bus transaction
add eax, STRIDESIZE
cmp eax, edx
jl slloop

示例 11-2:On-temporal Stores and Partial Bus Write Transactions

#define STRIDESIZE 256
Lea ecx, p64byte_Aligned
Mov edx, ARRAY_LEN
Xor eax, eax
slloop:
movntps XMMWORD ptr [ecx + eax], xmm0
movntps XMMWORD ptr [ecx + eax+16], xmm0
movntps XMMWORD ptr [ecx + eax+32], xmm0

; Storing 48 bytes results in several bus partial transactions
add eax, STRIDESIZE
cmp eax, edx
jl slloop