Problem with my algorithm

[electroRF]

Hi,
I'm got a 10KB buffer in a small memory, and I divide it into 2 equal halves.
I write data to it on real time.
Every time I cross to from one half another, I trigger a DMA to transfer the previous half to a large memory.

Every time I write to the 10KB buffer, I reserve in advance (atomic operation) the length of the data to be written, and only then I write it.
That is in order to protect every data from being overridden in case it's interrupted by other data.

The problem is that:

It occurred to me a few times that when I came to write a message A to the 10KB buffer in the end of the top half (i.e. just before crossing to the bottom half) I was interrupted by another message B, and therefore didn't finish yet to write message A.
Message B already crossed to the bottom half, and triggered the DMA to transfer the top half.

Now, before the uC returned to complete Message A (which is in the end of the top half), the DMA already transferred the top half (it took the uC "too long" to get back and finish writing message A).

Therefore, what happens here is that the DMA lost message A, since message A was written completely only AFTER the DMA finished transferring the top half.

How can I avoid losing messages in such way?

I cannot afford writing each message in atomic operation, because it'd damage the real-time functionality of the system (What I could afford was to reserve the length of the message in advance, in atomic operation)

Thank you very much.

 

[NorthGuy]

You need another pointer.

Right now you have "Reserved" and "Transmitted by DMA". You need "Reserved", "Completely written" and "Transmitted by DMA".

 

[electroRF]

Hi NorthGuy,
thank you friend, im always happy to get your feedback.

could you please explain what you meant by that?

i didnt quite follow you.

Currently, I got 2 pointers:

1. Global Pointer which points on the next address to write to, on the 10KB Buffer

2. Global Pointer which points on the next address for the DMA to transfer data to, on the large Buffer

 

[NorthGuy]

You need a third pointer which reflects the amount of data actually written. You advance it after the data is written. Since the data written might be fragmented, it is actualy more of a counter than a pointer.

Let's call them

R- reserved
W-written

You do:

R += requested; // atomic; reserves the space
  //write something; doesn't need to be atomic
W += requested; // atomic; mark that the writting is done.
if (R == W) {
  // think about DMA
}

 

[electroRF]

Hi NorthGuy,
I like your idea.

I can also ask:

if (W >= (5120) ) //5120 = 5K = Half Buffer's Size
{
    W = 0;
    TriggerDma;
}

My fear is that I may write an entire half buffer, before (W >= 5120), and in this case, I'd be in a problem.

I think of another way which I'd like to get your opinion on.

Currently, I do:

A = R - Address_Of_Half_Buffer
if (signbit != Expected_sign_bit)
{
    Excpected_sign ^= 1; //According the the signbit, I know whether to transfer the lower of higher half of the Buffer
    TriggerDma;
}

Now, I think of:
- When I'm in the first half of the buffer, I'd compare the R Pointer with address of 1/4 of the Buffer
- When I'm in the second half of the buffer, I'd compare the R Pointer with the address of 3/4 of the Buffer

That way, only when I reach 3/4 of the Buffer, I'd transfer the first half of the Buffer, and that way I'd lower the chances that I didn't manage to complete a message in the first half of the buffer, before instructing the DMA to transfer the first half to the Large Buffer.

Additionally, the DMA transfers data much faster than I fill 1/4 of the 10KB Buffer.

What do you think of it?

I didn't figure out yet how to do it efficiently though, do you have a suggestion please?

Thank you very much!

 

[NorthGuy]

Obviously, with high enough data rate and slow enough DMA write rate, any method will fail. Therefore, you cannot design a method which works for every situation, only for a specified data rate.

You absolutely need to know timing parameters. What is your peak data rate? How much data can get written at the peak rate? What is the minimum time in which the full buffer might be filled? How about half the buffer? Or quarter of the buffer? How fast are writes to your "fast" memory? How fast are writes to the "slow" memory? How fast can you trigger DMA? How fast DMA writes?

Without answers to these questions, there is absolutely impossible to discuss whether 1/4 buffer solution is better than 1/2 buffer. For some timing patterns, one will be better, but for different timing pattern, it could be opposite. There's also a possibility that both are ok, or both are unacceptable.

 

[electroRF]

hi NorthGuy,
thank you again!

the dma transfer rate 10 times faster than the messages rate.

ts why i think of transferring the first half when i reach the 4th quarter, and transfer the second half when i reach the 2nd quarter

 

[electroRF]

what do you think of it?
how would you implement it?

 

[NorthGuy]

the dma transfer rate 10 times faster than the messages rate.

That doesn't quite answer a dozen of questions that I've asked, so we're still in the dark here.

