How do you pass data between multiable objects in multible COGs?

Charlie Johnson · 2006-05-15 19:29

Attached is an non working (No propeller Dev hareware yet) outline of how I think it would be done.· Please enlighten me, as I feel I am way out in left field.

Thanks

Charlie Johnson
AKA dy8coke

Charlie Johnson · 2006-05-16 19:01

Lots of views but no replies.·· :-)

Post Edited By Moderator (Chris Savage (Parallax)) : 5/17/2006 1:05:51 AM GMT

Martin Hebel · 2006-05-16 19:33

It's too simple [noparse]:)[/noparse]· Simply declare a global variable.· All cogs and all routines in the cogs have access to the same variable.

There's no issue unless the variable is an array (more than 4 bytes) where you may run into a problem of reading data that is in the process of being updated.

-Martin

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Martin Hebel
Southern Illinois University Carbondale - Electronic Systems Technologies

Personal Links with plenty of BASIC Stamp info
StampPlot - Graphical Data Acquisition and Control

Charlie Johnson · 2006-05-16 20:51

Martin,

Thank you for the reply, I will be getting my Propsticks tomorrow so I will be able to play. I will be using the LockNew, LockSet, LockClr and LockRet to control access to the GPS data. I guess I am just getting hung up on the last sentance on page 4-166 of the SPIN Language Reference.· I guess I will just have to play with it tomorrow.

Thanks
Charlie

Post Edited (dy8coke) : 5/16/2006 8:59:08 PM GMT

Martin Hebel · 2006-05-16 21:03

It simply needs to be declared in the top object. If you don't want to be restricted to having every object use the same variable there are means to pass variables addresses that you can use when the lower objects are initialized.

-Martin

Paul Baker · 2006-05-16 21:15

Charlie, you only have a single cog altering the GPS data correct? If so, there is no need for using locks. If the data occupies more than one long (32 bits) you may want to use a status byte, but this is different from a lock. A status byte is another memory location used to indicate that the data is in the process of being updated. Anyone wanting the data would wait until the status indicates the update is complete. This prevents getting data which is part old, part new. The reason you dont want to use a lock is it acts like Hiesenburg's Uncertainty Principle, you must affect the value to detect the value. Since you only want the cog connected to the GPS to control the update status's value, the lock wont work.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
1+1=10

Tracy Allen · 2006-05-16 22:45

Paul,

I don't follow your analogy to the uncertainty principle. It seems to me there is a quantum measure of uncertainty with a status byte, while there is none at all with the lock. BTW, this follows up your great example with the ma

Mike Green · 2006-05-16 23:30

If only one COG is "producing" (writing) data and only one COG is "consuming" (reading) data, you don't have to use a semaphore if you implement the buffer pointer updating properly. This only matters when there's a severe time crunch and you can't afford to lock out the "other" COG long enough to update the pointers. With the Propellor, the overhead to use the semaphore instructions is short. With many operating systems, the equivalent can take many many instructions to do.

Phil Pilgrim (PhiPi) · 2006-05-17 00:02

Guys,

I think a single status bit is only useful/valid when one process (the server) is force-feeding another (the client). In such a scenario, the server sets the status bit when it has data ready. As long as this bit is set, it cannot further update the buffer. The client polls the status bit. When it becomes set, it reads the data buffer, then clears the bit, freeing the server to do another update.

For a more interactive approach, a fully-interlocked handshake can be used. This employs two status bits: RFD (ready for data) and DAV (data available). When the client needs data, it waits for DAV to become cleared. Then it sets the RFD bit. The server, seeing this bit set, and once it has data, sets the DAV bit. As long as this bit is set, the server cannot update the buffer. The client, seeing DAV set, then reads the data and clears its RFD bit. The server, seeing that RFD is clear, then clears the DAV bit.

Neither approach, by itself, is adequate when the server is constantly updating the buffer, and the client needs data only occasionally. For this you can use a semaphore or a modified interlocked handshake that uses two buffers: one for current data that gets updated continuously, and one for communication with the client and which is controlled by the handshaking.

With the Propeller, a valid reason to employ status bits is to conserve the limited lock resource. I ran into this with my dynamic memory manager but was able to solve it by using a single lock, which controlled 32 status bits. To access a status bit, you have to own the lock. Therefore these status bits actually form a set of sub-locks, protected by one master lock.

