Interfaces for Dynamic Optimization about nemo HOT 11 CLOSED

OK, so I talked with Eunji(our new lab member) and got some great insights for this.

In traditional compilers, jit compilation is usually used for code blocks that are executed multiple times(think loops). They generate a complete execution plan prior to the execution, and then as the iteration goes on, re-write the plan based on obtained stats.

In contrast, the DAGs we execute do not contain cycles, and runtime optimization(e.g., dynamic partitioning) of an operator usually depends on the results of previous operators. This lets us get away with a simpler design where the compiler generates the execution plan piece by piece, without having to re-write the plan across multiple layers(ir/runtime-logical/runtime-physical).

For example, let's say we're applying a dynamic partitioning optimization to a MapReduce application. First, the compiler generates a partial execution plan for Map and dynamically added KeyHistogram operators. After that, it can generate the rest of the execution plan for Reduce. We do not need to do any re-writes during the process.

I know Optimus does re-writing. But my feeling is that it is more to do with the system's legacy code than with the actual requirements.

Of course, we might want to do a re-write while executing the operator(e.g., change the number of reducers while executing the reducer), especially for streaming applications. Thus, I guess we need the re-writing mechanism after all? Then I guess we really need to put in efforts to make the re-writing across multiple layers easy. What are your thoughts?

from nemo.

Hmm... I guess we need the re-writing mechanism after all. Even the Beam applications that we have now(MLR, ALS) have implicit conditional cycles/loops. It'd be great if we can explicitly express the cycles/loops in our IR, and use the traditional compiler's techniques on them.

from nemo.

How do we handle the cycles/loops currently?
It'd be nice to have cycles/loops in our IR.

from nemo.

Currently, we do not have cycle/loop in our IR. I'll file an issue for it.
Note that Beam also does not have cycle/loop in its language. I suppose we need to identify it ourselves in our Beam frontend.

from nemo.

Then, how do we handle cycles (iterations) now?

from nemo.

Right now, we just have a long DAG with duplicate sets of operators.
Because Beam does not have the concept of conditional loop, we have fixed number of iterations for ALS and MLR.
For example, if we have 2 operators in a loop, and there are 10 iterations, we simply have a long chain of 20 operators.

from nemo.

@johnyangk Do you plan to add a loop in the current IR? This can be a good topic to discuss in our meeting.

from nemo.

Sure this is a good discussion topic. If we have concrete optimization techniques to use for loops, then we can make this a high priority task , since this is something the Optimus paper did not have. However, if we don't, then I think it'd be better to postpone this task.

from nemo.

If we decide to add a loop, there are two potential approaches

• Add a high-level loop construct
• Add a low-level jump/condition construct to create a loop

from nemo.

Loops will be handled with #121

from nemo.

See issues marked with DynOpt

from nemo.