Author |
Message |
robfinch
Joined: Sat Feb 02, 2013 9:40 am Posts: 2095 Location: Canada
|
Is the following a way of implementing the Forth swap primitive ? Code: SWAP: OVER >R >R DROP R> R>
Is there another faster way of implementing swap ?
_________________Robert Finch http://www.finitron.ca
|
Tue Jan 23, 2018 4:46 am |
|
![](./styles/serenity/theme/images/spacer.gif) |
Garth
Joined: Tue Dec 11, 2012 8:03 am Posts: 285 Location: California
|
LOL, that's a pretty complicated way to do a SWAP ! But yes, it'll work. Is this for a stack machine where the instructions shown are assembly-language instructions (making this a primitive)?
_________________http://WilsonMinesCo.com/ lots of 6502 resources
|
Tue Jan 23, 2018 7:38 am |
|
![](./styles/serenity/theme/images/spacer.gif) |
robfinch
Joined: Sat Feb 02, 2013 9:40 am Posts: 2095 Location: Canada
|
Yes, they are assembly language instructions for a stack machine. There isn't an easy way to do a swap primitive in hardware, so I'm looking at how it can be done using the limited instruction set. Although it's six instructions I think it'll execute in only two clock cycles. The instructions are short - 5 bits. I thought there might be a way using DUP and XOR as well.
I've basically got the Bugs18 instruction set plus a couple of more instructions. I have room to add a couple of instruction if that would help. But it can't be an exchange. About the only thing I could think of was to modify the DROP instruction to shift the dropped values into a temp storage area then add two instructions to push back the temporary storage words. That would reduce the instruction sequence to four instructions, but the additional instructions would be useless for anything but a swap.
_________________Robert Finch http://www.finitron.ca
|
Tue Jan 23, 2018 12:20 pm |
|
![](./styles/serenity/theme/images/spacer.gif) |
BigEd
Joined: Wed Jan 09, 2013 6:54 pm Posts: 1783
|
Could you take a leaf from the Z80 implementation, and implement a swap by twiddling the addressing of the register file?? (I'm assuming the stack, or the top of it, are actually registers on chip)
|
Tue Jan 23, 2018 1:19 pm |
|
![](./styles/serenity/theme/images/spacer.gif) |
Dr Jefyll
Joined: Tue Jan 15, 2013 5:43 am Posts: 189
|
robfinch wrote: But it can't be an exchange. What if you don't actually swap what's in those locations? Could there be some sort of indirection or register renaming that merely alters which register gets selected? Just throwin' the idea out there. That's how my KK Computer swaps the contents of K0 and K3 when doing a Far jump or call -- it just toggles a flipflop that says which register is which; the data never actually moves. Obviously that's in a much simpler context, and the cost in your case would be a lot higher. But maybe there'd be spin-off benefits that make it worthwhile. I leave that to you to judge! ( For those who may've missed it, the post describing the Bugs18 CPU is here. ) ps- darn it, Ed! You managed to post while I was still typing! ![Razz :P](./images/smilies/icon_razz.gif)
|
Tue Jan 23, 2018 1:22 pm |
|
![](./styles/serenity/theme/images/spacer.gif) |
robfinch
Joined: Sat Feb 02, 2013 9:40 am Posts: 2095 Location: Canada
|
Quote: Could you take a leaf from the Z80 implementation, and implement a swap by twiddling the addressing of the register file? Quote: What if you don't actually swap what's in those locations? Could there be some sort of indirection or register renaming that merely alters which register gets selected? Thanks, I had not thought of fiddling with the address. Maybe some kind of map would work. There are only 64 locations after all. The LSB address bit can't just be flipped because that would mean memory is accessed in pairs on even addresses and the address might be odd. Memory is laid out like: address0 address1 address0 If the bit of the second cell is flipped which other cell should be referenced ? If there was a map maybe incrementing the one cell and decrementing the other one would do for a swap. But that's tricky because the map may need to be reset at some point. The problem is also parallel hardware. What if there's a swap followed by a swap (with an intervening operation) ? A map could get quite scrambled. In any case its looking like a complicated solution would be required. I may go back to changing DROP into a POP operation into a fifo instead of a stack. Then have add a PUSH from fifo operation. It would allow swapping the order of words on the stack around. It might be usable with other things like numeric conversions. Code: POP POP POP PUSHR \ reverse order push PUSHR PUSHR
would change the order of the top three words around on stack. Maybe if the fifo were accessible with fetch and store too it would be more useful. I have to put some more thought into it.
_________________Robert Finch http://www.finitron.ca
|
Tue Jan 23, 2018 8:31 pm |
|
![](./styles/serenity/theme/images/spacer.gif) |
Myron Plichota
Joined: Mon Jan 22, 2018 2:49 pm Posts: 19
|
robfinch wrote: <snip>There isn't an easy way to do a swap primitive in hardware,<snip> Actually, this is no more difficult than any other single-cycle primitive. In psuedo-HDL: Code: on_rising_edge_of_clk begin switch(current_instruction) begin case swap begin top_of_stack <- next_on_stack next_on_stack <- top_of_stack end ... other primitives end end
The only reason that Bugs18 does not implement swap is because other primitives were deemed more valuable given the limited choice of 16 4-bit encodings. A wider opcode (eg. 32 5-bit encodings) would increase the choices of what to implement. Myron Plichota
|
Wed Jan 24, 2018 10:48 pm |
|
![](./styles/serenity/theme/images/spacer.gif) |
robfinch
Joined: Sat Feb 02, 2013 9:40 am Posts: 2095 Location: Canada
|
Quote: Actually, this is no more difficult than any other single-cycle primitive. In psuedo-HDL: I've been a bit misleading in the simplicity of the core. I should maybe mention that the instructions are all executing in parallel at the same time (sort of). The new top of stack from one instruction is fed to the next one in a cascade of logic, and the instruction needs to update the stack at the same time. Right now I have the core writing only one value to the top of stack per instruction executed (five write ports). Updating the next on stack at the same time would double the number of write ports required just for that single instruction, and the cores already huge (50,000 LUTs). It's only about 350 LOC but has lots of read / write ports in it. Cascading the logic no double slows down the cycle time a lot but everything gets done in one cycle.
_________________Robert Finch http://www.finitron.ca
|
Thu Jan 25, 2018 4:57 am |
|
![](./styles/serenity/theme/images/spacer.gif) |
BigEd
Joined: Wed Jan 09, 2013 6:54 pm Posts: 1783
|
It must be the second write port which hurts - but then, it's only needed for one register, I think? Is there a way to make use of that?
|
Thu Jan 25, 2018 11:16 am |
|
![](./styles/serenity/theme/images/spacer.gif) |
Dr Jefyll
Joined: Tue Jan 15, 2013 5:43 am Posts: 189
|
I wrote: What if you don't actually swap what's in those locations? Could there be some sort of indirection or register renaming that merely alters which register gets selected? robfinch wrote: [...] Maybe some kind of map would work. There are only 64 locations after all. [...] If there was a map maybe incrementing the one cell and decrementing the other one would do for a swap. But that's tricky because the map may need to be reset at some point. The problem is also parallel hardware. [...] A map could get quite scrambled. [...] It does sound challenging! But since you're crazy enough to contemplate a parallel implementation I thought I'd throw the idea out there -- a map, as you say. Register renaming, although in a form far more complex and expensive than what my KK or the Z80 does. BigEd wrote: It must be the second write port which hurts - but then, it's only needed for one register, I think? Two, since it's a swap we want. Probably what you meant. But the real trouble is it won't always be the same two, if I understand what Rob's up to.
Last edited by Dr Jefyll on Thu Jan 25, 2018 3:35 pm, edited 1 time in total.
|
Thu Jan 25, 2018 3:02 pm |
|
![](./styles/serenity/theme/images/spacer.gif) |
BigEd
Joined: Wed Jan 09, 2013 6:54 pm Posts: 1783
|
(I was thinking one of the writes just uses the usual write port - you need one write port to get anywhere! - and so it's only the other write which needs a second port. If that were always the top of stack - and if that were always the same physical register - then I was thinking of pulling that register out of the register file. However, you might be right, and the world of Rob's CPU is much more complex than that.)
|
Thu Jan 25, 2018 3:27 pm |
|
|