> I must admit I wasn't thinking clear. Yes,
your solution
>looks very good. Are you willing to patent it :> ? But I
>still belive that the fact that range of jump (ie. how much
>you can jump forwards/backwards from current position)
>depends on location of opcode within page may need carefull
>thinking during tool chain development.
> I believe for that reason it only makes sense if the block size is small
enough that you
work with the worst case without hassle. If you leave significantly more
than two bits
of the adder intact you can always assume that you are at the wrong end
of the block
without loosing a large portion of your jump range.
Also note that in an FPGA if you use the adder also for another purpose
than adding jump
displacements the logic to block the carry might use up more delay that
the removal of
half the adder bits saves you.
Kolja Sulimma
Reply by Tomasz Sztejka●April 7, 20052005-04-07
--- Rob Finch <robfinch@robf...> wrote: >
>
> --- In fpga-cpu@fpga..., Tomasz Sztejka
> <sztejkat@y...> wrote:
> >
> > --- Rob Finch <robfinch@s...> wrote:
> > >
> > (...)
I must admit I wasn't thinking clear. Yes, your solution
looks very good. Are you willing to patent it :> ? But I
still belive that the fact that range of jump (ie. how much
you can jump forwards/backwards from current position)
depends on location of opcode within page may need carefull
thinking during tool chain development.
Sorry for late answer, my internet connection went down
for a day.
> Maybe I should mention this is for my
SuperUltraGeeWhizzExtraNew
> desktop cpu design, it's not an embedded system design. The cpu is
> using virtual memory so the need for relocatble code is not so much.
Hey that sounds like the name I want to call my table top cpu design.
Is your Instruction Set Documented on your site yet?
> The problem with branches stems from the fact
I'm using 42 bit
> opcodes packed into 128 bits. There isn't a way to calculate a
> constant relative displacement for completely relocatable code. (eg
> relocatable by instruction slots - the pc increments 0,1,2,0,1,2,...)
> Relocatability has to be restricted to at least 16 byte (128 bit)
> boundaries. Since there is a restriction anyway, I figure might as
> well make it a real PITA and conserve some hardware / improve
> performance. (If you're going to create a PITA, do a good job of
> it :).
That is true removing long branches will save some time.
Note if you sort you data space you don't need to use large
data offesets. Offhand you really only need about max_word_size **.5
for offsets.
> What's wrong with pages ? Programmers love
pages. They hate
> segmentation and bank switching. Well I consider most programs to be about 3 sizes.
<= 64KB >64KB and bloated stuff.
> Each subroutine does not have to fit
> within a page and it does not have to begin on a page boundary. The
> subroutines can be coded anywhere and be any size. The only
> restriction comes into play if one wants relocatable code. Then the
> code can only be relocated according to the number of bits used for
> absolute addressing. I'm choosing the memory management page size as
> the size to use for the absolute portion. Being able to relocate
> things based on a page versus a byte boundary isn't that much of an
> issue.
> Sure you can. There's no dependency between
instructions.
> The ISA does have absolute jumps and calls as well.
I think absolute calls are only need for system traps
and jumps for interupt stuff.
> There are other things that can benefit from using
a combo approach.
> For instance the branch target may be being calculated during the ID
> or even IF stage and the target calculation needs to be as fast as
> possible. Trimming a few bits off the adder doesn't hurt. The branch
> target is also used to index into a target buffer. Not having to go
> through an adder first helps.
> Ben alias woodelf.
PS. Since I am only doing a 16 bit CPU I need a bigger name than
your 128? bit CPU --- any good ideas.
Reply by Rob Finch●April 4, 20052005-04-04
--- In fpga-cpu@fpga..., Tomasz Sztejka <sztejkat@y...> wrote: >
> --- Rob Finch <robfinch@s...> wrote:
> >
> (...)
> > Something I ran into today: why aren't branch
> > displacements a
> > combination of both relative and absolute addressing ?
> > The high order
> > bits of the displacement could be used as a relative
> > offset to a block
> > of instructions, while the low order bits are used as an
> > absolute
> > index.
> (...)
Maybe I should mention this is for my SuperUltraGeeWhizzExtraNew
desktop cpu design, it's not an embedded system design. The cpu is
using virtual memory so the need for relocatble code is not so much.
The problem with branches stems from the fact I'm using 42 bit
opcodes packed into 128 bits. There isn't a way to calculate a
constant relative displacement for completely relocatable code. (eg
relocatable by instruction slots - the pc increments 0,1,2,0,1,2,...)
Relocatability has to be restricted to at least 16 byte (128 bit)
boundaries. Since there is a restriction anyway, I figure might as
well make it a real PITA and conserve some hardware / improve
performance. (If you're going to create a PITA, do a good job of
it :).
> Because it joins all disadvantages of relative
addressing
> and absolute. You will need an adder anyway to add most
Yes it requires at least the upper two bits be relative, otherwise it
might not be possible to branch forward. I'm planning on using at
least three or four relative bits otherwise the branch range becomes
too lopsided.
> significant bits. And you will get PAGES
(programmers hate
> PAGED addressing) within which each subroutine will have to
> fit. It complicates linker and compiler alot.
>
What's wrong with pages ? Programmers love pages. They hate
segmentation and bank switching. Each subroutine does not have to fit
within a page and it does not have to begin on a page boundary. The
subroutines can be coded anywhere and be any size. The only
restriction comes into play if one wants relocatable code. Then the
code can only be relocated according to the number of bits used for
absolute addressing. I'm choosing the memory management page size as
the size to use for the absolute portion. Being able to relocate
things based on a page versus a byte boundary isn't that much of an
issue. Usually two different programs don't share space in the same
page of memory. Note, I'm assuming the whole program is being
relocated, not individual subroutines. If the whole program is
relocated then the branch target bits don't need to be recalculated,
as long as the program is relocated on a page boundary.
It does not complicate the linker or compiler at all. The compiler
doesn't even have to know about it. The assembler handles it. It's
easy to calculate the target bits. Just mask off the low order bits,
compute the difference in pages, and tack on the original low order
bits of the target.
> Can you do long branches then by combinig sequence
of
> short relative jumps? If pages won't overlap the answer is
> no. But it does not matter when you have absolute/long
> branch opcode in your ISA.
Sure you can. There's no dependency between instructions.
The ISA does have absolute jumps and calls as well.
There are other things that can benefit from using a combo approach.
For instance the branch target may be being calculated during the ID
or even IF stage and the target calculation needs to be as fast as
possible. Trimming a few bits off the adder doesn't hurt. The branch
target is also used to index into a target buffer. Not having to go
through an adder first helps.
Reply by Tomasz Sztejka●April 4, 20052005-04-04
--- Rob Finch <robfinch@robf...> wrote: > (...) > Something I ran into today: why aren't
branch
> displacements a
> combination of both relative and absolute addressing ?
> The high order
> bits of the displacement could be used as a relative
> offset to a block
> of instructions, while the low order bits are used as an
> absolute
> index. (...)
Because it joins all disadvantages of relative addressing
and absolute. You will need an adder anyway to add most
significant bits. And you will get PAGES (programmers hate
PAGED addressing) within which each subroutine will have to
fit. It complicates linker and compiler alot.
Can you do long branches then by combinig sequence of
short relative jumps? If pages won't overlap the answer is
no. But it does not matter when you have absolute/long
branch opcode in your ISA.
In my opinion, if displacement adder matters to size of
desing use absolute addressing with separate page latch
register for bits which does not fit in opcode. Be prepared
that the guy who will write compile will hate you. If you
find that ease of programming is more important use full
relative displacement.
I have source for Digital Research's demo chess program written in
PL/I if you have a need.
Richard
--- In fpga-cpu@fpga..., "Leon Heller" <leon.heller@d...>
wrote: > ----- Original Message -----
> From: "John Kent" <jekent@o...>
> To: <fpga-cpu@fpga...>
> Sent: Monday, April 04, 2005 10:02 AM
> Subject: Re: [fpga-cpu] Chess Computer
> >
> > Hi Kolja
> >
> > Looks interesting.
> >
> > One of the first projects I was interested in when I bought my 6800 D2 > > kit
> > back in the late 70s was converting Sargon from the Z80 to the 6800. > > Dan and Kathe Spracklen released a book with
the source code called > > "Sargon: a Computer Chess
Program"
> >
> > http://www.answers.com/topic/sargon-chess
> >
> > At the time we were using a 300baud Kansas City Standard tape loader. > > We got so far coding it that my brother
thought he'd throw away the source > > and patch the binary ... BIG mistake !. He/we
never did finish the > > project.
> > We got the game to make an opening move on the memory mapped VDU,
> > then BLAT, the opposition move scambled it's piece on the display. > > Not good :-)
>
> My first 'computer' was the D2 kit. It cost me 209 GBP IIRC,
quite a lot of > money in those days. It came with 128 bytes of
user RAM, I added another > chip and had all of 256 bytes available. I
hand-assembled the little > programs I wrote.
>
> Leon
Reply by Leon Heller●April 4, 20052005-04-04
----- Original Message -----
From: "John Kent" <jekent@jeke...>
To: <fpga-cpu@fpga...>
Sent: Monday, April 04, 2005 10:02 AM
Subject: Re: [fpga-cpu] Chess Computer
>
> Hi Kolja
>
> Looks interesting.
>
> One of the first projects I was interested in when I bought my 6800 D2
> kit
> back in the late 70s was converting Sargon from the Z80 to the 6800.
> Dan and Kathe Spracklen released a book with the source code called
> "Sargon: a Computer Chess Program"
>
> http://www.answers.com/topic/sargon-chess
>
> At the time we were using a 300baud Kansas City Standard tape loader.
> We got so far coding it that my brother thought he'd throw away the
source
> and patch the binary ... BIG mistake !. He/we never did finish the
> project.
> We got the game to make an opening move on the memory mapped VDU,
> then BLAT, the opposition move scambled it's piece on the display.
> Not good :-)
My first 'computer' was the D2 kit. It cost me 209 GBP IIRC, quite a
lot of
money in those days. It came with 128 bytes of user RAM, I added another
chip and had all of 256 bytes available. I hand-assembled the little
programs I wrote.
Leon
Reply by Kolja Sulimma●April 4, 20052005-04-04
There was a paper about Hydra in last years FPL conference. I think they
had an architecture with a processing element per square.
But apparently a lot of their know-how is an efficient partitioning
between smart high level algorithms running in software and parallel
brute force search running in dozens of FPGAs.
Kolja
Reply by John Kent●April 4, 20052005-04-04
Hi Kolja
Looks interesting.
One of the first projects I was interested in when I bought my 6800 D2 kit
back in the late 70s was converting Sargon from the Z80 to the 6800.
Dan and Kathe Spracklen released a book with the source code called
"Sargon: a Computer Chess Program"
At the time we were using a 300baud Kansas City Standard tape loader.
We got so far coding it that my brother thought he'd throw away the
source
and patch the binary ... BIG mistake !. He/we never did finish the project.
We got the game to make an opening move on the memory mapped VDU,
then BLAT, the opposition move scambled it's piece on the display.
Not good :-)
The Byte Book of Pascal had a chess program in it (am I showing my age?)
which was a tinsy bit to big for my 8 bit machine and the Lucidata Pcode
Pascal
compiler at the time.
I guess these days you have gnu chess, although I'd hate to try and
implement
that in hardware.
Anyway I have the Sargon source code book somewhere. I'm not sure if it
is
possible to microcode a move generator that will go through all possible
movements
of a chess piece. Each move could be stored in a 12 x 12 nybble array
(8 x 8 with a 2 nybble perimeter to test for out of bounds moves).
I think that was how Sargon was implemented.
Empty, Pawn, Rook, Knight, Bishop, Queen, King and Boundary could be
code in 3 bits
and one bit for the side (white / black)
With 256K bytes of RAM, that would allow 3640 moves to be stored.
My guess is that hydrachess is a parallel archictecture which just farms
off more
moves in each of the processors.
Evaluation of a position would take into account which pieces were being
attacked
which pieces were attacking, how many peices were defending other peices and
how many squares the peices controlled. Also if you where in check !
The end game probably demands another strategy ... how to get the
opponent in check mate. Maybe that comes out in the wash, by virtue of
the squares being controlled.
Just a few thoughts to fill up peoples mailboxes :-)