c# - 缓存友好优化 : Object oriented matrix multiplication and in-function tiled matrix multiplication

Question

在使用 this implementation 编写了表示两个一维缓冲区中的整个矩阵的矩阵类之后，我已经达到了我项目中的矩阵混合部分，现在倾向于一些缓存友好的优化。偶然发现了两个选项(问题在本页的下半部分):

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

• 在 C++ DLL 函数中完成，因此没有函数开销。
• 由于代码会更复杂，因此更难应用额外的优化。

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

• 面向对象的方法为子矩阵的额外优化留出了空间。
• C# 的对象 header 和填充行为可以帮助克服关键步骤吗？
• 函数开销在调用多次而不是几次后可能会成为问题。

示例矩阵乘法: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

(1.4GHz fx8150 的平均结果，使用 32 位 float 的 avx 优化代码)(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-function-C# 开销。 1024x1024 的情况似乎是缓存未命中的起点。虽然工作量仅增加了 7 倍，但执行时间却增加了 15 倍。

编辑::本周将使用面向对象的方法尝试 Strassen 的 3 层深度算法。主矩阵将由 4 个子矩阵组成。然后他们将分别由4个子子组成。然后他们将分别由4个sub-sub-subs组成。这应该提供接近 (8/7)(8/7)(8/7)= +%50 的加速。如果有效，会将 DLL 函数转换为补丁优化函数，这将使用更多缓存。

Answer 1

将 Strassen 算法仅应用于一层(例如 256x256 中的四层作为 512x512)作为一种面向对象的方法(父类(super class)是 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)，因为使用更小的 block 更有利于缓存使用。

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

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

我对 Strassen 算法的实现需要五倍的内存(正在处理)。

编辑:一些递归已完成，在结果出现时更新表格。

 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.

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