When the output from the buffer is so much faster than the input, you usually do not need a big buffer. With the little information we have, it doesn't seem like the existance of intermediary circular buffer is justified at all. Just building a short (2 or 4 requests) DMA request queue, or perhaps even writing directly to the "slow" memory, is likely to give you better performance.

 

[electroRF]

Hi NorthGuy, thanks friend.

data rate iz 10kB/3ms while transfer rate is 10 times faster.

i cant predict completely written rate, but obviously its max 10kB/3ms.

i cant afford writing directly to the slow buffer, too slow.

what do you mean by dma queue of requezt

 

[NorthGuy]

30 us/KB is 120ns to write a word (32-bit), it's 12 instructions. If your average write is 5 words, it's perhaps 60 instructions (can't tell exactly withot knowing your MIPS). Would writing directly save you 60 instructions? Probably not, but it might be. You can disassembly and count the instructions. If it was 10us/KB, it would be a totally different story.

If your DMA is 10 times faster than your peak data rate, you do not need a big buffer at all.

You create a small pool of buffers. Each of the buffers is big enough to hold few messages and DMA destination address (perhaps some other DMA information). When you need to write, you pick up a free buffer, add a message to it. At the end of each write, if DMA is not busy, you initiate DMA on the buffer you just wrote to. Will work faster becuase you don't need to worry about wrapping. Will save you 8K of memory or so.

If you only have one DMA channel, you can go with 2 relatively big (512 bytes?) buffers. If you have more than one, you can go with 4-6 smaller buffers with one message per buffer.

 

[electroRF]

hi NorthGuy, thank you again mate.

the thing is that i cant afford triggering the DMA every few writes.

I think of trigerring it to transfer half buffers, every time i cross either to the 4th or 2nd quarter.

that should work well, since i already worked that way only that i triggered the DMA every time i crossed to the 1st or 2

 

[NorthGuy]

the thing is that i cant afford triggering the DMA every few writes.

What do you mean by "can't afford"?

 

[electroRF]

hi NorthGuy

Triggering the DMA would cost me too many cycles as i measured it.

thats why i wanna trigger the DMA every half buffer amd have the buffer as bigger as i can afford.

do you have an idea how to detect with one IF condition that i crossed to the 2nd or 4th

 

[electroRF]

i meant an idea to detect the i reached the 2nd or 4th quarters, with one IF condition, so when i crossed to the 4th Q. i would transfer the 1st half and when i crossed to the 2nd Q. i'd transfer the2nd half.

I manage to do it with one IF condition, but when reaching the 1st or 3rd Quarters

 

[NorthGuy]

Triggering the DMA would cost me too many cycles as i measured it.

How many cycles exactly? Have you looked at the disassembly of your DMA triggering code? Since it saves cycles elsewhere, it may be worth it.

If you do not want to trigger it very often, you can make buffers bigger so that they can fit more messages. Right now you're spending enormous amount of cycles to deal with circularity, which, with DMA being this fast, doesn't produce any benefits. Getting rid of the circularity (in favor of plain buffers) will save you much more cycles than bettering a single logical operation.

 

[electroRF]

hi NrothGuy,
thank you friend!

triggwring the dma involves powering on the bus if its off, and writing the dma registers, which sums up to 4us which i honestly cant afford to spend too often.


how would several buffers,in small mwmory would be transferred to a 100 times bigger memory?

 

[NorthGuy]

triggwring the dma involves powering on the bus if its off

Who powers it off when DMA is done?

and writing the dma registers

This part should be few cycles only.

how would several buffers,in small mwmory would be transferred to a 100 times bigger memory?

You just record the destination big memory address when you start the buffer. Then DMA transfers it to there.

 

[electroRF]

Hi NorthGuy,
Thank you again,

The uC powers the bus off if none of the tasks need that bus.

You just record the destination big memory address when you start the buffer. Then DMA transfers it to there.

So you still need to take care of circularity, don't you?

I think that dividing the small memory buffer into two halves, is the simplest and easiest solution, and it makes it very efficient to check whether to transfer the first half or second half.

However, now that I want to transfer the first half, when I'm in the 4th Quarter, and to transfer the second half, when I'm in the 2nd quarter, it makes it a bit more challenging, and that' the logic I'm looking for.

Any idea?

 

[NorthGuy]

The uC powers the bus off if none of the tasks need that bus.

So, if you don't tell it that you don't need it then it won't turn it off right? The question is do you tell it to turn it off?

So you still need to take care of circularity, don't you?

Not when you write into small memory. Writing without worrying about wrapping is twice as fast on most processors as when checking for wrapping.

As to the big memory, since it is now big you don't really want to worry about loosing few hunderd bytes out of it, so you can get rid of circularity too. If something doesn't fit at the end, you don't wrap it, but rather start re-writting your buffer from the beginning. Will save you some cycles too.