Fast Bytecode Interpreter

17810121330

Comments

  • jmgjmg Posts: 13,917
    edited 2017-03-22 - 04:55:00
    Seairth wrote: »
    If I understand correctly, this 8-bit penalty only occurs if you encounter 9 or more consecutive ones in the mask. If that's the kind of block skip that's being performed, it seems like a standard branch would be a better fit anyhow.
    I think that is the cost for each 8b crossing. ie cannot do 32 wide due to logic delays, so instead do 4 lots of 8, which is 3 boundaries to cross, no matter what bit pattern is contained there.
    Skip of all but the last opcode (skip31) would be 3 skips + 1 opcode timing.
  • Brian FairchildBrian Fairchild Posts: 508
    edited 2017-03-22 - 07:05:10
    jmg wrote: »
    This is pretty cool ( but I would say that, as I've suggested a SKIP before :) )

    There was a DSP, the AL3101, designed for audio applications whose only flow control opcode was "SKIP condition N". Because you need a constant sample rate for audio, the DSP had a fixed clock rate which was 1024 times the audio sample rate. The DSP executed all 1024 instructions in the program memory in a loop at 1 cycle per instruction. The only conditional execution was the SKIP opcode which tested the flags and did a skip of between 1 and 255 instructions. The effect of the SKIP was to execute those intervening instructions as NOPs. Like that, you had absolute determinism in your timings.

    It's a technique that could be applied to more general cases where you must get something done in a fixed time.
  • Here's an example of how you can use SKIP without going insane.

    Chip, I just read through that this evening. It's pretty darn clean. The use of constants makes a ton of sense.

    I just want to point out, the little operators, ways we can specify data are powerful. The shift operators position the constants nicely, and the OR operators make for a clean, sane data table spec. Love it.

    Looks like a big win to me. I know I can explain this to someone fairly quickly. We should be able to include some examples, perhaps just this one, maybe a driver related one or two, in the more verbose, new or just user docs to come, and get people to the right place on this quick.

    Like anything really powerful, yeah one can make a mess. But, one can make something beautiful too.

    Frankly, I find this easier to digest than I do a complicated set of branches, jumps, snippets and conditionals. In terms of vertical space, so important to see flow, it's hard to beat that body of code for what it does.

    Do not taunt Happy Fun Ball! @opengeekorg ---> Be Excellent To One Another SKYPE = acuity_doug
    Parallax colors simplified: https://forums.parallax.com/discussion/123709/commented-graphics-demo-spin<br>
  • I realized that '_RET_ SKIP' was not working, due to the simultaneous jump. I got that fixed and tried out a bigger priority encoder and shifter, in order to be able to skip 15 instructions at once. It stuck out like a sore thumb in the timing analysis. So, I put things back to 7 instructions getting skipped. That's what we're going to have to live with.
  • It's still a potent option. And programmers do have lots of others, should that somehow end up a bottleneck.

    Do not taunt Happy Fun Ball! @opengeekorg ---> Be Excellent To One Another SKYPE = acuity_doug
    Parallax colors simplified: https://forums.parallax.com/discussion/123709/commented-graphics-demo-spin<br>
  • potatohead wrote: »
    It's still a potent option. And programmers do have lots of others, should that somehow end up a bottleneck.

    It's 8x faster than just cancelling instructions. And it only even happens if there are more than seven 1's in a row. Most code can be jiggered around so that it never even happens. And in case you want to execute just one lone instruction amid many, there's always ALTI, which lets you execute a register as the next instruction.
  • Good stuff, good forum commentary, it's very motivating to watch when Chip is "in the zone".
  • Cluso99Cluso99 Posts: 15,398
    edited 2017-03-22 - 10:11:45
    cgracey wrote: »
    I realized that '_RET_ SKIP' was not working, due to the simultaneous jump. I got that fixed and tried out a bigger priority encoder and shifter, in order to be able to skip 15 instructions at once. It stuck out like a sore thumb in the timing analysis. So, I put things back to 7 instructions getting skipped. That's what we're going to have to live with.
    Easy to live with and way better than nothing!

    Chip,
    Just a thought. Since this makes some 1 clock instructions, and only if easy to do...

    Are the if_xxx instructions where the conditional is not met (ie instruction not executed) capable of being 1 clock?
    If so, could there be a cog setting to enable these 1 clock instructions? I am thinking for determinism they would need to be kept to 2 clocks (hence the default) but if the user wanted speed instead then it could be cog enabled.

    In a similar vein, are any of the ALT/AUG/modifier instructions capable of being 1 clock instructions?

    Forget it. Just realised that this would really upset the pipeline code.
    My Prop boards: P8XBlade2, RamBlade, CpuBlade, TriBlade
    Prop OS (also see Sphinx, PropDos, PropCmd, Spinix)
    Website: www.clusos.com
    Prop Tools (Index) , Emulators (Index) , ZiCog (Z80)
  • JasonDorie wrote: »
    David Betz wrote: »
    I'm not sure what your objection to lambda functions is. Maybe they're more awkward in C++ than they were in LISP.

    Mostly readability. If you issue a callback, inside a few nested if's, and then pass an inline lambda function, it just makes the code harder to follow. I prefer a function pointer, or a derived interface unless it's something really simple.
    As I said, maybe lambda in C++ is less elegant than it was in LISP. I have never tried the C++ version.

  • jmg wrote: »
    Seairth wrote: »
    If I understand correctly, this 8-bit penalty only occurs if you encounter 9 or more consecutive ones in the mask. If that's the kind of block skip that's being performed, it seems like a standard branch would be a better fit anyhow.
    I think that is the cost for each 8b crossing. ie cannot do 32 wide due to logic delays, so instead do 4 lots of 8, which is 3 boundaries to cross, no matter what bit pattern is contained there.
    Skip of all but the last opcode (skip31) would be 3 skips + 1 opcode timing.

    No, I think he's shifting the mask on each instruction fetch. The cost is the depth of the mux for testing the LSBs of the mask. This means you only hit the problem if there is a long (>7?) consecutive run of skips in those LSBs.
  • One thing that concerns me about this development is that we're adding hardware to optimize one particular kind of program (an interpreter). I actually think that if higher Spin performance is a major goal then we should think more out of the box and implement a real Spin compiler (oh wait, we have that already:)) or a JIT bytecode interpreter. No matter what hardware tricks we perform, interpreting the instructions in a loop over and over is always going to be slower than running COG instructions in that same loop. So translating the Spin codes into PASM at run time, for example, would be a much bigger win than adding more hardware support for the interpreter.

    Heck, if you really think that byte codes are that important, why not build the byte codes into the hardware? That will improve perforamnce much more than any specialized instructions for the interpreter.

    I'm not saying "skip" is wrong or a bad idea, although it does have all kinds of potential side effects that make it a minefield for the programmer. But the overall process, where the focus is on optimizing one particular way of implementing one application, seems to me misguided.

    What I really liked about P1 was how simple and elegant it was. I see P2 getting further and further away from that ideal. It seems like a classic second system effect.

    Sorry, I guess I'm just venting here. I'm sure Chip will do whatever he wants, and it'll turn out the way it does. His track record so far is good, so I hope I'm wrong. Most of all I hope we get working silicon sometime this year...

    Eric
  • Look at these snippets which read constants. I've harmonized them by making things like 'wz' consistent, even though it's not always needed:
    con_bx		rfbyte	x	wz
    		setcz	x	wc,wz
    		decod	x
    	if_c	sub	x,#1
    	if_nz	not	x
    	_ret_	pusha	x
    
    con_bp		rfbyte	x	wz
    	_ret_	pusha	x
    
    con_bn		rfbyte	x	wz
    	if_nz	not	x
    	_ret_	pusha	x
    
    con_wp		rfword	x	wz
    	_ret_	pusha	x
    
    con_wn		rfword	x	wz
    	if_nz	not	x
    	_ret_	pusha	x
    
    con_lg		rflong	x
    	_ret_	pusha	x
    
    Those add up to 18 longs.

    They can all be collapsed into 8 longs using SKIP:
    con_x		rfbyte	x	wz	'bx bp bn  |  |  |
    		rfword	x	wz	' |  |  | wp wn  |
    		rflong	x		' |  |  |  |  | lg
    		setcz	x	wc,wz	'bx  |  |  |  |  |
    		decod	x		'bx  |  |  |  |  |
    	if_c	sub	x,#1		'bx  |  |  |  |  |
    	if_nz	not	x		'bx  | bn  | wn  |
    	_ret_	pusha	x		'bx bp bn wp wn lg
    

    Here are the SKIP bit patterns to replicate the original functions (for use in the bytecode interpreter loop):
    CON		con_bx		=	%00000110 << 9		SKIP patterns for con_x
    		con_bp		=	%01111110 << 9
    		con_bn		=	%00111110 << 9
    		con_wp		=	%01111101 << 9
    		con_wn		=	%00111101 << 9
    		con_lg		=	%01111011 << 9
    
  • SeairthSeairth Posts: 2,386
    edited 2017-03-22 - 11:48:51
    Neat, but that example seems counterproductive to your argument for SKIP. You've saved 4 longs at best, and less if you are doing the same lookup technique as your earlier example. While the first block of code is longer, it is definitely easier to read/understand/maintain/modify. With the skip approach, you've added quite a bit of complexity to the code for minor savings.
  • And what are you doing up at 4 in the morning???
  • Cluso99Cluso99 Posts: 15,398
    edited 2017-03-22 - 13:53:55
    Seairth wrote: »
    Neat, but that example seems counterproductive to your argument for SKIP. You've saved 4 longs at best, and less if you are doing the same lookup technique as your earlier example. While the first block of code is longer, it is definitely easier to read/understand/maintain/modify. With the skip approach, you've added quite a bit of complexity to the code for minor savings.

    I'd call 18 -> 8 longs/instructions a good saving.
    The code to jump & skip will be a common routine, so they do not take any more longs.

    But, they will all take longer to execute by about 8 clocks??? (setup + skip instruction plus at least 2 skip overs)
    Is that worth 10 longs??? I am not convinced in this example.

    The setup and skip will be common, and therefore effectively free.
    Still checking on the skip overs but these appear to also be free???

    BTW I can easily see how this works. It's not obscure at all. In fact I find it easier to read what the various bytecodes will do.
    My Prop boards: P8XBlade2, RamBlade, CpuBlade, TriBlade
    Prop OS (also see Sphinx, PropDos, PropCmd, Spinix)
    Website: www.clusos.com
    Prop Tools (Index) , Emulators (Index) , ZiCog (Z80)
  • Cluso99 wrote: »
    Seairth wrote: »
    Neat, but that example seems counterproductive to your argument for SKIP. You've saved 4 longs at best, and less if you are doing the same lookup technique as your earlier example. While the first block of code is longer, it is definitely easier to read/understand/maintain/modify. With the skip approach, you've added quite a bit of complexity to the code for minor savings.

    I'd call 18 -> 8 longs/instructions a good saving.
    You're leaving out the skip instruction itself, plus code and data to calculate the skip mask. That may be non-trivial. Chip's example isn't apples to apples because it doesn't include all the code.
    The code to jump & skip will be a common routine, so they do not take any more longs.
    It's a common routine but it still needs to be there, i.e. yes it does take up space. We'd need to see just how complicated the skip mask calculation is to estimate how much overhead there is.

    For example, IIRC the original Tachyon interpreter executes bytecodes very quickly because each bytecode is basically the address of the routine implementing it. The outer loop for such an interpreter is extremely small and fast, and skip is unlikely to be of much help.

    Eric
  • cgraceycgracey Posts: 11,711
    edited 2017-03-22 - 12:43:34
    Here's the interpreter, so far:
    CON		con_bx		=	%00000110 << 9		SKIP patterns for con_x
    		con_bp		=	%01111110 << 9
    		con_bn		=	%00111110 << 9
    		con_wp		=	%01111101 << 9
    		con_wn		=	%00111101 << 9
    		con_lg		=	%01111011 << 9
    
    		offset_byte	=	%110 << 9		SKIP patterns for mem_rw
    		offset_word	=	%101 << 9
    		offset_long	=	%011 << 9
    
    		base_pbase	=	%110 << 12
    		base_vbase	=	%101 << 12
    		base_dbase	=	%011 << 12
    
    		read_byte	=	%0000_0110_1111 << 15
    		read_byte_indx	=	%0000_0110_0110 << 15
    		read_word	=	%0000_0101_1111 << 15
    		read_word_indx	=	%0000_0101_0100 << 15
    		read_long	=	%0000_0011_1111 << 15
    		read_long_indx	=	%0000_0011_0010 << 15
    		write_byte	=	%0000_1111_1111 << 15
    		write_byte_indx	=	%0000_1111_0110 << 15
    		write_word	=	%0010_1111_1111 << 15
    		write_word_indx	=	%0010_1111_0100 << 15
    		write_long	=	%0110_1111_1111 << 15
    		write_long_indx	=	%0110_1111_0010 << 15
    
    
    DAT		org		'cog space
    '
    '
    ' Interpreter loop
    '
    		rep	#1,#8		'pre-stuff stack with loop address
    		push	#loop		'all uncalled _ret_'s will jump to loop
    
    loop		rfbyte	p		'get program bytecode
    		rdlut	i,p		'lookup long in lut
    		altd	i		'get snippet address from 9 LSBs
    		push	#0		'push snippet address
    		shr	i,#9		'shift right to get 23-bit skip pattern
    	_ret_	skip	i		'set skip pattern and execute snippet
    '
    '
    ' Constant snippets
    '
    con_n1	_ret_	pusha	_FFFFFFFF
    con_0	_ret_	pusha	#0
    con_1	_ret_	pusha	#1
    con_2	_ret_	pusha	#2
    con_3	_ret_	pusha	#3
    con_4	_ret_	pusha	#4
    con_7	_ret_	pusha	#7
    con_8	_ret_	pusha	#8
    con_15	_ret_	pusha	#15
    con_16	_ret_	pusha	#16
    con_31	_ret_	pusha	#31
    con_32	_ret_	pusha	#32
    
    con_x		rfbyte	x	wz	'bx bp bn |  |  | 
    		rfword	x	wz	'|  |  |  wp wn | 
    		rflong	x		'|  |  |  |  |  lg
    		setcz	x	wc,wz	'bx |  |  |  |  | 
    		decod	x		'bx |  |  |  |  | 
    	if_c	sub	x,#1		'bx |  |  |  |  | 
    	if_nz	not	x		'bx |  bn |  wn | 
    	_ret_	pusha	x		'bx bp bn wp wn lg
    '
    '
    ' Memory read/write snippet
    '
    mem_rw		rfbyte	m		'ob |  |	offset
    		rfword	m		'|  ow |
    		rflong	m		'|  |  ol
    
    		add	m,pbase		'bp |  |	base
    		add	m,vbase		'|  bv |
    		add	m,dbase		'|  |  bd
    
    		popa	x		'|  ib iw il	index
    		shl	x,#1		'|  |  iw |
    		shl	x,#2		'|  |  |  il
    		add	m,x		'|  ib iw il
    
    		rdbyte	x,m		'rb |  |	read
    		rdword	x,m		'|  rw |
    		rdlong	x,m		'|  |  rl
    	_ret_	pusha	x		'rb rw rl
    
    		popa	x		'wb ww wl	write
    	_ret_	wrbyte	x,m		'wb |  |
    	_ret_	wrword	x,m		'   ww |
    	_ret_	wrlong	x,m		'      wl
    '
    '
    ' Bytecode lookup values
    '
    		org	$200	'lut space
    
    rw_table	long	con_n1
    		long	con_0
    		long	con_1
    		long	con_2
    		long	con_3
    		long	con_4
    		long	con_7
    		long	con_8
    		long	con_15
    		long	con_16
    		long	con_31
    		long	con_32
    		long	con_x		|con_bx
    		long	con_x		|con_bp
    		long	con_x		|con_bn
    		long	con_x		|con_wp
    		long	con_x		|con_wn
    		long	con_x		|con_lg
    
    		long	mem_rw		|offset_byte|base_pbase|read_byte
    		long	mem_rw		|offset_word|base_pbase|read_byte
    		long	mem_rw		|offset_long|base_pbase|read_byte
    		long	mem_rw		|offset_byte|base_vbase|read_byte
    		long	mem_rw		|offset_word|base_vbase|read_byte
    		long	mem_rw		|offset_long|base_vbase|read_byte
    		long	mem_rw		|offset_byte|base_dbase|read_byte
    		long	mem_rw		|offset_word|base_dbase|read_byte
    		long	mem_rw		|offset_long|base_dbase|read_byte
    		long	mem_rw		|offset_byte|base_pbase|read_byte_indx
    		long	mem_rw		|offset_word|base_pbase|read_byte_indx
    		long	mem_rw		|offset_long|base_pbase|read_byte_indx
    		long	mem_rw		|offset_byte|base_vbase|read_byte_indx
    		long	mem_rw		|offset_word|base_vbase|read_byte_indx
    		long	mem_rw		|offset_long|base_vbase|read_byte_indx
    		long	mem_rw		|offset_byte|base_dbase|read_byte_indx
    		long	mem_rw		|offset_word|base_dbase|read_byte_indx
    		long	mem_rw		|offset_long|base_dbase|read_byte_indx
    
    		long	mem_rw		|offset_byte|base_pbase|read_word
    		long	mem_rw		|offset_word|base_pbase|read_word
    		long	mem_rw		|offset_long|base_pbase|read_word
    		long	mem_rw		|offset_byte|base_vbase|read_word
    		long	mem_rw		|offset_word|base_vbase|read_word
    		long	mem_rw		|offset_long|base_vbase|read_word
    		long	mem_rw		|offset_byte|base_dbase|read_word
    		long	mem_rw		|offset_word|base_dbase|read_word
    		long	mem_rw		|offset_long|base_dbase|read_word
    		long	mem_rw		|offset_byte|base_pbase|read_word_indx
    		long	mem_rw		|offset_word|base_pbase|read_word_indx
    		long	mem_rw		|offset_long|base_pbase|read_word_indx
    		long	mem_rw		|offset_byte|base_vbase|read_word_indx
    		long	mem_rw		|offset_word|base_vbase|read_word_indx
    		long	mem_rw		|offset_long|base_vbase|read_word_indx
    		long	mem_rw		|offset_byte|base_dbase|read_word_indx
    		long	mem_rw		|offset_word|base_dbase|read_word_indx
    		long	mem_rw		|offset_long|base_dbase|read_word_indx
    
    		long	mem_rw		|offset_byte|base_pbase|read_long
    		long	mem_rw		|offset_word|base_pbase|read_long
    		long	mem_rw		|offset_long|base_pbase|read_long
    		long	mem_rw		|offset_byte|base_vbase|read_long
    		long	mem_rw		|offset_word|base_vbase|read_long
    		long	mem_rw		|offset_long|base_vbase|read_long
    		long	mem_rw		|offset_byte|base_dbase|read_long
    		long	mem_rw		|offset_word|base_dbase|read_long
    		long	mem_rw		|offset_long|base_dbase|read_long
    		long	mem_rw		|offset_byte|base_pbase|read_long_indx
    		long	mem_rw		|offset_word|base_pbase|read_long_indx
    		long	mem_rw		|offset_long|base_pbase|read_long_indx
    		long	mem_rw		|offset_byte|base_vbase|read_long_indx
    		long	mem_rw		|offset_word|base_vbase|read_long_indx
    		long	mem_rw		|offset_long|base_vbase|read_long_indx
    		long	mem_rw		|offset_byte|base_dbase|read_long_indx
    		long	mem_rw		|offset_word|base_dbase|read_long_indx
    		long	mem_rw		|offset_long|base_dbase|read_long_indx
    
    
    		long	mem_rw		|offset_byte|base_pbase|write_byte
    		long	mem_rw		|offset_word|base_pbase|write_byte
    		long	mem_rw		|offset_long|base_pbase|write_byte
    		long	mem_rw		|offset_byte|base_vbase|write_byte
    		long	mem_rw		|offset_word|base_vbase|write_byte
    		long	mem_rw		|offset_long|base_vbase|write_byte
    		long	mem_rw		|offset_byte|base_dbase|write_byte
    		long	mem_rw		|offset_word|base_dbase|write_byte
    		long	mem_rw		|offset_long|base_dbase|write_byte
    		long	mem_rw		|offset_byte|base_pbase|write_byte_indx
    		long	mem_rw		|offset_word|base_pbase|write_byte_indx
    		long	mem_rw		|offset_long|base_pbase|write_byte_indx
    		long	mem_rw		|offset_byte|base_vbase|write_byte_indx
    		long	mem_rw		|offset_word|base_vbase|write_byte_indx
    		long	mem_rw		|offset_long|base_vbase|write_byte_indx
    		long	mem_rw		|offset_byte|base_dbase|write_byte_indx
    		long	mem_rw		|offset_word|base_dbase|write_byte_indx
    		long	mem_rw		|offset_long|base_dbase|write_byte_indx
    
    		long	mem_rw		|offset_byte|base_pbase|write_word
    		long	mem_rw		|offset_word|base_pbase|write_word
    		long	mem_rw		|offset_long|base_pbase|write_word
    		long	mem_rw		|offset_byte|base_vbase|write_word
    		long	mem_rw		|offset_word|base_vbase|write_word
    		long	mem_rw		|offset_long|base_vbase|write_word
    		long	mem_rw		|offset_byte|base_dbase|write_word
    		long	mem_rw		|offset_word|base_dbase|write_word
    		long	mem_rw		|offset_long|base_dbase|write_word
    		long	mem_rw		|offset_byte|base_pbase|write_word_indx
    		long	mem_rw		|offset_word|base_pbase|write_word_indx
    		long	mem_rw		|offset_long|base_pbase|write_word_indx
    		long	mem_rw		|offset_byte|base_vbase|write_word_indx
    		long	mem_rw		|offset_word|base_vbase|write_word_indx
    		long	mem_rw		|offset_long|base_vbase|write_word_indx
    		long	mem_rw		|offset_byte|base_dbase|write_word_indx
    		long	mem_rw		|offset_word|base_dbase|write_word_indx
    		long	mem_rw		|offset_long|base_dbase|write_word_indx
    
    		long	mem_rw		|offset_byte|base_pbase|write_long
    		long	mem_rw		|offset_word|base_pbase|write_long
    		long	mem_rw		|offset_long|base_pbase|write_long
    		long	mem_rw		|offset_byte|base_vbase|write_long
    		long	mem_rw		|offset_word|base_vbase|write_long
    		long	mem_rw		|offset_long|base_vbase|write_long
    		long	mem_rw		|offset_byte|base_dbase|write_long
    		long	mem_rw		|offset_word|base_dbase|write_long
    		long	mem_rw		|offset_long|base_dbase|write_long
    		long	mem_rw		|offset_byte|base_pbase|write_long_indx
    		long	mem_rw		|offset_word|base_pbase|write_long_indx
    		long	mem_rw		|offset_long|base_pbase|write_long_indx
    		long	mem_rw		|offset_byte|base_vbase|write_long_indx
    		long	mem_rw		|offset_word|base_vbase|write_long_indx
    		long	mem_rw		|offset_long|base_vbase|write_long_indx
    		long	mem_rw		|offset_byte|base_dbase|write_long_indx
    		long	mem_rw		|offset_word|base_dbase|write_long_indx
    		long	mem_rw		|offset_long|base_dbase|write_long_indx
    

    Here's the loop:
    loop		rfbyte	p		'get program bytecode
    		rdlut	i,p		'lookup long in lut
    		altd	i		'get snippet address from 9 LSBs
    		push	#0		'push snippet address
    		shr	i,#9		'shift right to get 23-bit skip pattern
    	_ret_	skip	i		'set skip pattern and execute snippet
    
    That takes 15 clocks to get into the snippets, with SKIP already running. Every bytecode branches to a snippet with a unique 23-bit SKIP field.
  • Cluso99Cluso99 Posts: 15,398
    edited 2017-03-22 - 13:17:52
    Chip,
    Is this timing correct..
    loop            rfbyte  p               'get program bytecode                   5-18
                    rdlut   i,p             'lookup long in lut                     2
                    altd    i               'get snippet address from 9 LSBs        2
                    push    #0              'push snippet address                   2
                    shr     i,#9            'shift right to get 23-bit skip pattern 2
            _ret_   skip    i               'set skip pattern and execute snippet   2
                                                                                   ------
                                                                        overhead = 15-28
                                                                                   
    con_x           rfbyte  x       wz      'bx bp bn |  |  |                      2  2  2  0  0  0
                    rfword  x       wz      '|  |  |  wp wn |                      0  0  0  2  2  0
                    rflong  x               '|  |  |  |  |  lg                     0  0  0  0  0  2
                    setcz   x       wc,wz   'bx |  |  |  |  |                      2  0  0  0  0  0
                    decod   x               'bx |  |  |  |  |                      2  0  0  0  0  0
            if_c    sub     x,#1            'bx |  |  |  |  |                      2  0  0  0  0  0
            if_nz   not     x               'bx |  bn |  wn |                      2  0  2  0  2  0
            _ret_   pusha   x               'bx bp bn wp wn lg                     2  2  2  2  2  2
                                                                                  -- -- -- -- -- --
                                                                                  12  4  6  4  6  4
    

    So, in the above, there is no execution penalty for these small skips. If there are more than 8 skips in a row, add an extra 2 clocks for each set of 8.
    My Prop boards: P8XBlade2, RamBlade, CpuBlade, TriBlade
    Prop OS (also see Sphinx, PropDos, PropCmd, Spinix)
    Website: www.clusos.com
    Prop Tools (Index) , Emulators (Index) , ZiCog (Z80)
  • Cluso99 wrote: »
    Chip,
    Is this timing correct..

    Shouldn't the _ret_ instructions be +3 clocks for reloading the pipeline? Also, I think it's if there are no more than 7 skips in a row, then you don't get the two clock penalty.

  • cgracey wrote: »
    Here's the loop:
    loop		rfbyte	p		'get program bytecode
    		rdlut	i,p		'lookup long in lut
    		altd	i		'get snippet address from 9 LSBs
    		push	#0		'push snippet address
    		shr	i,#9		'shift right to get 23-bit skip pattern
    	_ret_	skip	i		'set skip pattern and execute snippet
    
    That takes 15 clocks to get into the snippets, with SKIP already running. Every bytecode branches to a snippet with a unique 23-bit SKIP field.

    Clever! I like how you use the the _ret_ and the pre-stuffed call stack.

    Putting this in context to the discussion of processing constants earlier, it's reasonable to argue that the masked version really only takes 8 longs since you were still going to take up 6 longs in the LUT for the jump table either way.
  • On page 1 of this thread, Chip said
    This '_RET_' is an implied return that uses code %0000 of the conditional field. This means NOP cannot be $00000000, anymore, as it would become a RET instruction. Having implied RET's saves lots of instructions, especially in a situation like this where you have lots of snippets of code that get CALL'd. Each _RET_ saves two clocks and a long.
    So the _RET_ is free!
    My Prop boards: P8XBlade2, RamBlade, CpuBlade, TriBlade
    Prop OS (also see Sphinx, PropDos, PropCmd, Spinix)
    Website: www.clusos.com
    Prop Tools (Index) , Emulators (Index) , ZiCog (Z80)
  • It has been said that in all of programming there is only, sequence, selection and iteration.

    Sequence: Do this, then do that, then do...
    Selection: If this do that else do the other...
    Iteration: Keep doing this until that happens....

    With SKIP it looks like Chip has squished Sequence and Selection down to a single instruction!

    Can we also put loops in a block of potentially skipped instructions? That would be a hat trick!
  • SeairthSeairth Posts: 2,386
    edited 2017-03-22 - 14:30:03
    Cluso99 wrote: »
    On page 1 of this thread, Chip said
    This '_RET_' is an implied return that uses code %0000 of the conditional field. This means NOP cannot be $00000000, anymore, as it would become a RET instruction. Having implied RET's saves lots of instructions, especially in a situation like this where you have lots of snippets of code that get CALL'd. Each _RET_ saves two clocks and a long.
    So the _RET_ is free!

    That can't be right, unless the _RET_ flag is being processed at the first stage of the pipeline. But that would have to come with a lot of caveats and edge cases! So, I'm assuming that the _RET_ is still being processed when the "host" instruction is executed. In which case...

    You are only saving the cost of the additional RET instruction (i.e. "saves two clocks and a long"). But _RET_ should still cause the current pipelined instructions to be cancelled and the popped instruction branch to be loaded, just like a RET instruction would have caused. Looking at the instruction listing, RET costs 4 clocks. Presumably, that's 1 for executing and 3 for reloading the pipeline. In the case of something like "_ret_ skip #0", the SKIP will take two cylces to execute and the _ret_ will cause 3 additional cycles for reloading the pipeline.
  • @cgracey, what happens if there's an active skip mask inside of a rep block? Will the rep still work correctly?
  • Almost don't need JMPREL if you have SKIP...
    You can just do a DECODE and then a SKIP, right?
    Prop Info and Apps: http://www.rayslogic.com/
  • Rayman wrote: »
    Almost don't need JMPREL if you have SKIP...
    You can just do a DECODE and then a SKIP, right?

    Nope. Totally different use cases.
  • Seairth wrote: »
    Cluso99 wrote: »
    On page 1 of this thread, Chip said
    This '_RET_' is an implied return that uses code %0000 of the conditional field. This means NOP cannot be $00000000, anymore, as it would become a RET instruction. Having implied RET's saves lots of instructions, especially in a situation like this where you have lots of snippets of code that get CALL'd. Each _RET_ saves two clocks and a long.
    So the _RET_ is free!

    That can't be right, unless the _RET_ flag is being processed at the first stage of the pipeline. But that would have to come with a lot of caveats and edge cases! So, I'm assuming that the _RET_ is still being processed when the "host" instruction is executed. In which case...

    You are only saving the cost of the additional RET instruction (i.e. "saves two clocks and a long"). But _RET_ should still cause the current pipelined instructions to be cancelled and the popped instruction branch to be loaded, just like a RET instruction would have caused. Looking at the instruction listing, RET costs 4 clocks. Presumably, that's 1 for executing and 3 for reloading the pipeline. In the case of something like "_ret_ skip #0", the SKIP will take two cylces to execute and the _ret_ will cause 3 additional cycles for reloading the pipeline.
    No. I believe there is no clock penalty.

    Remember, the fetch of the pop isn't from a cog register/memory, but from an internal register, so it can be gated straight to the instruction counter logic as well as to the cog address register.

    If clock 1 fetches the instruction with _RET_, the clock 2 fetches the D and S operands. Also we know in clock 2 the type of instruction. Provided it is not a jump type such as DJNZ, the RET address can be used as the next fetch address for clock 3, and at the same time gated to the increment logic for PC++. So for normal instructions, the RET will be fetching the instruction at the return address concurrently with the 2 clock ALU stage (clocks 3and 4) of the _RET_ instruction.

    In the DJNZ and similar, in clocks 3 & 4, the DJNZ will assumed to be taken as usual, so will fetch its jump taken address (no ret). If it is determined during the DJNZ ALU execution that the jump is not to be taken, the pipe will be flushed and the PC effectively replaced with the _RET_ address. So again, it will be the DJNZ not taken clocks (think it's a 2 clock penalty?).

    So in all cases, as Chip said, the _RET_ is free!

    My Prop boards: P8XBlade2, RamBlade, CpuBlade, TriBlade
    Prop OS (also see Sphinx, PropDos, PropCmd, Spinix)
    Website: www.clusos.com
    Prop Tools (Index) , Emulators (Index) , ZiCog (Z80)
  • @Cluso99, take a look at Chip's main loop. He's performing a PUSH only two instructions beforehand. If _RET_ was processed early in the pipeline, it would POP before the PUSH occurred!
  • Cluso99Cluso99 Posts: 15,398
    edited 2017-03-23 - 01:50:36
    Chip,
    I could see this execution loop
    loop            rfbyte  p               'get program bytecode                   5-18
                    rdlut   i,p             'lookup long in lut                     2
                    altd    i               'get snippet address from 9 LSBs        2
                    push    #0              'push snippet address                   2
                    shr     i,#9            'shift right to get 23-bit skip pattern 2
            _ret_   skip    i               'set skip pattern and execute snippet   2
                                                                                   ------
                                                                        overhead = 15-28
    
    being able to be utilised in all sorts of interpreters, as well as in special lookup tables for executing special routines.

    Therefore, what about 1 new instruction "execute p" as follows...
    loop            rfbyte  p               'get program bytecode                   5-18
                    execute p                                                       2
                                                                                   ------
                                                                        overhead = 7-20
    
    pipeline clocks for "execute p" would become:
    1:      rd "execute p" instruction 
    2:      rd lut address "p" into internal 32bit register "i" (maybe same as SETQ2 register??)
    3:      forward i[8:0] to PC and cog address so that this clock fetches the next instruction (ie the _RET_ goto)          
            load internal skip register with i[31:9] as skip[22:0] & set skip valid
    4:
    5:      optional: wr i[31:0] to cog register "p"
    6:
    
    By directly forwarding "i" (= contents of lut "p")into the return address and skip register, the push/pop is not required,
    meaning neither is altd i and shr i,#9.
    The "execute p" instruction effectively performs the following in 2 clocks (saving 8 clocks every bytecode)...
                    rdlut   i,p             'lookup long in lut                     2
                    altd    i               'get snippet address from 9 LSBs        2
                    push    #0              'push snippet address                   2
                    shr     i,#9            'shift right to get 23-bit skip pattern 2
            _ret_   skip    i               'set skip pattern and execute snippet   2
                                                                                   ------
                                                                                   10
    
    This would save 8 clocks overhead for every bytecode (down from 15-28).
    My Prop boards: P8XBlade2, RamBlade, CpuBlade, TriBlade
    Prop OS (also see Sphinx, PropDos, PropCmd, Spinix)
    Website: www.clusos.com
    Prop Tools (Index) , Emulators (Index) , ZiCog (Z80)
  • potatoheadpotatohead Posts: 9,785
    edited 2017-03-22 - 17:49:43
    You're leaving out the skip instruction itself, plus code and data to calculate the skip mask.

    Though it can be used dynamically, easy, best case time and density savings is pretty obvious when the masks are known in advance. And that we have a LUT in this design is a big win. Code execute from there is like HUB code, in that the primary COG RAM is used for registers and code. Stuffing the skip patterns into LUT does for code what a LUT does for pixels.

    Will be interesting to see how people end up using this dynamically.

    As presented by Chip, it's really more like "case" for PASM than anything else. I can easily see people using a spreadsheet to optimize time / space critical COG code.
    One thing that concerns me about this development is that we're adding hardware to optimize one particular kind of program (an interpreter). I actually think that if higher Spin performance is a major goal then we should think more out of the box and implement a real Spin compiler (oh wait, we have that already:)) or a JIT bytecode interpreter. No matter what hardware tricks we perform, interpreting the instructions in a loop over and over is always going to be slower than running COG instructions in that same loop.

    Yes, and if we take a look at the more general case uses here, it's clear SKIP will deliver gains in COG centric code overall, not just interpreter code. If it were more specific case, like the instruction Cluso presented, that would actually center on interpreters, and your statement here would be a lot stronger. (not that Cluso has a bad idea there --it's just a great example of this dynamic we are discussing)

    Chip did it general purpose, potentially trading the very peak gains possible, for broad applicability. It's worth doing on that basis. Again, driver code that is COG centric will benefit from this. One super easy case to see is video / pixel crunching COG drivers. Both of those are modal, resolution, depth, including optional dynamically generated and displayed elements.

    SKIP masks, if dynamic, can be generated during blanking times, and or with HUB code, keeping the time critical things in COG. Otherwise, SKIP patterns can be used to account for a broad range of resolutions, depths, display characteristics. While a lot of display uses will be simple, bitmap, tile, sprite, this hardware can do a ton more on a lot less overall HUB RAM when a dynamic display is part of the picture.

    Edit: One case here, with video specifically, involves the NCO based timing. Deriving timing mathematically with a PLL is a lot easier. It's often just a divide and go, maybe rounding a little. The NCO comes with the need to manage jitter and or phase for similar display consistency across different modes, depths and timings. SKIP can be put to great use here. Responsive video drivers are harder and require more code / constants. SKIP will improve on the kinds of drivers people can build and the dynamic capabilities they may offer. Work out all the necessary cases, tabulate them with SKIP, and the end result is going to be compact, easy to USE. In some cases, easy to modify, add to, where warranted. :D

    Doing these things mathematically and or with various overlays, both offer flexibility. But, it's either hard, or slow, and or take code space that must be managed, or leaves the user of the driver code in a position where they should commit to a mode for optimal performance. SKIP, applied well and in a way similar to what we are seeing Chip do with the interpreter, should get the driver closer to looking like hardware, able to respond dynamically.

    Had this been in the P1 in some form, many video drivers would have been either one COG, or more responsive than they ended up being.

    I don't see this feature as a general PASM case tool. Could be, depending on the programmer, but Chip is right. "Ninja level."

    SKIP is for maximizing the hardware access and or presenting library / driver code to others that can perform flexibly and optimally without having to manage so many constants and or conditional code builds. On that point, this presents conditional code in a compelling way when contrasted with #IfDef type meta constructs. IMHO, of course. It has the advantage of being dynamic as well, should a developer choose to offer such to parallel uses of their code. (Have to avoid "downstream" here, as that's often a single processor view, and not inclusive on multi-processor environments.)

    In the case of our SPIN interpreter, making sure it occupies a single COG makes a ton of sense. When people fire off concurrent instances of SPIN, it's going to be nice to see them work mostly like they do on P1. This is a multi-processor point of view optimization.

    SKIP viewed from a single processor point of view can seem excessive and or troublesome. It can't be interrupted, etc... But, SKIP from a multi-processor point of view makes a lot of sense as it's generally going to be compartmentalized and purpose based when used. Most downstream and or parallel use cases won't involve getting into it, meaning the hard work of making sure it's used well and debugged is worth doing. A whole group of us could work something out, and once done, it's done! Super useful PASM objects. No different than we did on P1, just more potent and flexible are possible now.

    For comparison, interrupts, or events as we are gonna end up calling them on the P2, work in a similar way. From a single processor point of view, they are trouble, and we've all identified why and how that's true. All valid. However, P2 is a concurrent multi-processor, and those events are processor unique. We can compartmentalize difficult code. Once that is done, reuse by others is very significantly improved over what we would expect in a single processor, or multi-core scenario lacking the COG memory isolation and concurrency P2 has.

    This is a non trivial difference, and worth keeping in mind, IMHO.

    Do not taunt Happy Fun Ball! @opengeekorg ---> Be Excellent To One Another SKYPE = acuity_doug
    Parallax colors simplified: https://forums.parallax.com/discussion/123709/commented-graphics-demo-spin<br>
Sign In or Register to comment.