Simple coroutine trick, thanks to pipelining.

Phil Pilgrim (PhiPi)

In the thread "Self-modified code execution timing" posted by lucidman, the question came up of what happens when a jmpret (i.e. call) goes to a location containing a ret. Because of pipelining, the new return address is not written until after the value of the target location is fetched, which means the ret jumps to the return address written there from the previous call.

This is, indeed, a serendipitious property! It means that a simple task switcher for cooperative coroutines can be written in one line, without requiring additional memory. To test the theory, I wrote the following program that includes two tasks: one for turning on an LED, another for turning it off.

[b]CON[/b]

  [b]_clkmode[/b]      = [b]xtal[/b]1 + [b]pll[/b]16x
  [b]_xinfreq[/b]      = 5_000_000

[b]PUB[/b] start

  [b]cognew[/b](@switcher, 0)

[b]DAT[/b]

switcher      [b]movs[/b]      switch,#task1           'Initialize switch return address.
              [b]mov[/b]       [b]dira[/b],_0001_0000         'Set A16 (LED) as an output.
              [b]mov[/b]       cntnxt,[b]cnt[/b]              'Initialize time delay.
              [b]add[/b]       cntnxt,delta

task0         [b]mov[/b]       [b]outa[/b],_0001_0000         'Turn LED on.
              [b]waitcnt[/b]   cntnxt,delta            'Wait 1/4 sec.
              [b]call[/b]      #switch                 'Switch to task1.
              [b]jmp[/b]       #task0                  'Loop back when task1 returns.

task1         [b]mov[/b]       [b]outa[/b],#0                 'Turn LED off.
              [b]waitcnt[/b]   cntnxt,delta            'Wait 1/4 sec.                                            
              [b]call[/b]      #switch                 'Switch back to task0.
              [b]jmp[/b]       #task1                  'Loop back when task0 returns.

switch                                          'CALL stores new return address at return,
switch_ret    [b]ret[/b]                               '  and returns to previous caller.

_0001_0000    [b]long[/b]      $0001_0000              'Bit 16.
delta         [b]long[/b]      20_000_000              '1/4 sec at 80MHz.

cntnxt        [b]res[/b]       1                       'Save area for next cnt value.

And it works! The LED flashes on and off with a 1/2-second period.

-Phil

bambino

Sweet!!!!

Without your explaination, I never would have understood whats happening from just looking at the code

Mark Swann

Hmm. I like it.

I suppose this would also work with three (or n) tasks. A very simple round-robin scheduler?

Mark

mynet43

Great discovery! Lots of food for thought. Could be very handy!

Mark Swann

Phil,

On closer examination, one RET can only handle flipping between two coroutines. More complex flipping would require a second RET, as in: task0 calls Switch_A, task1 calls Switch_B, task2 calls Switch_A, etc. I haven't fully thought this through, but it could get quite fancy.

Mark

Phil Pilgrim (PhiPi)

It wouldn't work for round-robin scheduling of three or more tasks, since it's basically just a task-swapper. In round-robin sceduling, the task-switching routine has to keep track of who's next, so the calling routine doesn't have to. The simple paradigm made possible by pipelining will always ping-pong between two tasks. From a task's point of view, the "previous caller" that I switch to is always the task that switched to me.

-Phil

Phil Pilgrim (PhiPi)

Mark,

I looked at a multi-switch scheme like you suggested, but I think it's doomed. What will happen is that for any switch called by two or more tasks, the intended round-robin cycling will lapse into a ping-pong between the last two to call it, and other tasks in the cycle that use other switches will get left out.

This isn't to say that a round-robin scheme that uses jmprets can't exist — just not one that uses this pipelining paradigm.

-Phil

rokicki

Actually, just make it ping pong between the "real" tasks (n of them) and a simple "scheduler" that just "maintains the list".

So to do three, the "scheduler" looks like:

topofloop:
JMPRET rendezvouspt1
JMPRET rendezvouspt2
JMPRET rendezvouspt3
JMP topofloop

To deschedule a task, change the JMPRET to a NOP. To schedule a task, fill in the JMPRET with the appropriate address.

deSilva

The standard implementation for a pair of coroutines A and B is:

A
...
   JMPRET switchA, switchB
...
B
...
  JMPRET switchB, switchA
...

switchA   LONG A
switchB   LONG B

This takes a cell more, but is "clean" and easily expandable to more coroutines...

I should consider this an even more interesting application of JMPRET...

Dennis Ferron

If the Propeller 2 will be made with deeper pipelining than the Propeller 1, that might have unintended consequences with this kind of code.

Still very, very, cool though.

cgracey

The self-modifying code timing will be exactly the same as·it is in·the current Propeller. So, if you modify an instruction and you want the modification to execute, you must place one other instruction between them. If you modify the next instruction, the 'old' next instruction will execute - not the 'new' one.

Dennis Ferron said...

If the Propeller 2 will be made with deeper pipelining than the Propeller 1, that might have unintended consequences with this kind of code.

Still very, very, cool though.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔


Chip Gracey
Parallax, Inc.