[SYSTEMML-2335] Improved instruction generation for large DAGs (CP/SP) This patch significantly improves the performance of instruction generation from LOP DAGs as done during initial compilation and dynamic recompilation. So far, we always computed the transitive closure which became the bottleneck for large DAGs with 10,000+ operators due to its squared time complexity. Fortunately, this is only required in MR execution modes and thus not needed for our default CP/SPARK modes. Since these execution modes also use a different instruction scheduling (depth-first for lower memory requirements), we now use a plain instruction generation with pseudo linear time complexity.
On compiling the main DAG of ResNet 200, this patch improved the instruction generation time from 4,562ms to 437ms. On average DAGs of 50-200 operators the improvements are smaller, but ALL scripts and APIs benefit from this patch. Project: http://git-wip-us.apache.org/repos/asf/systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/55ce4853 Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/55ce4853 Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/55ce4853 Branch: refs/heads/master Commit: 55ce4853c9312d213ada8f44ea2fd048643b0108 Parents: e270960 Author: Matthias Boehm <[email protected]> Authored: Sun May 20 00:54:00 2018 -0700 Committer: Matthias Boehm <[email protected]> Committed: Sun May 20 14:35:11 2018 -0700 ---------------------------------------------------------------------- src/main/java/org/apache/sysml/lops/Data.java | 10 +- .../java/org/apache/sysml/lops/compile/Dag.java | 1840 +++++++++--------- 2 files changed, 899 insertions(+), 951 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/systemml/blob/55ce4853/src/main/java/org/apache/sysml/lops/Data.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/lops/Data.java b/src/main/java/org/apache/sysml/lops/Data.java index f000bab..53f169b 100644 --- a/src/main/java/org/apache/sysml/lops/Data.java +++ b/src/main/java/org/apache/sysml/lops/Data.java @@ -295,16 +295,18 @@ public class Data extends Lop * Method to check if this represents a transient variable. * @return true if this data lop is a transient variable */ - public boolean isTransient() - { + public boolean isTransient() { return transient_var; } - public boolean isPersistentWrite() - { + public boolean isPersistentWrite() { return operation == OperationTypes.WRITE && !transient_var; } + public boolean isPersistentRead() { + return operation == OperationTypes.READ && !transient_var; + } + /** * Method to generate appropriate MR write instructions. * Explicit write instructions are generated only in case of external file formats
