LinuxCNCKnowledgeBase | RecentChanges | PageIndex | Preferences | LinuxCNC.org

Queuebusters revisited

Thinking about the future of linuxcnc, it is helpful to revisit the term 'queuebuster operation'. The result is a bit surprising - there are no 'queuebuster operations', there are only 'queuebuster state references'. I sketch a different, more flexible, less error prone model which is data-driven, not operation-driven.

It turns out this model supports any language in the frontend, without requiring that yet-to-be-defined language having to explicitly handle 'queuebusters'.

The current interpreter execution model

A different perspective on the 'queuebuster problem'

Standing back a bit we see:

So this is really a cache consistency problem. A cache always brings a tradeoff between consistency and performance. Under this angle 'readahead' really means 'generate blocks as long as the state cache is valid'.

Explicit and implicit state references

The key term here is 'reference': that is, when state is referred to, either implicitly or explicitly.

Examples of state references:

Tainted references and the syncing requirement

Some machine operations 'taint' certain parameters. For instance, 'probe' taints the current point, and parameters #5061 up to #5070.

Tainting here means: 'the result of the affected parameter cannot be determined at this point (readahead time)'. Not every change to a parameter taints it: for instance, for endpoint calculation, if the starting point is known, then the endpoint will be known to match between interp and machine, so for instance a move does not taint the current point..

tainting example

