一种基于转置的向量三角函数快速查表方法及系统

技术领域

本发明涉及处理器中的数据并行与向量三角函数运算技术，具体涉及一种基于转置的向量三角函数快速查表方法及系统，用于向量三角函数实现中使用的快速向量查表。

背景技术

现代处理器中包含向量处理单元，能够进行数据并行计算，是处理器的重要部件。处理器向量单元的核心是其支持的SIMD指令集(也称为浮点指令集、向量指令集)和向量寄存器。向量寄存器，又称浮点寄存器，相比普通的通用寄存器可以存储多个元素，是运行SIMD指令集的核心存储部件。SIMD指令集的一条SIMD指令可以同时对存储于向量寄存器的多个元素进行操作。具体而言，本文涉及Intel处理器中的SSE2、AVX、AVX2指令集以及Arm处理器中的ADVSIMD：

1、SSE2指令集有16个128位宽的向量寄存器(寄存器被命名为xmm0到xmm15)，每个向量寄存器可以存放2个双精度浮点数或2个64位整数，该指令集提供向量连续加载指令(movapd、movupd指令)用于将指定内存地址处的2个双精度浮点数加载至向量寄存器中，以及向量交错解包指令(unpcklpd、unpckhpd指令)用于将两个向量寄存器的高64位元素或者低64位元素合并存储到一个向量寄存器中。

2、AVX与AVX2指令集有16个256位宽的向量寄存器(寄存器被命名为ymm0到ymm15)，每个向量寄存器可以存放4个双精度浮点数或4个64位整数，该指令集提供向量连续加载指令(vmovapd、vmovupd指令)用于将指定内存地址处的4个双精度浮点数加载至向量寄存器中，以及向量交错解包指令(vunpckhpd、vunpcklpd指令)用于将两个向量寄存器奇数位置双精度浮点数或偶数位置双精度浮点数组合并储存到另外一个向量寄存器中，该指令集还提供了向量置换指令vperm2f128，该指令通过立即数常数的指定将两个向量寄存器的高低128位域进行重组并存储到另一个向量寄存器中，AVX2指令集还额外提供了向量聚合加载指令，可以根据索引向量的指示把多个随机内存地址处的元素一次性加载到一个向量寄存器中。

3、ADVSIMD指令集有32个128位宽的向量寄存器(寄存器被命名为V0到V31或者Q0到Q31)，每个寄存器可以存放2个双精度浮点数或者2个64位整数。该指令集提供了多元素向量连续加载指令(ldp指令与ld2指令)用于将指定内存地址处的4个双精度浮点数加载到两个128位宽向量寄存器中，以及向量交错解包指令(zip1、zip2指令)用于将两个向量寄存器的高64位元素或者低64位元素合并存储到一个向量寄存器中，以及向量元素插入指令(ins指令)用于将指定寄存器的指定元素插入到另一个向量寄存器指定位置中。

SIMD指令集的SIMD内建函数(intrinsics)是SIMD指令集提供的一套C语言接口。SIMD指令集的intrinsics使得程序员可以在C/C++语言中通过其提供的向量变量类型直接使用向量寄存器，以及通过其提供的向量内建函数直接使用对应向量指令。具体而言：

1、SSE2指令集向量intrinsics中提供了__m128d与__m128i向量类型用于直接使用SSE2指令集的向量寄存器，__m128d向量类型存储两个双精度浮点数，__m128i存储两个64位整数。SSE2指令集向量intrinsics中提供了与向量加载指令movapd与movupd对应的向量加载函数_mm_load_pd()与_mm_loadu_pd()，提供了与向量交错解包指令unpcklpd与unpckhpd对应的向量交错解包函数_mm_unpacklo_pd()与_mm_unpackhi_pd()。

2、AVX与AVX2指令集向量intrinsics中提供了__m256d与__m256i向量类型用于直接使用AVX和AVX2指令集的向量寄存器，__m256d向量类型存储四个双精度浮点数，__m256i存储四个64位整数。AVX与AVX2指令集向量intrinsics中提供了与向量加载指令vmovapd与vmovupd对应的向量加载函数_mm256_load_pd()与_mm256_loadu_pd()，提供了与向量交错解包指令vunpcklpd与vunpckhpd对应的向量交错解包函数_mm256_unpacklo_pd()与_mm256_unpackhi_pd()，以及提供了向量置换指令vperm2f128对应的向量置换函数_mm256_permute2f128_pd()。

