Forums

Tripple buffering scheme

Started by Soumit November 15, 2004
Hi,
  I am working on DM642 video driver, it uses triple buffering scheme.
I am unable to understand the queuing mechanism.
"Soumit" <soumit_mukherjee@rediffmail.com> wrote in message 
news:dd04640a.0411151315.367e6569@posting.google.com...
> Hi, > I am working on DM642 video driver, it uses triple buffering scheme. > I am unable to understand the queuing mechanism.
hmmmm... that's too bad. What is it about the queuing that you don't understand? I find no mention of triple buffering in the data sheet. So, are you referring to a particular driver instead? I wonder why triple buffering would be used. Do you have any idea? Have you considered that a single frame buffer and double buffering have characteristics that overlap? For example, double buffering will allow the interframe transitions to occur between frames while single buffering will sometimes have the transitions near the frame edges - which appear nearly the same as the result from double buffering. In both cases there will be judder. Have you considered that buffering beyond double will accentuate the anomalies of frame repeating / frame dropping? More isn't necessarily better. More buffering will increase the elapsed time between frame drops / frame repeats but those drops and repeats will have greater impacts because there are more frames repeated / dropped. Fred
Hi Fred,

"Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote

> I wonder why triple buffering would be used. Do you have any idea? > Have you considered that a single frame buffer and double buffering have > characteristics that overlap? For example, double buffering will allow the > interframe transitions to occur between frames while single buffering will > sometimes have the transitions near the frame edges - which appear nearly > the same as the result from double buffering.
I don't understand why you make this statement: the whole point of using double buffering is so that you can complete the frame before displaying it...
> In both cases there will be judder.
I also don't understand this statement.
> Have you considered that buffering beyond double will accentuate the > anomalies of frame repeating / frame dropping?
Again, I don't see this.
> More isn't necessarily > better. More buffering will increase the elapsed time between frame drops / > frame repeats but those drops and repeats will have greater impacts because > there are more frames repeated / dropped.
Any explanations gratefully received by the curious! Ciao, Peter K.
Peter,

Responses interspersed at *** below.

Let me say that when I first encountered frame dropping and frame repeating 
I somehow had the naive notion that it was due to poor engineering or cheap 
design.  Of course, it isn't.  It's due to physics.

The analogy I like is this:
Put a race horse and a race car on the same track and have them proceed 
around the track in the same direction at their normal running speeds - the 
car being faster than the horse.
Let the car "read" the horse poops that are regularly deposited on the 
track.
Let the horse "read" the oil drops that are regularly depositied on the 
track (new drops cancel older drops).
Eventually the race car will overtake the horse and will re-read a "frame" 
of "data".
Eventually the horse will be overtaken by the car and the horse will read 
new drops of oil - and will miss a circuit of older drops.

The extension to double buffering uses a figure-8 race track and when the 
junction is reached, the car takes the loop that will cause it to not 
overtake the horse.  Or, the horse takes the loop that will cause it to not 
be overtaken by the car.

There is no escape from dropping / repeating racecourse circuits or video 
frames when the rates are different.

Fred