-Phil

Tracy Allen · 2006-05-17 01:13

Phil, those examples make good sense.

In the case of the GPS, I'm curious, what method would you favor? Say both the reading and the writing of the buffer are asychronous. Do you see any reason a lock would _not_ work?

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com

Phil Pilgrim (PhiPi) · 2006-05-17 01:28

Tracy, in a totally asynchronous client/server environment (call it the "buffet" model), with more than four bytes of long-aligned data being passed, I think a lock is entirely sufficient -- and with the Propeller, drop-dead simple. A lock just enforces synchronization where none exists otherwise. Now, having said that, you may still need two buffers: a character-oriented incoming data buffer that's not governed by the lock, and a block-oriented communications buffer that is. You don't want the lock blocking the stream that comes from the GPS.

-Phil

Post Edited (Phil Pilgrim (PhiPi)) : 5/17/2006 1:32:16 AM GMT

Charlie Johnson · 2006-05-17 02:28

I plan on having multible consumers of the parsed GPS Data. The GPS COG will get, parse and store the data. It will use a lock while updating the parsed data. The raw GPS string is not leaving this COG. Instead of hooking up a RTC, any Object that needs time will get it from the Parsed Data and there is no fixed schedule to say when the time will be needed.

Thanks for this disscussion...Can't wait for the propsticks to show up.

Charlie

Paul Baker · 2006-05-17 02:32

Tracy Allen said...
Paul,

I don't follow your analogy to the uncertainty principle. It seems to me there is a quantum measure of uncertainty with a status byte, while there is none at all with the lock. BTW, this follows up your great example with the ma

Tracy Allen · 2006-05-17 16:43

Paul,

I was more puzzled by the statement, "The reason you dont want to use a lock is it acts like Hiesenburg's Uncertainty Principle, you must affect the value to detect the value. Since you only want the cog connected to the GPS to control the update status's value, the lock won't work." Why won't work? It seems to me it would work easily, provided the caveat that Phii mentioned of perhaps needing double buffering.

Also, Charlie just mentioned having multiple consumers of the GPS data. With the semaphore lock, only one cog can have it at a time, so two cogs can't be either reading at exactly the same time. Each cog that wants to access the buffer attempts to set the lock. If the previous state was clear, it continues on with its routine and does its access, either read or write. And releases the lock when finished. If the previous state was set, it just skips the access routine and tries again later. Only one in control at a time. That could slow down response, because there is nothing otherwise wrong with simultaneous reading. Maybe there is an easy way around that, but whatever it is will certainly take more code, whereas the lock by itself is one instruction. The timing contraints would have to be awfully tight for that to make a difference.

I see how the _interlocked_ handshake status bits Phil suggested would work for the asynchronous process, but it gets more complicated when there are multiple receivers or senders. On the other hand, it seems to me, the semaphore lock is still "drop dead simple", even when there are multiple senders/receivers, provided timing constraints are not too tight.

The way I see the simple status byte fail is,
"Cog0 fetches the status byte, sees its not being updated, and proceeds to read the data on the next rotation."
appending this phrase,
", but during the time of that one rotation, Cog1 starts the update, setting the status to 'update in progress'".
So Cog0 and Cog1 at that instant think they are both in control. It is vastly more problematic for Spin, where there will be hundreds of hub rotations between reading the status and the next action.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com

Paul Baker · 2006-05-17 17:41

Gotcha, sorry I wasn't directly responsive. I was refering to using a semaphore in a writer-reader situation, such as the GPS data. In a one writer/many reader, a reader doesn't need to have exclusive access to the data preventing all others access to it, if two or more readers want simultaneous access they should be able to obtain it. The reference to the Uncertainty Principle is with regard to trying to fit a semaphore into this observation of allowing many readers, but only one writer. For this to occur, a reader would have to test without affecting the field, but the semaphores don't support this ability. In order to read the value, the semaphore's value must be unconditionally set or cleared. This could interfere with what the writer is trying to do.

I admit that spin complicates the issue, but I am willing to bet that the execution time for the·copy operation is symmetric regardless of direction. If the writer is copying data into the GPS data, or a reader is copying data out of the data, the execution time would be the same. So I am nearly convinced at this point no control mechanism is needed if the data is accessed in one swift motion.

