递归为何导致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'
相关产品推荐
相关产品推荐

