Bugs in optimization

[MaggieQi]

When I try to add optimization into some applications, I find that there are something wrong for map and shuffle fusion. The example is as follows:

In [5]: x = expr.ndarray((10,), dtype=np.float, reduce_fn=np.add)

In [6]: y = expr.ones((10,10))

In [7]: expr.shuffle(y, lambda array, ex: [(extent.index_for_reduction(ex, axis=1), array.fetch(ex).sum(axis=1))], target=x).optimized().force()
Out[7]: DistArrayImpl(id=75153680, shape=(10,), dtype=float64)

In [8]: x.glom()
Out[8]:
array([ 6.92288859e-310, 6.92288859e-310, 6.92288859e-310,
6.92288859e-310, 6.92288859e-310, 6.92288859e-310,
6.92288859e-310, 6.92288859e-310, 6.92288859e-310,
6.92288859e-310])

In [9]: expr.shuffle(y, lambda array, ex: [(extent.index_for_reduction(ex, axis=1), array.fetch(ex).sum(axis=1))], target=x).force()
Out[9]: DistArrayImpl(id=75154064, shape=(10,), dtype=float64)

In [10]: x.glom()
Out[10]: array([ 10., 10., 10., 10., 10., 10., 10., 10., 10., 10.])

I think when we try to set a target for shuffle, we cannot fusion the target create map with this shuffle since we will use this target in the future. Moreover, can we add this shuffle expr as a dependency of expr that uses this target? Then we will not need to force it each time we use this kind of shuffle.

[rjpower]

Good catch. Yeah, because shuffle has a target, it's behavior is somewhat
tricky.

I like the idea of having the shuffle be a dependency of the target. Maybe
shuffle should always return a value, even if it has a target? So we could
write:

x = expr.ndarray(...)
sx = expr.shuffle(y, target=x)
sx.force()

The user would have to remember to use the output of the shuffle instead of
the original x, but that doesn't seem too bad. What do you think?

[MaggieQi]

Yes, if we can return the final target as the result of the shuffle expr,
then we can build the expr tree without force it each time we use it. That
maybe a good idea to solve the problem!

2014-04-21 15:22 GMT-04:00 Russell Power [email protected]:

Good catch. Yeah, because shuffle has a target, it's behavior is somewhat
tricky.

I like the idea of having the shuffle be a dependency of the target. Maybe
shuffle should always return a value, even if it has a target? So we could
write:

x = expr.ndarray(...)
sx = expr.shuffle(y, target=x)
sx.force()

The user would have to remember to use the output of the shuffle instead of
the original x, but that doesn't seem too bad. What do you think?

—
Reply to this email directly or view it on GitHubhttps://issues/137#issuecomment-40966978
.

Chen Qi
Department of Computer Science
School of EECS
Peking University

[fegin]

The simplest way to solve this question is to change NdArrayExpr.visit(). Current NdArrayExpr.visit() returns a new NdArrayExpr. This causes losing the original dependence when we call optimized(). Since NdArrayExpr doesn't have dependences, it should just do return self. However, if the target is not NdArrayExpr, this would not help.

Russell's method seems the most general way to solve the issue. Another idea is to add a variable replaced_expr to expr. When we call expr_like we set the replaced_expr in the original expr to new expr. Whenever we need to evaluate the original expr, we evaluate replaced_expr.

[rjpower]

​Double checking, it looks like shuffle returns target when it's
evaluated, so we can start using this form now:

x = ndarray(..)
sx = shuffle(y, target=x)

The behavior of shuffle is tricky, because it doesn't quite fit into the
expression graph (unless you always are careful to use the sx value).
I'm not totally sure how to address this as we use shuffle in a number of
places to write over the top of an existing array. It might "just work" to
use the shuffle in a loop:

wts = randn(...)
for i in range(1000):
  wts = shuffle(expr, target=wts)

But I can't say off the top of my head.

I'll send a pull request to fix the visit for ndarrayexpr.