You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@systemds.apache.org by "ReneEnjilian (via GitHub)" <gi...@apache.org> on 2024/01/20 00:57:20 UTC
[PR] Rewrite for Matrix Distributive Property [systemds]
ReneEnjilian opened a new pull request, #1986:
URL: https://github.com/apache/systemds/pull/1986
This pull request implements a simplification rewrite for the input pattern (A%*%B) + (A%*%C). The resulting rewrite is A%*%(B+C). However, for the rewrite to be applied a number of conditions need to be fulfilled. All three matrices A, B, and C have to be dense and certain properties like the number-of-non-zeros (NNZ) need to be available. Further, the rewrite is only applied if the number of floating point operations is actually reduced by the rewrite. Testing has been added.
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Rewrite for Matrix Distributive Property [systemds]
Posted by "Baunsgaard (via GitHub)" <gi...@apache.org>.
Baunsgaard commented on code in PR #1986:
URL: https://github.com/apache/systemds/pull/1986#discussion_r1460114592
##########
src/main/java/org/apache/sysds/hops/rewrite/RewriteAlgebraicSimplificationDynamic.java:
##########
@@ -1137,46 +1138,88 @@ else if( right.getDim2()>1 ) //multi column vector
return hi;
}
-
- private static Hop simplifyDiagMatrixMult(Hop parent, Hop hi, int pos)
- {
- if( hi instanceof ReorgOp && ((ReorgOp)hi).getOp()==ReOrgOp.DIAG && hi.getDim2()==1 ) //diagM2V
+
+ private static Hop simplifyDiagMatrixMult(Hop parent, Hop hi, int pos) {
+ if(hi instanceof ReorgOp && ((ReorgOp) hi).getOp() == ReOrgOp.DIAG && hi.getDim2() == 1) //diagM2V
{
Hop hi2 = hi.getInput().get(0);
- if( HopRewriteUtils.isMatrixMultiply(hi2) ) //X%*%Y
+ if(HopRewriteUtils.isMatrixMultiply(hi2)) //X%*%Y
{
Hop left = hi2.getInput().get(0);
Hop right = hi2.getInput().get(1);
-
+
//create new operators (incl refresh size inside for transpose)
ReorgOp trans = HopRewriteUtils.createTranspose(right);
BinaryOp mult = HopRewriteUtils.createBinary(left, trans, OpOp2.MULT);
AggUnaryOp rowSum = HopRewriteUtils.createAggUnaryOp(mult, AggOp.SUM, Direction.Row);
-
+
//rehang new subdag under parent node
HopRewriteUtils.replaceChildReference(parent, hi, rowSum, pos);
HopRewriteUtils.cleanupUnreferenced(hi, hi2);
-
+
hi = rowSum;
LOG.debug("Applied simplifyDiagMatrixMult");
- }
+ }
}
-
+
return hi;
}
-
- private static Hop simplifySumDiagToTrace(Hop hi)
- {
- if( hi instanceof AggUnaryOp )
- {
+
+ private static Hop simplifyMatrixFactorization(Hop parent, Hop hi, int pos) {
+ // Check for Hop being Binary
+ if(hi instanceof BinaryOp) {
+ Hop left = hi.getInput().get(0);
Review Comment:
i think we can avoid the nested get(0), via hi.getInput(0).
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Rewrite for Matrix Distributive Property [systemds]
Posted by "ReneEnjilian (via GitHub)" <gi...@apache.org>.
ReneEnjilian commented on PR #1986:
URL: https://github.com/apache/systemds/pull/1986#issuecomment-1902260306
thats really good to know (regarding FMA), thanks Matthias.
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Rewrite for Matrix Distributive Property [systemds]
Posted by "mboehm7 (via GitHub)" <gi...@apache.org>.
mboehm7 closed pull request #1986: Rewrite for Matrix Distributive Property
URL: https://github.com/apache/systemds/pull/1986
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Rewrite for Matrix Distributive Property [systemds]
Posted by "ReneEnjilian (via GitHub)" <gi...@apache.org>.
ReneEnjilian commented on PR #1986:
URL: https://github.com/apache/systemds/pull/1986#issuecomment-1902242842
Thanks @mboehm7. I dont really understand why you chose m*n*l (for A%*%B) as the formula for the FLOPs in costOriginal. Shouldnt it be 2*m*n*l ? I will start with SYSTEMDS-3666.
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Rewrite for Matrix Distributive Property [systemds]
Posted by "ReneEnjilian (via GitHub)" <gi...@apache.org>.
ReneEnjilian commented on code in PR #1986:
URL: https://github.com/apache/systemds/pull/1986#discussion_r1460485453
##########
src/main/java/org/apache/sysds/hops/rewrite/RewriteAlgebraicSimplificationDynamic.java:
##########
@@ -1137,46 +1138,88 @@ else if( right.getDim2()>1 ) //multi column vector
return hi;
}
-
- private static Hop simplifyDiagMatrixMult(Hop parent, Hop hi, int pos)
- {
- if( hi instanceof ReorgOp && ((ReorgOp)hi).getOp()==ReOrgOp.DIAG && hi.getDim2()==1 ) //diagM2V
+
+ private static Hop simplifyDiagMatrixMult(Hop parent, Hop hi, int pos) {
+ if(hi instanceof ReorgOp && ((ReorgOp) hi).getOp() == ReOrgOp.DIAG && hi.getDim2() == 1) //diagM2V
{
Hop hi2 = hi.getInput().get(0);
- if( HopRewriteUtils.isMatrixMultiply(hi2) ) //X%*%Y
+ if(HopRewriteUtils.isMatrixMultiply(hi2)) //X%*%Y
{
Hop left = hi2.getInput().get(0);
Hop right = hi2.getInput().get(1);
-
+
//create new operators (incl refresh size inside for transpose)
ReorgOp trans = HopRewriteUtils.createTranspose(right);
BinaryOp mult = HopRewriteUtils.createBinary(left, trans, OpOp2.MULT);
AggUnaryOp rowSum = HopRewriteUtils.createAggUnaryOp(mult, AggOp.SUM, Direction.Row);
-
+
//rehang new subdag under parent node
HopRewriteUtils.replaceChildReference(parent, hi, rowSum, pos);
HopRewriteUtils.cleanupUnreferenced(hi, hi2);
-
+
hi = rowSum;
LOG.debug("Applied simplifyDiagMatrixMult");
- }
+ }
}
-
+
return hi;
}
-
- private static Hop simplifySumDiagToTrace(Hop hi)
- {
- if( hi instanceof AggUnaryOp )
- {
+
+ private static Hop simplifyMatrixFactorization(Hop parent, Hop hi, int pos) {
+ // Check for Hop being Binary
+ if(hi instanceof BinaryOp) {
+ Hop left = hi.getInput().get(0);
Review Comment:
I am using the name simplifyDistributiveMatrixMult() now.
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Rewrite for Matrix Distributive Property [systemds]
Posted by "Baunsgaard (via GitHub)" <gi...@apache.org>.
Baunsgaard commented on code in PR #1986:
URL: https://github.com/apache/systemds/pull/1986#discussion_r1460144152
##########
src/main/java/org/apache/sysds/hops/rewrite/RewriteAlgebraicSimplificationDynamic.java:
##########
@@ -1137,46 +1138,88 @@ else if( right.getDim2()>1 ) //multi column vector
return hi;
}
-
- private static Hop simplifyDiagMatrixMult(Hop parent, Hop hi, int pos)
- {
- if( hi instanceof ReorgOp && ((ReorgOp)hi).getOp()==ReOrgOp.DIAG && hi.getDim2()==1 ) //diagM2V
+
+ private static Hop simplifyDiagMatrixMult(Hop parent, Hop hi, int pos) {
+ if(hi instanceof ReorgOp && ((ReorgOp) hi).getOp() == ReOrgOp.DIAG && hi.getDim2() == 1) //diagM2V
{
Hop hi2 = hi.getInput().get(0);
- if( HopRewriteUtils.isMatrixMultiply(hi2) ) //X%*%Y
+ if(HopRewriteUtils.isMatrixMultiply(hi2)) //X%*%Y
{
Hop left = hi2.getInput().get(0);
Hop right = hi2.getInput().get(1);
-
+
//create new operators (incl refresh size inside for transpose)
ReorgOp trans = HopRewriteUtils.createTranspose(right);
BinaryOp mult = HopRewriteUtils.createBinary(left, trans, OpOp2.MULT);
AggUnaryOp rowSum = HopRewriteUtils.createAggUnaryOp(mult, AggOp.SUM, Direction.Row);
-
+
//rehang new subdag under parent node
HopRewriteUtils.replaceChildReference(parent, hi, rowSum, pos);
HopRewriteUtils.cleanupUnreferenced(hi, hi2);
-
+
hi = rowSum;
LOG.debug("Applied simplifyDiagMatrixMult");
- }
+ }
}
-
+
return hi;
}
-
- private static Hop simplifySumDiagToTrace(Hop hi)
- {
- if( hi instanceof AggUnaryOp )
- {
+
+ private static Hop simplifyMatrixFactorization(Hop parent, Hop hi, int pos) {
+ // Check for Hop being Binary
+ if(hi instanceof BinaryOp) {
+ Hop left = hi.getInput().get(0);
Review Comment:
That would be okay. But the best way ( in my opinion) would be to add a Java doc on the method to specify exactly what it is intended to do.
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Rewrite for Matrix Distributive Property [systemds]
Posted by "j143 (via GitHub)" <gi...@apache.org>.
j143 commented on code in PR #1986:
URL: https://github.com/apache/systemds/pull/1986#discussion_r1460477292
##########
src/main/java/org/apache/sysds/hops/rewrite/RewriteAlgebraicSimplificationDynamic.java:
##########
@@ -1137,46 +1138,88 @@ else if( right.getDim2()>1 ) //multi column vector
return hi;
}
-
- private static Hop simplifyDiagMatrixMult(Hop parent, Hop hi, int pos)
- {
- if( hi instanceof ReorgOp && ((ReorgOp)hi).getOp()==ReOrgOp.DIAG && hi.getDim2()==1 ) //diagM2V
+
+ private static Hop simplifyDiagMatrixMult(Hop parent, Hop hi, int pos) {
+ if(hi instanceof ReorgOp && ((ReorgOp) hi).getOp() == ReOrgOp.DIAG && hi.getDim2() == 1) //diagM2V
{
Hop hi2 = hi.getInput().get(0);
- if( HopRewriteUtils.isMatrixMultiply(hi2) ) //X%*%Y
+ if(HopRewriteUtils.isMatrixMultiply(hi2)) //X%*%Y
{
Hop left = hi2.getInput().get(0);
Hop right = hi2.getInput().get(1);
-
+
//create new operators (incl refresh size inside for transpose)
ReorgOp trans = HopRewriteUtils.createTranspose(right);
BinaryOp mult = HopRewriteUtils.createBinary(left, trans, OpOp2.MULT);
AggUnaryOp rowSum = HopRewriteUtils.createAggUnaryOp(mult, AggOp.SUM, Direction.Row);
-
+
//rehang new subdag under parent node
HopRewriteUtils.replaceChildReference(parent, hi, rowSum, pos);
HopRewriteUtils.cleanupUnreferenced(hi, hi2);
-
+
hi = rowSum;
LOG.debug("Applied simplifyDiagMatrixMult");
- }
+ }
}
-
+
return hi;
}
-
- private static Hop simplifySumDiagToTrace(Hop hi)
- {
- if( hi instanceof AggUnaryOp )
- {
+
+ private static Hop simplifyMatrixFactorization(Hop parent, Hop hi, int pos) {
+ // Check for Hop being Binary
+ if(hi instanceof BinaryOp) {
+ Hop left = hi.getInput().get(0);
Review Comment:
> I just realized that the name of the method simplifyMatrixFactorization() might be misleading because somebody might think we perform a matrix factorization (i.e., [decomposition](https://en.wikipedia.org/wiki/Matrix_decomposition)) instead of factoring out a term (i.e., here matrix A). Should I change the name to something more neutral like simplifyMatrixDistributiveFactorization() ?
@ReneEnjilian -- if you prefer you can call this, may be `MatrixCombineMultiply`. It's up to you. 😺
Factorization has a different meaning!
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Rewrite for Matrix Distributive Property [systemds]
Posted by "mboehm7 (via GitHub)" <gi...@apache.org>.
mboehm7 commented on PR #1986:
URL: https://github.com/apache/systemds/pull/1986#issuecomment-1902171324
Thanks again - during the merge I change the rewrite condition to only apply to binary-plus (not binary in general) and tightened the cost conditions, so the rewrite does not apply for two vector-matrix multiplications (where a large matrix-matrix addition of B+C can be way more costly).
Furthermore, if you're interested contributing to improved rewrites, I created SYSTEMDS-3666 for adding various simplifications for not and comparison operations.
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Rewrite for Matrix Distributive Property [systemds]
Posted by "ReneEnjilian (via GitHub)" <gi...@apache.org>.
ReneEnjilian commented on code in PR #1986:
URL: https://github.com/apache/systemds/pull/1986#discussion_r1460130696
##########
src/main/java/org/apache/sysds/hops/rewrite/RewriteAlgebraicSimplificationDynamic.java:
##########
@@ -1137,46 +1138,88 @@ else if( right.getDim2()>1 ) //multi column vector
return hi;
}
-
- private static Hop simplifyDiagMatrixMult(Hop parent, Hop hi, int pos)
- {
- if( hi instanceof ReorgOp && ((ReorgOp)hi).getOp()==ReOrgOp.DIAG && hi.getDim2()==1 ) //diagM2V
+
+ private static Hop simplifyDiagMatrixMult(Hop parent, Hop hi, int pos) {
+ if(hi instanceof ReorgOp && ((ReorgOp) hi).getOp() == ReOrgOp.DIAG && hi.getDim2() == 1) //diagM2V
{
Hop hi2 = hi.getInput().get(0);
- if( HopRewriteUtils.isMatrixMultiply(hi2) ) //X%*%Y
+ if(HopRewriteUtils.isMatrixMultiply(hi2)) //X%*%Y
{
Hop left = hi2.getInput().get(0);
Hop right = hi2.getInput().get(1);
-
+
//create new operators (incl refresh size inside for transpose)
ReorgOp trans = HopRewriteUtils.createTranspose(right);
BinaryOp mult = HopRewriteUtils.createBinary(left, trans, OpOp2.MULT);
AggUnaryOp rowSum = HopRewriteUtils.createAggUnaryOp(mult, AggOp.SUM, Direction.Row);
-
+
//rehang new subdag under parent node
HopRewriteUtils.replaceChildReference(parent, hi, rowSum, pos);
HopRewriteUtils.cleanupUnreferenced(hi, hi2);
-
+
hi = rowSum;
LOG.debug("Applied simplifyDiagMatrixMult");
- }
+ }
}
-
+
return hi;
}
-
- private static Hop simplifySumDiagToTrace(Hop hi)
- {
- if( hi instanceof AggUnaryOp )
- {
+
+ private static Hop simplifyMatrixFactorization(Hop parent, Hop hi, int pos) {
+ // Check for Hop being Binary
+ if(hi instanceof BinaryOp) {
+ Hop left = hi.getInput().get(0);
Review Comment:
Okay I changed all instances where this occurs. Further, I just realized that the name of the method simplifyMatrixFactorization() might be misleading because somebody might think we perform a matrix factorization (i.e., [decomposition](https://en.wikipedia.org/wiki/Matrix_decomposition)) instead of factoring out a term (i.e., here matrix A). Should I change the name to something more neutral like simplifyMatrixDistributiveFactorization() ?
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Rewrite for Matrix Distributive Property [systemds]
Posted by "mboehm7 (via GitHub)" <gi...@apache.org>.
mboehm7 commented on PR #1986:
URL: https://github.com/apache/systemds/pull/1986#issuecomment-1902139741
LGTM - thanks for the patch @ReneEnjilian. I'm merging it in with a few modifications.
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Rewrite for Matrix Distributive Property [systemds]
Posted by "mboehm7 (via GitHub)" <gi...@apache.org>.
mboehm7 commented on PR #1986:
URL: https://github.com/apache/systemds/pull/1986#issuecomment-1902252345
It's related to fused-multiply-add (FMA) operations of modern processors for pairs of multiply-add as used in matrix multiplications. Also, given that matmult is generally more efficient than elementwise multiplications with comparatively large costs for allocation this gave a good (and still meaningful) break-even points for examples.
--
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: dev-unsubscribe@systemds.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org