[
https://issues.apache.org/jira/browse/SYSTEMML-2039?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Matthias Boehm updated SYSTEMML-2039:
-------------------------------------
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
{code}
E = A * B + C * D
F = (A + B) + (C + D)
{code}
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.
was:
In large DAGs, the strict topological ordering (depth-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
{code}
E = A * B + C * D
F = (A + B) + (C + D)
{code}
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.
Summary: Memory-inefficiency due to breadth-first instruction
generation (was: Memory-inefficiency due to breath-first instruction
generation )
> Memory-inefficiency due to breadth-first instruction generation
> ----------------------------------------------------------------
>
> Key: SYSTEMML-2039
> URL: https://issues.apache.org/jira/browse/SYSTEMML-2039
> Project: SystemML
> Issue Type: Bug
> Reporter: Matthias Boehm
>
> 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
> {code}
> E = A * B + C * D
> F = (A + B) + (C + D)
> {code}
> 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.
--
This message was sent by Atlassian JIRA
(v6.4.14#64029)
