Sandwich Delays. A technique to improve the scheduling of timed tasks in super loops on X2 chips.

Flenser

Senior Member
The problem

A lot, if not most, PICAXE applications use a super loop architecture.
  • It has the advantages that it is simple, and therefore easy to understand, and that it consumes virtually no system memory or CPU resources.
  • It has the limitation that it is very difficult to execute a task at precise intervals of time.
and when tasks need to be executed at specific intervals of time it is common to see the following technique used:
Code:
main:
    <code for task 1>
    pauseus XX
    <code for task 2>
    pauseus YY
goto main:
but this approach will only work if you know the precise duration of each task and these durations never vary. If any of the task durations are variable then it is almost impossible to achieve precisely scheduled tasks with this approach.

A solution

This is where a sandwich delay comes to the rescue.

Between 1999 and about 2014 there was research being done on the development of highly reliable embedded systems using a time-triggered architecture. This seems to have been done mainly at the Univesity of Leicester and the research is described as being targetted at "low-cost, resource-constrained microcontrolles" where the hardware might include "an 8-bit or 16/32-bit microcontroller with very limited memory and CPU performance" and the code was intended to be used in compiled C programs on these small microcontrollers.

The descriptions of "Resource-constained" and "an 8-bit microcontroller with very limited memory and CPU performance" certianly applies to the PICAXE chips so the sandwich delay caught my attention as something that was worth testing to to see if it could be used to improve the scheduling of timed tasks running in super loops on the PICAXE chips.

This post is my implementation, for the PIXAXE X2 chips, of the following sandwich delay example:
Code:
while(1)
{
    Start_Sandwich_Delay(A); // Set timer to match fn. duration
    FunctionA();
    Wait_For_Sandwich_Delay_To_Complete();

    Start_Sandwich_Delay(B);
    FunctionB();
    Wait_For_Sandwich_Delay_To_Complete();

    Start_Sandwich_Delay(C);
    FunctionC();
    Wait_For_Sandwich_Delay_To_Complete();
}
The implementation of a sandwich delay

The sandwich delay uses a hardware timer.
i.e. the start of the sandwich delay always involves starting a hardware timer with this code:
Code:
SETTIMER OFF
SETTIMER <preload value for this sandwich delay duration>
The wait for the sandwich delay is implemented by putting the chip into a low power state using the DOZE command . At the completion of this sandwich delay wite the hardware timer interrupt wakes the chip from the DOZE and the PICAXE firmware simply continues on with the next BASIC command. i.e. no PICAXE BASIC commands need to be executed as a part of waiting for the sandwich delay to complete.

Code:
#PICAXE 20X2

#NO_DATA
#NO_TABLE

SETFREQ M8

; A timer tick occurs every 4us @8MHz 
#DEFINE TIMER_8MHz_10mS        63036
#DEFINE TIMER_8MHz_20mS        60536
#DEFINE TIMER_8MHz_30mS        58036
#DEFINE TIMER_8MHz_50mS        53036
#DEFINE TIMER_8MHz_100mS        40536
#DEFINE TIMER_8MHz_200mS        15536
#DEFINE TIMER_8MHz_250mS        3036

; VARIABLES
SYMBOL    RANDOM_SEED    = W1    ; B3:B2
SYMBOL    TEMP_W0         = W0    ; B1:B0

; INITIALIZATION
HIGH B.0                    ; Initialize B.0 low measure the task 1 sandwich delay duration and high to measure task 2 sandwich delay duration
READADC C.1, RANDOM_SEED        ; Initialize the seed for the RANDOM() function

main:
    SETTIMER OFF
    SETTIMER TIMER_8MHz_50mS    ; Set the sandwich delay for this task
    TOGGLE B.0                ; Toggle B.0 at the start of the task 1 slot
    GOSUB task_1
    DOZE 0                ; Put the chip to sleep until the next hardware timer interrupt
  
    SETTIMER OFF
    SETTIMER TIMER_8MHz_100mS    ; Set the sandwich delay for this task
    TOGGLE B.0                ; Toggle B.0 at the start of the task 1 slot
    GOSUB task_2
    DOZE 0                ; Put the chip to sleep until the next hardware timer interrupt
goto main

task_1:                    ; Task 1 is a random delay in the range 0 - 39.9 ms
    RANDOM RANDOM_SEED
    TEMP_W0 = RANDOM_SEED // 4000
    pauseus TEMP_W0
return

task_2:                    ; Task 2 is a random delay in the range 0 - 89.9 ms
    RANDOM RANDOM_SEED
    TEMP_W0 = RANDOM_SEED // 9000
    pauseus TEMP_W0
return
NOTES:
This approach uses the SETTIMER and DOZE commands so it can only be used on the X2 chips.

For the SETTIMER command the manual states "Timer cannot be used at the same time as the servo command, as the servo command requires sole use of the timer to calculate the servo pulse intervals."

