Shonan challenge sample: simplified HMM

[Kenichi Asai]

Dear all,

I have created a temporary web page that describes the (simplified)
hidden Markov model (if I understand it correctly) and its possible
solution in MetaOCaml.

http://pllab.is.ocha.ac.jp/~asai/StagedHPC/1.html

The point here is that it specifies two things clearly:

- the input program (that HPC people are OK to write), and
- the output program(s) (that HPC people want to obtain).

If these two are explicit, it is also OK to add various background
information to it. I also wrote possible solutions in MetaOCaml.
Solutions should include:

- what kind of hack we need,
- the staged program that generates code, and
- produced code.

HPC people can then say whether the hack is understandable and whether
the produced code is good enough. (In case the hack is not
understandable, it would be a good research topic for staging people how
to remove such a hack. In case the produced code is not good enough,
HPC people can say why it is bad (and possibly make a new challenge to
overcome the deficiency) and we could go forward to solve the problem.

Does this seem to be OK? Any comments are welcome, both on the format
and the contents. I would think the above works fine for small
problems. If it looks fine, I will create a web page for a few more
challenges from Reiji (whose solutions I do not know). Meanwhile,

- How should I write this kind of things in a shared place (Git-hub)?
It would be very nice if someone could make a template document
at an appropriate directory containing the skeleton (section names) of
the challenge.

- Could you also write your challenges?

- Could you start writing a sample challenge for middle-sized problems,
i.e., libraries? I am not sure if the current template works well for
libraries, too. It would be nice to write one and see if it is
feasible.

Sincerely,

--
Kenichi Asai

[Tiark Rompf]

Hi all,

and thanks Kenichi for getting the ball rolling.

Here is a straightforward Scala port (using plain LMS without Delite):

def sparse_mv_prod(a: Array[Array[Int]], v: Rep[Array[Int]]) = {
val v1 = NewArray[Int](n)
for (i <- 0 until n: Range) {
if ((a(i) filter (_ != 0)).length < 3) {
for (j <- 0 until n: Range) {
if (a(i)(j) != 0)
v1(i) = v1(i) + a(i)(j) * v(j)
}
} else {
for (j <- 0 until n: Rep[Range]) {
v1(i) = v1(i) + (staticData(a(i)) apply j) * v(j)
}
}
}
v1
}

If we add a a few helper methods and rewrites we can also write it like this:

def sparse_mv_prod(a: Array[Array[Int]], v: Rep[Array[Int]]) = {
val v1 = NewArray[Int](n)
for (i <- 0 until n: Range) {
for (j <- unrollIf(0 until n)((a(i) filter (_ != 0)).length < 3)) {
v1(i) = v1(i) + (staticData(a(i)) apply j) * v(j)
}
}
v1
}

In the end I think the input should just be this:

val a = MixedSparseDenseMatrix(.... data ...)

val v1 = a * v

This should not be too hard with Delite because matrix and vector operations are already implemented for OptiLA/OptiML but I don't have the time to try it right now.

The full code is here:
https://github.com/TiarkRompf/virtualization-lms-core/blob/delite-develop2/test-src/epfl/test11-shonan/TestHMM.scala

It produces this output:
https://github.com/TiarkRompf/virtualization-lms-core/blob/delite-develop2/test-out/epfl/test11-hmm1.check
https://github.com/TiarkRompf/virtualization-lms-core/blob/delite-develop2/test-out/epfl/test11-hmm2.check

Cheers,
- Tiark