systemml-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Matthias Boehm <mboe...@googlemail.com>
Subject Re: SystemML optimizer design
Date Tue, 17 Jan 2017 15:04:23 GMT
Hi Dylan,

these are very interesting questions - let me answer them one by one:

0. SPOOF: We developed the SPOOF compiler framework in a separate fork 
that will be integrated back into SystemML master soon. Initially, we 
will add the code generation part as an experimental feature, likely in 
our SystemML 1.0 release. The sum-product part will follow later because 
it's still in a very early stage.

1a. Rewrites: At a high-level, there are two types of rewrites: static 
and dynamic. Static rewrites are size-independent while dynamic rewrites 
depend on sizes in terms of constraints or costs. During initial 
compilation, intra- and inter-procedural analysis only propagates sizes 
that are valid over the entire program lifetime. The rewrites are then 
indeed applied in an in-place manner (i.e., "destructively"), which is 
ok because sizes are guaranteed not to change. However, during dynamic 
recompilation, we use exact sizes and recompile HOP DAGs very 
aggressively. In order to allow for non-reversible rewrites, we keep the 
original HOP DAG, create a deep copy, rewrite the copied HOP DAG and 
finally generate LOPs and executable instructions. You'll find the 
details here:
https://github.com/apache/incubator-systemml/blob/master/src/main/java/org/apache/sysml/hops/recompile/Recompiler.java

1b. Rewrite Phase Ordering: Determining the order or rewrites, which is 
often called phase ordering in compilers, is currently done manually 
with the context-knowledge of side effects between individual rewrites. 
This usually works very well in SystemML but gets more complicated as we 
add more rewrites and we've already seen a couple of cases were phase 
ordering problems led to suboptimal plans. As far as I know, there 
doesn't exist a principled approach to phase ordering in other compilers 
like GCC or LLVM either.

1c. Cost-based Optimization: Right now, different components use 
different cost functions and heuristics. For example, matrix 
multiplication chain optimization uses the number of floating point 
operations, operator selection of distributed matrix multiplications 
uses the I/O and shuffle costs weighted by the degree of parallelism, 
other decisions use simply the estimated size, and our resource 
optimizer uses a full-fledged time-based cost model regarding generated 
runtime plans (see 
https://github.com/apache/incubator-systemml/blob/master/src/main/java/org/apache/sysml/hops/cost/CostEstimatorStaticRuntime.java).

For SPOOF, we extended this time-based cost model.

2. Explain: Yes partially, we provide a flag -explain that allows 
investigating the generated plans at HOP level (-explain hops), at 
runtime level (-explain runtime), and during dynamic recompilation 
(-explain recompile_hops, -explain recompile_runtime). However, the HOP 
explain already shows the rewritten plans. As workarounds, you can (1) 
set the optimization level in SystemML-config.xml to 1 in order to see 
the initial plans without rewrites, or (2) set 
ProgramRewriter.LDEBUG=true (and rebuild SystemML) to see the applied 
rewrites. Furthermore, for task-parallel parfor programs you can add 
log=DEBUG in the parfor header to see the the plan before recompilation, 
after recompilation, and after rewrites along with some details on the 
individually applied rewrites.

3. Relationship to Apache Calcite: Well, Calcite is a cost-based 
optimizer for relational algebra. As mentioned in (0), our sum-product 
optimization is still in a very early stage. In SystemML master, we 
purely focus on linear algebra and statistical functions - hence, there 
is not much similarity. However, it is indeed an interesting question to 
build our sum-product optimizer on top of an existing rewrite framework 
such as Calcite, Spark's Catalyst optimizer, or the Columbia optimizer, 
etc. So far we tend to build it from scratch as our restricted linear 
algebra actually simplifies a couple of rewrites.

I hope this gives a general overview - if you have further questions 
with regard to a specific topic, please just ask.


Regards,
Matthias

On 1/17/2017 4:05 AM, Dylan Hutchison wrote:
> Hi there,
>
> I learned about SystemML and its optimizer from the recent SPOOF paper
> <http://cidrdb.org/cidr2017/papers/p3-elgamal-cidr17.pdf>.  The gist I
> absorbed is that SystemML translates linear algebra expressions given by
> its DML to relational algebra, then applies standard relational algebra
> optimizations, and then re-recognizes the result in linear algebra kernels,
> with an attempt to fuse them.
>
> I think I found the SystemML rewrite rules here
> <https://github.com/apache/incubator-systemml/tree/master/src/main/java/org/apache/sysml/hops/rewrite>.
> A couple questions:
>
>    1. It appears that SystemML rewrites HOP expressions destructively,
>    i.e., by throwing away the old expression.  In this case, how does SystemML
>    determine the order of rewrites to apply?  Where does cost-based
>    optimization come into play?
>
>    2. Is there a way to "debug/visualize" the optimization process?  That
>    is, when I start with a DML program, can I view (a) the DML program parsed
>    into HOPs; (b) what rules fire and where in the plan, as well as the plan
>    after each rule fires; and (c) the lowering and fusing of operators to LOPs?
>
>    I know this is a lot to ask for; I'm curious how far SystemML has gone
>    in this direction.
>
>    3. Is there any relationship between the SystemML optimizer and Apache
>    Calcite <https://calcite.apache.org/>?  If not, I'd love to understand
>    the design decisions that differentiate the two.
>
> Thanks, Dylan Hutchison
>

Mime
View raw message