Lets look at an example program under the angle 'what information gets tainted by which operation':

 N10    G90
 N20    G38.2 (taints current point, i.e. #5420-#5428, plus #5061 and #5070)
 N30    G91
 N40    G0 X5 (implicit state reference to current point, #5420-#5428)
 N50    o100 if [#5070 EQ 1]   (explicit state reference to #5070)

By tracking the tainting behavior of an instruction, it is possible to automatically determine that a synchronization of the tainted state is required, and where that must happen the latest. In the above example, syncing #5420-#5428 must happen before N40 is executed, and syncing #5070 must happen before N50 is executed.

Forms of state tainting

If we classify interpreter state with respect to tainting we find:

The #5XXX parameters by tainting category

Going through the #5xxx parameters at http://www.linuxcnc.org/docs/devel/html/gcode/overview.html#_numbered_parameters_a_id_sub_numbered_parameters_a we find:

Since the current point is often used, we define its own category for it:

So we really have only 4 tainting categories: never, by probe, by input read, by toolchange. For further discussion, we better rename 'by input read' to mean 'assume as always tainted' . Because it is so common, we add a fifth category: 'current point' (current point valid)

When a category gets tainted, all parameters which are in that category become stale cache values. When any stale parameter is needed as reference, it needs to be refreshed 'by sync'.

Example: Introducing and categorizing a new parameter

Let's assume we want to introduce a new parameter, 'execution time', and give it #5500 for now. We want it to reflect the execution time, in seconds, when the referencing statement is executed. So a use case would be:

     (debug, we are now #5500 seconds into the program)

Clearly, this is a parameter which must be considered 'always tainted' - it is a queuebuster parameter. So to create meaningful output, readahead must stop before this block, wait until the machine 'executes' this statement, signaling that point in execution has been reached. Then it would be ok to determine the elapsed time, set #5500, and continue.

So we'd add #5500 to the 'always tainted' category above.

There are no 'queuebuster operations' - the queue is busted by referencing stale state

I chose the 'execution time' example on purpose - there is no corresponding G-code 'operation', there is just a parameter reference, and *still* we have a queuebuster?

The important conclusion is: readahead needs stopping *when stale state is referenced*, not when 'some queuebuster operation is executed'.

The inverse is also true: Not all programs containing our former 'queuebuster operations' actually need syncing - only those referencing stale state do.

That realization suggests that 'queuebusting' better be handled at the state reference level, not at the operation model.

Tracking tainting and automatic syncing

For each block, we can determine the static pre- and postconditions with respect to state references at parse time:

Then we have a 'current cache condition' which describes which state categories are currently in sync. At program start or interpreter initialization, the 'current cache condition is set to 'all state references invalid:

        valid = {}

This will cause an initial sync, so post-sync we have

       valid = {'byprobe','bytoolchange', 'currentpoint'}. 

We do not record the 'never' category. Also, we do not add the 'always' category.

Outline of cache coherency algorithm

This would be executed as the blocks list is generated, which could be parse time or later.

 initial sync. # start cache condition now: s = {'byprobe','bytoolchange', 'currentpoint'}. 
 while not end of program
      inspect current block and determine set of preconditions p =  {...}
      i = intersect( p, s)
      m = i - p # determine missing categories
      if m != {} # current block references some tainted state
	 wait for sync to succeed
	 s = union(s,m)
	 goto redo:
      q = {...} # set of categories tainted by current block
      s = s - p # invalidate these in current valid set

An example:

 ;s = {'byprobe','bytoolchange','currentpoint'} through initial sync
 G90 ;p = {}, q = {} # G90 has no implicit state references, no categories tainted

 ;s = {'byprobe','bytoolchange','currentpoint'}
 G38.2 ;p = {}, q = {'byprobe','currentpoint'} 

 ;s = {'bytoolchange'}
 G91 ;p = {}, q = {} # G91 has no implicit state references, no categories tainted

 ;s = {'bytoolchange'}
 ; since in relative mode, current  point needs to be valid to determine endpoint
 G0 X5 ;p = {'currentpoint'}, q = {} 

 --> s is missing the 'currentpoint' category here, so a sync is
    Post-sync we again have
    s = {'byprobe','bytoolchange','currentpoint'}
    so the execution succeeds since 'currentpoint' is in the valid set.

 ; s = {'currentpoint','byprobe','bytoolchange'}
 o100 if [#5070 EQ 1]  ;p = {'byprobe'}, q = {} 
 ; no sync needed since 'byprobe' category valid

Determining the precondition set of a block

Determining the taint set of a block:

Implementation outline

(not fully thought through, but straightforward and really simple):

Memory requirements

set size: given that all features including save/restore are recorded here an unsigned32 is fine with lots of reserve.

Processing requirements

Processing tradeoffs

I see the following ways to deal with syncing tainted values:

  1. automatic minimal sync (only sync whats needed right now - more syncs but less information synced per operation)
  2. automatic full sync (less syncs but all possibly tainted parameters synced)
  3. sync explicitly triggered by interpreter when a block is evaluated

Options 1 and 2 mean 'the interpreter has no need to know about tainted parameters'; this would be the future as any new interpreter could choose to just ignore the problem, but it needs to go through getter methods.

Option 3 is likely the easiest to do in the current interpreter code. In this case, getters are optional.

In terms of number of syncs generated, 2 and 3 are identical. not sure whether the difference between 1 and 2 is worth making configurable.


The current interpreter doesnt have a lot of state introspection capabilites, and none are used during stepping, but other interpreter code bases might.

Since performance is not an issue while stepping the interpreter, it could just as well sync at every step. The only change needed to achieve this is to set the current-cache-validity set to 'all values tainted' before a block is evaluated, which will cause a sync before every block evalutaion. There is no point in doing that when using the automatic scheme (options 1 or 2).


Note added 8-8-2012

It just occurred to me that in the algorithm outline above, I implicitly assumed a strict separation of parse and execute phases for a block; during parse one would determine precondition and taint sets, sync if required, only then execute the block.

This assumed separation in the current rs274ngc code doesnt exist, in particular wrt expressions: expressions and assignments are evaluated at parse time. This implies that either syncing must happen on the fly during reference to stale parameters during expression evaluation, or expression handling is separated into a parse tree generation during read() and parse tree evaluation during execute().

LinuxCNCKnowledgeBase | RecentChanges | PageIndex | Preferences | LinuxCNC.org
This page is read-only. Follow the BasicSteps to edit pages. | View other revisions
Last edited August 24, 2012 1:02 am by MichaelHaberler (diff)
Published under a Creative Commons License