3、ADVSIMD指令集向量intrinsics中提供了float64x2_t与int64x2_t向量类型用于直接使用ADVSIMD指令集的向量寄存器，float64x2_t与int64x2_t类型向量分别存储了2个双精度浮点数或2个64位整数。ADVSIMD指令集向量intrinsics中提供了与多元素向量加载指令ld2对应的多元素向量加载内建函数vld2_f64()，提供了与向量交错解包指令zip1与zip2对应的内建函数vzip1q_f64()与vzip2q_f64()，但并没有为ldp指令与ins指令提供对应的内建函数。

C/C++内联汇编是C/C++编译器提供的一种语法支持，该语法支持可以在C/C++语言代码中直接插入汇编指令，使C/C++语言代码可以直接调用指定的汇编指令与使用指定的汇编寄存器。C/C++内联汇编使得C/C++语言代码可以使用SIMD指令集中没有对应内建函数的向量指令，比如ADVSIMD指令集中的ins指令与ldp指令。并且由于向量寄存器和intrinsics向量类型是一一对应的，因此在本文的实现中，intrinsics的向量类型与向量寄存器同义，本文的实现中向量既指代了向量寄存器也指代了intrinsics中的向量类型。

访存操作存在空间局部性。现代处理器体系结构使用的存储器系统是一个具有不同容量、成本和访问时间的存储设备的层次结构。靠近CPU的存储设备(比如L1高速缓存)性能更快但容量很低，远离CPU的存储设备(比如主存储器)容量更高但性能更差。空间局部性是指计算机程序最近引用过的内存位置以及周边的内存位置容易被程序再次引用。所以拥有更好空间局部性与时间局部性的程序能避免访存瓶颈从而获得更好的性能。

三角函数实现的过程一般分为规约、近似和重建三个步骤。规约是利用三角函数的对称性与周期性，将任意区间映射到指定的区间里面(比如[0,π/4])。业界常用的规约算法有Cody-Waite规约算法与Payne-Hanek规约算法(这两种规约算法均被广泛使用在标量数学库GNU LIBM与向量数学库SLEEF等常用的基础数学库中)。Cody-Waite规约算法适用于将范围较小的区间(比如[-1.0×e

向量三角函数内部使用SIMD指令实现向量化，根据使用的SIMD指令集的向量宽度，一次向量三角函数调用会同时计算多个浮点操作数，从而获取数倍的性能提升。向量三角函数的实现也分成规约、近似和重建三个步骤，每个步骤都使用SIMD指令实现向量化。向量化后的规约算法针对输入的浮点数向量，对它的每个元素进行规约，向量三角函数使用的规约算法是向量化后的Cody-Waite规约算法与Payne-Hanek规约算法。对应地，向量Payne-Hanek规约算法对浮点向量vx的每个元素进行规约时，会使用向量vx计算生成索引向量，索引向量中每个索引对应vx每个元素需要进行查表操作所需的索引，并使用该索引向量以向量形式进行4次索引单步递增的查表，这种查表方式可以称为向量查表。

向量查表操作由加载指令实现，在SSE2、AVX与ADVSIMD指令集中，向量查表操作缺乏硬件指令支持，所以只能由标量加载指令实现：先将索引向量的所有元素拆分保存到多个标量寄存器中，然后根据这些索引值调用多次标量加载指令把多个内存地址处的浮点数加载到多个标量寄存器，最后将这些标量寄存器的值组合到一个向量寄存器中。具体的，在SSE2与ADVSIMD指令集中向量化Payne-Hanek规约算法需要8次标量加载指令，在AVX指令集中需要16次标量加载指令，这些标量加载指令以及其他额外的拆分与组装向量的指令严重影响了性能。AVX2指令集的向量聚合加载指令根据索引向量中的多个索引偏移量值一次性加载多个非连续内存地址处的数据到向量寄存器中，该指令可以直接用于向量查表，一次向量聚合加载指令便可以进行一次向量查表操作，从而整个向量Payne-Hanek规约算法只需要4次聚合加载指令便可以完成16次查表操作，这无疑极大提升了向量查表的性能。但由于向量聚合加载指令需要从多个随机非连续的地址处进行数据加载，对空间局部性不友好，并且受限于处理器访存部件的性能，与向量连续加载指令相比性能会更差。现有技术《使用SIMD指令的向量函数快速查表法、系统及介质》(中国专利申请号为CN201910561095.7)提供了一种快速的向量查表方法，不需要使用向量聚合加载指令，并且具备良好的空间局部性，可以提供快速的向量查表操作。但该方法受限于动态置换指令(只有AVX2、AVX512F与SVE指令集提供了该指令)的支持以及待查表的大小限制(待查表的数据量需要小于一个向量寄存器的可以保存的数据量)，这导致该方法既无法应用在SSE2、AVX与ADVSIMD指令集中，也无法应用在查表的规模较大的查表操作中。

总之，上述这些情况使得向量三角函数软件实现要么放弃使用向量Payne-Hanek规约算法从而对输入操作数范围区间较大的情况不进行计算(比如Vector-libm和VDT数学库)，要么使用性能非常缓慢的标量加载指令实现向量查表操作(比如Intel的商业数学库VML在SSE2指令集的实现以及开源的SLEEF向量数学库在SSE2与ADVSIMD指令集的实现)，要么在最新的SIMD指令集上使用空间局部性较差的聚合加载指令实现向量查表(比如Intel的商业数学库VML在AVX2指令集与AVX512F指令集的实现，以及SLEEF向量数学库在AVX2、AVX512F与SVE指令集的实现)。这无疑都不是最佳的向量查表实现，并且成为了向量三角函数的性能瓶颈。

发明内容

本发明要解决的技术问题：针对现有技术的上述问题，提供一种基于转置的向量三角函数快速查表方法及系统，本发明旨在减少向量查表操作中加载函数或加载指令的使用次数，且不需要特殊的向量聚合加载指令与动态置换指令的支持，提升向量查表操作以及使用向量查表操作的向量三角函数的性能。

为了解决上述技术问题，本发明采用的技术方案为：

一种基于转置的向量三角函数快速查表方法，包括：

1)输入待查表数组M的基址地址pb和索引向量vi，其中索引向量vi包含VL个偏移量值{i

2)将索引向量vi的VL个偏移量值{i

3)使用向量加载操作，把VL个地址值{p

4)对保存在VL个向量组{tv

5)将4个宽度为VL的向量vr

可选地，步骤1)～步骤5)为基于SSE2指令集实现双精度浮点数向量查表操作，步骤1)中索引向量vi的宽度VL为2，索引向量vi包含2个偏移量值i

