MISC - Stack Based vs. Register Based

"Arlet Ottens" <usenet+5@c-scape.nl> wrote in message
news:5157e1a1$0$6924$e4fe514c@news2.news.xs4all.nl...
> On 03/30/2013 10:54 PM, Rod Pemberton wrote:

> >>
> >> I guess looking at other peoples designs (such as Chuck's)
> >> has changed my perspective over the years so that I am
> >> willing and able to do optimizations in ways I would not have
> >> wanted to do in the past. But I am a bit surprised that there
> >> has been so much emphasis on stack oriented MISC machines
> >> which it may well be that register based MISC designs are
> >> also very efficient, at least if you aren't building them to
> >> service a C compiler or trying to match some ideal RISC
> >> model.
> >>
> >
> > Are those your actual results or did you just reiterate what
> > is on Wikipedia?  Yes, that's a serious question.  Read the
> > MISC page: [link]
> >
> > See ... ?!
>
> It sounds to me rickman is questioning the (unsupported) claims
> on wikipedia that stack based machines have an advantage in size
> and/or simplicity, not reiterating them.
>

Well, you snipped alot of context.  I wouldn't have reformatted
all of it either.

Anyway, what I took from rickman's statements was that he had only
managed to confirm what is already known about MISC according to
Wikipedia.  I.e., what was/is the point?

> > Code density is a CISC concept.  I don't see how it applies to
> > your MISC project.  Increasing code density for a MISC
> > processor means implementing more powerful instructions,
> > i.e., those that do more work, while minimizing bytes in the
> > instruction opcode encoding.  Even if you implement
> > CISC-like instructions, you can't forgo the MISC instructions
> > you already have in order to add the CISC-like instructions.
> > So, to do that, you'll need to increase the size of the
> > instruction set, as well as implement a more complicated
> > instruction decoder.  I.e., that means the processor will no
> > longer be MISC, but MISC+minimal CISC hybrid, or pure
> > CISC...
>
> It is perfectly possible to trade one type of MISC processor for
> another one. The choice between stack and register based is an
> obvious one. If you switch from stack to register based, there's
> no need to keep stack manipulation instructions around.
>

Yes, true.  But, what does eliminating MISC stack instructions and
replacing them with MISC register instructions have to do with the
CISC concept of code density or with CISC instructions? ...

> > Also, you cross-posted to comp.arch.fpga.  While they'll
> > likely be familiar with FPGAs, most there are not going
> > to be familiar with the features of stack-based processors
> > or Forth processors that you discuss indirectly within your
> > post.  They might not be familiar with ancient CISC
> > concepts such as "code density" either, or understand why
> > it was important at one point in time.  E.g., I suspect this
> > Forth related stuff from above won't be widely
> > understood on c.a.f. without clarification:
>
> The design of simple and compact processors is of great interest
> to many FPGA engineers. Plenty of FPGA designs need some
> sort of control processor, and for cost reduction it's important
> to use minimal resources. Like rickman said, this involves a
> careful balance between implementation complexity, speed,
> and code density, while also considering how much work it
> is to write/maintain the software that's running on the
> processor.
>
> Code density is still critically important. Fast memory is
> small, both on FPGA as well as general purpose processors.
>

So, shouldn't he dump the entire MISC instruction set he has, and
implement a CISC instruction set instead?  That's the only way
he's going to get the "critically important" code density, which
I'll take it you rank well above MISC as being important.  Of
course, a CISC instruction set requires a more complicated
instruction decoder ...  So, it seems that either way he proceeds,
he is being contrained by the "minimal resources" of his FPGA.
That was what he stated:

  "My efforts have shown it hard to improve on code density by a
significant degree while simultaneously minimizing the resources
used by the design."

I.e., if the FPGA he is attempting to use is insufficient to do
what he wants or needs, then it's insufficient.  Or, he needs some
new techniques.  He didn't explicitly ask for any though ...

Glen mentioned the numerous address modes of the VAX.  The 6502
also had alot of address modes and had instructions which used
zero-page as a set of fast registers.  I would think that early,
compact designs like the 6502 and Z80 could be useful to rickman.
They had low transistor counts.

Z80   8500 transistors
6502  9000 transistors
8088 29000 transistors (for comparison...)


Rod Pemberton

In comp.arch.fpga Rod Pemberton <do_not_have@notemailnotq.cpm> wrote:

(snip)

> Well, you snipped alot of context.  I wouldn't have reformatted
> all of it either.
 
> Anyway, what I took from rickman's statements was that he had only
> managed to confirm what is already known about MISC according to
> Wikipedia.  I.e., what was/is the point?
 
(snip, someone wrote)
>> It is perfectly possible to trade one type of MISC processor for
>> another one. The choice between stack and register based is an
>> obvious one. If you switch from stack to register based, there's
>> no need to keep stack manipulation instructions around.
 
> Yes, true.  But, what does eliminating MISC stack instructions and
> replacing them with MISC register instructions have to do with the
> CISC concept of code density or with CISC instructions? ...

Seems to me that one could still Huffman code the opcode, even
within the MISC concept. That is, use fewer bits for more common
operations, or where it otherwise simplifies the result.

As someone noted, you can have an N-1 bit load immediate instruction
where N is the instruction size. 

In one of Knuth's TAOCP books he describes a two instruction computer.

Seems like if one is interested in MISC, someone should build that one.

Also, maybe a MIX and MMIX machine, maybe the decimal version.

For those who don't read TAOCP, MIX is defined independent of the
underlying base. Programs in MIXAL are supposed to assemble and
run correctly on hosts that use any base within the range specified.

Instruction bytes have, if I remember, between 64 and 100 possible
values, such that six bits or two decimal digits are possible 
representations. 

I believe that allows for bases 2, 3, 4, 8, 9, 10, and 16.

-- glen

On 04/02/2013 02:10 AM, Rod Pemberton wrote:

> Yes, true.  But, what does eliminating MISC stack instructions and
> replacing them with MISC register instructions have to do with the
> CISC concept of code density or with CISC instructions? ...

I don't think 'code density' is a CISC concept at all. Code density 
applies to any kind of instruction encoding.

Any kind of MISC architecture will have a certain code density (for a 
given application), and require a certain amount of FPGA resources. And 
if you store the code in local FPGA memory, and you know your 
application, you can even convert it all to FPGA resources.

Obviously, one MISC design will have better resource use than another, 
and one of the questions is whether we can make any kind of general 
statement about stack vs register implementation.

> So, shouldn't he dump the entire MISC instruction set he has, and
> implement a CISC instruction set instead?  That's the only way
> he's going to get the "critically important" code density, which
> I'll take it you rank well above MISC as being important.  Of
> course, a CISC instruction set requires a more complicated
> instruction decoder ...  So, it seems that either way he proceeds,
> he is being contrained by the "minimal resources" of his FPGA.

Exactly. If you want to get FPGA resources low, a MISC design seems most 
appropriate. But within the MISC concept, there are still plenty of 
design decisions left.

Really, the biggest problem with FPGA CPU design is that there are too 
many design decisions, and each decision influences everything else.

> Glen mentioned the numerous address modes of the VAX.  The 6502
> also had alot of address modes and had instructions which used
> zero-page as a set of fast registers.  I would think that early,
> compact designs like the 6502 and Z80 could be useful to rickman.
> They had low transistor counts.
>
> Z80   8500 transistors
> 6502  9000 transistors
> 8088 29000 transistors (for comparison...)

Low transistor counts do not necessarily translate to low FPGA 
resources. Early CPUs used dynamic storage, dual clock latches, pass 
logic and tri-state buses to create really small designs that don't 
necessarily map well to FPGAs. On the other hand, FPGAs have specific 
features (depending on the brand) that can be exploited to create really 
tight designs.

Also, these processors are slow, using multi cycle instructions, and 8 
bit operations. That may not be acceptable. And even if low performance 
is acceptable, there are numerous other ways where you can trade speed 
for code density, so you'd have to consider these too. For instance, I 
can replace pipelining with multi-cycle execution, or use microcode.

On 3/31/2013 2:34 PM, glen herrmannsfeldt wrote:
> In comp.arch.fpga rickman<gnuarm@gmail.com>  wrote:

(snip)
>
> I have an actual RX2600 dual Itanium box, but don't run it very
> often, mostly because of the power used.

A 100 watt lightbulb uses about $10 a month if left on 24/7.  So I 
wouldn't worry too much about the cost of running your Itanium.  If you 
turn it off when you aren't using it I can't imagine it would really 
cost anything noticeable to run.


> For Itanium, the different units do different things. There are
> instruction formats that divide up the bits in different ways to make
> optimal use of the bits. I used to have the manual nearby, but I don't
> see it right now.

Yes, the array processor I worked on was coded from scratch, very 
laboriously.  The Itanium is trying to run existing code as fast as 
possible.  So they have a number of units to do similar things, but also 
different types, all working in parallel as much as possible.  Also the 
parallelism in the array processor was all controlled by the programmer. 
  In regular x86 processors the parallelism is controlled by the chip 
itself.  I'm amazed sometimes at just how much they can get the chip to 
do, no wonder there are 100's of millions of transistors on the thing. 
I assume parallelism in the Itanium is back to the compiler smarts to 
control since it needs to be coded into the VLIW instructions.


> For x87, they avoid the DUP, SWAP, and such by instructions being able
> to specify any register in the stack. You can, for example, add any
> stack register (there are eight) to the top of stack. I haven't thought
> about it for a while, but I believe either pushing the result, or
> replacing the previous top of the stack.

That is something I have not yet looked at, a hybrid approach with a 
stack, but also with stack top relative addressing.  It is important to 
keep the hardware simple, but that might not be too hard to implement.
Arlet talked about his hybrid processor design with multiple stacks.  I 
would need to give this a bit of thought as the question becomes, what 
possible advantage would a hybrid processor have over the other two? 
Actually, the image in my mind is a bit like the C language stack frame 
model.  You can work with addressing relative to the top of stack and 
when a sub is called it layers its variables on top of the existing 
stack.  That would require a bit of entry and exit code, so there will 
be a tradeoff between simple register addressing and simple subroutine 
entry.


> Seems to me that one possibility is to have a really functional stack
> operation instruction, such that, with the give number of bits, it
> allows for the most opertions. Some combination of DUP, SWAP, and POP
> all at once. Though that isn't easy for the stack itself.

Like many tradeoffs, this can complicate the hardware.  If you want to 
be able to combine an ADD with a SWAP or OVER, you need to be able to 
access more than two operands on the stack at once.  In my designs that 
means pulling another register out of the proper stack.  Rather than one 
register and a block of memory, each stack would need two registers and 
the block of memory along with the input multiplexers.  This would need 
to be examined in context of common code to see how much it would help 
vs the expense of added hardware.

I'm still not complete in my analysis of a register based MISC design, 
but at the moment I think the register approach gives better instruction 
size efficiency/faster execution as well as simpler hardware design.

-- 

Rick

On 3/30/2013 5:54 PM, Rod Pemberton wrote:
> "rickman"<gnuarm@gmail.com>  wrote in message
> news:kj4vae$msi$1@dont-email.me...
>
>> I have been working with stack based MISC designs in FPGAs for
>> some years.  All along I have been comparing my work to the work
>> of others.  These others were the conventional RISC type
>> processors supplied by the FPGA vendors as well as the many
>> processor designs done by individuals or groups as open source.
>>
>> So far my CPUs have always ranked reasonably well in terms of
>> speed, but more importantly to me, very well in terms of size
>> and code density.  My efforts have shown it hard to improve on
>> code density by a significant degree while simultaneously
>> minimizing the resources used by the design.  Careful selection
>> of the instruction set can both improve code density and
>> minimize logic used if measured together, but there is always a
>> tradeoff.  One can always be improved at the expense of the
>> other.
>>
>> The last couple of days I was looking at some code I plan to use
>> and realized that it could be a lot more efficient if I could
>> find a way to use more parallelism inside the CPU and use fewer
>> instructions. So I started looking at defining separate opcodes
>> for the two primary function units in the design, the data stack
>> and the return stack.  Each has its own ALU.  The data stack has
>> a full complement of capabilities while the return stack can
>> only add, subtract and compare.  The return stack is actually
>> intended to be an "address" processing unit.
>>
>> While trying to figure out how to maximize the parallel
>> capabilities of these units, I realized that many operations
>> were just stack manipulations.  Then I read the thread about the
>> relative "cost" of stack ops vs memory accesses and I realized
>> these were what I needed to optimize.  I needed to find a way to
>> not use an instruction and a clock cycle for moving data around
>> on the stack.
>>
>> In the thread on stack ops it was pointed out repeatedly that
>> very often the stack operands would be optimized to register
>> operands, meaning they wouldn't need to do the stack ops at all
>> really.  So I took a look at a register based MISC design.
>> Guess what, I don't see the disadvantage!  I have pushed this
>> around for a couple of days and although I haven't done a
>> detailed design, I think I have looked at it enough to realize
>> that I can design a register oriented MISC CPU that will run as
>> fast, if not faster than my stack based design and it will use
>> fewer instructions.  I still need to add some features like
>> support for a stack in memory, in other words,
>> pre-increment/post-decrement (or the other way around...), but I
>> don't see where this is a bad design.  It may end up using
>> *less* logic as well.  My stack design provides access to the
>> stack pointers which require logic for both the pointers and
>> muxing them into the data stack for reading.
>>
>> I guess looking at other peoples designs (such as Chuck's) has
>> changed my perspective over the years so that I am willing and
>> able to do optimizations in ways I would not have wanted to do
>> in the past. But I am a bit surprised that there has been so
>> much emphasis on stack oriented MISC machines which it may well
>> be that register based MISC designs are also very efficient,
>> at least if you aren't building them to service a C compiler or
>> trying to match some ideal RISC model.
>>
>
> Are those your actual results or did you just reiterate what is on
> Wikipedia?  Yes, that's a serious question.  Read the MISC page:
> http://en.wikipedia.org/wiki/Minimal_instruction_set_computer
>
> See ... ?!

You clearly don't understand my post or the Wiki article or possibly 
both.  I suggest you reread both and then ask questions if you still 
don't understand.


> Code density is a CISC concept.  I don't see how it applies to
> your MISC project.

Yes, I get that you don't understand.  Do you have a specific question?


> Increasing code density for a MISC processor
> means implementing more powerful instructions, i.e., those that do
> more work, while minimizing bytes in the instruction opcode
> encoding.

Yes, that part you seem to understand.


> Even if you implement CISC-like instructions, you can't
> forgo the MISC instructions you already have in order to add the
> CISC-like instructions.

Really?  I can't drop the entire instruction set and start over?  Who 
says so?  Am I breaking a law?


> So, to do that, you'll need to increase
> the size of the instruction set, as well as implement a more
> complicated instruction decoder.

Define "increase the size of the instruction set".  I am using a 9 bit 
opcode for my stack design and am using a similar 9 bit opcode for the 
register design.  In what way is the register design using a larger 
instruction set?

That was exactly the blinder I was wearing until now.  I had read a lot 
about register CPU instruction sets where the intent was not in line 
with MISC goals.  MicroBlaze is a good example.  I think it uses well in 
excess of 1000 LUTs, maybe multiple 1000's.  I need something that is 
much smaller and it hadn't occurred to me that perhaps the common goals 
of register designs (lots of registers, orthogonality, address mode 
flexibility, etc) could be limited or even tossed out the window.  I 
don't need a machine that is easy for a C compiler to produce code for. 
  My goals are for minimal hardware without losing any more performance 
than is essential.  In particular I work in FPGAs, so the design needs 
to work well in that environment.


> I.e., that means the processor
> will no longer be MISC, but MISC+minimal CISC hybrid, or pure
> CISC...

Nonsense.  "Minimal Instruction Set Computer (MISC) is a processor 
architecture with a very small number of basic operations and 
corresponding opcodes." from Wikipedia.  BTW, I don't think the term 
MISC is widely used and is not well defined.  This is the only web page 
I found that even tries to define it.

Actually, if you consider only the opcodes and not the operand 
combinations, I think the register design may have fewer instructions 
than does the stack design.  But the register design still is in work so 
I'm not done counting yet.

There are some interesting corners to be explored.  For example a MOV 
rx,rx is essentially a NOP.  There are eight of these.  So instead, why 
not make them useful by clearing the register?  So MOV rx,rx is a clear 
to be given the name CLR rx... unless the rx is r7 in which case it is 
indeed a MOV r7,r7 which is now a NOP to be coded as such.  The CLR r7 
is not needed because LIT 0 already does the same job.  Even better the 
opcode for a NOP is 0x1FF or octal 777.  That's very easy to remember 
and recognize.  It feels good to find convenient features like this and 
makes me like the register MISC design.


> No offense, but you seem to be "reinventing the wheel" in terms of
> microprocessor design.  You're coming to the same conclusions that
> were found in the 1980's, e.g., concluding a register based
> machine can perform better than a stack based machine, except
> you've applied it to MISC in an FPGA package...  How is that a new
> conclusion?

I don't see how you can say that.  I don't know of other MISC designs 
that are very good.  I think the picoBlaze is one, but I don't think it 
was designed to be very MISC really.  It was designed to be small, 
period.  It has a lot of fixed features and so can't be altered without 
tossing old code.  Some of the MicroChip devices might be MISC.  I have 
not worked with them.  I might want to take a look actually.  There may 
be useful ideas.

But "reinventing the wheel"?  I don't think so.

-- 

Rick

In comp.arch.fpga rickman <gnuarm@gmail.com> wrote:
> On 3/31/2013 2:34 PM, glen herrmannsfeldt wrote:
>> In comp.arch.fpga rickman<gnuarm@gmail.com>  wrote:
 
> (snip)

>> I have an actual RX2600 dual Itanium box, but don't run it very
>> often, mostly because of the power used.
 
> A 100 watt lightbulb uses about $10 a month if left on 24/7.  So I 
> wouldn't worry too much about the cost of running your Itanium.  If you 
> turn it off when you aren't using it I can't imagine it would really 
> cost anything noticeable to run.

It is a dual processor box, plus all the rest of the systems
in the box. Yes, I was considering running it all the time, but
it is too expensive for that.
 
>> For Itanium, the different units do different things. There are
>> instruction formats that divide up the bits in different ways to make
>> optimal use of the bits. I used to have the manual nearby, but I don't
>> see it right now.
 
> Yes, the array processor I worked on was coded from scratch, very 
> laboriously.  The Itanium is trying to run existing code as fast as 
> possible.  So they have a number of units to do similar things, but also 
> different types, all working in parallel as much as possible.  Also the 
> parallelism in the array processor was all controlled by the programmer. 
>  In regular x86 processors the parallelism is controlled by the chip 
> itself.  I'm amazed sometimes at just how much they can get the chip to 
> do, no wonder there are 100's of millions of transistors on the thing. 
> I assume parallelism in the Itanium is back to the compiler smarts to 
> control since it needs to be coded into the VLIW instructions.

Seems to me that the big problem with the original Itanium was the
need to also run x86 code. That delayed the release for some time, and
in that time other processors had advanced. I believe that later
versions run x86 code in software emulation, maybe with some hardware
assist. 

-- glen

On 4/1/2013 8:10 PM, Rod Pemberton wrote:
> "Arlet Ottens"<usenet+5@c-scape.nl>  wrote in message
> news:5157e1a1$0$6924$e4fe514c@news2.news.xs4all.nl...
>> On 03/30/2013 10:54 PM, Rod Pemberton wrote:
>
>>>>
>>>> I guess looking at other peoples designs (such as Chuck's)
>>>> has changed my perspective over the years so that I am
>>>> willing and able to do optimizations in ways I would not have
>>>> wanted to do in the past. But I am a bit surprised that there
>>>> has been so much emphasis on stack oriented MISC machines
>>>> which it may well be that register based MISC designs are
>>>> also very efficient, at least if you aren't building them to
>>>> service a C compiler or trying to match some ideal RISC
>>>> model.
>>>>
>>>
>>> Are those your actual results or did you just reiterate what
>>> is on Wikipedia?  Yes, that's a serious question.  Read the
>>> MISC page: [link]
>>>
>>> See ... ?!
>>
>> It sounds to me rickman is questioning the (unsupported) claims
>> on wikipedia that stack based machines have an advantage in size
>> and/or simplicity, not reiterating them.
>>
>
> Well, you snipped alot of context.  I wouldn't have reformatted
> all of it either.
>
> Anyway, what I took from rickman's statements was that he had only
> managed to confirm what is already known about MISC according to
> Wikipedia.  I.e., what was/is the point?

You really need to reread the wiki description of MISC.  There seems to 
be a disconnect.


>>> Code density is a CISC concept.  I don't see how it applies to
>>> your MISC project.  Increasing code density for a MISC
>>> processor means implementing more powerful instructions,
>>> i.e., those that do more work, while minimizing bytes in the
>>> instruction opcode encoding.  Even if you implement
>>> CISC-like instructions, you can't forgo the MISC instructions
>>> you already have in order to add the CISC-like instructions.
>>> So, to do that, you'll need to increase the size of the
>>> instruction set, as well as implement a more complicated
>>> instruction decoder.  I.e., that means the processor will no
>>> longer be MISC, but MISC+minimal CISC hybrid, or pure
>>> CISC...
>>
>> It is perfectly possible to trade one type of MISC processor for
>> another one. The choice between stack and register based is an
>> obvious one. If you switch from stack to register based, there's
>> no need to keep stack manipulation instructions around.
>>
>
> Yes, true.  But, what does eliminating MISC stack instructions and
> replacing them with MISC register instructions have to do with the
> CISC concept of code density or with CISC instructions? ...

Weren't you the person who brought CISC into this discussion?  Why are 
you asking this question about CISC?


>>> Also, you cross-posted to comp.arch.fpga.  While they'll
>>> likely be familiar with FPGAs, most there are not going
>>> to be familiar with the features of stack-based processors
>>> or Forth processors that you discuss indirectly within your
>>> post.  They might not be familiar with ancient CISC
>>> concepts such as "code density" either, or understand why
>>> it was important at one point in time.  E.g., I suspect this
>>> Forth related stuff from above won't be widely
>>> understood on c.a.f. without clarification:
>>
>> The design of simple and compact processors is of great interest
>> to many FPGA engineers. Plenty of FPGA designs need some
>> sort of control processor, and for cost reduction it's important
>> to use minimal resources. Like rickman said, this involves a
>> careful balance between implementation complexity, speed,
>> and code density, while also considering how much work it
>> is to write/maintain the software that's running on the
>> processor.
>>
>> Code density is still critically important. Fast memory is
>> small, both on FPGA as well as general purpose processors.
>>
>
> So, shouldn't he dump the entire MISC instruction set he has, and
> implement a CISC instruction set instead?  That's the only way
> he's going to get the "critically important" code density, which
> I'll take it you rank well above MISC as being important.  Of
> course, a CISC instruction set requires a more complicated
> instruction decoder ...  So, it seems that either way he proceeds,
> he is being contrained by the "minimal resources" of his FPGA.
> That was what he stated:
>
>    "My efforts have shown it hard to improve on code density by a
> significant degree while simultaneously minimizing the resources
> used by the design."

I have "dumped" the stack related portion of the instruction set and 
replaced it with register references.  Why would I do otherwise?


> I.e., if the FPGA he is attempting to use is insufficient to do
> what he wants or needs, then it's insufficient.  Or, he needs some
> new techniques.  He didn't explicitly ask for any though ...

No one said anything about "insufficient".  I am looking for an optimal 
design for a small CPU that can be used efficiently in an FPGA.


> Glen mentioned the numerous address modes of the VAX.  The 6502
> also had alot of address modes and had instructions which used
> zero-page as a set of fast registers.  I would think that early,
> compact designs like the 6502 and Z80 could be useful to rickman.
> They had low transistor counts.
>
> Z80   8500 transistors
> 6502  9000 transistors
> 8088 29000 transistors (for comparison...)

I'm not counting transistors.  That is one of the fallacies of comparing 
chip designs to FPGA designs.  When you have the flexibility of using 
transistors you can do things in ways that are efficient that are not 
efficient in the LUTs of an FPGA.

The two big constraints are resources used in the FPGA and opcode size. 
  If an instruction would require addition of resources to the design, 
it needs to justify that addition.  An instruction also needs to justify 
the portion of the opcode space it requires.  Operations that specify 
more than one register become very expensive in terms of opcode bits. 
Operations that require additional data paths become expensive in terms 
of resources.  Doing as much as possible with as little as possible is 
what I'm looking for.

BTW, the ZPU is a pretty good example of just how small a design can be. 
  But it is very slow.  That's the other size of the equation.  Improve 
speed as much as possible while not using more resources than possible. 
  The optimal point depends on the coefficients used... in other words, 
my judgement.  This is not entirely objective.

-- 

Rick

On 4/1/2013 8:54 PM, glen herrmannsfeldt wrote:
>
> Seems to me that one could still Huffman code the opcode, even
> within the MISC concept. That is, use fewer bits for more common
> operations, or where it otherwise simplifies the result.
>
> As someone noted, you can have an N-1 bit load immediate instruction
> where N is the instruction size.

Yup, I am still using the high bit to indicate an immediate operand. 
This requires an implied location, so this literal is always in R7, the 
addressing register.  In my stack design it is always the return stack, 
also the addressing register.

Jumps and calls still contain a small literal to be used alone when the 
relative jump is within range or with the literal instruction when not.

I think this is very similar to Huffman encoding.


> In one of Knuth's TAOCP books he describes a two instruction computer.
>
> Seems like if one is interested in MISC, someone should build that one.

You can design a one instruction computer, but there is a balance 
between resources used and the effectiveness of the resulting design. 
The effectiveness of this sort of design is too low.


> Also, maybe a MIX and MMIX machine, maybe the decimal version.
>
> For those who don't read TAOCP, MIX is defined independent of the
> underlying base. Programs in MIXAL are supposed to assemble and
> run correctly on hosts that use any base within the range specified.
>
> Instruction bytes have, if I remember, between 64 and 100 possible
> values, such that six bits or two decimal digits are possible
> representations.
>
> I believe that allows for bases 2, 3, 4, 8, 9, 10, and 16.

Doesn't sound like an especially practical computer.  Has anyone ever 
built one?

-- 

Rick

On 4/2/2013 2:25 AM, Arlet Ottens wrote:
> On 04/02/2013 02:10 AM, Rod Pemberton wrote:
>>
>> Z80 8500 transistors
>> 6502 9000 transistors
>> 8088 29000 transistors (for comparison...)
>
> Low transistor counts do not necessarily translate to low FPGA
> resources. Early CPUs used dynamic storage, dual clock latches, pass
> logic and tri-state buses to create really small designs that don't
> necessarily map well to FPGAs. On the other hand, FPGAs have specific
> features (depending on the brand) that can be exploited to create really
> tight designs.
>
> Also, these processors are slow, using multi cycle instructions, and 8
> bit operations. That may not be acceptable. And even if low performance
> is acceptable, there are numerous other ways where you can trade speed
> for code density, so you'd have to consider these too. For instance, I
> can replace pipelining with multi-cycle execution, or use microcode.

I think you have a very good handle on the nature of my goals.

-- 

Rick

In comp.arch.fpga rickman <gnuarm@gmail.com> wrote:

(snip, I wrote)
>> Also, maybe a MIX and MMIX machine, maybe the decimal version.

>> For those who don't read TAOCP, MIX is defined independent of the
>> underlying base. Programs in MIXAL are supposed to assemble and
>> run correctly on hosts that use any base within the range specified.

>> Instruction bytes have, if I remember, between 64 and 100 possible
>> values, such that six bits or two decimal digits are possible
>> representations.

>> I believe that allows for bases 2, 3, 4, 8, 9, 10, and 16.
 
> Doesn't sound like an especially practical computer.  
> Has anyone ever built one?

Well, it exists mostly to write the examples (and, I believe,
homework problems) in the book. I believe that there have been
software emulation, but maybe no hardware (FPGA) versions.

MIXAL programs should be base independent, but actual implementations
are likely one base. 

(The model number, 1009 or MIX in roman numerals, is supposed to
be the average of the model numbers of some popular machines.

There is also the DLX, a RISC machine used by Hennessy and Patterson
in their book, which could also be in roman numerals.

-- glen