Deterministic Timing Alogrithm
SRLM
Posts: 5,045
I'm looking for an algorithm that will work correctly with the Propeller CNT to run a snippet of code every n clock cycles.
The naive approach is something like this:
The problem with this code is that it will fail in the case that the addition to nextMatch rolls over the 32 bit value, and incorrectly satisfies the while condition.
The requirements:
1) The code should correctly account for CNT rollover
2) The code should be flexible enough for several events (ie, run task A every 100ms, task B every 230ms, and task C every 23ms)
3) The code should be posted as an algorithm, and not rely on any specific language features.
4) The hit on each cycle doesn't need to be exactly at the mark: it's ok if it has a bit of jitter. For example, a cycle that should take 100ms everytime:
5) Everything should be in the same cog.
6) Assume that the tasks take almost no time, i.e, you don't need to worry about the execution time of the tasks.
Background: I'd like to be able to read some external sensors. This collection of sensors has different update rates, ie. 300hz, 100hz, and 25hz. I could just read all the sensors at 300hz and "double log" the slower sensors data, but I would prefer to read each sensor at it's output frequency.
The naive approach is something like this:
nextMatch = CNT + delayCycles repeat while CNT < nextMatch do nothing nextMatch += delayCycles //Do something
The problem with this code is that it will fail in the case that the addition to nextMatch rolls over the 32 bit value, and incorrectly satisfies the while condition.
The requirements:
1) The code should correctly account for CNT rollover
2) The code should be flexible enough for several events (ie, run task A every 100ms, task B every 230ms, and task C every 23ms)
3) The code should be posted as an algorithm, and not rely on any specific language features.
4) The hit on each cycle doesn't need to be exactly at the mark: it's ok if it has a bit of jitter. For example, a cycle that should take 100ms everytime:
Do something executed at: 100ms 210ms 302ms 400ms 543ms 600msNotice that it executes Do something once during every 100ms window, with a bias towards the beginning of the window.
5) Everything should be in the same cog.
6) Assume that the tasks take almost no time, i.e, you don't need to worry about the execution time of the tasks.
Background: I'd like to be able to read some external sensors. This collection of sensors has different update rates, ie. 300hz, 100hz, and 25hz. I could just read all the sensors at 300hz and "double log" the slower sensors data, but I would prefer to read each sensor at it's output frequency.
Comments
kReadPeriod = CLKFREQ/10; //Every 100 ms nextReadTime = CNT + kReadPeriod; currentCNT = CNT; //Case CNT = High and nextReadTime = Low if( (currentCNT>>31==1 && (nextReadTime<CLKFREQ) return; //Case CNT = Low and nextReadTime = Low //Case CNT = High and nextReadTime = High if( currentCNT > nextReadTime //Case CNT = Low and nextReadTime = High || ( currentCNT < CLKFREQ && nextReadTime>>31==1 ) ) { //Do something nextReadTime += kReadPeriod; }This block should be called at least once every cycle that the code is expected to run. To run more than one task, simply make duplicates of the above.
If its software tasking in the same cog, I thought there wasn't a nice say to do this without knowing the cycles required for each currently running task. Do we know how long the tasks run? Or can we assume that every candidate task will finish with sufficient time before the next task needs to start?
Good points. The answers:
5) Everything should be in the same cog.
6) Assume that the tasks take almost no time, i.e, you don't need to worry about the execution time of the tasks.
The multi-tasking thread scheduler I have will do what you want. Unfortunately I am not permitted to release it under MIT license where it might end up being used for commercial applications. If your needs are strictly personal, then perhaps I can help you.
The assembler scheduler code consumes a single cog and can repeatedly activate any number of events with one microsecond granularity.
The repeat intervals can also be modified on the fly.
Let me know if this is of interest to you.
Cheers,
Peter (pjv)
-Phil
Make the first step be to determine what the end_time = cnt+running_time is then do the routine. After it returns (hopefully ahead of end_time), wait until CNT = end_time and either do it again via a loop or repeat instruction or for a series of these, do the same as above for each needed item falling through to the next and at the end of all return and do again. Unless you are going to access the hub, and as long as none of the routines jumps the tracks and exceeds your end_time value, you should be ok. As to your concerns of comparison at boundary conditions where cnt <> end time you may need to figure an absolute value from the CNT and end_time and compare it with a fixed value so that when CNT has not rolled over and end_time is less than CNT you can correct for that event.
Consider using the counters as an alternative as well. Determine the count needed for your time requirements, clock at 1/4 freq and set the value to be your time frame in instructions (or clock at freq/1 and the time in instructions being the clock cycles to run the routine. Then, do a waitpne or waiteq for the counter to run out once the routine finishes to repeat or move on to the next one.
Haven't tried this, but not to far down the road it will probably come up....... Those would be the first two methods I would try if I had to do this......
Frank
The point being that waitcnt compensates for rollover, right?
Mickster
You did not mention the size of the tasks, or the precision needed.
The 1ms LSB above, infers you need to resolve to whole 1ms time units ?
If the tasks are shorter than this time-tick, then a simple solution is to run a precision 1ms timer, and then call-off every X,Y,Z counts.
Thanks for the offer, but I would like to stick with less-restricted options for now. Still, I appreciate the nice word that you included: "scheduler". I like it much better than "timer."
This won't fulfill requirement 2 (multiple tasks/periods). I thought about maybe adding three counters, and then using the waitcnt on the "next" one. That solution, however, requires the same rollover code.
Can you provide psuedo-code for the first one?
I've also considered the counter alternative. I have code that will divide the system clock to put the current "time" in units of 1/2400th of a second (or some such odd number) into one of the counter registers. This would allow for the simple implementation of the scheduling algorithm, but a) it won't last for long (a couple of days?) and b) it's jittery for the non integer divisors of the unit.
I don't have any hard requirements for the minimum or maximum time step.
If my memory is good they have a Open Source Scheduler Library in C.
In the Arducopter programs (Ardupilot) perhaps you can find something like that.
Try a Google search about that ?
https://github.com/Zuph/AVRQueue ?
Jean Paul
There's a software round robin for all the tasks. When a task is complete, it gives control to the next task in line.
If a task does something that requires it to wait, it makes its request, then gives control to the next task in line.
Using this method, its very easy to get the tasking loop completely deterministic. Just be sure to give up control periodically when doing somthing too long; for example yeild control at each iteration of a loop in a task. Of course the thing that we have to wait for will always take as long as they take, but they won't impact the rest of the system, since we just yield control while we detect we are waiting.
We do this all the time in forth but it can be done in any language. http://dec.bournemouth.ac.uk/forth/forth.html#13
pub main timer1 := cnt + PERIOD_1 timer2 := cnt + PERIOD_2 timer3 := cnt + PERIOD_3 repeat if ((timer1 - cnt) < 0) timer1 += PERIOD_1 blip(16) if ((timer2 - cnt) < 0) timer2 += PERIOD_2 blip(18) if ((timer3 - cnt) < 0) timer3 += PERIOD_3 blip(20) pub blip(p) high(p) pause(25) low(p)Note that you were just a little bit off in how you calculated the end of the period; this version works -- I lifted the logic from the bit timing of FDS.
CON _clkmode = xtal1 + pll16x _xinfreq = 5_000_000 VAR long intvl0, intvl1, intvl2, intvl3 long time0, time1, time2, time3 long time PUB start | i intvl0 := clkfreq * 10 / 1000 intvl1 := clkfreq * 13 / 1000 intvl2 := clkfreq * 20 / 1000 intvl3 := clkfreq * 22 / 1000 dira[0..3]~~ time := cnt repeat i from 0 to 3 time0[i] := time + intvl0[i] repeat waitcnt(time += (time0 - time) <# (time1 - time) <# (time2 - time) <# (time3 - time)) if (time == time0) !outa[0] time0 += intvl0 if (time == time1) !outa[1] time1 += intvl1 if (time == time2) !outa[2] time2 += intvl2 if (time == time3) !outa[3] time3 += intvl3Here's a snapshot of the output:
One thing to pay attention to is the "time interval granularity," which is the greatest common divisor of all the intervals. In the above example, it's one millisecond. For this technique to work, the loop must always be able to complete in one granular unit of time.
-Phil
if lastcnt is close to rollover then the next interval will be too short.
I tried a little and now I am wondering ...
cnt is unsigned 32 bit
but SPIN arithmetic is signed 32 bit isn`t it ??
please enlighten my confusion
OK I did it myself - SPIN is 32bit signed
CORRRECTED!! - the arithmetic calculations with wrapping around behaviour can be simulated in high level languages like VB by following the + / - operation
with a AND &hFF for 8-bit or what ever bit length is required. This prevents the overflow errors that normally occur.
This confirms that localroger is right. sorry for the confusion.
Example for 8-bit in VBA to run inside EXCEL
Dim cnt As Long Dim lastcnt As Long Dim delaycycles As Long Sub tst1() delaycycles = 17 lastcnt = delaycycles For i = 1 To 1000 cnt = cnt + 1 cnt = cnt And &HFF Selection.Value = i If ((cnt - lastcnt) And &HFF) < delaycycles Then lastcnt = (lastcnt + delaycycles) And &HFF Selection.Offset(0, 1).Value = 1 Else Selection.Offset(0, 1).Value = 0 End If Selection.Offset(1, 0).Select Next i End SubTime := cnt ' lets assume cnt was 0 when this statement was executed repeat waitcnt(Time += Delta) ' lets assume Delta is $11111111 !outa[0]After 15 times through the loop Time will be set to $FFFFFFFF, and once cnt reaches $FFFFFFFF it will exit the waitcnt instruction, execute the !outa[0] and repeat the waitcnt.
The waitcnt(Time += Delta) will add Delta (11111111) to Time ($FFFFFFFF) so time will now equal $11111110, and the waitcnt waits until the cnt register equals that value.
During this time the cnt register has gone from $FFFFFFFF to 0 and continued incrementing at the _clkfreq rate.
-Phil
AND this only works with using waitcnt and not by polling the CNT where you will easily miss the equality.
To handle the polling version requires some more thought and manual handling of the wrap around.
-Phil
Both yours and Phil's are valid points. This only works with waitcnt. By putting the code you want to execute in the repeat loop it will be executed at the desired rate as long as the code in the entire loop takes less time to execute than the waitcnt Delta time.
No it won't. It's an interesting property of this kind of binary math that, for addition and subtraction, it doesn't matter whether it's signed or unsigned; subtraction rolls over. The value (cnt - lastcnt) will always return the number of cycles between the current cnt and lastcnt as long as the difference is less than 31 bits.
-Phil
No, OP is testing out the various methods posted. It takes me a while, but I like to be sure of having a solid base. I've been able to write a test harness using the code that I put in post #2, but now I'm working on substituting Jon's code in to see if it's any better.
As a side note, I'm using this algorithm to read I2C bus sensors. Each sensor comes with a different read frequency specified (150Hz, 100Hz, 25Hz, 20Hz, 1Hz, and 1Hz). So it's definitely practical.