For the DOZE command the manual states "all timers are left on and so the pwmout, timer and servo commands will continue to function". The use of SETTIMER already means that the timer and servo commands will not operate correctly. You might be able to use the pwmout command as it sounds like it does not use the SETTIMER timer.

The DOZE command means that the chip will use less power when tasks are not actually executiing making this approach also useful for battery powered applications.

Disclaimer: This approach relies on the hardware interrupt that occurs when the hardware timer overflows to 0. This behaviour is an undocumented feature of the PICAXE firmware so you use it at your own risk. I've tested it on a 20X2 chip so I expect it should work on the other X2 chips but they are untested.

My investigation with Hippy into the hardware timer interrupt is in this post Setting an interrupt on the timer 0 overflow appears to cause a hardware interrupt at 8x the timer interrupt frequency where we confirmed that the hardware interrupt occurs at 8 x the frequency of the SETTIMER preload value you set for the PICAXE polled timer interrupt. i.e. if you SETTIMER t1s_8 at 8MHz so that the TIMER value will increment every 1 sec then the hardware timer interrupt will occur every 125ms. This means that you will need to allow for this factor of 8 when you calculate the timer preload value to use for your task sandwich delays.

and the timer 1 hardware interrupt behaviour I am using is described in this post by Hippy The hardware timers - utilisation - Post #10
"There is no need to define a polled interrupt using SETINTFLAGS and you do not need to create an INTERRUPT subroutine."
Not needing to create an INTERRUPT subroutine is an advantage as it reduces the overhead of the interpreted PICAXE BASIC commands that need to be executed when using this technique.

Finally, the advice about when to use this type of task scheduling is "to use the simplest super loop that works".
E.g. flashing a LED at 1s probably does not need a sandwich delay and the simpler approach of using fixed PAUSE or PAUSEUS commands would likely be a better solution.

Performance

My gauge for how well the sandwich delay works is how precise the sandwich delay is and how it compares to the precision of a simple task that has just one TOGGLE command and one PAUSEUS command. If the sandwich delay time varies by a lot or if the variation in the sandwich delays is much more than the then variation of a simple PAUSEUS task then the sandwich delay does not perform well.

The tasks in the implementation code above have a TOGGLE B.0 as the first command for both tasks 1 and 2.
  • If I initialize B.0 LOW then the high pusle is the duration of the sandwich delay for task 1
  • If I initialize B.0 HIGH then the high pusle is the duration of the sandwich delay for task 2

And this is code for the two tasks I used to measure the jitter of simple PAUSEUS 10000 and 5000 tasks:
Code:
; INITIALIZATION
LOW B.0
SETFREQ M8

main:
    ; Task 1
    toggle B.0
    pauseus 10000

    ; Task 2
    toggle B.0
    pauseus 5000
goto main
I paste the measured duration of 2000 high pulses using the PULSIN command on a 2nd 14M2 chip running at 16MHz into a spreadsheet to calculate the jitter.

These are the results:
Measured Jitter
Task 1 TOGGLE B.0; PAUSEUS 10000 -0.55% to +0.56%
Task 2 TOGGLE B.0; PAUSEUS 5000 -0.58% to +0.52%
Task 1 50ms sandwich delay -0.46% to +0.45%
Task 2 100ms sandwich delay -0.47% to +0.49%


So the jitter is about the same for different lengths of the sandwich delay and about the same as the jitter for simple PAUSEUS 10000 and PAUSEUS 5000 tasks.

NOTE: Using PULSIN on the 14M2 at 16MHz means that the measured duration of the high pulses has a resolution of 2.5us. This probably effects the accuracy of these measurements so I don't think that we should reading too much into the slightly lower jitter for the sandwich delay tests.
 
Last edited:

Flenser

Senior Member
References:
Pont's 2001 book it is available as a free download Patterns for time-triggered embedded systems (Michael J. Pont 2001)
This book predates the development of the sandwich delay pattern and the implementation for precisely scheduleing tasks described in section 13.4 "A better solution" is to put the application code into an interrupt routine and trigger that using a hardware timer. The main loop is empty in this implementation. i.e. all the application code is executed from the interrrupt routine.

Meeting real-time constraints using “Sandwich Delays” (2006)
This paper is the one that "introduces one new pattern (SANDWICH DELAY) and describes one possible implementation of this pattern".
The implemention described in this paper is a refinement of the solution described in Pont's 2001 book. It has all the tasks and their sandwich delays coded in the interrupt routine. Note that this implementation requires two timers, the first to trigger the interrupt routine and the second to use for the sandwich delays.

Implementation of Highly Predictable Time-Triggered Cooperative Scheduler using Simple Super Loop Architecture (2011)
This paper is where I got the example code for using sandwich delays around tasks in the main loop that uses the hardware timer interrupt to wake the microcontroller from a low-power sleep mode.
Only one timer is needed for the sandwich delays and the duration of each cycle of the main loop is simply the sum of the sandwich delays for the tasks in the loop.
 

Flenser