For the writer:

Get the GPS data, store in temporary location (WT0,WT1),
GPS0 = WT0
GPS1 = WT1

For the reader:

RT0 = GPS0
RT1 = GPS1
Process data stored in temporary space RT0, RT1

This should work for any arbitrary length of data, the amount of time each assignment takes will be the same, therefore the possibility of an unsynchronized·transfer of data doesn't exist, any interleaving of data between writer and reader will be done in a organized, non-corruptive manner;·determinism dictates this, and while spin isn't fully deterministic, it is when you're doing an apples to apples comparison.

Implementing handshaking, status byte, semaphores or any other control mechanism just creates an unessesary bottleneck in an attempt to cover a situation that wouldn't occur by using an agreed upon methodolgy of accessing the data.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
1+1=10

Post Edited (Paul Baker) : 5/17/2006 5:48:37 PM GMT

Phil Pilgrim (PhiPi) · 2006-05-17 19:17

Paul,

Okay, I think I see what you're getting at: once a reader starts reading data, it will stay as many steps ahead of (or behind) the writer as when it started, so it can't get pieces of two different datasets. I'll buy it insofar as the reader and writer were able to access memory without the commutator intervening. But are you sure the commutator doesn't throw in a wrinkle of uncertainty that might screw up the process?

BTW, one "handshaking" method I forgot to include above is the one often employed with clock chips: read the data multiple times until you get two full datasets in a row which are identical.

-Phil

Charlie Johnson · 2006-05-17 19:37

Since the GPS data will be more than a few longs, I think the use of a semaphore will be the way to go. I don't want the consumer to have LatA, LonB, HdgC and Time
D. it should have LatA, LonA, HdgA at TimeA.

Charlie

Paul Baker · 2006-05-17 20:35

Phil Pilgrim (PhiPi) said...
Paul,

Okay, I think I see what you're getting at: once a reader starts reading data, it will stay as many steps ahead of (or behind) the writer as when it started, so it can't get pieces of two different datasets. I'll buy it insofar as the reader and writer were able to access memory without the commutator intervening. But are you sure the commutator doesn't throw in a wrinkle of uncertainty that might screw up the process?

BTW, one "handshaking" method I forgot to include above is the one often employed with clock chips: read the data multiple times until you get two full datasets in a row which are identical.

-Phil

I dont think the commutator will throw a wrinkle in, what is important is that once the data begins to be accessed by a cog (either reading or writing) that the subsequent accesses occur in a deterministic fashion, it doesnt matter if it is performed every hub rotation, every 4th rotation or every n rotation. As long as the number of rotations is equivalent between accesses and between the reader and writer, data integrity is preserved.

So if a "A = B" is executed in spin, let's say·the first hub access is the "=" (operator), the second hub access is the address of·B (source), the 3rd hub access is copying the value at·B into local memory, the 4th hub access is the address of A (destination) and the 5th hub access is copying the local value of·B into global location B. So even though it takes 5 hub rotations to perform the operation, it should take 5 hub rotations each and every time a pure assignment operation occurs (physical global address to physical global access), whether the writer is doing it or the reader is doing it.

Now if there is a hub operation missed due to some computation done (which likely would occur during decoding or address computation) this should occur in the same span. Perhaps a picture would help:

Lets map a hypothetical assignment operation in spin, and say 2 hub spins are missed in decoding, and 1 is missed in address formation. A | signifies a hub access, and a : signifies a missed hub access. The pattern would be:
 
 
| : : | : | | : |     for both reading an writing assignments, 
                      in the writing, the last | represents the contents of the shared memory being altered
                      in the reading, the middle | represents the contents of the shared memory being read
Heres a diagram of the write sequence (continuous) with the critical access in red, below is all the possible read sequences, thier critical access in red (changed to I to make more promenent)
 
