Ruby compilers (for DSP processors and alike)

[Bart Masschelein]

Hi guys,

A few weeks ago, sbdy talked to me about Ruby, and Rails, and how
beautiful /sniff/ the language is. I took a look at it, and indeed, I
love the simplicity, or let me rephrase, the humanity of the language.
Definitely because I have a background in C/C++/Java, the first one
missing the ability of easy 'meta-languaging', the second one being
basically an OO hack of the first one (no offense meant), and the third
one, well, ok, close but no cigar. The company I work for builds tool
for optimizing algorithms (mainly multimedia applications), from the raw
description until the target platform. The problem is that all those
tools only accept C. I believe that Ruby might be a better choice for
this, definitely in the early stages of the optimization, because you
can analyse your program from a layer above it, which according to Godel
is sometimes necessary. So in my off-duty time, I'm building some
examples to convince them. But alas, I already now their first question,
and have no answer to it, and that's why I phrase it here: What if the
code is optimized, how do you go to a platform with specific processors
on them? For C, many are out there. So here is my question to you guys:

1) Are there any efforts, or is it at all possible, to write a Ruby
compiler, for lets say a TI/C64 DSP processor?

2) If the answer to the first question is negative, how good is the
(http://easter.kuee.kyoto-u.ac.jp/~hiwada/ruby/rb2c/) ruby to C
convertor? I did not have a look at it, and wont have time probably in
the near future, but can it handle any Ruby code? That would be amazing,
as there not even really good C++ -> C convertors. Does it handle 'your
typical Ruby' constructions? I would already be happy if it can handle
C-alike code mixed with classes.

I know, an obvious answer would be, try it yourself, but if sbdy can
shed a light, that would be a big motivation/demotivation. One answer I
can imagine is that Ruby is not targeted for such low-level stuff.

Best regards,

Bart.

 

[Phil Tomson]

Hi guys,

A few weeks ago, sbdy talked to me about Ruby, and Rails, and how
beautiful /sniff/ the language is. I took a look at it, and indeed, I
love the simplicity, or let me rephrase, the humanity of the language.
Definitely because I have a background in C/C++/Java, the first one
missing the ability of easy 'meta-languaging', the second one being
basically an OO hack of the first one (no offense meant), and the third
one, well, ok, close but no cigar. The company I work for builds tool
for optimizing algorithms (mainly multimedia applications), from the raw
description until the target platform. The problem is that all those
tools only accept C. I believe that Ruby might be a better choice for
this, definitely in the early stages of the optimization, because you
can analyse your program from a layer above it, which according to Godel
is sometimes necessary. So in my off-duty time, I'm building some
examples to convince them. But alas, I already now their first question,
and have no answer to it, and that's why I phrase it here: What if the
code is optimized, how do you go to a platform with specific processors
on them? For C, many are out there. So here is my question to you guys:

1) Are there any efforts, or is it at all possible, to write a Ruby
compiler, for lets say a TI/C64 DSP processor?

Not likely. If we had a compiler that would target a DSP we would also
have a compiler that would target x86, no?

Might I suggest a different approach:
A few weeks back I was doing a lot of work with video processing using a
Matrox card and their Genesis API. A lot like doing DSP, actually.
Their C API has all sorts of image processing functions. However, it's
rather klunky - I would say it's akin to programming in assembly in C:
Allocate a buffer then load the buffer with data then perform some
transformation on the buffer... very tedious, very easy to make mistakes
which are difficult to debug. So then I had an idea: why
not write a DSL (domain specific langauge) using Ruby that would allow me
to bypass some of the tedium. The DSL would be used to describe the
dataflow. That description would then be translated to the Matrox API (C
code).

So for example I could do things like this (to the best of my memory):

require 'gencode'
include GenMatrox
Description.new {
Task {
cam1 = Camera
b1 = Buffer(640,480) #allocate an 640X480 video processing buffer
halfsize = Buffer(320,240)
b1 << cam1 #capture camera output in b1
halfsize << b1.zoom(0.5) #zoom in
}
}.to_c

When that code was run it would generate about 40 lines of C code
including all the variable declarations which could then be compiled.

So perhaps you could create a DSL for specifying the algorithm you want
and generate C code targetted to the DSP. The DSL would then generate
the C code for you. Of course this is only a win if you can create the DSL
in such a way that it is a much higher-level description than the C would be
(as the example above where about 10 line of Ruby became about 40 lines of C)

