Wonderful explanations Matthias! Thank you for the history. On Jan 17, 2017 7:04 AM, "Matthias Boehm" <mboe...@googlemail.com> wrote:
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 > >
