systemml-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Matthias Boehm (JIRA)" <j...@apache.org>
Subject [jira] [Updated] (SYSTEMML-2039) Memory-inefficiency due to breadth-first instruction generation
Date Thu, 07 Dec 2017 04:41:00 GMT

     [ 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)

Mime
View raw message