video buffering scheme, nonsequential access (no spatial locality)

[wallge]

I am doing some embedded video processing, where I store an incoming
frame of video, then based on some calculations in another part of the
system, I warp that buffered frame of video. Now when the frame goes
into the buffer
(an off-FPGA SDRAM chip), it is simply written in one pixel at a time
in row major ordering.

The problem with this is that I will not be accessing it in this way. I
may want to do some arbitrary image rotation. This means
the first pixel I want to access is not the first one I put in the
buffer, It might actually be the last one in the buffer. If I am doing
full page reads, or even burst reads, I will get a bunch of pixels that
I will not need to determine the output pixel value. If i just do
single reads, this waists a bunch of clock cycles setting up the SDRAM,
telling it which row to activate and which column to read from. After
the read is done, you then have to issue the precharge command to close
the row. There is a high degree of inefficiency to this. It takes 5,
maybe 10 clock cycles just to retrieve one
pixel value.

Does anyone know a good way to organize a frame buffer to be more
friendly (and more optimal) to nonsequential access (like the kind we
might need if we wanted to warp the input image via some
linear/nonlinear transformation)?

 

[Patrick Dubois]

I have somewhat the same problem and I'm using ram that provides fast
random access, i.e. ZBT ram. You can get ZBT ram that runs at 200 MHz,
so that you can effectively process 100 Mpixels/s. ZBT ram is very
small compared to SDRAM, but if you only need to store a few frames,
that shouldn't be a problem.

Adding ZBT might not be an option on your system however... Maybe
someone can suggest a clever algorithm for your particular problem.


Patrick Dubois

 

[Martin Thompson]

I am doing some embedded video processing, where I store an incoming
frame of video, then based on some calculations in another part of the
system, I warp that buffered frame of video. Now when the frame goes
into the buffer
(an off-FPGA SDRAM chip), it is simply written in one pixel at a time
in row major ordering.

The problem with this is that I will not be accessing it in this way. I
may want to do some arbitrary image rotation. This means
the first pixel I want to access is not the first one I put in the
buffer, It might actually be the last one in the buffer. If I am doing
full page reads, or even burst reads, I will get a bunch of pixels that
I will not need to determine the output pixel value. If i just do
single reads, this waists a bunch of clock cycles setting up the SDRAM,
telling it which row to activate and which column to read from. After
the read is done, you then have to issue the precharge command to close
the row. There is a high degree of inefficiency to this. It takes 5,
maybe 10 clock cycles just to retrieve one
pixel value.

If you are doing truly arbitrary warping, then is it not right that
you can never get an optimal organisation for all warps?

Does anyone know a good way to organize a frame buffer to be more
friendly (and more optimal) to nonsequential access (like the kind we
might need if we wanted to warp the input image via some
linear/nonlinear transformation)?

Could you do some kind of caching scheme where you read an entire DRAM
row in at a time, and "hope it comes in handy" later?

Failing that, can you use SSRAM for your frame buffer?

Or, can you parallelise your task so that it operates on (eg) 4 wildly
different areas of input data at a time, which means you can use the
banking mechanism of the DRAMs to hide the latency?