可选地，所述使用unpcklpd、unpckhpd指令或对应的_mm_unpacklo_pd()、_mm_unpackhi_pd()内建函数将向量组tv

可选地，步骤1)～步骤5)为基于AVX指令集与AVX2指令集实现双精度浮点数向量查表操作；步骤1)中索引向量vi的宽度VL为4，索引向量vi包含4个偏移量值i

可选地，所述使用vunpcklpd、vunpckhpd指令或对应的_mm256_unpacklo_pd()、_mm256_unpackhi_pd()内建函数将向量组tv

可选地，步骤1)～步骤5)为基于ADVSIMD指令集实现双精度浮点数向量查表操作，步骤1)中索引向量vi的宽度VL为2，索引向量vi包含2个偏移量值i

可选地，所述使用zipl、zip2指令或对应的vziplq_f64()、vzip2q_f64()内建函数将向量组tv

可选地，步骤1)～步骤5)为基于ADVSIMD指令集实现双精度浮点数向量查表操作，步骤1)中索引向量vi的宽度VL为2，索引向量vi包含2个偏移量值i

可选地，步骤1)～步骤5)为基于ADVSIMD指令集实现双精度浮点数向量查表操作，步骤1)中索引向量vi的宽度VL为2，索引向量vi包含2个偏移量值i

此外，本实施例还提供一种基于转置的向量三角函数快速查表装置，包括相互连接的微处理器和存储器，该微处理器被编程或配置以执行所述基于转置的向量三角函数快速查表方法的步骤。

此外，本实施例还提供一种计算机可读存储介质，该计算机可读存储介质中存储有计算机程序，且该计算机程序用于被微处理器编程或配置以实施所述基于转置的向量三角函数快速查表方法的步骤。

和现有技术相比，本发明主要具有下述优点：

1、本发明创新性地设计了向量转置操作，将向量连续加载指令应用在向量三角函数的查表操作中。该方法可以使得向量查表操作无需依赖向量聚散加载指令或者向量动态置换指令，也使得向量查表操作无需拆分成标量加载指令实现。

2、对于没有向量聚散加载指令的SIMD指令集，本发明方法和业界通过拆分成标量加载指令实现向量查表的方法相比，该方法提供了向量化实现，可以成倍减少加载指令使用的次数，从VL*4次(VL是向量中元素的个数)标量加载指令最多可减少为2次向量连续加载指令(ADVSIMD指令集中的双精度浮点数向量查表实现)，最少可减少为4次向量连续加载指令(AVX与SSE2指令集中双精度浮点数向量查表实现)，这无疑大大提升了向量三角函数的性能。