"Peter Kootsookos" <p.kootsookos@iolfree.ie> wrote in message 
news:3fca8095.0411171700.6219e85b@posting.google.com...
> Hi Fred, > > "Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote > >> I wonder why triple buffering would be used. Do you have any idea? >> Have you considered that a single frame buffer and double buffering have >> characteristics that overlap? For example, double buffering will allow >> the >> interframe transitions to occur between frames while single buffering >> will >> sometimes have the transitions near the frame edges - which appear nearly >> the same as the result from double buffering. > > I don't understand why you make this statement: the whole point of > using double buffering is so that you can complete the frame before > displaying it...
***I did say: "double buffering will allow the interframe transitions to occur between frames" which I think is almost equivalent to what you say here: "so that you can complete the frame before displaying it". However, I would not use your statement verbatim Peter. That's because it's not clear to me what "complete the frame" means. Here's an example of what I mean here: Let's assume double buffering. I'm assuming that the buffers are filled line by line and are read out line by line. So, a buffer does not have to be filled in order to start reading from it - it only needs to be filled by the time you read the last line. Thus, writing a frame does not have to be *complete* before starting to display / read it. Perhaps this is a nit and everyone understands this to be the case.
> >> In both cases there will be judder. > > I also don't understand this statement.
***Judder is the anomaly that occurs when a frame is repeated or when a frame is dropped. In the former case things in motion "jump" forward instantaneously. In the latter case, things in motion stop briefly. Both appear as jerky motion when the motion should be smooth. A single buffer will effectively exhibit the same thing when the frame split is near the beginning or the end of the buffer. Otherwise, single buffering results in a mid-frame jog in vertical lines if there is horizontal motion. It's this jog that multiple buffering will eliminate. However it will not eliminate the judder caused by frame dropping / repeating.
> >> Have you considered that buffering beyond double will accentuate the >> anomalies of frame repeating / frame dropping? > > Again, I don't see this.
***OK. Let's assume: a) single frame buffer b) double frame buffer c) quadruple frame buffer a) With a single frame buffer there is no opportunity to avoid inter-frame overlap. That is, if writing is faster than reading then a frame will be skipped, potentially at mid-frame. If reading is faster than writing then a frame will be repeated, potentially at mid-frame. b) With a double frame buffer let us assume that we alternate writes into the buffers. When we initiate a read, we have the option of reading from either buffer. If the writing is only somewhat faster than reading we can start the read process immediately after writing and in the original, first buffer. However, eventually, we get to a point that if a read is started in buffer "W" it will be overwritten by the write process before the frame read is completed. This is unacceptable - so we initiate the read from buffer "X" which is the last buffer just read. But, this buffer was written after we read it. Thus there is the frame drop which we expect because reading is slower than writing. If reading is faster than writing we have to wait for enough of the first frame to be written before we can read a full frame. Thereafter we can read until we get to a point that if a read is started in buffer "W" it will overtake the write process before the frame read is completed. This is also unacceptable - so we initiate the read from buffer "X" which is the last buffer just read. But, this buffer has not been written anew. Thus there is the frame repeat which we expect because reading is slower than writing. c) With a more-than double buffer - quadruple in this example - the two situations in B are modified as follows: - With W>R and buffers W,X,Y and Z, eventually we get to a point that if a read is started in buffer "W" it would be overwritten by the write process before the frame read is completed. This is unacceptable - so to take advantage of the added buffers, we initiate the read from the buffer that is closest behind the write that is possible, buffer "Z". Accordingly, buffers W,X and Y are dropped. - With R>W and buffers W,X,Y and Z, eventually we get to a point that if a read is started in buffer "W" it would overtake the write before the frame read is completed. This is unacceptable - so to take advantage of the added buffers, we initiate the read from the buffer that is closest ahead the of the write that is possible, buffer "X". Accordingly buffers X,Y and Z are repeated. So, while the frequency of these anomalies is reduced with quadruple buffering, the degree of the transient is much greater. Reducing the drop / repeat number of frames effectively goes back to a smaller number of buffers. Or, maybe there's a more elegant implementation that I've not thought of..... Fred
Fred Marshall wrote:

  ...

> So, while the frequency of these anomalies is reduced with quadruple > buffering, the degree of the transient is much greater. Reducing the drop / > repeat number of frames effectively goes back to a smaller number of > buffers.
When reading and writing happen at different rates, the number of frames written and read in a given time must differ. The number of frames that must be dropped or repeated in that time is determined only by the difference in rates, and not at all by the scheme. At least two buffers must be used to add or insert complete frames. For most purposes, the least objectionable way is to space the corrections as evenly as possible in time. So, ... Jerry -- Engineering is the art of making what you want from things you can get. &#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
I think you're talking about different things here. Of course you need 
to insert/delete frames if you change the display rate - that's 
equivalent to zero order hold "interpolation" for audio. You could also 
interpolate between adjacent frames - the better the result should be 
the more frames you need to buffer (as in all higher order 
interpolation schemes).

However, what Peter K. refers to as "double buffering" is a technique 
used to avoid drawing directly in the screen buffer (which would create 
flicker). You do this by silently drawing into a second buffer and when 
you're done you simply swap the addresses of the two buffers to display 
it.

The former implies a change in display frame rate, the latter does not.
-- 
Stephan M. Bernsee
http://www.dspdimension.com

"Stephan M. Bernsee" <spam@dspdimension.com> wrote in message 
news:302sh1F2ri5loU1@uni-berlin.de...
> > I think you're talking about different things here. Of course you need to > insert/delete frames if you change the display rate - that's equivalent to > zero order hold "interpolation" for audio. You could also interpolate > between adjacent frames - the better the result should be the more frames > you need to buffer (as in all higher order interpolation schemes). > > However, what Peter K. refers to as "double buffering" is a technique used > to avoid drawing directly in the screen buffer (which would create > flicker). You do this by silently drawing into a second buffer and when > you're done you simply swap the addresses of the two buffers to display > it. > > The former implies a change in display frame rate, the latter does not. > -- > Stephan M. Bernsee > http://www.dspdimension.com >
I haven't looked closely at that video port driver but I think it can actually use more than 3 buffers. This is used for doing things such as MPEG-2 encode/decode where you have a group of pictures (GOP) that requires you to do things such as motion vectors based on past frames and interpolation of frames. In response to the original question, Soumit, have you read any app notes on this? Here's a link to the DM642 product page: http://focus.ti.com/docs/prod/folders/print/tms320dm642.html There are several app notes on video port drivers. For example, section 3.2 of spra918a talks about the buffer management: http://focus.ti.com/docs/apps/catalog/resources/appnoteabstract.jhtml?abstractName=spra918a Brad
Jerry said:

