1

在使用此实现编写了一个表示两个 1D 缓冲区中的整个矩阵的矩阵类之后 ，我已经在我的项目中达到了矩阵多重乘法部分，并且现在倾向于一些缓存友好的优化。偶然发现了两个选项（问题在此页面的下部）：

1）仅在乘法时间内选择阻塞/平铺子矩阵。

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

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

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

矩阵乘法示例：C=AB

 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-function-C# 开销。1024x1024 的情况似乎是缓存未命中的起点。虽然工作量只增加了七倍，但执行时间却增加到了十五倍。

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

4

1 回答 1

0

将 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 算法的实现需要五倍的内存（正在处理它）。

编辑：一些递归已经完成，随着结果的到来更新表格。

 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。

于 2013-07-23T15:46:40.863 回答