3、对于提供了聚合加载指令的SIMD指令集，本发明方法和业界直接使用向量聚合加载指令实现向量查表的方法相比，该方法使用同样次数向量连续加载指令便可以实现向量查表，但该方法的访存空间局部性更好，所以可以获取更佳的性能提升。

4、本发明方法和现有技术《使用SIMD指令的向量函数快速查表法、系统及介质》(中国专利申请号为CN201910561095.7)的方法相比，不需要依赖动态置换指令，并且不会受到待查表的大小限制。本发明方法只需要使用向量解包指令之类的简单指令进行实现向量转置操作，并且这些指令普遍存在于各种SIMD指令集中，所以该方法拥有更好的适用性。

附图说明

图1为本发明实施例方法的基本流程示意图。

图2为本发明实施例方法的基本原理示意图。

图3为本发明实施例中向量查表操作的基本原理示意图。

图4为本实施例一在SSE2指令集中实现的原理示意图。

图5为本实施例二在AVX指令集和AVX2指令集中实现的原理示意图。

图6为本实施例三在ADVSIMD指令集中使用ldp指令实现的原理示意图。

图7为本实施例四在ADVSIMD指令集中使用ld2指令实现的原理示意图。

具体实施方式

实施例一：

如图1和图2所示，本实施例提供一种基于转置的向量三角函数快速查表方法，包括：

1)输入待查表数组M的基址地址pb和索引向量vi，其中索引向量vi包含VL个偏移量值{i

2)将索引向量vi的VL个偏移量值{i

3)使用向量加载操作，把VL个地址值{p

4)对保存在VL个向量组{tv

参见图2，向量vr

5)将4个宽度为VL的向量vr

图3展示了向量查表操作的基本原理图，索引向量vi的宽度为VL(VL＝simd有效宽度/数据位数)，向量查表操作根据索引向量vi的指示把pb地址处对应的VL个浮点数加载至宽度同为VL的向量Vr中。vr中的元素与索引向量vi保存的偏移量值一一对应，即vi的第i个元素作为偏移量与基址地址pb相加得到需要加载到vr中第i个位置处数据的内存地址。使用Payne-Hanek规约算法的向量三角函数实现会连续使用4次向量查表操作，这4次向量查表操作使用相同的基址地址，并且这4次向量查表使用的索引向量中的各索引值是单步递增的，意味着这4次向量查表操作中每个元素所查的表数据是来自一片连续地址处的四个浮点数。本实施例方法基于这一特征，使用向量连续加载指令与向量转置操作对这4次向量查表操作进行优化。先将索引向量中的偏移量值拆分到标量并与基址地址相加得到VL个地址值，然后使用向量连续加载指令或加载函数分别将这VL个地址处的4个浮点数一次性加载到VL个向量中，最后将这VL个向量的数据转置成向量查表所需的4个宽度为VL的向量vr

需要说明的是，前述步骤1)～步骤5)可以使用汇编语言实现，也可以在C/C++语言中使用向量intrinsics中对应的向量类型与内建函数实现，也可以使用C/C++嵌入汇编的形式混合使用汇编语言与intrinsics函数实现，即一部分使用汇编指令实现，另外一部分使用intrinsics中对应的内建函数实现。

作为一种可选的实施方式，如图4所示，本实施例步骤1)～步骤5)为基于SSE2指令集实现双精度浮点数向量查表操作。

本实施例中，步骤1)中索引向量vi的宽度VL为2(VL＝2)，索引向量vi包含2个偏移量值i

本实施例中，步骤3)包括：使用4次向量加载指令或向量加载函数将地址p

本实施例中，步骤4)包括使用unpcklpd、unpckhpd指令或对应的_mm_unpacklo_pd()、_mm_unpackhi_pd()内建函数将向量组tv

本实施例中，使用unpcklpd、unpckhpd指令或对应的_mm_unpacklo_pd()、_mm_unpackhi_pd()内建函数将向量组tv

此外，本实施例还提供一种基于转置的向量三角函数快速查表装置，包括相互连接的微处理器和存储器，该微处理器被编程或配置以执行前述所述基于转置的向量三角函数快速查表方法的步骤。

此外，本实施例还提供一种计算机可读存储介质，该计算机可读存储介质中存储有计算机程序，且该计算机程序用于被微处理器编程或配置以实施前述所述基于转置的向量三角函数快速查表方法的步骤。

实施例二：

本实施例与实施例一原理基本相同，但是本实施例方法中所基于的指令集有所不同。如图5所示，本实施例步骤1)～步骤5)为基于AVX指令集与AVX2指令集实现双精度浮点数向量查表操作；步骤1)中索引向量vi的宽度VL为4(VL＝4)，索引向量vi包含4个偏移量值i

