You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

递归为何导致Strassen-Winograd矩阵乘法处理时间出现不连续性?

Strassen-Winograd矩阵乘法算法的性能断点问题

问题背景

我正在优化Java实现的Strassen-Winograd矩阵乘法算法。根据维基百科对Strassen算法的描述:

若矩阵足够非方形,将初始运算转化为更接近方形的乘积会更划算

因此我通过测量不同矩阵宽高比的计算时间,来确定何种程度的“非方形”会带来过高耗时。但收集数据时发现时间曲线存在不连续性:当宽高比超过约1.28时,算法计算时间陡增约10倍,对应宽高比与计算时间的3D pyplot图。

测试采用的矩阵尺寸为[A X B] * [B X C],其中B为常量,宽高比1为A/B,宽高比2为C/B,A和C为变量。我原本预期改变B值时不连续点会移动,但在B取50、100、200时,该断点位置始终不变。

定位到的问题范围

通过适用于递归函数的自定义计时器,发现跨越该宽高比阈值时,仅函数的递归部分出现性能下降,相关代码如下:

Manix u, v, w;
// u = (A[2] - A[0]) X (B[1] - B[3])
u = A[2].sub(A[0], numberType).fastDot(B[1].sub(B[3], numberType), numberType);
// v = (A[2] + A[3]) X (B[1] - B[0])
v = A[2].add(A[3], numberType).fastDot(B[1].sub(B[0], numberType), numberType);
// w = A[0] X B[0] + (A[2] + A[3] - A[0]) X (B[0] + B[3] - B[1])
w = ABNaught.add(A[2].add(A[3].sub(A[0], numberType), numberType).fastDot(B[0].add(B[3], numberType).sub(B[1], numberType), numberType), numberType);


/* Strassen-Winograd:
 * 
 * |         A[0] X B[0] + A[1] X B[2]              v + w + (A[0] + A[1] - A[2] - A[3]) X B[3] |
 * |                                                                                           |
 * | u + w + A[3] X (B[1] + B[2] - B[0] - B[3])                      u + v + w                 |
 * 
 * Note that A[0] X B[0] is used here and in w, meaning we only have to calculate 7 multiplications instead of 8
*/

Manix[] productLayer = { 
        ABNaught.add(A[1].fastDot(B[2], numberType), numberType), 
        v.add(w, numberType).add(A[0].add(A[1], numberType).sub(A[2], numberType).sub(A[3], numberType).fastDot(B[3], numberType), numberType),
        u.add(w, numberType).add(A[3].fastDot(B[1].add(B[2], numberType).sub(B[0], numberType).sub(B[3], numberType), numberType), numberType), 
        u.add(v, numberType).add(w, numberType)
};

我已测试该部分代码中使用的add和sub函数,未发现异常。目前仅剩fastDot递归调用未排查。原本预期数据呈现平滑曲线,而非不连续状态,仅能推测这与Java的函数调用开销有关,但缺乏确切依据,希望熟悉Java编译器的人士解释该现象。

内容的提问来源于stack exchange,提问作者Fire 'N Lightnin'

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.06.28 21:27:03