Elmanjhg opened a new pull request, #2465: URL: https://github.com/apache/systemds/pull/2465
This adds a new HOP rewrite rule, RewriteMatrixMultChainWithTransOptimization.java, to find the optimal execution plan for matrix multiplication chains containing transposes. Previously, these chains were optimized using a simple heuristic that just pushes transposes down from t(A %*% B) -> t(B) %*% t(A), which fails to be the optimal plan in some instances especially with large matrices. An example would be R = t(A %*% B) %*% C with dimensions A = [16, 23], B = [23, 22], C = [16, 34] which would be according to the old rewrite class solved with (t(B) %*% t(A)) %*% C -> costs: t(B) -> 23*22 + t(A) -> 16 * 23 + t(B) %*% t(A) -> 22*23*16 + [...] %*% C -> 22*16*34 = 20938 FLOPs Optimal would be simply: t(A %*% B) %*% C - costs: A %*% B -> 16*23*22 + t(A %*% B) -> 16*22 + [...] %*% C -> 22*16*34 = 20416 FLOPs - difference gets larger with higher matrix dimensions. To solve this, we applied a DP Algorithm with a Memo Table containing Plans without transposing and Plans containing Transposing subchains calculating wether an algebraic transpose pushdown or direct transpose operation is cheaper. This also includes 24 automated DML test cases asserting intermediate HOP dimensions to validate optimal parenthesization and transpose placement. = 20938 FLOPs Optimal would be simply: t(A %*% B) %*% C - costs: A %*% B -> 16*23*22 + t(A %*% B) -> 16*22 + [...] %*% C -> 22*16*34 = 20416 FLOPs - difference gets larger with higher matrix dimensions. To solve this, we applied a DP Algorithm with a Memo Table containing Plans without transposing and Plans containing Transposing subchains calculating wether an algebraic transpose pushdown or direct transpose operation is cheaper. This also includes 24 automated DML test cases asserting intermediate HOP dimensions to validate optimal parenthesization and transpose placement. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
