View unanswered posts | View active topics It is currently Mon Oct 15, 2018 3:48 pm



Reply to topic  [ 11 posts ] 
 Forth Primitives 
Author Message

Joined: Sat Feb 02, 2013 9:40 am
Posts: 675
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
Profile WWW

Joined: Tue Dec 11, 2012 8:03 am
Posts: 250
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
Profile WWW

Joined: Sat Feb 02, 2013 9:40 am
Posts: 675
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
Profile WWW

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 995
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
Profile
User avatar

Joined: Tue Jan 15, 2013 5:43 am
Posts: 177
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! :P

_________________
http://LaughtonElectronics.com


Tue Jan 23, 2018 1:22 pm
Profile WWW

Joined: Sat Feb 02, 2013 9:40 am
Posts: 675
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
Profile WWW

Joined: Mon Jan 22, 2018 2:49 pm
Posts: 5
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
Profile

Joined: Sat Feb 02, 2013 9:40 am
Posts: 675
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
Profile WWW

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 995
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
Profile
User avatar

Joined: Tue Jan 15, 2013 5:43 am
Posts: 177
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.

_________________
http://LaughtonElectronics.com


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
Profile WWW

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 995
(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
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 11 posts ] 

Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software