W | : : | : | | : [color=red]I[/color] | : : | : | | : [color=#ff0000]I[/color] | : : | : | | : [color=#ff0000]I[/color] | : : | : | | : [color=#ff0000]I[/color] | : : | : | | : [color=#ff0000]I[/color] | : : | : | | : [color=#ff0000]I[/color] 
 
1 | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : |
2   | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : |
3     | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : |
4       | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : |
5         | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : |  
6           | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | 
7             | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | 
8               | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | 
9                 | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : | | : : | : [color=#ff0000]I[/color] | : |

So given this hypothical sequence for spin to do the assignment operation, there are 9 possible relationships possible between the reader and writer. The read examples 1 - 3 will get the old data, the read examples 5-9 will get the new data, and read sequence 4 will get the new or old data depending on the relationship between the writing cog and the reading cog.

As you can see there is never a situation where the writer "overtakes" a reader, or a reader "overtakes" a writer. They all behave in harmony irrespective of where they are in the sequence, or even how many hub delays occur (as long as the same number of hub delays is consistant between the reader and writer).

Charlie,
·What Im trying to get at is it doesnt matter how many longs there are, as long as the longs are written to or read from using no intervening spin commands (= after = after = for however many longs there are), you could be doing this over thousands of longs if nesessary. In fact the more number of longs there are, the more you want to stay away from using semaphores because it takes so long to access the entire datagram that the writer could actually get starved out of updating the datagram for much longer than it should. Starvation occurs when a high priority process (your cog doing the GPS update) keeps getting bumped by low priority processes (the cogs reading the GPS data) comandering the datagram. Lets say each long access takes 9 hub rotations as in the above example, and you have 16 longs of data, and you have 1 writer and 4 readers. Lets say the writer gets first access and fills up the data, that takes 144 hub rotations, then reader 1 reads it taking another 144 hub rotations, then right after that reader 2 gets the access for another 144 rotations, then reader 3, then reader 4. This will occur because the the readers will be higher up in the waiting cue (due to the predictable rotation of the commutor), so the writer must wait 576 hub rotations before it can update the data again. That is ALOT·of time wasted by all cogs involved waiting for no reason when everyone could be accessing it whenever they feel if they just adhere to a simple rule of accessing the datagram.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
1+1=10

Paul Baker · 2006-05-17 20:48

A caviat to this that I haven't stressed is that the assignment must be equivalent, meaning the address must be of the same form between reader and writer, that means the source address and destination address must be of the same form, for instance the following wouldn't work:

Writer:

GPS0 = WT0
GPS1 = WT1
...
GPSN = WTN

Reader:
RT[noparse][[/noparse]0] = GPS0
RT[noparse][[/noparse]1] = GPS1
...
RT[noparse][[/noparse]N] = GPSN

this is because there is a hidden addition operation in arrays where the array index is added to the array address base, and this could cause the writer to overtake the reader.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
1+1=10

Phil Pilgrim (PhiPi) · 2006-05-17 20:53

Okay, Paul, you've convinced me. I agree that the commutator shouldn't be an issue. However, there's still one thing that may be: In Spin, different variables -- even of the same size -- require different access times, based on how many bytecodes are used to address them. Local variables, for example, require fewer bytecodes to access if they are within the first group of (I believe) eight variables declared. This may or may not also apply to global variables. Chip would have to confirm or deny that. In any event, you'd have to make sure that all the variables involved in the transaction were accessed via the same interpretive mechanism. Once you've done that, I can't find any flaws with your reasoning.

-Phil

Update: As an addendum, I'd also recommend adding copious comments to the program about what's been done. This is the kind of thing which, a couple months down the road, a person might forget and make innocent-looking but no-so-innocent-acting changes to. Also, it's the kind of thing that might break with updates to the compiler.

Post Edited (Phil Pilgrim (PhiPi)) : 5/17/2006 8:58:20 PM GMT

Paul Baker · 2006-05-17 20:56

Excellent point, and something I hadn't fully considered, that would definitely fit into another "hidden aspect" of the caviat I mentioned.

Even more reason for me to get my behind in gear and get to the dissasembler project so we can really look at the spin interpretor code (that would be in a more readable form).

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
1+1=10

Post Edited (Paul Baker) : 5/17/2006 8:59:39 PM GMT

Paul Baker · 2006-05-17 21:13

In re to your update,

Yet another facet I didnt take into consideration (compiler updates). So perhaps a double buffer situation is best. This way the readers could all access a valid data set while the writer updates the other buffer.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
1+1=10

How do you pass data between multiable objects in multible COGs?

Comments