相关疑难解决方法(0)

在对不同尺寸的方形矩阵进行一些实验后,出现了一种模式.转换一个大小的矩阵2^n2^n+1总是比转换一个大小的矩阵慢.对于较小的值n,差异并不重要.

然而,在512的值上会出现很大的差异.(至少对我而言)

免责声明:我知道由于元素的双重交换,函数实际上并没有转置矩阵,但它没有任何区别.

遵循代码:

#define SAMPLES 1000
#define MATSIZE 512

#include <time.h>
#include <iostream>
int mat[MATSIZE][MATSIZE];

void transpose()
{
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
   {
       int aux = mat[i][j];
       mat[i][j] = mat[j][i];
       mat[j][i] = aux;
   }
}

int main()
{
   //initialize matrix
   for ( int i = 0 ; …

所以转置矩阵的显而易见的方法是使用:

  for( int i = 0; i < n; i++ )

    for( int j = 0; j < n; j++ )

      destination[j+i*n] = source[i+j*n];

但是我想要一些能利用局部性和缓存阻塞的东西.我正在查找它并且找不到可以执行此操作的代码,但我被告知它应该是对原始的非常简单的修改.有任何想法吗？

编辑:我有一个2000x2000矩阵,我想知道如何使用两个for循环更改代码,基本上将矩阵拆分为我单独转置的块,比如2x2块或40x40块,并查看哪个块大小最有效.

编辑2:矩阵以列主要顺序存储,即对于矩阵

a1 a2    
a3 a4

存储为a1 a3 a2 a4.

(出于测试目的)我编写了一个简单的方法来计算nxn矩阵的转置

void transpose(const size_t _n, double* _A) {
    for(uint i=0; i < _n; ++i) {
        for(uint j=i+1; j < _n; ++j) {
            double tmp  = _A[i*_n+j];
            _A[i*_n+j] = _A[j*_n+i];
            _A[j*_n+i] = tmp;
        }
    }
}

当使用优化级别O3或Ofast时,我期望编译器展开一些循环,这将导致更高的性能,尤其是当矩阵大小是2的倍数(即,每次迭代可以执行双循环体)或类似时.相反,我测量的恰恰相反.2的权力实际上表明执行时间显着增加.

这些尖峰也是64的固定间隔,间隔128更明显,依此类推.每个尖峰延伸到相邻的矩阵大小,如下表所示

size n  time(us)
1020    2649
1021    2815
1022    3100
1023    5428
1024    15791
1025    6778
1026    3106
1027    2847
1028    2660
1029    3038
1030    2613

我使用gcc版本4.8.2编译但是同样的事情发生在clang 3.5上,所以这可能是一些通用的东西？

所以我的问题基本上是:为什么执行时间周期性增加？是否有一些通用的东西与任何优化选项一起出现(就像clang和gcc一样)？如果是这样的优化选项导致了这个？

这怎么可能如此重要,即使O0版本的程序在512的倍数时优于03版本？

编辑:注意此(对数)图中峰值的大小.转换具有优化的1024x1024矩阵实际上花费的时间与在没有优化的情况下转置1300x1300矩阵一样多.如果这是一个缓存故障/页面错误问题,那么有人需要向我解释为什么内存布局对于程序的优化版本是如此显着不同,它失败的功能为2,只是为了恢复高性能稍大的矩阵.缓存故障是否应该创建更多类似步骤的模式？为什么执行时间会再次下降？(为什么优化会创建以前不存在的缓存错误？)

编辑:以下应该是gcc生成的汇编代码

没有优化(O0):

_Z9transposemRPd:
.LFB0:
    .cfi_startproc
    push    rbp …

我碰巧有几次将部分程序与OpenMP并行化,只是为了注意到最终,尽管具有良好的可扩展性,但由于单线程情况的性能较差,大多数预见的加速都会丢失(如果与串行版).

网络上出现的这种行为的常见解释是编译器生成的代码在多线程情况下可能更糟糕.无论如何,我无法在任何地方找到解释为什么装配可能更糟的参考.

那么,我想问问编译器的人是:

多线程可以抑制编译器优化吗？万一,性能怎么会受到影响？

如果它可以帮助缩小问题,我主要对高性能计算感兴趣.

免责声明:正如评论中所述,以下部分答案可能在将来过时,因为它们简要讨论了在提出问题时编译器处理优化的方式.

通过制作四个4x4矩阵并转置每个矩阵,可以实现8x8矩阵的转置.这不是我想要的.

在另一个问题中,一个答案提供了一个解决方案,只需要24个8x8矩阵指令.但是,这不适用于花车.

由于AVX2包含256位寄存器,因此每个寄存器适合8个32位整数(浮点数).但问题是:

如何使用AVX/AVX2转换8x8浮点矩阵,尽可能使用最小的指令？

是否有一种高性能方法可以将 numpy 数组转换为 FORTRAN 有序 ctypes 数组，理想情况下不需要副本，并且不会触发与步幅相关的问题？

import numpy as np\n\n# Sample data\nn = 10000\nA = np.zeros((n,n), dtype=np.int8)\nA[0,1] = 1\n\ndef slow_conversion(A):\n    return np.ctypeslib.as_ctypes(np.ascontiguousarray(A.T))\n\nassert slow_conversion(A)[1][0] == 1\n

仅调用as_ctypes的性能分析：

%%timeit\nnp.ctypeslib.as_ctypes(A)\n

3.35 \xc2\xb5s \xc2\xb1 每个循环 10.5 ns（意味着 \xc2\xb1 标准偏差 7 次运行，每次 100000 次循环）

所提供的（慢速）转换的性能分析

%%timeit\nslow_conversion(A)\n

206 ms \xc2\xb1 每个循环 10.4 ms（平均 \xc2\xb1 标准偏差 7 次运行，每次 1 次循环）

理想的结果是获得与调用类似的性能as_ctypes。

我想为我和我的朋友写一个真正(非常)快速的Sobel算子用于射线追踪器(可以在这里找到源码).以下是我到目前为止所得到的......

首先,假设图像是8位无符号整数数组中逐行的灰度图像存储.

要编写真正的Sobel滤波器,我需要为每个像素计算Gx和Gy.由于原点旁边有6个像素,因此计算出这些数字中的每一个.但SIMD指令允许我处理16或甚至32(AVX)像素.希望运算符的内核具有一些不错的属性,因此我可以通过以下方式计算Gy:

• 减去每个i和i + 2行并将结果存储在某个其他图片(数组)的i + 1行中
• 添加i,i + 1和i + 2列的两倍给出最终图片的i + 1列

我会做同样的(但转置)计算Gx然后添加两张图片.

一些说明:

• 我不关心内存分配,因为一切都将在开始时分配.
• 我可以处理溢出并签署将值除以4的问题(感谢_mm_srli_epi8) (uint8_t >> 2 - uint8_t >> 2) = int7_t //really store as int8_t
int7_t + uint8_t << 1 >> 2 + int7_t = uint8_t
//some precision is lost but I don't care

我面临的真正问题是从行到列.因为我无法将图片加载到SIMD寄存器中.我必须三次翻转图像至少不是吗？

一旦原始图片.然后我可以计算Gx和Gy的第一步,然后翻转结果图片以计算第二步.

所以,这是我的问题:

• 这种实现是一个好主意吗？
• 有没有办法比dumb算法更快地转置数组？(我不这么认为)
• 瓶颈在哪里？(有什么猜测？:P)

我正在使用以下内容在SSE和AVX中编写矩阵向量乘法:

for(size_t i=0;i<M;i++) {
    size_t index = i*N;
    __m128 a, x, r1;
    __m128 sum = _mm_setzero_ps();
    for(size_t j=0;j<N;j+=4,index+=4) {
         a = _mm_load_ps(&A[index]);
         x = _mm_load_ps(&X[j]);
         r1 = _mm_mul_ps(a,x);
         sum = _mm_add_ps(r1,sum);
    }
    sum = _mm_hadd_ps(sum,sum);
    sum = _mm_hadd_ps(sum,sum);
    _mm_store_ss(&C[i],sum);
}

我对AVX使用了类似的方法,但最后,由于AVX没有等效的指令_mm_store_ss(),我用过:

_mm_store_ss(&C[i],_mm256_castps256_ps128(sum));

SSE代码比串行代码的速度提高了3.7.但是,AVX代码比串行代码的速度提高了4.3.

我知道将SSE与AVX一起使用可能会导致问题,但我使用g ++编译了-mavx'标志,这应该删除SSE操作码.

我也可以使用:_mm256_storeu_ps(&C[i],sum)做同样的事情,但加速是一样的.

关于我还能做些什么来提高性能的任何见解？它可以与:performance_memory_bound相关,虽然我不明白该线程的答案.

此外,即使包含"immintrin.h"头文件,我也无法使用_mm_fmadd_ps()指令.我启用了FMA和AVX.

我想学习使用英特尔Haswell CPU微体系结构的并行编程.关于在asm/C/C++ /(任何其他语言)中使用SIMD:SSE4.2,AVX2？你能推荐书籍,教程,网络资源,课程吗？

谢谢!

我有一个4x4字节块,我想使用通用硬件进行转置.换句话说,对于字节AP,我正在寻找最有效(就指令数量而言)的方式

A B C D
E F G H
I J K L
M N O P

至

A E I M
B F J N
C G K O
D H L P

我们可以假设,我有有效指针指向A,E,I,并M在内存中(这样从读取32位将让我的包含整数字节ABCD).

由于对大小和数据类型的限制,这不是此问题的重复.我的矩阵的每一行都可以适合32位整数,我正在寻找可以使用通用硬件快速执行转置的答案,类似于SSE宏的实现_MM_TRANSPOSE4_PS.

如何在没有额外空间的情况下转置前导维度 N 的一维数组？任何语言都可以

我做了一个矩阵类,我想实现一个转置方法:

template<typename T>
void Matrix<T>::Transpose()
{
    // for square matrices
    if(this->Width() == this->Height())
    {
        for(std::size_t y = 1; y < this->Height(); ++y)
        {
            for(std::size_t x = 0; x < y; ++x)
            {
                // the function operator is used to access the entries of the matrix
                std::swap((*this)(x, y), (*this)(y, x));
            }
        }
    }
    else
    {
        // TODO
    }
}

问题是如何在不分配全新矩阵(该类用于大密集矩阵)的情况下实现非平方矩阵的转置方法,而是在其中.还有办法吗？