本实施例中，步骤3)包括：使用4次向量加载指令或向量加载函数将地址p

本实施例中，步骤4)包括：使用vunpcklpd、vunpckhpd指令或对应的_mm256_unpacklo_pd()、_mm256_unpackhi_pd()内建函数将向量组tv

本实施例中，使用vunpcklpd、vunpckhpd指令或对应的_mm256_unpacklo_pd()、_mm256_unpackhi_pd()内建函数将向量组tv

综上所述，本实施例方法包括输入索引向量vi与基址地址pb，将索引向量vi保存的偏移量值拆分到标量中，并与基址地址pb相加得到VL个地址，使用向量加载指令将VL个地址处共VL×4个浮点数加载到VL个向量组中，每个向量组包含对应地址处的4个浮点数，然后将VL个向量组进行转置得到向量长度为VL的向量vr

此外，本实施例还提供一种基于转置的向量三角函数快速查表装置，包括相互连接的微处理器和存储器，该微处理器被编程或配置以执行前述所述基于转置的向量三角函数快速查表方法的步骤。

此外，本实施例还提供一种计算机可读存储介质，该计算机可读存储介质中存储有计算机程序，且该计算机程序用于被微处理器编程或配置以实施前述所述基于转置的向量三角函数快速查表方法的步骤。

实施例三：

本实施例与实施例一原理基本相同，但是本实施例方法中所基于的指令集有所不同。如图6所示，本实施例步骤1)～步骤5)为基于ADVSIMD指令集实现双精度浮点数向量查表操作，步骤1)中索引向量vi的宽度VL为2(VL＝2)，索引向量vi包含2个偏移量值i

本实施例中，步骤3)包括：使用2次ldp指令将地址p

本实施例中，使用zip1、zip2指令或对应的vzip1q_f64()、vzip2q_f64()内建函数将向量组tv

此外，本实施例还提供一种基于转置的向量三角函数快速查表装置，包括相互连接的微处理器和存储器，该微处理器被编程或配置以执行前述所述基于转置的向量三角函数快速查表方法的步骤。

此外，本实施例还提供一种计算机可读存储介质，该计算机可读存储介质中存储有计算机程序，且该计算机程序用于被微处理器编程或配置以实施前述所述基于转置的向量三角函数快速查表方法的步骤。

实施例四：

本实施例与实施例一原理基本相同，但是本实施例方法中所基于的指令集有所不同。如图7所示，本实施例步骤1)～步骤5)为基于ADVSIMD指令集实现双精度浮点数向量查表操作，步骤1)中索引向量vi的宽度VL为2(VL＝2)，索引向量vi包含2个偏移量值i

本实施例中，步骤3)包括：使用2次ld2指令或对应的vld2_f64()内建函数将地址p

本实施例中，步骤4)包括：使用zip1、zip2指令或对应的vziplq_f64()、vzip2q_f64()内建函数将向量组tv

此外，本实施例还提供一种基于转置的向量三角函数快速查表装置，包括相互连接的微处理器和存储器，该微处理器被编程或配置以执行前述所述基于转置的向量三角函数快速查表方法的步骤。

此外，本实施例还提供一种计算机可读存储介质，该计算机可读存储介质中存储有计算机程序，且该计算机程序用于被微处理器编程或配置以实施前述所述基于转置的向量三角函数快速查表方法的步骤。

实施例五：

本实施例与实施例四原理基本相同，其主要区别为步骤4)中将向量组tv

此外，本实施例还提供一种基于转置的向量三角函数快速查表装置，包括相互连接的微处理器和存储器，该微处理器被编程或配置以执行前述所述基于转置的向量三角函数快速查表方法的步骤。

此外，本实施例还提供一种计算机可读存储介质，该计算机可读存储介质中存储有计算机程序，且该计算机程序用于被微处理器编程或配置以实施前述所述基于转置的向量三角函数快速查表方法的步骤。

需要说明的是，前述实施例一～实施例五为本发明基于转置的向量三角函数快速查表方法在部分指令集中的实现实例，基于实施例一的原理以及前述五种实现，本发明方法还可以基于更多的同类指令集实现。

本领域内的技术人员应明白，本申请的实施例可提供为方法、系统、或计算机程序产品。因此，本申请可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机可读存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。本申请是参照根据本申请实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

以上所述仅是本发明的优选实施方式，本发明的保护范围并不仅局限于上述实施例，凡属于本发明思路下的技术方案均属于本发明的保护范围。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理前提下的若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。