When reading and writing happen at different rates, the number of frames
written and read in a given time must differ. The number of frames that
must be dropped or repeated in that time is determined only by the
difference in rates, and not at all by the scheme. At least two buffers
must be used to add or insert complete frames. For most purposes, the
least objectionable way is to space the corrections as evenly as
possible in time. So, ...

Jerry

Then Stephan said:

"Stephan M. Bernsee" <spam@dspdimension.com> wrote in message 
news:302sh1F2ri5loU1@uni-berlin.de...
> > I think you're talking about different things here. Of course you need to > insert/delete frames if you change the display rate - that's equivalent to > zero order hold "interpolation" for audio. You could also interpolate > between adjacent frames - the better the result should be the more frames > you need to buffer (as in all higher order interpolation schemes). > > However, what Peter K. refers to as "double buffering" is a technique used > to avoid drawing directly in the screen buffer (which would create > flicker). You do this by silently drawing into a second buffer and when > you're done you simply swap the addresses of the two buffers to display > it. > > The former implies a change in display frame rate, the latter does not. > -- > Stephan M. Bernsee > http://www.dspdimension.com >
We would probably agree if we were in front of a white board drawing pictures because I know that you know ...... However, I have to take a little exception with the words. These cases being a literalist seems somehow useful. First Jerry's remarks: Absolutely. The difference in frame rates determines the number of frames written and read in a given time. This is what I call "physics". It's also correct to say that "The number of frames that must be dropped or repeated in that time is determined only by the difference in rates". However, while I might agree technically, I can't jump to simply saying "not at all by the scheme" as I'll try to make clear below. I also agree that "at least two buffers "must be used to add or insert complete frames". Stephan's remark about interpolation is a good one. I'm reminded of the approach used to undo 3-2 pulldown - which is a type of interpolation I suppose. However, when there's motion then the more frames used for interpolation, the fuzzier the image will become. So, that's not what's typically done. Just study MPEG to see how much effort is involved in dealing with motion frame-to-frame. I believe you'll find that the better decoding approaches put lots of effort into dealing with motion. I can't imagine that we all don't understand double buffering Stephan.... My points was that *more* than double buffering is often not a good idea because: (first some simple background): Single buffering will cause "tears" in vertical lines that have horizontal motion - when the frame data changes in mid-frame. Single buffering will look like double buffering - when the frame data changes at the top or bottom edge. (Normally the frame split rotates - so these conditions "alternate"). As we all know, double buffering eliminates the tearing by forcing the frame data changes to occur on an entire frame. Now...... What if we think that "more is better" and that multiple buffers would be better than double buffering? Unless there is some strange hardware constraint, I suggest this is not so and I suggest that the number of frames dropped or repeated at an instant will increase using N buffers > 2. So, while one can only agree with Jerry that the number of frames dropped or repeated *per unit time* is the same, this implementation does two things: 1) It reduces the frequency of the occurrence of the drop/repeat points. 2) It increases the number of frames dropped or repeated from 1 (seen with double buffering) to (N-1). So, the judder rate is reduced at the expense of greater distances involved in the judder. In double buffering the judder is exhibited by a single frame being repeated or dropped each occurrence. In N>2 buffering the judder is exhibited by (N-1) frames being repeated or dropped each occurrence. How do you think it looks if motion stops for 3 frames? How do you think it looks if motion advances 3 frames? .... even if the occurrences are fewer? To argue that the number of frames dropped or repeated at one instant *could be* less in this implementation is to suggest the implementation should be used *as if* it were a double buffer. This takes away the intended purpose of the multiple buffer. So, the implementation does impact the number of frames dropped or repeated *at one time* on an absolute basis while not changing the rate. And, that's usually "a bad thing". Fred
Fred Marshall wrote:

