You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@systemds.apache.org by GitBox <gi...@apache.org> on 2022/01/14 10:04:05 UTC
[GitHub] [systemds] jhaberl opened a new pull request #1505: [SYSTEMDS-2837] Improve DAG linearization order
jhaberl opened a new pull request #1505:
URL: https://github.com/apache/systemds/pull/1505
Improve linearization order of LOPs in the DAG to reduce memory consumption of intermediates.
The existing solution is a depth-first algorithm. We modify this to execute LOPs that result in smaller intermediates first in order to reduce maximum memory consumption. This is achieved using a bottom-up approach considering memory estimates (OptimizerUtils.estimateSizeExactSparsity) of parent LOPs.
**Results**
We've compared the implementations using this script:
```
totalResult = matrix(0, rows=1000, cols=1)
for (i in 1:100) {
A = rand(rows=1000, cols=1000)
b = rand(rows=1000, cols=1000)
C = rand(rows=1000, cols=1000)
d = rand(rows=1000, cols=1000)
result = (A + b) %*% rowMaxs(C + d)
totalResult = totalResult + result
}
print(toString(totalResult))
```
In the existing implementations to calculate the result `A + b` is executed first and results in a 1000x1000 matrix as an intermediate while calculating `rowMaxs`. In our solution, `rowMaxs` is executed first, which only leads to an intermediate vector of 1000x1.
For the following data, we've forced the garbage collector to run after every instruction.
When enabling JMLC_MEM_STATISTICS we get these results:
**Max size of live objects:**
Depth-first (existing): 30.526 MB (5 total objects)
Breadth-first: 38.155 MB (6 total objects)
Min-intermediate (ours): 22.904 MB (5 total objects)
This is a graph of memory consumption over time for the test script:
For a more detailed view, the same graph but only the first 45 instructions. This includes two loop iterations.
--
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
[GitHub] [systemds] Baunsgaard closed pull request #1505: [SYSTEMDS-2837] Improve DAG linearization order
Posted by GitBox <gi...@apache.org>.
Baunsgaard closed pull request #1505:
URL: https://github.com/apache/systemds/pull/1505
--
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
[GitHub] [systemds] Baunsgaard commented on pull request #1505: [SYSTEMDS-2837] Improve DAG linearization order
Posted by GitBox <gi...@apache.org>.
Baunsgaard commented on pull request #1505:
URL: https://github.com/apache/systemds/pull/1505#issuecomment-1031282865
Closing because imminent merge #1539
--
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
[GitHub] [systemds] jhaberl commented on pull request #1505: [SYSTEMDS-2837] Improve DAG linearization order
Posted by GitBox <gi...@apache.org>.
jhaberl commented on pull request #1505:
URL: https://github.com/apache/systemds/pull/1505#issuecomment-1030905292
We've now made your requested changes.
The setting we have added is "DAG_LINEARIZATION" (sysds.compile.linearization) with options "topological" and "min_intermediate". Default is "topological".
Our test cases include our initial example and two other existing tests (CsplineCG, LinearRegression) we have adapted to compare outputs using topological vs min_intermediate linearization. These existing test were helpful to us during debugging.
--
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
[GitHub] [systemds] mboehm7 commented on pull request #1505: [SYSTEMDS-2837] Improve DAG linearization order
Posted by GitBox <gi...@apache.org>.
mboehm7 commented on pull request #1505:
URL: https://github.com/apache/systemds/pull/1505#issuecomment-1030920218
This is a great patch (but I leave the review to @Baunsgaard as he already started) - during the merge, please rename the 'topological' to depth-first (as in the past topological sort referred to breadth-first but here it refers to our current depth-first), and potentially add the breadth-first as an enum option too (would be good to experiment with that externally).
--
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
[GitHub] [systemds] Baunsgaard commented on a change in pull request #1505: [SYSTEMDS-2837] Improve DAG linearization order
Posted by GitBox <gi...@apache.org>.
Baunsgaard commented on a change in pull request #1505:
URL: https://github.com/apache/systemds/pull/1505#discussion_r785311327
##########
File path: src/main/java/org/apache/sysds/lops/compile/Dag.java
##########
@@ -65,13 +65,7 @@
import org.apache.sysds.runtime.instructions.cp.VariableCPInstruction;
import org.apache.sysds.runtime.meta.MatrixCharacteristics;
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.Iterator;
-import java.util.List;
+import java.util.*;
Review comment:
no wildcard imports, i think perhaps that your editor does this.
--
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