delite reduce & tuple question

[Alexander Samoilov]

Hello All !

tuple is likely to be broken for the reduce operation, that is for the both tests below:

  def ReduceEdges(in: Rep[Int]) = {

    val edges = DeliteArray.fromFunction(in) { i => make_tuple2( i + 1.0,  make_tuple2(i , i + 1 )) }

    val zero = make_tuple2( Double.MaxValue, make_tuple2(Int.MaxValue, Int.MaxValue ) )

    val x = edges.reduce( ( left, right )   =>   { if (left._1 < right._1) {left} else {right}  } , zero)

    println(x)

  }

and for the make_tuple3 variant:

  def ReduceEdges(in: Rep[Int]) = {

    val edges = DeliteArray.fromFunction(in) { i => make_tuple3( i + 1.0,  i , i + 1 ) } 

    val zero = make_tuple3( Double.MaxValue, Int.MaxValue, Int.MaxValue )

    val x = edges.reduce( ( left, right )   =>   { if (left._1 < right._1) {left} else {right}  } , zero)

    println(x)

  }

for the test being run solely, i.e. not in series I'm getting the following error message:

[info] - testReduceEdges *** FAILED ***

[info]   java.lang.RuntimeException: transforming reduce elem but rFunc is not a struct and func is

[info]   at scala.sys.package$.error(package.scala:27)

[info]   at ppl.delite.framework.transform.MultiloopSoATransformExp$class.soaTransform$2(MultiLoopSoA.scala:220)

[info]   at ppl.delite.framework.transform.MultiloopSoATransformExp$class.soaReduce(MultiLoopSoA.scala:228)

[info]   at ppl.tests.scalatest.delite.DeliteExternalApp$$anon$1.soaReduce(MVMTestSuite.scala:12)

[info]   at ppl.delite.framework.transform.MultiloopSoATransformWithReduceExp$class.transformLoop(MultiLoopSoA.scala:16)

[info]   at ppl.tests.scalatest.delite.DeliteExternalApp$$anon$1.transformLoop(MVMTestSuite.scala:12)

[info]   at ppl.delite.framework.transform.MultiloopSoATransformExp$$anon$1.transformStm(MultiLoopSoA.scala:28)

[info]   at scala.virtualization.lms.common.ForwardTransformer$class.traverseStm(ForwardTransformer.scala:48)

[info]   at ppl.delite.framework.transform.MultiloopSoATransformExp$$anon$1.traverseStm(MultiLoopSoA.scala:26)

[info]   at scala.virtualization.lms.internal.NestedBlockTraversal$$anonfun$traverseStmsInBlock$1.apply(BlockTraversal.scala:117)

But for the test being run the second in the series, say after

  def Rec(in: Rep[Int]) = {

    def Complex(re: Rep[Double], im: Rep[Double]) = new Record { val real = re; val imag = im }

    val v = DeliteArrayBuffer.fromFunction(in){ i => Complex(i, 0-i) }

    val x = v.reduce{ (a,b) => Complex(a.real + b.real, a.imag + b.imag) }(Complex(0,0))

    println(x)

  }

the series passes ok - very strange but is possible in theory.

[info] MVMTestSuite:

[info] - testRecord

[info] - testReduceEdges

[info] Run completed in 26 seconds, 108 milliseconds.

[info] Total number of tests run: 2

[info] Suites: completed 1, aborted 0

[info] Tests: succeeded 2, failed 0, canceled 0, ignored 0, pending 0

[info] All tests passed.

Could you please help to locate the root cause of this seems to be erratic behavior?

Thanks!

Alexander

[Alexander Samoilov]

Hello Again !

It was firmly established that if you create a new context for each of the tests then the erratic dependency from the tests order won't occur.

That is the test ReduceEdges fails unconditionally in both cases, i.e. being run either solely or in series.

Thanks,

Alexander

[Kevin Brown]

Hey, 

I'm not sure why the test passes when run with other tests, but the test case you've devised is known to fail.  The SoA transformer for reduce operations currently only works in special cases.  For your reduceComplex example, the operation is cleanly separable into a reduce over the real component and a reduce over the imag component, so the transformer should work.  But for the reduceEdges example, it can't figure out how to separate it and throws an exception.

Because of this issue we've factored the SoA transformer into two separate traits. MultiloopSoATransformExp only transforms map/zip/filter operations and is always safe (to the best of our knowledge).  MultiloopSoATransformWithReduceExp also includes transforming reduces but is currently buggy.  

So hopefully if you change the mixin trait those tests should pass.

--Kevin

--
You received this message because you are subscribed to the Google Groups "OptiML" group.
To unsubscribe from this group and stop receiving emails from it, send an email to optiml+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Alexander Samoilov]

Hi Kevin,

Thanks for answering on the questions.

Could you please expand on how to circumvent this reduce op restriction (that is elaborate on what places in the delite code are to be modified), as currently this is a showstopper for us?

Thanks!

Alexander

[Kevin Brown]

Are you using the DeliteTestSuite to run these examples? If so, choosing which soa trait to use is at this line:

https://github.com/stanford-ppl/Delite/blob/develop/framework/delite-test/src/ppl/tests/scalatest/DeliteTestDSL.scala#L86

If you want to improve the transformer, everything you need to change is located in this function:

https://github.com/stanford-ppl/Delite/blob/develop/framework/src/ppl/delite/framework/transform/MultiLoopSoA.scala#L188

The problem we never solved is that if the function isn't cleanly separable into a function over each field individually, then once you break the reduce into a separate reduce for each field you no longer have a reference to all of the function inputs.  In theory this could still work, because we will then fuse the separated reduces back together (minus the struct wrapper), so all of the pieces are in the same scope by the time code is generated, but we're missing a mechanism to reconnect the broken dependencies.  We also never implemented a check to see if the function is separable and only apply the transformer in those cases, which is why we have the trait where it's completely disabled. 

If you make any improvements, I'd love to hear about it.  This has been an outstanding issue for a while now.

--Kevin

[Alexander Samoilov]

Hi Kevin,

Thanks for your help, 

Endeed changing the mixin from 
MultiloopSoATransformWithReduceExp

to

MultiloopSoATransformExp

hack as you proposed i.e. effectively disabling transformLoop within the 1st mixin really works.

[Alexander Samoilov]

Let me expand on the changes I've made to the delite code in order to force reduce op working for tuples or structures.

I added a few traits with the suffix WithoutReduceTransform, 8 to be more exact:

find . -name '*.scala'|xargs grep WithoutReduceTransform | grep trait | uniq| wc -l

8

such as 
DeliteTestDSLExpWithoutReduceTransform etc.

I'm not very satisfied with the scale of such intrusion but looks like this is inevitable due to the cake pattern or maybe you know a better solution to minimize intrusion to the code?

Thanks,

Alexander