> Jerry said: > > When reading and writing happen at different rates, the number of frames > written and read in a given time must differ. The number of frames that > must be dropped or repeated in that time is determined only by the > difference in rates, and not at all by the scheme. At least two buffers > must be used to add or insert complete frames. For most purposes, the > least objectionable way is to space the corrections as evenly as > possible in time. So, ... > > Jerry > > Then Stephan said: > > "Stephan M. Bernsee" <spam@dspdimension.com> wrote in message > news:302sh1F2ri5loU1@uni-berlin.de... > >>I think you're talking about different things here. Of course you need to >>insert/delete frames if you change the display rate - that's equivalent to >>zero order hold "interpolation" for audio. You could also interpolate >>between adjacent frames - the better the result should be the more frames >>you need to buffer (as in all higher order interpolation schemes). >> >>However, what Peter K. refers to as "double buffering" is a technique used >>to avoid drawing directly in the screen buffer (which would create >>flicker). You do this by silently drawing into a second buffer and when >>you're done you simply swap the addresses of the two buffers to display >>it. >> >>The former implies a change in display frame rate, the latter does not. >>-- >>Stephan M. Bernsee >>http://www.dspdimension.com >> > > > We would probably agree if we were in front of a white board drawing > pictures because I know that you know ...... However, I have to take a > little exception with the words. These cases being a literalist seems > somehow useful. > > First Jerry's remarks: > > Absolutely. The difference in frame rates determines the number of frames > written and read in a given time. This is what I call "physics". It's also > correct to say that "The number of frames that must be dropped or repeated > in that time is determined only by the difference in rates". However, while > I might agree technically, I can't jump to simply saying "not at all by the > scheme" as I'll try to make clear below. > > I also agree that "at least two buffers "must be used to add or insert > complete frames". > > Stephan's remark about interpolation is a good one. I'm reminded of the > approach used to undo 3-2 pulldown - which is a type of interpolation I > suppose. > > However, when there's motion then the more frames used for interpolation, > the fuzzier the image will become. So, that's not what's typically done. > Just study MPEG to see how much effort is involved in dealing with motion > frame-to-frame. I believe you'll find that the better decoding approaches > put lots of effort into dealing with motion. > > I can't imagine that we all don't understand double buffering Stephan.... > > My points was that *more* than double buffering is often not a good idea > because: > (first some simple background): > Single buffering will cause "tears" in vertical lines that have horizontal > motion - when the frame data changes in mid-frame. > Single buffering will look like double buffering - when the frame data > changes at the top or bottom edge. > (Normally the frame split rotates - so these conditions "alternate"). > As we all know, double buffering eliminates the tearing by forcing the frame > data changes to occur on an entire frame. > > Now...... > What if we think that "more is better" and that multiple buffers would be > better than double buffering? > Unless there is some strange hardware constraint, I suggest this is not so > and I suggest that the number of frames dropped or repeated at an instant > will increase using N buffers > 2. So, while one can only agree with Jerry > that the number of frames dropped or repeated *per unit time* is the same, > this implementation does two things: > 1) It reduces the frequency of the occurrence of the drop/repeat points. > 2) It increases the number of frames dropped or repeated from 1 (seen with > double buffering) to > (N-1). So, the judder rate is reduced at the expense of greater distances > involved in the judder. > > In double buffering the judder is exhibited by a single frame being repeated > or dropped each occurrence. > In N>2 buffering the judder is exhibited by (N-1) frames being repeated or > dropped each occurrence. How do you think it looks if motion stops for 3 > frames? How do you think it looks if motion advances 3 frames? .... even > if the occurrences are fewer? > > To argue that the number of frames dropped or repeated at one instant *could > be* less in this implementation is to suggest the implementation should be > used *as if* it were a double buffer. This takes away the intended purpose > of the multiple buffer. So, the implementation does impact the number of > frames dropped or repeated *at one time* on an absolute basis while not > changing the rate. And, that's usually "a bad thing".
Fred, We agree completely. When I wrote that the number of frames dropped or repeated in a given time is independent of the scheme, I had in mind the total in a relatively long interval. I also wrote that one wanted these temporal discontinuities spaced as evenly as possible, consistent with the desire to act on whole frames (or fields). I summed up the rest of your argument with "So ...". That was probably too terse. :-) Jerry -- Engineering is the art of making what you want from things you can get. &#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
"Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote 

> > Responses interspersed at *** below. >
Fred, thanks heaps for the explanation! I see we're talking about two slightly different beasts: in my case (drawing overlay graphics on video), the buffer read and buffer write rates are generally the same. Double-buffering is used, as Stephan said, to reduce the flicker of such overlay graphics which occurs when you write directly to the display buffer. Triple buffering can help in this pipeline if you have multiple processes and lots of extra overlay to draw. Again, it's usually the case that dropping any frames is a Bad Thing(TM), so we keep the read and write rates precisely in-synch. The trade off in double-buffering is that there is a one-frame delay between what you're playing (reading from file) and what you're displaying. Triple-buffering causes a two-frame delay. This can get annoying if there is accompanying audio and it is not delayed appropriately. Ciao, Peter K.