2) If the answer to the first question is negative, how good is the
(http://easter.kuee.kyoto-u.ac.jp/~hiwada/ruby/rb2c/) ruby to C
convertor? I did not have a look at it, and wont have time probably in
the near future, but can it handle any Ruby code? That would be amazing,
as there not even really good C++ -> C convertors. Does it handle 'your
typical Ruby' constructions? I would already be happy if it can handle
C-alike code mixed with classes.

A much more recent (and maintained) Ruby to C converter can be found
here:
http://rubyforge.org/projects/ruby2c/

Anything like this will have limitations (a lot of dynamic things like
eval can't be converted) but maybe they're not an issue for what you're
doing?

I know, an obvious answer would be, try it yourself, but if sbdy can
shed a light, that would be a big motivation/demotivation. One answer I
can imagine is that Ruby is not targeted for such low-level stuff.

Maybe you can give us a little more info about what you're doing? I
would think about the DSL approach I described above - it might be a fit
for what you're doing. I know similar
approaches have been used to define assemblers in Ruby and assemblers are
pretty low-level.

Phil

 

[Lothar Scholz]

Hello Bart,

BM> Hi guys,

BM> A few weeks ago, sbdy talked to me about Ruby, and Rails, and how
BM> beautiful /sniff/ the language is. I took a look at it, and indeed, I
BM> love the simplicity, or let me rephrase, the humanity of the language.
BM> Definitely because I have a background in C/C++/Java, the first one
BM> missing the ability of easy 'meta-languaging', the second one being
BM> basically an OO hack of the first one (no offense meant), and the third
BM> one, well, ok, close but no cigar. The company I work for builds tool
BM> for optimizing algorithms (mainly multimedia applications), from the raw
BM> description until the target platform. The problem is that all those
BM> tools only accept C. I believe that Ruby might be a better choice for
BM> this, definitely in the early stages of the optimization, because you
BM> can analyse your program from a layer above it, which according to Godel
BM> is sometimes necessary. So in my off-duty time, I'm building some
BM> examples to convince them. But alas, I already now their first question,
BM> and have no answer to it, and that's why I phrase it here: What if the
BM> code is optimized, how do you go to a platform with specific processors
BM> on them? For C, many are out there. So here is my question to you guys:

First of all i'm not sure if i understand you correctly.
Do you mean your company write optimized multimedia algorithms (or
build tools, what the hell is a build tool for an algorithm ????).

If you develop algorithms then you can use Ruby to prototype a new algorithm
(if it's not already way to slow even for this) but writting optimized
algorithm for processing multimedia in ruby is the hugest possible mismatch
of language and application domain i've seen so far. It's always my
example that in this cases a ruby program is about 100-200 times
slower then a c program.

If you only have a few optimized low level algorithms that are easy to
interface you could write a c extension and use ruby as a scripting language.

Maybe you could explain a little bit more what exactly you are looking
for and what you want to do with a ruby -> c translater (what kinds of
code should it translate ?).

 

[Bart Masschelein]

Ok, let me explain a bit more what I am aiming for... I'll explain it
with the work I'm currently doing. The ultimate goal is to have MPEGs
latest video codec, SVC (Scalable Video Codec), running on a
multi-processor platform, with heterogenous processors for regular
kernels, like motion compensation, and dedicated hardware for
bit-mingling stuff, like the arithmetic coder. We start at the highest
level, taking the reference software from MPEG. The next step is running
this software through our in-house developed toolset, which analyses for
instance the number of accesses (reads, writes) to the arrays in the
program. This gives you information on where to reduce and reuse data
access, and hence accesses to memories, and hence the power consumption,
which enables you to watch video longer on a mobile device. These tools
also gives you a hint on memory hierarchy in the design, how much L1, L2
and higher level memory you need, so you can reduce memory accesses to
big memories, as there are more energy consuming. The idea is that
production of data and consumption of data should be as close as
possible, avoiding storage of huge data sets, for instance complete
frames of a sequence.

This worked out quite well, since all reference software until now was
written in C, and our toolset only allows C as input. But the reference
software of SVC is written in C++, so these tools were not usuable
anymore, so yours truly, and that is where the frustration comes from,
has to rewrite the complete codec into C, so our tools can support it.
The problem they have with having C++ as input is the dynamic behaviour
of the data, they analyses the data statically, not at run-time, so when
you instantiate an object from a class using new, they cannot analyse
that. Which sounds strange to me, they can as well do run-time analysis
in my opinion, but that is a discussion I will have to have with them.

Anyway, so I thought Ruby might pop in here, because of the
metaprogramming concepts. I think that might solve a lot of their
problems. But I don't have any proofs yet, so I'm trying to figure these
things out now, with small examples.

Do you mean your company write optimized multimedia algorithms (or
build tools, what the hell is a build tool for an algorithm ????).

;-), no, the mail said 'our company builds tools', not we make build
tools ;-)

If you develop algorithms then you can use Ruby to prototype a new algorithm
(if it's not already way to slow even for this) but writting optimized
algorithm for processing multimedia in ruby is the hugest possible mismatch
of language and application domain i've seen so far. It's always my
example that in this cases a ruby program is about 100-200 times
slower then a c program.

I knew there was going to be a decrease in speed, but 100-200 times
more, that IS a lot... Isn't a plus one for Ruby...

If you only have a few optimized low level algorithms that are easy to
interface you could write a c extension and use ruby as a scripting language.

I guess that could indeed be the approach to take then, start with a
high level, full implementation of the algorithm in Ruby, and when the
algorithm is optimized, rewriting kernels (intra-prediction, motion
estimation, ...) in C and use them as C extension.

Maybe you could explain a little bit more what exactly you are looking
for and what you want to do with a ruby -> c translater (what kinds of
code should it translate ?).

I would not expect that ruby->C translator could translate a full SVC
application to C with a push of the button. That would be Utopia, but if
it could handle kernels, which are just a bunch of methods in a class,
eventually, that would be great.

I will continue writing some test examples, thinking of how I can
replace some of their tools with a Ruby variant, and try to convince
them with the simplicity of such tools compared with their C
implementation. It will be a hard one, but a nice time-spending then
rewriting C++->C so their tools can support it.

 

[Bart Masschelein]

So then I had an idea: why
not write a DSL (domain specific langauge) using Ruby that would allow me
to bypass some of the tedium. The DSL would be used to describe the
dataflow. That description would then be translated to the Matrox API (C
code).

So what is such a DSL exactly then? In your case, it is a Ruby piece of
code which is translated into C, which uses the Matrox API? Or is there
more behind the piece of code you give here, which is part of the DSL,
like a convertor to replace a specific Ruby line of code into specific C
lines of code?

So for example I could do things like this (to the best of my memory):

require 'gencode'
include GenMatrox
Description.new {
Task {
cam1 = Camera
b1 = Buffer(640,480) #allocate an 640X480 video processing buffer
halfsize = Buffer(320,240)
b1 << cam1 #capture camera output in b1
halfsize << b1.zoom(0.5) #zoom in
}
}.to_c



Maybe you can give us a little more info about what you're doing? I
would think about the DSL approach I described above - it might be a fit
for what you're doing. I know similar
approaches have been used to define assemblers in Ruby and assemblers are
pretty low-level.

Where could I find more information on this issues? It would be
interested to have a look at these.

Thanks,

B.

 

[Phil Tomson]

Ok, let me explain a bit more what I am aiming for... I'll explain it
with the work I'm currently doing. The ultimate goal is to have MPEGs
latest video codec, SVC (Scalable Video Codec), running on a
multi-processor platform, with heterogenous processors for regular
kernels, like motion compensation, and dedicated hardware for
bit-mingling stuff, like the arithmetic coder. We start at the highest
level, taking the reference software from MPEG. The next step is running
this software through our in-house developed toolset, which analyses for
instance the number of accesses (reads, writes) to the arrays in the
program. This gives you information on where to reduce and reuse data
access, and hence accesses to memories, and hence the power consumption,
which enables you to watch video longer on a mobile device. These tools
also gives you a hint on memory hierarchy in the design, how much L1, L2
and higher level memory you need, so you can reduce memory accesses to
big memories, as there are more energy consuming. The idea is that
production of data and consumption of data should be as close as
possible, avoiding storage of huge data sets, for instance complete
frames of a sequence.

This worked out quite well, since all reference software until now was
written in C, and our toolset only allows C as input. But the reference
software of SVC is written in C++, so these tools were not usuable
anymore, so yours truly, and that is where the frustration comes from,
has to rewrite the complete codec into C, so our tools can support it.
The problem they have with having C++ as input is the dynamic behaviour
of the data, they analyses the data statically, not at run-time, so when
you instantiate an object from a class using new, they cannot analyse
that. Which sounds strange to me, they can as well do run-time analysis
in my opinion, but that is a discussion I will have to have with them.

Anyway, so I thought Ruby might pop in here, because of the
metaprogramming concepts. I think that might solve a lot of their
problems. But I don't have any proofs yet, so I'm trying to figure these
things out now, with small examples.

So just to understand: you need to be able to find out how many times
various arrays in the SVC implementation are accessed (read or written
to) during some specified time period and you think that if you had these
algorithms in Ruby that would be easy (correct?). It probably would be
easy as you could (for example) override the Array access operators ( []
and []=) to record this information.

Couldn't you do something similar in C++ (yeah, it would be more
difficult than in Ruby, but certainly doable): Create a class that stands
in for the arrays (or vectors or whatever collection class that might be
used from the STL) that monitors access to the data in the collections?
Bascially, you could create an 'instrumented' version of your current C++
code for the SVC that, when run, would collect all of the statistics you're
looking for. (or am I misunderstanding something?)

Or to put it another way: Let's say the reference C++ code for the SVC
algorithms uses an STL vector for the collection class. You could create
a class called MonitoredVector that has-a STL vector as a member. All
access operators in MontoredVector eventually call the same access
operators (methods) in the STL vector, but first they record the
statistics you're looking for somewhere and then make the calls to the
delegate. You wouldn't even need to change your C++ SVC code very much -
just change the std::vector declarations to monitoredVector declarations
(or even use a typedef to make it really easy to switch back-and-forth
between the two).

I knew there was going to be a decrease in speed, but 100-200 times
more, that IS a lot... Isn't a plus one for Ruby...

I guess that could indeed be the approach to take then, start with a
high level, full implementation of the algorithm in Ruby, and when the
algorithm is optimized, rewriting kernels (intra-prediction, motion
estimation, ...) in C and use them as C extension.

Or could you even take the C++ reference code you get and use Swig
(http://www.swig.org) to wrap that code so that you can access the C++
classes from Ruby?

I would not expect that ruby->C translator could translate a full SVC
application to C with a push of the button. That would be Utopia, but if
it could handle kernels, which are just a bunch of methods in a class,
eventually, that would be great.

I will continue writing some test examples, thinking of how I can
replace some of their tools with a Ruby variant, and try to convince
them with the simplicity of such tools compared with their C
implementation. It will be a hard one, but a nice time-spending then
rewriting C++->C so their tools can support it.

Question: After you analyze the algorithm and optimize it, will you be
targetting hardware (like an FPGA using an HDL like VHDL or Verilog) or
will it run on a DSP?

Phil

 

[Phil Tomson]

So what is such a DSL exactly then? In your case, it is a Ruby piece of
code which is translated into C, which uses the Matrox API?

It's not translated per se, but running that Ruby code causes the C code
to be generated - it's more correct to think of it as a code generator
than a code translator, I think (I'm not doing any parsing, for example)

Or is there
more behind the piece of code you give here, which is part of the DSL,
like a convertor to replace a specific Ruby line of code into specific C
lines of code?

Kind of. Actually, each Ruby line of code might generate several lines
of C code.

For example, if I declare a Buffer in my Ruby-DSL like so:

b1= Buffer(640,480)

In C we first need to declare the buffer somewhere toward the top:
long b1; //declaration

Then we need to actually set up the buffer later on using the matrox API:
imCreateBuffer(Thread, 640,480, 0L, 0L, &b1); //allocation

Then later on at the end of the program we need to de-allocate that
buffer:
imBufFree(Thread,b1,0L,0L); //de-allocation

So that one line of Ruby generates all three lines of C in the right
place in the C code (I break it up into three pieces: declaration,
allocation, de-allocation - actually some actions required a 4th step
between allocation and de-allocation, now I forget what that was, but
you get the idea)

Where could I find more information on this issues? It would be
interested to have a look at these.

From your other response (that I also responded to this evening) I'm not
sure this approach (a DSL that generates C) would necessarily work in
your case, but perhaps it would.

The idea is that if you could somehow describe your algorithm using this
DSL you could then execute the ruby program that your DSL describes and
generate C code. For example, you mentioned array accesses:

Defining the array in Ruby:
array = Array.new(8)

Would have to create the following in C:

int array[8];

Then later on when you access the array:

array[x]= y #in Ruby

generates:
array[x]=y; //in C

Actually, those are prettymuch identical.

YOu could do this by redefining the various Array methods you're using so
that they spit out some corresponding C code when they are run (remember
to alias the original Array methods so that you can call them after
generating the C code - that way your DSL can be executable to actually
run the algorithm as well as generating C code if that's what you want)
Oh, and you probably would need to define some class that pairs a value
with a name, so that the 'y' above would have been defined like:
y = MyVar.newy) #need some way to know the name of var y
(yes, it seems a bit redundant, but there's no way to know the name of
the variable 'y' otherwise when you're generating the C code).

But, based on what you said in your other response, I'm not entirely sure
that this approach buys you much. Perhaps if you need to generate two
different types of output (C and VHDL for example) it might save some
effort to use a DSL approach because you could create to_C and to_VHDL
methods so you would be able to generate either from the same input.

Phil