Those are my initial thoughts (whilst waiting for a very loooooong
simulation to run

Cheers,
Martin

 

[Mike Treseler]

Does anyone know a good way to organize a frame buffer to be more
friendly (and more optimal) to nonsequential access

Sounds like a RAM.
If it didn't fit in fpga block ram
I would use an external device.

-- Mike Treseler

 

[wallge]

I should have been more specific in my question.

I have to use a small (64 Mbit) mobile sdram. I can't choose
to use a different storage element in the system (other than *some*
FPGA buffering, though not full frame).

I have heard some discussion of the way in which graphic accelerator
boards do memory transactions, storing pixels in blocks of neighbor
pixels
(instead of being organized row major). In other words the spatial
locality
in the SDRAM buffer might look like:

Image pixels:
N2 N3 N4
N1 P N5
N8 N7 N6

Memory organization:
ADDR DATA
0x0000 P
0x0001 N1
0x0002 N2
0x0003 N3
0x0004 N4
0x0005 N5
0x0006 N6
0x0007 N7
0x0008 N8


Where P is the central pixel of interest, and the N's are its
neighbors.
We organize the pixels in the SDRAM buffer not by rows, but by regions
of interest.
This way if we are doing some kind of Image warp and we want to get
more bang for the buck
in terms of read latency, we are more likely to reuse pixels in the
neighborhood of the currently accessed pixel
than if we were arranged in a row or column major ordering (consider
the case were we wanted to rotate an image by 47.2 degrees from input
to output).

Has anyone seen something like this or know of any resources online
with regard to memory buffer organization schemes for graphics or image
processing?

 

[Pete Fraser]

Image pixels:
N2 N3 N4
N1 P N5
N8 N7 N6

Have you thought about what order of filtering you'll
need to use?

 

[wallge]

I am not doing any image filtering.
This is not a filtering operation.
It is an interpolation operation
typically bilinear or bicubic
to do image transformations.

 

[Pete Fraser]

I am not doing any image filtering.

Yes you are.

This is not a filtering operation.

Yes it is.

It is an interpolation operation
typically bilinear or bicubic
to do image transformations.

And that's a filtering operation.
So the maximum kernel size is 4 x 4, though
you might use 2 x 2. The kernel size could have a substantail
bearing on the traffic to/from on-chip RAM.

I'm still not sure of your limitations on off-chip RAM.
You have a buffer on the input or output (or both?)
Do you have enough bandwidth to have an
intermediate buffer for a two-pass operation?

 

[wallge]

Can you write out the FIR filter coeffs for
a bilinear interpolation "filter kernel"?
How about a bicubic interpolator filter kernel
what are its filter coeffs?

arguing semantics was not the purpose of my post.

I will probably wind up doing bilinear interpolation or
"filtering". Which means I need 4 pixels of the input frame to
determine
1 pixel of output warped frame.

By the way what is the Freq response of the bilinear interpolation
"filter"?

 

[Pete Fraser]

Can you write out the FIR filter coeffs for
a bilinear interpolation "filter kernel"?
How about a bicubic interpolator filter kernel
what are its filter coeffs?

I'm happy to, but we're getting away from FPGA stuff,
so let's do that off line. Let me know how many phases you
need, and the coefficient format you'd like. I usually
use a minor 4x4 variation on cubic, but it's all set up in
Mathematica, so I could do cubic also.

arguing semantics was not the purpose of my post.

I will probably wind up doing bilinear interpolation or
"filtering". Which means I need 4 pixels of the input frame to
determine
1 pixel of output warped frame.

So you don't really need coefficient tables for this.
You can just use the fractional phase directly.

By the way what is the Freq response of the bilinear interpolation
"filter"?

It depends on the position of output relative to input pixel, but
for a central output pixel the frequency response would be
Cosusoidal.

Getting back to FPGA stuff though, what are your off-chip
RAM bandwidth limitations, and could you consider a two-pass approach?

 

[wallge]

I am not sure what you mean by two pass approach.
The max (theoretical) bandwidth I have available to/from the SDRAM
is about
16 bits * 100 Mhz = 1.6 Gbit/sec

This is not an achievable estimate of course, even if I only did full
page
reads and writes, since there is overhead associated with each. I also
have to refresh periodically.

My pixel bit width could be brought down to 8 bits. That way I could
store 2
pixels per address if need be.

 

[Martin Thompson]

I am not sure what you mean by two pass approach.
The max (theoretical) bandwidth I have available to/from the SDRAM
is about
16 bits * 100 Mhz = 1.6 Gbit/sec

This is not an achievable estimate of course, even if I only did full
page
reads and writes, since there is overhead associated with each. I also
have to refresh periodically.

Don't forget that for video apps, you often don't need to refresh, as
you are reading and writing the SDRAM rows in a regular fashion which
means you can guarantee that each gets touched often enough.

Indeed for some video applications, like output framebuffers, all you
need to do is ensure that you read the row out for display soon enough
after the write, which is often easy to achieve.

Cheers,
Martin

 

[wallge]

Gabor,

Are you saying that I don't need to activate/precharge the bank
when switching to another?
I am kind of unclear on this. When do activate and precharge commands
need to be issued? I thought when switching to a new row or bank you
had
to precharge (close) the previously active one, then activate the new
row/bank before
actually reading from or writing to it. Where am I going wrong here?

Also to the notion that I don't need to refresh since I am doing video
buffering: I am actually buffering multiple frames of video and then
reading
out several frames later. In other words, there may be a significant
fraction
of a second (say 1/8~1/4 sec) of delay between writing data into a
particular page of memory and actually reading it back out.
Is this too much time to expect my pixel data to still be valid
without refreshing?

 

[Marcus Harnisch]

Are you saying that I don't need to activate/precharge the bank when
switching to another?

Not necessarily.

I am kind of unclear on this. When do activate and precharge
commands need to be issued? I thought when switching to a new row or
bank you had to precharge (close) the previously active one, then
activate the new row/bank before actually reading from or writing to
it. Where am I going wrong here?

You have to precharge a bank only when you switch to another row
within that bank.

Also to the notion that I don't need to refresh since I am doing
video buffering: I am actually buffering multiple frames of video
and then reading out several frames later. In other words, there may
be a significant fraction of a second (say 1/8~1/4 sec) of delay
between writing data into a particular page of memory and actually
reading it back out. Is this too much time to expect my pixel data
to still be valid without refreshing?

That very much depends on the access patterns. The fact that you are
going to implement a frame buffer alone doesn't automatically mean
that you won't need a refresh. Double-, or triple-check your specs. If
in doubt I'd definitely recommend putting in a refresh as low priority
task.

Regards,
Marcus

--
note that "property" can also be used as syntaxtic sugar to reference
a property, breaking the clean design of verilog; [...]

-- Michael McNamara
(http://www.veripool.com/verilog-mode_news.html)

 

[wallge]

I just wanted to say thanks to everyone for responding
with a lot of helpful answers and feedback in this post.
Really great forum.