Senior Member
To judge the performance of Sandwich Delays for this project I measured the task jitter and the results I got were in the range +0.49% to -0.47%.

I've done some further investigation to see if I could find where the jitter was occurring and this update is what I found.

My first thought was that the PICAXE firmware has to do some stuff in the background and so that must be where the variation in execution times were occurring.
I could not find any evidence of this and, in fact, the results from my testing are that there is no variation in the execution time of my simple test program due to the PICAXE firmware.

This is the program I used for my original testing:
Code:
#DEFINE TIMER_8MHz_50mS           53036
#DEFINE TIMER_8MHz_100mS        40536

; INITIALIZATION
HIGH B.0                    ; Initialize B.0 low measure the task 1 sandwich delay duration and high to measure task 2 sandwich delay duration
READADC C.1, RANDOM_SEED        ; Initialize the seed for the RANDOM() function

main:
    SETTIMER OFF
    SETTIMER TIMER_8MHz_50mS    ; Set the sandwich delay for this task
    TOGGLE B.0                ; Toggle B.0 at the start of the task 1 slot
    GOSUB task_1
    DOZE 0                ; Put the chip to sleep until the next hardware timer interrupt
    
    SETTIMER OFF
    SETTIMER TIMER_8MHz_100mS    ; Set the sandwich delay for this task
    TOGGLE B.0                ; Toggle B.0 at the start of the task 1 slot
    GOSUB task_2
    DOZE 0                ; Put the chip to sleep until the next hardware timer interrupt
goto main

task_1:                    ; Task 1 is a random delay in the range 0 - 39.9 ms
    RANDOM RANDOM_SEED
    TEMP_W0 = RANDOM_SEED // 4000
    pauseus TEMP_W0
return

task_2:                    ; Task 2 is a random delay in the range 0 - 89.9 ms
    RANDOM RANDOM_SEED
    TEMP_W0 = RANDOM_SEED // 9000
    pauseus TEMP_W0
return
I use the PULSIN command on a 2nd 14M2 chip running at 16MHz to measure the duration of 2000 high pulses output on the B.0 pin by this program and paste these values into a spreadsheet to calculate the jitter.

I added one and then two extra TOGGLE B.1 commands between the SETTIMER TIMER_8MHz_***mS and the TOGGLE B.0 commands so that the PICAXE firmware would have extra work to do before the TOGGLE B.0 that I was using to measure the sandwich timer duration.
This had no affect at all on the measured jitter.

I then removed extra TOGGLE B.1 commands and the SETTIMER OFF and SETTIMER TIMER_8MHz_***mS commands from both tasks in the main loop and replaced these SETTIMER commands with a single SETTIMER TIMER_8MHz_50mS command in the INITIALIZATION section so that the PICAXE firmware would have no work at all to do before the TOGGLE B.0 that I was using to measure the sandwich timer duration.
This had no affect at all on the measured jitter.

So it appears the jitter I measure in my test program does not appear to be being caused by the work that PICAXE firmware has to do in the background.

Next I investigated whether there could be any jitter in microcontroller clock.
A google search came up with these two forum posts from people reporting clock jitter on both AVR and PIC chips:

I was using a 0.001 uF ceramic cap for the power supply filtering so I added an extra 0.01 uF ceramic cap in parallel as described as the fix in the PIC forum post.
This had no affect at all on the measured jitter.

I then noticed that the results from some of my earlier jitter measurements using the PULSIN command on a 2nd 14M2 chip running at 32MHz were in the range +0.25% / -0.25%.

I retested measuring the jitter:
  • With the Sandwich Timer code running on a 20X2 chip I measured using the PULSIN command on a 14M2 chip running at 32MHz and the results I got were now in the range +0.22% / -0.22%.
  • With the Sandwich Timer code running on a 28X2 chip I measured using the PULSIN command on a 20X2 chip running at 64MHz and the results I got were now in the range +0.19% / -0.20%.

So my original jitter results measured using PULSIN at 16MHz appear to have been wrong due to me usint the longer 2.5uS resolution of PULSIN at 16MHz.

Finally I found the following two section in the PIC datasheets:
The 08M2, 14M2, 18M2, 20M2 & 20X2 datasheets all have this table. This one if from the 20X2 datasheet.
25096

This table is from the 28X2/40X2 datasheet:
25097

So the jitter on the 20X2 chip measured using PULSEIN at 32MHz is a close match to the datasheet while the jitter on the 28X2 chip using PULSEIN at 64MHz is within the range, but much less than, the tolerance in the datasheet.
 

hippy

Technical Support
Staff member
Interesting analysis. Whenever I have looked at timings of the on-chip oscillators I have always been impressed that have been 'bang on', a lot better than the +/-2% datasheet spec would suggest. I am guessing the bell curve of variance more a high mountain shaped 'pulse' than gentle hill.

If my maths is correct, it looks like a 1 second delay could be +/-2.5ms out which for most intents and purposes would be fine, +/-1ms in 400ms.
 
Top