在使用this implementation编写表示两个1D缓冲区中的整个矩阵的矩阵类之后,我已经达到了项目中的矩阵乘法部分,并且现在倾向于某些缓存友好的优化。偶然发现两个选项(问题在本页下部):

1)仅在乘法时间内选择块/平铺子矩阵。


在c ++ DLL函数中完成,因此没有函数开销。
由于代码将更加复杂,因此其他优化将难以应用。


2)从子矩阵类(较小的补丁)构建矩阵类,因此通常在子矩阵类上进行乘法。


面向对象的方法为子矩阵的其他优化留出了空间。
C#的对象标头和填充行为可以帮助克服关键的进步吗?
在多次调用之后,函数开销可能会成为问题。


矩阵乘法示例:C = A.B

 A
 1 2 3 4   is used as  1 2    3 4
 4 3 4 2               4 3    4 2
 1 3 1 2
 1 1 1 2               1 3    1 2
                       1 1    1 2


 B
 1 1 1 1  --->         1 1    1 1
 1 1 1 1               1 1    1 1
 1 1 1 1
 1 1 1 1               1 1    1 1
                       1 1    1 1


 Multiplication:       1 2 * 1 1   +   3 4 * 1 1    ==>  upper-left tile of result
                       4 3   1 1       4 2   1 1


                       same for the upper-right of result

                       1 3 * 1 1   +   1 2 * 1 1    ==> lower left tile of result
                       1 1   1 1       1 2   1 1

                       same for lower-right tile of result

        Multiplication is O(n³) but summation is O(n²).


问题:是否有人尝试过(面向功能和面向对象)并进行了性能比较?现在,我没有任何针对缓存的优化的幼稚乘法需要:

 Matrix Size   Single Threaded Time    Multithreaded Time
 * 128x128   :     5    ms                 1ms-5ms(time sample error is bigger)
 * 256x256   :     25   ms                 7     ms
 * 512x512   :     140  ms                 35    ms
 * 1024x1024 :     1.3  s                  260   ms
 * 2048x2048 :     11.3 s                  2700  ms
 * 4096x4096 :     88.1 s                  24    s
 * 8192x8192 :     710  s                  177   s

 Giga-multiplications of variables per second
               Single threaded         Multithreaded           Multi/single ratio
 * 128x128   :     0.42                    2.0 - 0.4               ?
 * 256x256   :     0.67                    2.39                   3.67x
 * 512x512   :     0.96                    3.84                   4.00x
 * 1024x1024 :     0.83                    3.47                   4.18x
 * 2048x2048 :     0.76                    3.18                   4.18x
 * 4096x4096 :     0.78                    2.86                   3.67x
 * 8192x8192 :     0.77                    3.09                   4.01x


(使用32位浮点数,带有avx优化代码的1.4GHz fx8150的平均结果)(Visual Studio C#的Parallel.For()中dll函数中的C ++ avx-intrinsics)

高速缓存未命中,关键步幅和其他不良情况可能会影响上述哪种尺寸的矩阵?您知道如何获得使用内在函数的性能计数器吗?

谢谢您的光临。

编辑:DLL中的内联优化:

 Matrix Size   Single Threaded Time    Multithreaded Time           Multi/Single radio
 * 128x128   :  1     ms(%400)          390us avrage in 10k iterations(6G mult /s)
 * 256x256   :  12    ms(%108 faster)   2     ms   (%250 faster)         6.0x
 * 512x512   :  73    ms(%92 faster)    15    ms   (%133 faster)         4.9x
 * 1024x1024 :  1060  ms(%22 faster)    176   ms   (%48 faster)          6.0x
 * 2048x2048 :  10070 ms(%12 faster)    2350  ms   (%15 faster)          4.3x
 * 4096x4096 :  82.0  s(%7 faster)      22    s    (%9 faster)           3.7x
 * 8192x8192 :  676   s(%5 faster)      174   s    (%2 faster)           4.1x


内联后,较小乘法的阴影性能变得可见。
仍然存在DLL函数C#开销。 1024x1024的情况似乎是缓存丢失的起点。虽然工作仅增加了7倍,但执行时间却增加了15倍。

编辑::本周将尝试使用面向对象方法深入研究Strassen的3层算法。主矩阵将由4个子矩阵组成。然后它们将分别由4个子子组成。然后它们将分别由4个子子子组成。这应该使几乎(8/7)(8/7)(8/7)= +%50加速。如果可行,则将DLL函数转换为补丁优化的函数,这将使用更多的缓存。

最佳答案

将Strassen算法仅应用于一层(例如256x256中的四个为512x512)作为一种面向对象的方法(超类为Strassen,子矩阵为matrix类):

 Matrix Size   Single Threaded Time    Multithreaded Time           Multi/Single radio
 * 128x128   :  **%50 slowdown**        **slowdown**
 * 256x256   :  **%30 slowdown**        **slowdown**
 * 512x512   :  **%10 slowdown**        **slowdown**
 * 1024x1024 :  540   ms(%96 faster)    130   ms   (%35 faster)     4.15
 * 2048x2048 :  7500  ms(%34 faster)    1310  ms   (%79 faster)     5.72
 * 4096x4096 :  70.2  s(%17 faster)     17    s    (%29 faster)     4.13
 * 6144x6144 :          x               68    s
 * 8192x8192 :  outOfMemoryException    outOfMemoryException


DLL函数和C#之间的开销仍然有效,因此小型矩阵无法更快地运行。但是,当有加速时,它总是大于8/7(%14),因为使用较小的块会更好地利用缓存。

将编写一个基准类,该类反复测试Stressen算法的不同叶子大小与朴素的叶子大小,以找到临界大小。 (对于我的系统,它是512x512)。

超类将递归地构建子矩阵树,直到达到512x512的大小,并将对512x512节点使用朴素算法。然后在DLL函数中,修补/阻止算法(将在下周添加)将使其更快一些。但是我不知道如何选择适当的补丁大小,因为我不知道如何获取cpu的缓存行大小。递归Strassen完成后将进行搜索。

我的Strassen算法的实现需要五倍的内存(在上面工作)。

编辑:完成了一些递归操作,并随着resuts的到来更新表。

 Matrix Size   Single Threaded Time    Multithreaded Time
 * 2048x2048 :  x                       872     ms  average(double layer)
 * 2560x2560 :  x                       1527    ms  average(double layer)


并行进行树解析,减少内存占用并引入了完全递归性:

 Matrix Size   Single Threaded Time    Multithreaded Time                         m/s
 * 1024x1024 :  547   ms               123     ms  average(single layer)          4.45x
 * 2048x2048 :  3790  ms               790     ms  average(double layer)          4.79x
 * 4096x4096 :  26.4  s                5440    ms  average(triple layer)          4.85x
 * 8192x8192 :  185   s                38      s   average(quad layer)            4.87x
 * 8192x8192(4GHz):   x                15      s   average(quad layer)            4.87x


每秒乘法(x10 ^ 9):

 Matrix Size   Single Threaded         Multithreaded
 * 1024x1024 :  1.71                   7.64     (single layer)
 * 2048x2048 :  1.73                   8.31     (double layer)
 * 4096x4096 :  1.74                   8.45     (triple layer)
 * 8192x8192 :  1.74                   8.48     (quad layer)
 * 8192x8192(4GHz):   x                21.49    (quad layer)
 Strassen's cpu flops is multiplied by 7/8 for each layer.


刚刚发现,使用价格类似的GPU可以使用opencl在1秒内完成8kx8k。

关于c# - 缓存友好型优化:面向对象的矩阵乘法和函数内平铺矩阵乘法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/17785736/

10-11 22:36
查看更多