[SYSTEMDS-2039] Memory-inefficiency due to breadth-first instruction generation

• Type: Bug
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: SystemML 1.0.0
• Epic Link: Perftest and QA for SystemML 1.0 release
• Assignee: Matthias Boehm
• Reporter: Matthias Boehm
• Created: 07/Dec/17 04:39
• Updated: 09/Dec/17 01:35
• Resolved: 09/Dec/17 01:35

Description

In large DAGs, the strict topological ordering (breadth-first) instruction generation causes unnecessary memory-inefficiency and unnecessary evictions. Depth-first instruction generation ensures that all consumers of a DAG input (bound to a logical variable name) are executed before the logical variable is overwritten by an output. For example, in below script

E = A * B + C * D
F = (A + B) + (C + D)

we compute A*B, C*D, A+B, C+D, and subsequently AB+CD, (A+B)+(C+D), which causes unnecessary memory pressure in the lower levels of the DAG. Furthermore, this also causes poor temporal locality.

Instead, we should use a two-level approach where all intermediates are computed in a depth-first manner, and all transient writes are scheduled after these operations.