M68k add to memory is not a mistake any more

[Brett Davis]

Linus Torvalds told me that M68k add to memory is no longer a mistake.
Upon further reflection this breaks down to a x86 add from memory with
a free store instruction added, and you also save a register.

This actually kinda sounds smart, provided you are doing a high end
core, and have support for add from memory.

Not a fan of the idea, makes low end chips harder. Any comments?

(The general commentary is we could make the M68k competitive with x86
today, but there would need to be a market for it.)


Anyone want to speculate on indirect addressing?
Instruction cracking is cheap(?) and you get two instructions for the
cost of one.
I always hated indirect addressing, but now I know why Moto added all
those crazy indirect modes to the 68020.

[Tim McCaffrey]

In article <ggtgp-8D1AEA....@netnews.mchsi.com>, gg...@yahoo.com
says...

I don't know, but I guessed Moto added those indirect modes for Apple's
Macintosh OS. They perform the same function as 286 segments (kind-of).
Apple should have re-written the OS to take advantage of the MMU like a real
OS.

- Tim

[Michael S]

On Jan 31, 5:49 pm, timcaff...@aol.com (Tim McCaffrey) wrote:
> In article <ggtgp-8D1AEA.03180231012...@netnews.mchsi.com>, gg...@yahoo.com

'020 released in 1984.
First Apple Macintosh released in 1984.
First '020 Apple Macintosh - 1987?

Given the timeline, I don't buy Apple influence.

[MitchAlsup]

Even the 68020 guys understand that most of the new addressing modes in the 020 were "not good for the architecture" en-the-large, scaled index being the exception (it was useful and not damaging to the implementations).

Indirect addressing: If you don't have enough registers (like 8 with some dedicated), this addressing mode makes sense at the instruction set level. If you do have enough registers (like 32), it does not.

At the pipeline level, indirect addressing is a way to multiply the activity at the data cache while not adding much activity to the rest of the pipelines. Since the data cache is already on a critical path (or it would have been made bigger) adding new means to push more accesses through said cache is not going to make it any faster, and might make it smaller (to meet frequency/cycle-time).

This is completely different than the 360/x86 scheme where one could organize the pipeline so that inbound memory references (loads) are made to look less expensive by hiding the data cache access before the execute stage of the pipe. Indirect addressing creates a new forwarding path from address-generator through the data cache.

And as the latest 360-Z implementation showed, doing the data cache as if it were an function unit (instead of several stages in the pipeline) leads to simpler internal circuitry.

So, no, indirect addressing has a lot going against it and little for it.

Mitch

[Tim McCaffrey]

In article
<3014212d-edec-4964...@o13g2000vbf.googlegroups.com>,
already...@yahoo.com says...
>
>On Jan 31, 5:49=A0pm, timcaff...@aol.com (Tim McCaffrey) wrote:
>> In article <ggtgp-8D1AEA.03180231012...@netnews.mchsi.com>, gg...@yahoo.c=

>om
>> says...
>>
>>
>>
>>
>>
>> >Linus Torvalds told me that M68k add to memory is no longer a mistake.
>> >Upon further reflection this breaks down to a x86 add from memory with
>> >a free store instruction added, and you also save a register.
>>
>> >This actually kinda sounds smart, provided you are doing a high end
>> >core, and have support for add from memory.
>>
>> >Not a fan of the idea, makes low end chips harder. Any comments?
>>
>> >(The general commentary is we could make the M68k competitive with x86
>> >today, but there would need to be a market for it.)
>>
>> >Anyone want to speculate on indirect addressing?
>> >Instruction cracking is cheap(?) and you get two instructions for the
>> >cost of one.
>> >I always hated indirect addressing, but now I know why Moto added all
>> >those crazy indirect modes to the 68020.
>>
>> I don't know, but I guessed Moto added those indirect modes for Apple's

>> Macintosh OS. =A0They perform the same function as 286 segments (kind-of)=
>.
>> Apple should have re-written the OS to take advantage of the MMU like a r=
>eal
>> OS.
>>
>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 - Tim

>
>'020 released in 1984.
>First Apple Macintosh released in 1984.
>First '020 Apple Macintosh - 1987?
>
>Given the timeline, I don't buy Apple influence.

Mac development started in 1979 (1980 for 68000 version). Plenty of time for
OS programmers to whine to Moto about lack of indirect addressing. :)

- Tim

[ChrisQ]

Maybe bad from an purist architectural point of view, but from a programming
pov, it's one of the most valuable addressing modes available. In terms of
minimising code space and adding clarity to the code. Probably also very
helpfull for the compiler writers as well. By indirect, one assumes register
as well as memory indirect addressing modes.

At the time of the 68k release, memory was still expensive and code size
really did matter for a lot of applications.

Wasn't it the Computer Automation minis that had an indirect bit that could
be used for 'n' level indirect access ?...

Regards,

Chris

[jacko]

I liked the 68K, the EC or not matters little from the application side. I never missed anything the basic model didn't have. Were the new instructions on the A or F group, or just some free combinations of bits?

A modern implementation maybe should remove the multiply and divide instructions and add a MULL (multiply low 32*32) and MULH (multiply high 32*32) and MULS (signed high 32*32), and a MULC (multiply (16,16)-(16,16) signed complex). The div zero error trap could be reassigned as bus snoop DMA cache hit.

Was the floating point worth being standard?

[MitchAlsup]

On Wednesday, February 1, 2012 6:49:17 AM UTC-6, ChrisQ wrote:
> Wasn't it the Computer Automation minis that had an indirect bit that could
> be used for 'n' level indirect access ?...

PDP-10 did any number of indirection levels limited only by a timeout timer.

Mitch

[sarr.b...@alum.dartmouth.org]

MitchAlsup <Mitch...@aol.com> wrote:

PDP-10 did any number of indirection levels not limited by anything;
Instructions were restartable after an interrupt except for the byte
instructions which had a psw flag indicating if the increment had
already been done. So a program with an indirect loop was just like
any other program with an infinite loop.

--
--------
Sarr Blumson sarr.b...@alum.dartmouth.org
http://www-personal.umich.edu/~sarr/

[ChrisQ]

On 02/01/12 16:18, sarr.b...@alum.dartmouth.org wrote:
> MitchAlsup<Mitch...@aol.com> wrote:
> : On Wednesday, February 1, 2012 6:49:17 AM UTC-6, ChrisQ wrote:
> :> Wasn't it the Computer Automation minis that had an indirect bit that could
> :> be used for 'n' level indirect access ?...
>
> : PDP-10 did any number of indirection levels limited only by a timeout timer.
>
> PDP-10 did any number of indirection levels not limited by anything;
> Instructions were restartable after an interrupt except for the byte
> instructions which had a psw flag indicating if the increment had
> already been done. So a program with an indirect loop was just like
> any other program with an infinite loop.
>

I think that Motorola were heavily influenced by dec, both in their 8 bit
6800 series, where they cribbed the 11's instruction mnemonics and ditto
68k.
As with the transition from pdp8 to pdp11, Motorola made a complete break
from the defined function register style of 6800 to a more general purpose
register achitecture.

What I never worked out was why Motorola split the 16 registers into 8 x
data and 8 x address, rather that a cleaner 16 general purpose set. Perhaps
it was a limitation in the process technology of the day, but still think
that the 68k was a real achievement. There were also other mini style
architecture micros from Zilog and Nat Semi that looked interesting, but
never really achieved critical mass.

The arm micros i'm looking at these days seem to have a register for every
occasion, but also seem bereft of powerfull addressing modes. Everything via
registers makes it very laborious and long winded when programming
assembler.
Just a different mind set I guess...

Regards,

Chris

[Quadibloc]

On Jan 31, 2:18 am, Brett Davis <gg...@yahoo.com> wrote:

> (The general commentary is we could make the M68k competitive with x86
> today, but there would need to be a market for it.)

This is sad. It would be nice if there were a market for...

a resurrected Amiga...

a Macintosh which can run, at native speed, all Macintosh software
dating back to the very first Macintosh made.

In the latter case, of course, willingness on the part of Apple to
address that market would also be required. The failure of the
Macintosh to be a stable upwards-compatible platform over the years of
its existence is distressing.

Of course, IBM's emphasis on market segmentation for its profitability
also distresses me. I would have been much happier if the ubiquitous
PC platform was big-endian - whether based on the 68K architecture or
the IBM 360 architecture.

It would have been interesting to have a 360-compatible machine that
could switch into and out of Model 20 mode...

John Savard

[ChrisQ]

Fwir, there was a 360 on a couple of 68k devices using different microcode,
built by ibm, but you might be disappointed in the performance, even if you
could find one now.

One 8 bit embedded design, a rehashed 8051 architecture with a risc core,
(Silicon Labs) runs at over 50 mips and has been quite successfull. Not
really big iron, but shows what can be done if there is a potential market.
In the Si Labs case, a vast archive of 8051 code, tools and expertise...

Regards,

Chris

[Robert Wessel]

On Wed, 01 Feb 2012 19:16:53 +0000, ChrisQ <blac...@devnull.com>
wrote:

>On 02/01/12 18:21, Quadibloc wrote:
>> On Jan 31, 2:18 am, Brett Davis<gg...@yahoo.com> wrote:
>>
>>> (The general commentary is we could make the M68k competitive with x86
>>> today, but there would need to be a market for it.)
>>
>> This is sad. It would be nice if there were a market for...
>>
>> a resurrected Amiga...
>>
>> a Macintosh which can run, at native speed, all Macintosh software
>> dating back to the very first Macintosh made.
>>
>> In the latter case, of course, willingness on the part of Apple to
>> address that market would also be required. The failure of the
>> Macintosh to be a stable upwards-compatible platform over the years of
>> its existence is distressing.
>>
>> Of course, IBM's emphasis on market segmentation for its profitability
>> also distresses me. I would have been much happier if the ubiquitous
>> PC platform was big-endian - whether based on the 68K architecture or
>> the IBM 360 architecture.
>>
>> It would have been interesting to have a 360-compatible machine that
>> could switch into and out of Model 20 mode...
>>
>> John Savard
>
>Fwir, there was a 360 on a couple of 68k devices using different microcode,
>built by ibm, but you might be disappointed in the performance, even if you
>could find one now.

Shipped by IBM as the "XT/370". And it was a somewhat limited
implementation - most of the privileged mode was not implemented, and
it ran a customized version of CMS, and not any of the full OS's.

IIRC, only one of the two 68Ks was re-microcoded, the other was stock.

[Anne & Lynn Wheeler]

ChrisQ <blac...@devnull.com> writes:
> Fwir, there was a 360 on a couple of 68k devices using different microcode,
> built by ibm, but you might be disappointed in the performance, even if you
> could find one now.

it was problem mode 370 ... a couple boards in pc ... initially released
for pc/xt as xt/370 ... ran a modified version of vm370/cms ...
initially with 384kbyte 370 memory ... and about 80kips (about the MIP
rate of 370/115). an issue was all i/o was via communication with cp/88
running on the pc processor ... and disk activity was read/write record
on the xt 100ms/access hard disk.

I do some performance work and show that after vm370 fixed storage
requirements ... most CMS applications tended to page-thrash in the
remaining pageable memory. I then get blamed for six month schedule slip
in announce&ship while they upgrade the boards to 512kbyte 370 memory.

the additional 370 memory mitigates the page thrashing ... but cms
applications tended to be quite a bit more disk intensive than
equivalent PC applications ... which tended to be quite noticeable with
the XT 100ms/access disk (having come over from mainframe disk
environment where there was less of a disk activity bottleneck).

--
virtualization experience starting Jan1968, online at home since Mar1970

[Joe Pfeiffer]

ChrisQ <blac...@devnull.com> writes:

> On 02/01/12 16:18, sarr.b...@alum.dartmouth.org wrote:
>> MitchAlsup<Mitch...@aol.com> wrote:
>> : On Wednesday, February 1, 2012 6:49:17 AM UTC-6, ChrisQ wrote:
>> :> Wasn't it the Computer Automation minis that had an indirect bit that could
>> :> be used for 'n' level indirect access ?...
>>
>> : PDP-10 did any number of indirection levels limited only by a timeout timer.
>>
>> PDP-10 did any number of indirection levels not limited by anything;
>> Instructions were restartable after an interrupt except for the byte
>> instructions which had a psw flag indicating if the increment had
>> already been done. So a program with an indirect loop was just like
>> any other program with an infinite loop.
>>
>
> I think that Motorola were heavily influenced by dec, both in their 8 bit
> 6800 series, where they cribbed the 11's instruction mnemonics and
> ditto 68k.
> As with the transition from pdp8 to pdp11, Motorola made a complete break
> from the defined function register style of 6800 to a more general purpose
> register achitecture.
>
> What I never worked out was why Motorola split the 16 registers into 8 x
> data and 8 x address, rather that a cleaner 16 general purpose set. Perhaps
> it was a limitation in the process technology of the day, but still think
> that the 68k was a real achievement.

It doubled the number of registers without needing an extra bit to
address them. Also, when superscalar came in, it let you increase the
number of read/write ports more easily (I'd be surprised if this latter
advantage was even a gleam in anybody's eye when the decision was made,
though).

[Brett Davis]

In article
<b8de74f7-2b27-4032...@lr19g2000pbb.googlegroups.com>,

Quadibloc <jsa...@ecn.ab.ca> wrote:

> On Jan 31, 2:18 am, Brett Davis <gg...@yahoo.com> wrote:
>
> > (The general commentary is we could make the M68k competitive with x86
> > today, but there would need to be a market for it.)
>
> This is sad. It would be nice if there were a market for...
>
> a resurrected Amiga...

A bit slice graphics chip is the wrong way to go, it was a dead end
stop gap that had a tiny window of time to survive.
Once DRAM got cheap enough to do a 16 bit true color frame buffer
at reasonable resolutions it was dead.

The OS was an afterthought, in an age where software is what mattered.

I told the Amiga fanboys this at the time, but they did not care.

> a Macintosh which can run, at native speed, all Macintosh software
> dating back to the very first Macintosh made.

I used the original MAC and owned a MAC Plus, it was too far ahead
of its time, barely useable. The only Moto based Mac that did not
suck was the last 68040 based one, finally fast enough to use.

The Power Macs were ok.

My Intel Mac is faster than I need, want a less noisy machine.

> In the latter case, of course, willingness on the part of Apple to
> address that market would also be required. The failure of the
> Macintosh to be a stable upwards-compatible platform over the years of
> its existence is distressing.

While OSX 10.7 dropped support for Power, there are emulators available.
You can even find MacPlus emulators.

I have no desire to run MacPlus software at high speeds, by todays
standards all that software sucks now.

[Brett Davis]

In article <jgc332$dhh$1...@speranza.aioe.org>,

ChrisQ <blac...@devnull.com> wrote:

> One 8 bit embedded design, a rehashed 8051 architecture with a risc core,
> (Silicon Labs) runs at over 50 mips and has been quite successfull. Not
> really big iron, but shows what can be done if there is a potential market.
> In the Si Labs case, a vast archive of 8051 code, tools and expertise...

http://www.silabs.com/products/mcu/Pages/8051-microcontroller.aspx

Cool.

Ben expecting this as a real 8051 is pad limited, more transistors are free.

[Niels Jørgen Kruse]

Brett Davis <gg...@yahoo.com> wrote:

> My Intel Mac is faster than I need, want a less noisy machine.

Pray that Apple expose the dial-a-TDP functionality of Ivy Bridge.

Unfortunately, the desktop processors don't seem to have it.

--
Mvh./Regards, Niels Jørgen Kruse, Vanløse, Denmark

[Tim McCaffrey]

In article <jgbqmc$n2b$1...@speranza.aioe.org>, blac...@devnull.com says...

I think the 6800 was more influenced by the HP-1000/2000 series. Same
registers (A/B, X/Y) and direct page addressing, although the HP was more
flexible (it also had indirect addressing). OTOH, some of that stuff was in
the PDP-8 was well, which I think they all got from Whirlwind.

If you think of the 68000 address registers as an extension of the X register
in the 6800 (or X, Y & U in the 6809), and the data registers as an extension
of the A/B (& D in 6809) registers in the 6800, I think the ancestory is
pretty obvious. Yes, the assembler mnemonics were PDP-11ish, but so were the
8080's.

- Tim

[Joe Pfeiffer]

Brett Davis <gg...@yahoo.com> writes:

> In article
> <b8de74f7-2b27-4032...@lr19g2000pbb.googlegroups.com>,
> Quadibloc <jsa...@ecn.ab.ca> wrote:
>
>> On Jan 31, 2:18 am, Brett Davis <gg...@yahoo.com> wrote:
>>
>> > (The general commentary is we could make the M68k competitive with x86
>> > today, but there would need to be a market for it.)
>>
>> This is sad. It would be nice if there were a market for...
>>
>> a resurrected Amiga...
>
> A bit slice graphics chip is the wrong way to go, it was a dead end
> stop gap that had a tiny window of time to survive.
> Once DRAM got cheap enough to do a 16 bit true color frame buffer
> at reasonable resolutions it was dead.
>
> The OS was an afterthought, in an age where software is what mattered.

I *really* have to raise an eyebrow at that contention. Compared to the
OSes available at the time for PC and Mac, it was remarkably elegant and
well-designed.

> I told the Amiga fanboys this at the time, but they did not care.

Of course not (having been something of an Amiga fanboy at the time).
It was a good way to go to get good graphics at the time; the
expectation was that Amiga would continue to have cutting-edge graphics,
whatever that meant in the future. I sure had no idea just how insane
Commodore management was...

[Quadibloc]

On Feb 1, 12:16 pm, ChrisQ <blackh...@devnull.com> wrote:

> Fwir, there was a 360 on a couple of 68k devices using different microcode,

Oh, I knew that. I even remember reading the article in _Electronics_
magazine that discussed the design.

John Savard

[Stephen Sprunk]

On 31-Jan-12 03:18, Brett Davis wrote:
> Linus Torvalds told me that M68k add to memory is no longer a mistake.
> Upon further reflection this breaks down to a x86 add from memory with
> a free store instruction added, and you also save a register.

x86 has add to memory as well: just write "ADD m, r" instead of "ADD r,
m". IIRC, the difference is only one bit in the ModRM byte.

> This actually kinda sounds smart, provided you are doing a high end
> core, and have support for add from memory.
>
> Not a fan of the idea, makes low end chips harder. Any comments?

I'm a fan of load/store architectures and dislike mem-op-mem (and
mem-op, for that matter) instructions in general, but the latter seem to
be back in favor these days due to higher code density and therefore
higher utilization of decode bandwidth.

OTOH, I can't help but think decode bandwidth is limited mainly because
mem-op(-mem) instructions already spit out so many uops that there's
little benefit to making decoders wider, so it's a vicious cycle.

S

--
Stephen Sprunk "God does not play dice." --Albert Einstein
CCIE #3723 "God is an inveterate gambler, and He throws the
K5SSS dice at every possible opportunity." --Stephen Hawking

[Stefan Monnier]

> Maybe bad from an purist architectural point of view, but from a programming
> pov, it's one of the most valuable addressing modes available. In terms of
> minimising code space and adding clarity to the code. Probably also very
> helpfull for the compiler writers as well.

Compiler writers don't need the assembly code to be clear, so no: it's
mostly useless to compiler writers (and if not useless, it just makes
their job more complicated because it adds tradeoffs for when to use
which combination of instructions).


Stefan

[ChrisQ]

On 02/02/12 16:41, Tim McCaffrey wrote:

>
> I think the 6800 was more influenced by the HP-1000/2000 series. Same
> registers (A/B, X/Y) and direct page addressing, although the HP was more
> flexible (it also had indirect addressing). OTOH, some of that stuff was in
> the PDP-8 was well, which I think they all got from Whirlwind.
>

Whenever I see an accumulator and index register machine, I think more
of the DG Nova, or pdp8. I still think the 6800 was influenced more by
pdp11, due to the mnemonics, but admit the internal architecture doesn't
suggest that at all. Some of the more subtle commonalities were in things
like condition codes, where for example, the zero flag is set on a load,
in common with 68k and pdp11. Saves the laboured tst before a branch
requirement.

I used an HP1000 on one site, but knew nothing of the architecture. The wiki
page suggests that it was "one of many machines inspired by the pdp8". Both
belong to the dedicated register for everything style, rather than one
having
a general purpose register set.

Back to indirect addressing, the 6502 had pre and post indexed
addressing modes
and remember writing a menu driver program that traversed a tree
organised list
in just a few lines of assembler. Without the indirect modes, or doing
the same
on a 6800 would involved a lot more code.

>
> If you think of the 68000 address registers as an extension of the X register

> in the 6800 (or X, Y& U in the 6809), and the data registers as an extension

> of the A/B (& D in 6809) registers in the 6800, I think the ancestory is
> pretty obvious. Yes, the assembler mnemonics were PDP-11ish, but so were the
> 8080's.
>

That's a reasonable way to look at it, though the 68k was microcoded, so
it wasn't just a case of gluing on a bit more logic to the 8 bit design. One
of the Renesas embedded cpu's looks a bit like a souped up (8 bit) H8
to provide
16 bit functionality and more address space, but it's a far cry from the
transition
from 6800 to 68k.

Thought: Cisc machines make better use of limited memory, whereas risc
became
predominant because of cheap memory ?...

Regards,

Chris

[Chris Gray]

Brett Davis <gg...@yahoo.com> writes:

> A bit slice graphics chip is the wrong way to go, it was a dead end
> stop gap that had a tiny window of time to survive.
> Once DRAM got cheap enough to do a 16 bit true color frame buffer
> at reasonable resolutions it was dead.

Was DRAM cost the only issue? I'm just a software guy, so I don't know.

> The OS was an afterthought, in an age where software is what mattered.

There you surely must be deliberately trolling! AmigaOS may have been
something that they didn't initially plan on doing (I don't recall), but
it was *the* most elegant of the era. Pre-emptive multitasking (it took
MacOS what, another decade, to get that?), capable CLI/shells running
within GUI windows, full support for shared stereo sound access, etc.
Stuff not available until X-Windows became available on home machines.

> I told the Amiga fanboys this at the time, but they did not care.

Yup, deliberate troll.


-Chris Gray
(author, Amiga Draco compiler system, Amiga Empire multiplayer game,
AmigaMUD multiplayer programmable multimedia MUD system, etc.)

[Mark Thorson]

Stephen Sprunk wrote:
>
> I'm a fan of load/store architectures and dislike mem-op-mem (and
> mem-op, for that matter) instructions in general, but the latter seem to
> be back in favor these days due to higher code density and therefore
> higher utilization of decode bandwidth.
>
> OTOH, I can't help but think decode bandwidth is limited mainly because
> mem-op(-mem) instructions already spit out so many uops that there's
> little benefit to making decoders wider, so it's a vicious cycle.

So I guess that means you wouldn't be pleased
by instructions like A = (B + C) x (D + E)?

If we had a reasonably comprehensive set of
4- and 5-operand instructions, wouldn't that
considerably increase code density and lower
decode bandwidth?

[Brett Davis]

In article <1keuic3.5ot0po1kub280N%nos...@ab-katrinedal.dk>,

nos...@ab-katrinedal.dk (Niels Jørgen Kruse) wrote:

> Brett Davis <gg...@yahoo.com> wrote:
>
> > My Intel Mac is faster than I need, want a less noisy machine.
>
> Pray that Apple expose the dial-a-TDP functionality of Ivy Bridge.
>
> Unfortunately, the desktop processors don't seem to have it.

Apple uses mobile chips in its iMac's.
Unfortunately I have a MacPro due to wanting to reuse a 30" monitor.

[Brett Davis]

In article <1b8vkmm...@pfeifferfamily.net>,

Joe Pfeiffer <pfei...@cs.nmsu.edu> wrote:

> ChrisQ <blac...@devnull.com> writes:
> > On 02/01/12 16:18, sarr.b...@alum.dartmouth.org wrote:
> >> MitchAlsup<Mitch...@aol.com> wrote:
> > What I never worked out was why Motorola split the 16 registers into 8 x
> > data and 8 x address, rather that a cleaner 16 general purpose set. Perhaps
> > it was a limitation in the process technology of the day, but still think
> > that the 68k was a real achievement.
>
> It doubled the number of registers without needing an extra bit to
> address them. Also, when superscalar came in, it let you increase the
> number of read/write ports more easily (I'd be surprised if this latter
> advantage was even a gleam in anybody's eye when the decision was made,
> though).

That is what I thought would happen, that separate registers would make
the high end easier/faster.
But I heard that all the high end chips (68040) actually used a unified
register set under the hood.

[Brett Davis]

In article <1bwr85y...@pfeifferfamily.net>,

Joe Pfeiffer <pfei...@cs.nmsu.edu> wrote:

> Brett Davis <gg...@yahoo.com> writes:
>
> > In article
> > <b8de74f7-2b27-4032...@lr19g2000pbb.googlegroups.com>,
> > Quadibloc <jsa...@ecn.ab.ca> wrote:
> >>
> >> a resurrected Amiga...
> >
> > A bit slice graphics chip is the wrong way to go, it was a dead end
> > stop gap that had a tiny window of time to survive.
> > Once DRAM got cheap enough to do a 16 bit true color frame buffer
> > at reasonable resolutions it was dead.
> >
> > The OS was an afterthought, in an age where software is what mattered.
>
> I *really* have to raise an eyebrow at that contention. Compared to the
> OSes available at the time for PC and Mac, it was remarkably elegant and
> well-designed.

Everyones OS sucked back then. Apple had specific design goals as apposed
to random features thrown around. Some of Apples choices ended up wrong.

> > I told the Amiga fanboys this at the time, but they did not care.
>
> Of course not (having been something of an Amiga fanboy at the time).
> It was a good way to go to get good graphics at the time; the
> expectation was that Amiga would continue to have cutting-edge graphics,
> whatever that meant in the future. I sure had no idea just how insane
> Commodore management was...

Had Jack Tramiel got ahold of Amiga he would have cut costs, made Amiga
a game machine, and made it successful, like he did the Commodore 64.

The Amiga group had delusions of being a viable desktop PC, doomed.

It is a minor miracle Apple survived, before Steve Jobs came back I
expected Apple to die.

Then Steve engineered a reverse take over from NeXT, when interim CEO
Steve Jobs spoke at the Worldwide Developers Conference I got back my
religion.

Cloud computing in 1997 Steve Jobs WWDC
http://www.youtube.com/watch?v=xSxHd-ZJ080

The full hour of Steve Q&A
http://www.youtube.com/watch?v=GnO7D5UaDig

[Terje Mathisen]

Stephen Sprunk wrote:
> I'm a fan of load/store architectures and dislike mem-op-mem (and
> mem-op, for that matter) instructions in general, but the latter seem to
> be back in favor these days due to higher code density and therefore
> higher utilization of decode bandwidth.

I do like mem-op, even if I've been conditioned (by the 486 and Pentium)
to avoid them and instead manually schedule the load part to happen as
early as possible.

OTOH, even during that time, when I wrote a big part of all my asm code,
the x87 fp half had a slightly longer pipeline, with the EX stage just
after the LD stage, specifically so that load-op combinations would be
"free".

>
> OTOH, I can't help but think decode bandwidth is limited mainly because
> mem-op(-mem) instructions already spit out so many uops that there's
> little benefit to making decoders wider, so it's a vicious cycle.

As long as you use plain register-indirect addressing, a load-op
combination doesn't need to use any more opcode bytes than a reg-reg
operation, and it will often save bytes compared with an explicit split.

Re. # of uops: It seems like modern x86 cores tend to go in the opposite
direction and instead combine very common instruction pairs into a
single uop, i.e. stuff like CMP/Jcc. Keeping a load-op as a single uop
would seem simple in comparison. :-)

Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[Terje Mathisen]

Maybe:

Code density/decode bandwidth would also be impacted by the fact that in
order to specify such instructions you would need a _lot_ of opcode
bits, as well as allowing at least two of the operands to come from memory.

OTOH we do have instructions very similar to what you're asking for
already, in the form of short vector operations: You just need to make
sure that B and D (both double?) are stored in a single vector reg, with
C and E coming from either another vector reg, or from a 16-byte aligned
memory address.

I.e. you have to give up generalized addressing in order to reduce the
number of register/memory opcode bits, sort of like some cpus that had
instructions using sequential pairs of registers for double-wide operations.

[Joe Pfeiffer]

Brett Davis <gg...@yahoo.com> writes:

> In article <1bwr85y...@pfeifferfamily.net>,
> Joe Pfeiffer <pfei...@cs.nmsu.edu> wrote:
>
>> Brett Davis <gg...@yahoo.com> writes:
>>
>> > In article
>> > <b8de74f7-2b27-4032...@lr19g2000pbb.googlegroups.com>,
>> > Quadibloc <jsa...@ecn.ab.ca> wrote:
>> >>
>> >> a resurrected Amiga...
>> >
>> > A bit slice graphics chip is the wrong way to go, it was a dead end
>> > stop gap that had a tiny window of time to survive.
>> > Once DRAM got cheap enough to do a 16 bit true color frame buffer
>> > at reasonable resolutions it was dead.
>> >
>> > The OS was an afterthought, in an age where software is what mattered.
>>
>> I *really* have to raise an eyebrow at that contention. Compared to the
>> OSes available at the time for PC and Mac, it was remarkably elegant and
>> well-designed.
>
> Everyones OS sucked back then. Apple had specific design goals as apposed
> to random features thrown around. Some of Apples choices ended up wrong.

Amiga also had a coherent OS design, with multitasking and a really nice
integrated GUI/command line -- in other words, they got several things
right that Apple got wrong.

>> > I told the Amiga fanboys this at the time, but they did not care.
>>
>> Of course not (having been something of an Amiga fanboy at the time).
>> It was a good way to go to get good graphics at the time; the
>> expectation was that Amiga would continue to have cutting-edge graphics,
>> whatever that meant in the future. I sure had no idea just how insane
>> Commodore management was...
>
> Had Jack Tramiel got ahold of Amiga he would have cut costs, made Amiga
> a game machine, and made it successful, like he did the Commodore 64.
>
> The Amiga group had delusions of being a viable desktop PC, doomed.
>
> It is a minor miracle Apple survived, before Steve Jobs came back I
> expected Apple to die.

Amiga's delusions were no worse than Apple's at the time, with better
hardware and a better OS. I'll agree that Apple's survival was a minor
miracle; Amiga's would have been (from a technical standpoint) much less
surprising.

[Anton Ertl]

timca...@aol.com (Tim McCaffrey) writes:
>I think the 6800 was more influenced by the HP-1000/2000 series. Same
>registers (A/B, X/Y) and direct page addressing, although the HP was more
>flexible (it also had indirect addressing). OTOH, some of that stuff was in
>the PDP-8 was well, which I think they all got from Whirlwind.
>
>If you think of the 68000 address registers as an extension of the X register
>in the 6800 (or X, Y & U in the 6809), and the data registers as an extension
>of the A/B (& D in 6809) registers in the 6800, I think the ancestory is
>pretty obvious.

Yes, the 68k is more an extended accumulator machine than a
general-purpose register machine, even though the address registers
were a little less restricted than the index registers of earlier
accumulator machines.

- anton
--
M. Anton Ertl Some things have to be seen to be believed
an...@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html

[ChrisQ]

On 01/31/12 18:15, MitchAlsup wrote:

>
> So, no, indirect addressing has a lot going against it and little for it.
>
> Mitch

Although I find it interesting, i'm a user of cpu architectures, not an
architect, so features
that simplify the hardware design, or make programming at asm level
easier, or that reduce code
size, are often more important in the real world than the quest for
speed. Although code size
is less important now and there's less need for asm programming in
general, there must be an
optimum tradeoff at some point in terms of instruction set complexity
and the resulting code size
/ execution time. That is, you can get more done in a few lines of code
with a cisc architecture,
than can be done with risc. There's also the issue of programmer
productivity, which can be
helped a lot by a regular and powerfull instruction set and addressing
modes, if you need to
program at asm level. Probably going against the grain here, but in the
end, it's the code that
matters, irrespective of how good the machine is on paper...

Regards,

Chris

[ChrisQ]

On 02/02/12 21:46, Stefan Monnier wrote:

>
> Compiler writers don't need the assembly code to be clear, so no: it's
> mostly useless to compiler writers (and if not useless, it just makes
> their job more complicated because it adds tradeoffs for when to use
> which combination of instructions).
>
> Stefan

Compiler writing may be done with tools, but someone has to write the back
end, which requires intimate knowledge of the machine. I always understood
that a gp register architecture is better than a dedicated register
architecture because it allows more flexibility in terms of function call
args. ie: use registers rather than use the stack.

What you seem to be saying is that a less capable architecture is better
from a compiler writers point of view ?...

Regards,

Chris

[Anton Ertl]

ChrisQ <blac...@devnull.com> writes:
>On 02/02/12 21:46, Stefan Monnier wrote:
>
>>
>> Compiler writers don't need the assembly code to be clear, so no: it's
>> mostly useless to compiler writers (and if not useless, it just makes
>> their job more complicated because it adds tradeoffs for when to use
>> which combination of instructions).
>>
>> Stefan
>
>Compiler writing may be done with tools, but someone has to write the back
>end, which requires intimate knowledge of the machine. I always understood
>that a gp register architecture is better than a dedicated register
>architecture because it allows more flexibility in terms of function call
>args.

Also, with GP registers there are no tradeoffs between using different
register classes, which makes things simpler for the compiler writer.

But the point was about complex addressing modes.

>What you seem to be saying is that a less capable architecture is better
>from a compiler writers point of view ?...

If the additional capabilities introduce additional tradeoffs (e.g.,
"use the complex addressing mode or synthesize it from simpler
instructions"), it makes the compiler more complex (at least if it
should be able to use this capability) and the compiler writer's job
harder.

OTOH, if the additional capabilities eliminate tradeoffs (like uniform
general-purpose registers instead of several sets of more
special-purpose registers), they make the compiler simpler.

[ChrisQ]

On 02/03/12 16:12, Anton Ertl wrote:

>
> Also, with GP registers there are no tradeoffs between using different
> register classes, which makes things simpler for the compiler writer.
>

And it's not just limited to arg passing, but also things like fast temp
storage for pointers and variables, rather than having to shuffle
everything
between too few registers and the stack.

>
> If the additional capabilities introduce additional tradeoffs (e.g.,
> "use the complex addressing mode or synthesize it from simpler
> instructions"), it makes the compiler more complex (at least if it
> should be able to use this capability) and the compiler writer's job
> harder.

Agreed, a cleaner architecture should make a better interface to the
programmer, but one assumes that the additional capability is there for
a reason. It's part of the programmers task to become fluent in that, if
he is to get the best from the machine.

I guess that your point is that if the machine's programming interface
is hard work, most programmers will access only a fraction of the
capability, so much of the machine's design effort is effectively wasted...

Regards,

Chris

[Mark Thorson]

Terje Mathisen wrote:
>
> Code density/decode bandwidth would also be impacted by the fact that in
> order to specify such instructions you would need a _lot_ of opcode
> bits, as well as allowing at least two of the operands to come from memory.

You could restrict the generality and rely on
the compiler to anticipate using the instruction
and maneuver the operands into the right registers
before the CISCy instruction.

> OTOH we do have instructions very similar to what you're asking for
> already, in the form of short vector operations: You just need to make
> sure that B and D (both double?) are stored in a single vector reg, with
> C and E coming from either another vector reg, or from a 16-byte aligned
> memory address.

That's one way to do it.

> I.e. you have to give up generalized addressing in order to reduce the
> number of register/memory opcode bits, sort of like some cpus that had
> instructions using sequential pairs of registers for double-wide operations.

There's other ways to do it. You could have the
operand specifiers in registers and load them
in the set-up for a loop. Then, you could afford
to add autoincrement and autodecrement bits. And
maybe a skip-on-bounds bit for automatically dropping
out of a loop without spending any loop instructions
on bounds checking.

If you wanted to get fancy, there could be a loop
termination condition register for specifying
termination conditions other than hitting a bound,
for example if you were searching for a bit pattern.

This moves a lot of the bits (normally expressed in
the instruction stream for a loop) out of the loop.
The bits for specifying how pointers are managed
and how the loop is terminated are fed to the CPU
once during loop set-up, rather than being fed to
the CPU repeatedly for each loop iteration.

If we're feeling particularly fiendish, we could
have multiple sets of specifier registers. If the
CISCy instruction contained no operand or termination
specifiers in the opcode, there would be room for
a bit or a small bit field for selecting the specifier
register set. ABCDEF0 would use set 0, ABCDEF1 would
use set 1, etc. By moving all of the specifiers
except this one out of the opcode, the opcode space
consumed by the ABCDEFx instructions is quite small.
That's what allows us to implement a comprehensive set
of 4- and 5-operand instructions, like ABDEFx, ABCEFx,
etc.

[Anton Ertl]

Well, this subthread is about compilers, which (like programs in
general) tend to be dumber than typical programmers, but surprisingly
good for specific limited tasks (but pretty bad at getting the big
picture).

And the question was, whether an architectural feature is "helpful for
compiler writers". For complex addressing modes, the answer is, that
yes, there are compiler techniques that allow the compiler to use of
them. But using one of them makes the compiler more complex, so a
compiler writer will probably not find their existence very helpful,
even if the resulting code runs faster. As in architecture, the
question is whether the effort that goes into that feature wouldn't be
better spent on making the rest better (i.e., have a more streamlined
implementation of the architecture, or invest more effort in another
optimization).

[Quadibloc]

On Feb 1, 9:53 am, ChrisQ <blackh...@devnull.com> wrote:

> What I never worked out was why Motorola split the 16 registers into 8 x
> data and 8 x address, rather that a cleaner 16 general purpose set.

Well, as has already been noted, it saves a bit when specifying a
register. In my imaginary architecture,

http://www.quadibloc.com/arch/arcint.htm

I do the same thing, but with a subtle twist. The eight data registers
are also used as index registers, while the eight address registers
are used as base registers only.

This is because index values usually result from calculations, while
base register contents are usually constant values loaded
infrequently.

Thus, unlike the 68020, I am able to get full base-index addressing in
a 32-bit instruction even in the original form of the design without
taking special measures to increase code density.

The original form continues to exist as Simple Mode, although with
some changes:

http://www.quadibloc.com/arch/ar010006.htm

after I revised the instruction formats significantly once I made a
breakthrough that finally achieved what I considered a satisfactory
level of code density.

John Savard

[Quadibloc]

On Feb 1, 9:53 am, ChrisQ <blackh...@devnull.com> wrote:

> What I never worked out was why Motorola split the 16 registers into 8 x
> data and 8 x address, rather that a cleaner 16 general purpose set.

To be more specific in answering your question, both my imaginary
design and the 68k use 16 bit displacements when addressing memory.

The IBM 360, in order to use a set of 16 general-purpose registers,
and provide base-index registers, had to limit itself to 12-bit
displacements in order for memory-reference instructions to fit in 32
bits.

John Savard

[ken...@cix.compulink.co.uk]

In article <877h04p...@GraySage.com>, c...@GraySage.com (Chris Gray)
wrote:

> There you surely must be deliberately trolling! AmigaOS may have been
> something that they didn't initially plan on doing (I don't recall),

The Amiga started with a design request from Atari and as I understand
it the OS and hardware were developed together. Then Atari and the Amiga
group had a bust up and the Amiga went to Commodore. Atari did a hasty
job of throwing things together using of the shelf chips and whatever OS
they could pick up cheap which was Gem over TOS. That is how the ST
ended up with a Midi port it was on the same chip as the serial port for
the mouse. Gem may not have been fully multitasking but you could do a
hell of a lot with the accessories.

The ST did have a lot of problems, high resolution required an
expensive monitor and hard drives were much more expensive than PC ones
as they required their own power supply. Still when I was burgled they
left the TV and took the Atari and hard drive.

In the UK at the time the only remotely affordable 16 bit machines for
home use were the ST, Amiga and the QL. PV clones did not become
affordable until Amstrad got into the market and the Archimedes only
sold to schools.

Ken Young

[MitchAlsup]

On Wednesday, February 1, 2012 10:53:35 AM UTC-6, ChrisQ wrote:
> What I never worked out was why Motorola split the 16 registers into 8 x

> data and 8 x address, rather that a cleaner 16 general purpose set. Perhaps
> it was a limitation in the process technology of the day, but still think
> that the 68k was a real achievement.

A) They ran out of instruction bits
B) They could gain register file ports at low cost
C) Microcode could use both register files independently and simultaneously

Mitch

[MitchAlsup]

The grain you are pulling is right out of Bell and Newell. Where thye advocate strongly on the line towards instruction set expressivity. These guys were attached to the PDP-11 architecture, and I used to listen to them talking about it in the compute science parts of CMU when I was there.

The counter argument is the life (and times) of Seymore Cray (and to some extent Bill Wolfe). These guys built faster cycle time machines with somewhat inferrior instruction sets that delivered more to the bottom line (performance) than did the machines from the high expressive camp.

The "gone too far" agrument is embodied in the 432. No need to say more.

If it were possible to pipeline the crap out of a VAX instruction set, DEC would have done so. The difficulty in doing so did not improve DECs life as a viable company.

So, somewhere less than a VAX but greater than an x86 is probably where an optimum would lie. It is a whole lot easier to pipe the crap out of a PDP-11 than a VAX.

However, its all moot. There is not enough performance, area, power to be gained by another instruction set to pay for all the costs in getting said new instruction set off the ground and into a healthy market state.

Mitch

[MitchAlsup]

On Thursday, February 2, 2012 3:09:26 PM UTC-6, Stephen Sprunk wrote:
> OTOH, I can't help but think decode bandwidth is limited mainly because
> mem-op(-mem) instructions already spit out so many uops that there's
> little benefit to making decoders wider, so it's a vicious cycle.

Decode bandwidth is limited by the problem of parsing instruction boundaries. Post decode bandwidth is limited by the number of register rename ports one needs prior to accessing register files and beginning execution.

Neither one of these problems is greatly helped or hurt with mem-op-mem instructions.

And then there is the 3rd party 'problems' that are not present on machines with mem-op-mem instructions. Consider an OS race condition where one OS is modifying a translation table that is being used in another CPU. On a RISC style machine (LD-OP-ST) the Load might use the early bit pattern from memory while the Store might use the later bit pattern from memory. In a Mem-Op-Mep instruction, the store will use the same physical translation as the Load. In addition, the Load and Store can share the Cache/Memory Buffering entries instead of using 2 entries.

Mitch

[Stephen Sprunk]

It would, but at the expense of extra bits to encode all the various 4-
and 5-operand opcodes plus extra bits to encode more operands, which
would mitigate the code density and decode bandwidth improvement. So,
it's probably not worth it in most cases.

The main reason I dislike mem-op(-mem) instructions is that encoding
memory operands requires more bits, which could have been used to make
instructions shorter and/or enlarge the register file, which benefits
_all_ code, not just code that uses memory operands. Ditto for 3- vs
2-operand instructions: in most cases, the third operand isn't needed,
and saving the bits needed to encode it is worth the occasional register
copy to preserve an operand that will be reused.

For instance, x86 would have been an entirely different beast if the
ModRM byte's mode bits were eliminated, allowing 16 GPRs rather than 8;
only load and store instructions would have needed to pay the size
penalty of complex addressing modes. (And perhaps even _more_ complex
ones could have been added, if warranted, since most instructions
wouldn't have had to pay the price.)

[Stephen Sprunk]

On 03-Feb-12 00:42, Terje Mathisen wrote:
> Stephen Sprunk wrote:
>> I'm a fan of load/store architectures and dislike mem-op-mem (and
>> mem-op, for that matter) instructions in general, but the latter seem to
>> be back in favor these days due to higher code density and therefore
>> higher utilization of decode bandwidth.
>
> I do like mem-op, even if I've been conditioned (by the 486 and Pentium)
> to avoid them and instead manually schedule the load part to happen as
> early as possible.

Of course, with a larger register set and no mem-op instructions, it
would have been much easier for compilers to do load hoisting as well,
not to mention much lower stack pressure due to x86's limited register set.

I wonder if x86 could have gone another generation or two without OoO if
it hadn't become necessary so soon for the CPU to crack mem-op
instructions and do its own load hoisting. That transistor budget could
have, instead, gone into wider execution and/or larger caches.

> OTOH, even during that time, when I wrote a big part of all my asm code,
> the x87 fp half had a slightly longer pipeline, with the EX stage just
> after the LD stage, specifically so that load-op combinations would be
> "free".

I'll admit my eyes glaze over when folks talk about FP execution; it's
all I can do, as a layman, to try to keep up with the evolution of
integer pipelines. The idea of FP loads being "free" is bizarre to me,
but I just now barely understand the idea of FXCH being "free", so my
thoughts on that aren't worth much--and I probably won't understand yours.

>> OTOH, I can't help but think decode bandwidth is limited mainly because
>> mem-op(-mem) instructions already spit out so many uops that there's
>> little benefit to making decoders wider, so it's a vicious cycle.
>
> As long as you use plain register-indirect addressing, a load-op
> combination doesn't need to use any more opcode bytes than a reg-reg
> operation,

You still need at least one bit per operand to indicate it's
register-indirect rather than register-direct, don't you? And, no
matter how you slice it, a mem-op instruction is two uops and a
mem-op-mem instruction is three.

> and it will often save bytes compared with an explicit split.

I agree. In the degenerate case, you're looking at two or three
instructions replacing one, and no saving of a few bits here and there
will result in a net win on code size.

However, I dispute how often that case happens, and if saving those bits
enables you to eliminate _other_ instructions (eg. due to reduced stack
pressure from a larger register set) or make the CPU faster in other
ways (eg. due to better ILP), it may be a net win.

> Re. # of uops: It seems like modern x86 cores tend to go in the opposite
> direction and instead combine very common instruction pairs into a
> single uop, i.e. stuff like CMP/Jcc.

I haven't figured out yet why that's a win--or even how it's possible.
The second instruction obviously has a direct dependency on the first,
so how can they execute as a single uop?

Fusing them together for scheduling purposes makes sense, since they'd
likely end up traveling together anyway, but it seems like they'd need
to execute sequentially.

> Keeping a load-op as a single uop would seem simple in comparison. :-)

It doesn't seem like that would help. The _reason_ to crack such an
instruction is to allow hoisting the load far enough above the op that
the operand is available by the time the op is ready to execute and, if
there's a store, allowing that to execute in parallel with following
ops. Or do I misunderstand?

[Andy (Super) Glew]

(0) Let me call these "tree of computation" instructions. I don't really
want to say "CISCy" instructions, since, although complex, they often
could be done by combinatoric logic. Or by simple state machines, like
a divider. Less commonly do people stick references to memory, that
might take cache misses, inside.

A fellow I know who has proposed such an ISA calls them "logic cone"
instructions.

(1) First you create "tree of computation" instructions. And publish
them as an ISA.

(2) Then you hide the tree of computation instructions behind a simpler
ISA, and have a compiler or JITter create the "tree of computaion
instructions" in a hidden, non-public, ISA.

(3) Then you have hardware that can dynamically pack simple RISCy
instructions into such "tree of computati8on" microinstructions.

Dynamically, on the fly, via renamer tricks.

Possibly, probably, caching in a decoded instruction cache.

---

However, in this case the hardware solution may have come along before
the explicit ISA solution.

---

My own work on "dynamic instruction rewriting" is a very simple form of
(3). In that work I was mainly limited by the problem that on x86
memory stores and loads tend to interrupt the computation trees or
chains. I am pretty sure that memory renaming or registerization would
help, but at UWisc I decided that was beyond my scope.

By the way: although some of the memory store/loads were artifacts of
x86 with not enough registers, by no means all were. I tended to
concentrate on the SPEC benchmark gcc for my work, and many of the
store/load chains were writing something into an object's data members,
for later retrieval in completely separate methods and functions. Which
means that a compiler might NOT be able to eliminate these, unless it
had really good pointer disambiguation. Whereas a dynamic approach -
hardware or JIT - should be able to.

Now, there are many workloads that are not so pointer intensive. I
often talk about the ratio of computation to pointers. Gcc has a fairly
low ratio. Graphics is often pretty high. I am told that CAD tools are
also pretty high.

It might be nice to have a slightly better ratio than just the ratio of
computation to pointers. Because that might have the same value if you
had 100 independent register to register instructions per pointer chase,
as if you had 100 dependent register to register instructions per
pointer chase. The former is VLIW, that latter is tree of computation.
But I haven't got a simple metric.

In any case, there may be workloads that are even now susceptible to
"tree of computation".

---

I have spent a lot of time thinking about what particuilar arrangements
of ALUs and other execution units might be most generically useful.

Mark Thorson's example, A = BC + CD, is really just a general case of an
inner product D = sum(A[i]*B[i],i=0,n-1). It's SIMD packed vectors if
they are in a vector register, sorting else if the A[i] and B[i[ are in
separate scalar registers.

Anyway, I'll stipulate to any sort of vector reduction and vector
recurrence being a candidate. Many are mentioned on my wiki (although I
probably should have a page summarizing).

To go further, let's restrict ourselves to scalar trees of computation.
Since one can always do such operations for wevery element of vectors,
and then reduce, or do such computation in a recurrence.

How about reviving the DG Nova style stuff, most recently seen in the ARM?:

Consider a basic op like A*B+C (or A*B+C*D).

Make available a generic set of operations on the inputs and outputs:

transform( transform(A) * transform(B) + transform(C) )

where the transformations can be

transform( x )
:: x
:: -x
:: abs(x)
:: -abs(x)
:: shift( x << n )
:: shift( x >> n )
:: extract_field( x, frombit:tobit )

and so on. It's inconvenient to note, but the +/-/abs/nabs stuff might
be available after the shifts and extracts.

These are all relatively simple operations, that do not add too much
delay, and which are used in a surprisingly large number of situations.


(Note: when I say "too much delay", I am thinking not in terms of the
speed demons of the past like Wmt, 8 gate delays per clock, but in terms
of systems where you want to have as many logic levels as possible in a
clock, that can be useful, because that improves yields. (Or even,
asynch logic... nah, don't go there.))



I might also want to have operations such as max(x1,const), max(x1,x2),
min, limit(x1,lwb,upb), and so on. Probably you would mainly want
such limits on the output, but I wonder about having them on inputs.


Truncations and conversions int/float, and between various precisions.


I would also want such a "tree of computation" to not necessarily be
limited to a single result. If it it had multiple results from
independent subtrees, that would just be VLIW - but I think that we
might want to be able to share subtrtees in the same instruction leading
to different results. And/or record (output to a result register)
various sub-positions in the same tree.

[Andy (Super) Glew]

On 2/3/2012 10:14 PM, Stephen Sprunk wrote:
> On 03-Feb-12 00:42, Terje Mathisen wrote:
>> Stephen Sprunk wrote:
>>> I'm a fan of load/store architectures and dislike mem-op-mem (and
>>> mem-op, for that matter) instructions in general, but the latter seem to
>>> be back in favor these days due to higher code density and therefore
>>> higher utilization of decode bandwidth.
>>
>> I do like mem-op, even if I've been conditioned (by the 486 and Pentium)
>> to avoid them and instead manually schedule the load part to happen as
>> early as possible.
>
> Of course, with a larger register set and no mem-op instructions, it
> would have been much easier for compilers to do load hoisting as well,
> not to mention much lower stack pressure due to x86's limited register set.
>
> I wonder if x86 could have gone another generation or two without OoO if
> it hadn't become necessary so soon for the CPU to crack mem-op
> instructions and do its own load hoisting. That transistor budget could
> have, instead, gone into wider execution and/or larger caches.

Possibly.

However, I think it is worth noting that OoO P6 x86 is really the Intel
chip that killed the RISC upstarts.

All of the competitors could have played the same games.

[Brett Davis]

In article <jgiibd$hkq$1...@dont-email.me>,

Stephen Sprunk <ste...@sprunk.org> wrote:

> On 03-Feb-12 00:42, Terje Mathisen wrote:
> > Stephen Sprunk wrote:
> > Re. # of uops: It seems like modern x86 cores tend to go in the opposite
> > direction and instead combine very common instruction pairs into a
> > single uop, i.e. stuff like CMP/Jcc.
>
> I haven't figured out yet why that's a win--or even how it's possible.
> The second instruction obviously has a direct dependency on the first,
> so how can they execute as a single uop?
>
> Fusing them together for scheduling purposes makes sense, since they'd
> likely end up traveling together anyway, but it seems like they'd need
> to execute sequentially.

Branches are taken care of by the front end predictor, the pipelines
never see a branch, only sequential code.
The CMP has a bit set that fires an interrupt if the branch prediction
was wrong.

[Brian Drummond]

On Thu, 02 Feb 2012 17:41:16 -0700, Chris Gray wrote:

> Brett Davis <gg...@yahoo.com> writes:
>
>> A bit slice graphics chip is the wrong way to go, it was a dead end
>> stop gap that had a tiny window of time to survive. Once DRAM got cheap
>> enough to do a 16 bit true color frame buffer at reasonable resolutions
>> it was dead.
>

> Was DRAM cost the only issue? I'm just a software guy, so I don't know.

>
>> The OS was an afterthought, in an age where software is what mattered.
>

> There you surely must be deliberately trolling! AmigaOS may have been
> something that they didn't initially plan on doing (I don't recall),

It was. From what I remember of the story, Amiga pretty much had the
hardware prototyped, and no OS. Looking around for one, they found a
(Cambridge?) university project, Tripos, which was quickly ported to the
hardware.

SO from Amiga's POV it may have been an afterthought, but it was a well
thought out project. (Perhaps from the Tripos POV, the hardware was the
afterthought?)

- Brian

[Stephen Sprunk]

Ah, I didn't realize that's how it worked. That changes my
understanding of what the fused uops do and what happens on branch
mispredict, but as long as that's rare, it'll be a net win.

Thanks.

[Stephen Sprunk]

Right, for the reason mentioned above. However, if x86 had been
load-store from the start, compilers would (or at least could) have done
their own load hoisting rather than waiting for the silicon to do it for
them, and perhaps x86 would have pulled ahead earlier--and then wider
in-order execution or larger caches on the P5 would have put the nail in
competitors' coffins rather than the P6.

It's so hard to predict the downstream effects of such a fundamental
change, because it affects so many things. Perhaps a load-store x86
would have been stillborn and m68k would have taken the PC
market--though that seems like that would have been a win for everyone
(except Intel, of course).

> All of the competitors could have played the same games.

The RISC upstarts had huge code bloat due to 3-operand, fixed-size
instructions. That meant they required more RAM, disk, I-cache and
memory bandwidth for the same code, which hurt their price/performance
ratio. The idea wasn't so bad, but they didn't have the volume to hang
on until code size didn't matter.

[Andy (Super) Glew]

The following was probably triggered by a literal reading of the reply.
But I suspect that Brett meant something slightly different.

?? On every machine that I have worked on, the pipelines see almost
every branch, if only to verify that the prediction was correct.

If the predictors are correct, they should not be changing control flow.
But they are verifying control flow.

I.e.

* the pipelines check that the branch was taken or not taken as
predicted, for conditional branches

* the pipelines verify the branch target was as predicted, for indirect
jumps, indirect calls, and returns.

For some machines the branch target must also be verified for
conditional jumps, and/or the virtual to physical translation of the
branch target must be verified (for machines where the predictor
predicts physical targets, not virtual targets, and where the mapping
may change out from under you and/or the predictor is not fully tagged).

Unconditional direct jumps and calls might be elided from the pipeline
(except for the virtual to physical issue). But I've not seen anyone do
so. Calls typically flow down the pipeline, carrying the necessary info
for register stack adjustment or link registers.

You could handle changes of control flow at different points in the
pipeline. Indeed, machines with my fingerprints do as much verification
as possible early in the pipeline, i.e. at branch decode. And you could
defer the verification to the retirement or graduation pipestages. I.e.
you could have branches skip the out-of-order part of the pipeline.

But this usually loses performance, because it adds latency to detection
of incorrect branch predictions.

I.e. you could have branches that are correctly predicted never be seen
by the pipeline, if you restrict pipeline to the OOO part, and not the
in-order parts of the pipeline before ansd after. But the incorrectly
predicted branches, those benefit from OOO execution so as to be seen as
early as possible.

> The CMP has a bit set that fires an interrupt if the branch prediction
> was wrong.

Not an interrupt.

I've spent 20 years teaching people that branch mispredictions should be
handled faster than interrupts.

[Paul A. Clayton]

On Feb 4, 1:14 am, Stephen Sprunk <step...@sprunk.org> wrote:
[snip]

> I'll admit my eyes glaze over when folks talk about FP execution; it's
> all I can do, as a layman, to try to keep up with the evolution of
> integer pipelines.  The idea of FP loads being "free" is bizarre to me,
> but I just now barely understand the idea of FXCH being "free", so my
> thoughts on that aren't worth much--and I probably won't understand yours.

Skewed integer pipelines are sometimes used to reduce
the effective load-to-use latency for computations.
By putting one or more do-nothing (or perform load)
pipeline stages before the computational execution
stage, a load can begin one or more cycles earlier
(relative to a computation--this will not help the
load-sourcing-to-load path). The cost is a little
more power (relative to well-scheduled load operations,
which may not be practical due to branches or
register pressure) and a larger branch misprediction
penalty. (A modestly more complex pipeline could
allow evaluation of conditions at the load or the
execute stage, so that if the condition is set
sufficiently early then no extra misprediction
penalty would be suffered.)

The effective latency of a load can also be reduced
if the delay of reading the address register and/or
of computing the address can be reduced. E.g., a
future file (a possibly speculative copy of values)
can be accessed before renaming (removing perhaps
one pipeline stage of latency) and even have a
redundant encoding to accelerate addition, or a
cache might use a simple offset to index into
stack frames, the global region and thread-local
storage. Sum addressed memory (which overlaps
cache indexing and index computation) can also
reduce load latency.

[snip]

> You still need at least one bit per operand to indicate it's
> register-indirect rather than register-direct, don't you?  And, no
> matter how you slice it, a mem-op instruction is two uops and a
> mem-op-mem instruction is three.

If one only had loads for one source, then only one
extra bit per instruction would be needed. If this
operation was limited to the most common computation
operations, then it might only cost a fraction of a
bit. If it was encoded as a load instruction with
the destination register being the zero register,
then the next arbitrary instruction could use one
of its register source name fields for a destination
register name (if destructive operations are
typical)--and using the zero register might
indicate a load-op-store--or as an opcode extension.

[snip]

> I haven't figured out yet why that's a win--or even how it's possible.
> The second instruction obviously has a direct dependency on the first,
> so how can they execute as a single uop?
>
> Fusing them together for scheduling purposes makes sense, since they'd
> likely end up traveling together anyway, but it seems like they'd need
> to execute sequentially.

As Brett Davis mentioned, for compare-and-branch, this
is not the case. In other instances, delayed breaking
of a complex operation into simple operations can
reduce tracking overhead. In addition, a load-op has
an entirely internal dependency chain (the result of
the load can only wake-up [make ready for scheduling]
its own operation), which could simply the scheduling.

[snip]

> It doesn't seem like that would help.  The _reason_ to crack such an
> instruction is to allow hoisting the load far enough above the op that
> the operand is available by the time the op is ready to execute and, if
> there's a store, allowing that to execute in parallel with following
> ops.  Or do I misunderstand?

Allowing some scheduler entries to contain two or more
operations each effectively increases the capacity of
the scheduler. This would not be a full additional
entry since in some cases a separate load operation
would already have issued (and exited the scheduler)
by the time the dependent operation arrives. Likewise
for the ROB, joining multiple instructions can increase
effective capacity. (IIRC, POWER4 tracked chunks of
instructions in its ROB, though this made exceptions
in the middle of a chunk a little more expensive by
forcing a replay of the early instructions of the
chunk. Branches terminated a chunk, so a branch
misprediction would not have an excess penalty.)

[Paul A. Clayton]

On Feb 4, 12:12 pm, "Andy (Super) Glew" <a...@SPAM.comp-arch.net>
wrote:
[snip]

> Unconditional direct jumps and calls might be elided from the pipeline
> (except for the virtual to physical issue).  But I've not seen anyone do
> so.  Calls typically flow down the pipeline, carrying the necessary info
> for register stack adjustment or link registers.
>
> You could handle changes of control flow at different points in the
> pipeline.  Indeed, machines with my fingerprints do as much verification
> as possible early in the pipeline, i.e. at branch decode. And you could
> defer the verification to the retirement or graduation pipestages.  I.e.
> you could have branches skip the out-of-order part of the pipeline.

Implementations of the AT&T CRISP ISA calculated the next
address in the front-end and could execute an operation and
branch in one cycle (the compare was a separate instruction
to be hoisted as early as possible). (CRISP is/was an
interesting memory-memory ISA with a special stack cache
and did not support virtual memory [I think].)

[Terje Mathisen]

Stephen Sprunk wrote:
> On 04-Feb-12 00:49, Andy (Super) Glew wrote:
>> However, I think it is worth noting that OoO P6 x86 is really the Intel
>> chip that killed the RISC upstarts.
>
> Right, for the reason mentioned above. However, if x86 had been
> load-store from the start, compilers would (or at least could) have done
> their own load hoisting rather than waiting for the silicon to do it for
> them, and perhaps x86 would have pulled ahead earlier--and then wider
> in-order execution or larger caches on the P5 would have put the nail in
> competitors' coffins rather than the P6.

As I think you noted earlier, a compiler would have had big problems
with the original 6-7 available x86 registers, so you could only get rid
of load-op if you used those instruction bits to double the number of
registers.

Register pressure was in fact the main reason good asm programmers could
consistently beat the best compilers by a factor of 1.5 to 3 on most code.

I.e. Quake in Mike Abrash' optimized asm on a Pentium ran something like
3 times faster than the original (very good!) C code written by John
Carmack.

> The RISC upstarts had huge code bloat due to 3-operand, fixed-size
> instructions. That meant they required more RAM, disk, I-cache and
> memory bandwidth for the same code, which hurt their price/performance
> ratio. The idea wasn't so bad, but they didn't have the volume to hang
> on until code size didn't matter.

I'm not convinced 3-operand is a net loss at all, even if most of the
obvious wins are in really short sequences of complicated
latency-critical operations.

Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[Stephen Fuld]

On 2/2/2012 5:29 PM, Mark Thorson wrote:
> Stephen Sprunk wrote:
>>
>> I'm a fan of load/store architectures and dislike mem-op-mem (and
>> mem-op, for that matter) instructions in general, but the latter seem to
>> be back in favor these days due to higher code density and therefore
>> higher utilization of decode bandwidth.
>>

>> OTOH, I can't help but think decode bandwidth is limited mainly because
>> mem-op(-mem) instructions already spit out so many uops that there's
>> little benefit to making decoders wider, so it's a vicious cycle.
>
> So I guess that means you wouldn't be pleased
> by instructions like A = (B + C) x (D + E)?
>
> If we had a reasonably comprehensive set of
> 4- and 5-operand instructions, wouldn't that
> considerably increase code density and lower
> decode bandwidth?

I have occasionally thought about a sort of variation on this to
maximize code density and minimize op code usage for these types of
seqwuences. Strings of simple arithmetic operations are concisely
represented using a stack notation, so why not have an "evaluate stack"
instruction. The op code and a destination register would be followed
by a sequence of "operations", each taking only a few bits, which would
consist of the usual arithmetic operations, a push stack with contents
of a specified register operation, and whatever other operations seem
appropriate. Thus the sequence listed above would be encoded as
something like

Evaluate Stack A, push B, push C, Add, Push D, Push E, add, multiply

This would be converted by the decoder into the apropriate series of
uops. The advantages of this include very concise representation,
flexibility in being able to encode lots of sequences with only one op
code, and reduction in the compiler's having to allocate registers for
intermediate values.

Of course there are disadvantages too. :-( And lots of details to be
worked out.

And, also of course, lots of possible extensions.

Thoughts anyone?

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

[Stephen Fuld]

On 2/4/2012 11:53 AM, Terje Mathisen wrote:
> Stephen Sprunk wrote:

snip

>> The RISC upstarts had huge code bloat due to 3-operand, fixed-size
>> instructions. That meant they required more RAM, disk, I-cache and
>> memory bandwidth for the same code, which hurt their price/performance
>> ratio. The idea wasn't so bad, but they didn't have the volume to hang
>> on until code size didn't matter.
>
> I'm not convinced 3-operand is a net loss at all, even if most of the
> obvious wins are in really short sequences of complicated
> latency-critical operations.

A potential compromise would be to have a two operand instruction
format, but with an additional single bit field. Upon decoding, the
value of this field is added to the register number (from the
instruction istelf, not the contents of the specified register) to give
the destination register. Thus, if the value of the field is zero, the
instruction is a traditional two operand instruction. If the bit is
set, then the destination is one register "higher" than the source and
you have preserved the source register's contents.

I think this would gain much (but probably not all) of the value of
three operand instructions, but with only a single bit instead of
however many are needed for a full register specification.

[Stephen Sprunk]

On 04-Feb-12 13:53, Terje Mathisen wrote:
> Stephen Sprunk wrote:
>> On 04-Feb-12 00:49, Andy (Super) Glew wrote:
>>> However, I think it is worth noting that OoO P6 x86 is really the Intel
>>> chip that killed the RISC upstarts.
>>
>> Right, for the reason mentioned above. However, if x86 had been
>> load-store from the start, compilers would (or at least could) have done
>> their own load hoisting rather than waiting for the silicon to do it for
>> them, and perhaps x86 would have pulled ahead earlier--and then wider
>> in-order execution or larger caches on the P5 would have put the nail in
>> competitors' coffins rather than the P6.
>
> As I think you noted earlier, a compiler would have had big problems
> with the original 6-7 available x86 registers, so you could only get rid
> of load-op if you used those instruction bits to double the number of
> registers.

Indeed; that would have been the most logical use of the two bits
recovered by eliminating ModRM's addressing-mode field. However, I
don't know what eight extra registers would have cost the 8086 in terms
of transistors, nor whether reduced stack spills would have made up for
the need for explicit loads/stores.

> Register pressure was in fact the main reason good asm programmers could
> consistently beat the best compilers by a factor of 1.5 to 3 on most code.

How much was the asm advantage on systems with less register pressure?

>> The RISC upstarts had huge code bloat due to 3-operand, fixed-size
>> instructions. That meant they required more RAM, disk, I-cache and
>> memory bandwidth for the same code, which hurt their price/performance
>> ratio. The idea wasn't so bad, but they didn't have the volume to hang
>> on until code size didn't matter.
>
> I'm not convinced 3-operand is a net loss at all, even if most of the
> obvious wins are in really short sequences of complicated
> latency-critical operations.

Perhaps I'm conflating 3-operand instructions with fixed-size
instructions, but the two seem to travel together. A fixed-size
instruction format (eg. MIPS) capable of encoding three operands means a
lot of bits are wasted, resulting in code that is roughly double the
size of 2-operand, variable-length instruction sets (eg. x86, m68k).

Are there examples of a 3-operand, variable-length instruction set? Or,
better yet, a variable-length instruction set where the third operand is
optional?

[Brett Davis]

In article <jgkgik$6jt$1...@dont-email.me>,

Stephen Sprunk <ste...@sprunk.org> wrote:

> Perhaps I'm conflating 3-operand instructions with fixed-size
> instructions, but the two seem to travel together. A fixed-size
> instruction format (eg. MIPS) capable of encoding three operands means a
> lot of bits are wasted, resulting in code that is roughly double the
> size of 2-operand, variable-length instruction sets (eg. x86, m68k).
>
> Are there examples of a 3-operand, variable-length instruction set? Or,
> better yet, a variable-length instruction set where the third operand is
> optional?

Yes, Amtel AVR32
http://en.wikipedia.org/wiki/AVR32
http://www.atmel.com/Images/doc32000.pdf

Also ARM Thumb2/Cortex

[Robert Wessel]

CDC 6600 and Cray-1 (and various of their successors) come to mind.
Neither of those really had optional third operands, although both had
some two operand instructions, these were encoded with an ignored
third operand field.

[Brett Davis]

In article <4F2D6713...@SPAM.comp-arch.net>,

"Andy (Super) Glew" <an...@SPAM.comp-arch.net> wrote:

> On 2/4/2012 2:02 AM, Brett Davis wrote:
> > In article<jgiibd$hkq$1...@dont-email.me>,
> > Stephen Sprunk<ste...@sprunk.org> wrote:
> >
> >> On 03-Feb-12 00:42, Terje Mathisen wrote:
> >>> Stephen Sprunk wrote:
> >>> Re. # of uops: It seems like modern x86 cores tend to go in the opposite
> >>> direction and instead combine very common instruction pairs into a
> >>> single uop, i.e. stuff like CMP/Jcc.
> >>
> >> I haven't figured out yet why that's a win--or even how it's possible.
> >> The second instruction obviously has a direct dependency on the first,
> >> so how can they execute as a single uop?
> >>
> >> Fusing them together for scheduling purposes makes sense, since they'd
> >> likely end up traveling together anyway, but it seems like they'd need
> >> to execute sequentially.
> >
> > Branches are taken care of by the front end predictor, the pipelines
> > never see a branch, only sequential code.
>
> The following was probably triggered by a literal reading of the reply.
> But I suspect that Brett meant something slightly different.

Only kinda, never underestimate the ignorance of a software guy talking
about hardware. ;) I drank that grade school cool-aide I was peddling. ;)

> ?? On every machine that I have worked on, the pipelines see almost
> every branch, if only to verify that the prediction was correct.
>
> If the predictors are correct, they should not be changing control flow.
> But they are verifying control flow.
>
> I.e.
>
> * the pipelines check that the branch was taken or not taken as
> predicted, for conditional branches
>
> * the pipelines verify the branch target was as predicted, for indirect
> jumps, indirect calls, and returns.
>
> For some machines the branch target must also be verified for
> conditional jumps, and/or the virtual to physical translation of the
> branch target must be verified (for machines where the predictor
> predicts physical targets, not virtual targets, and where the mapping
> may change out from under you and/or the predictor is not fully tagged).
>
> Unconditional direct jumps and calls might be elided from the pipeline
> (except for the virtual to physical issue). But I've not seen anyone do
> so. Calls typically flow down the pipeline, carrying the necessary info
> for register stack adjustment or link registers.

This is news thanks.

> You could handle changes of control flow at different points in the
> pipeline. Indeed, machines with my fingerprints do as much verification
> as possible early in the pipeline, i.e. at branch decode. And you could
> defer the verification to the retirement or graduation pipestages. I.e.
> you could have branches skip the out-of-order part of the pipeline.
>
> But this usually loses performance, because it adds latency to detection
> of incorrect branch predictions.
>
> I.e. you could have branches that are correctly predicted never be seen
> by the pipeline, if you restrict pipeline to the OOO part, and not the
> in-order parts of the pipeline before ansd after. But the incorrectly
> predicted branches, those benefit from OOO execution so as to be seen as
> early as possible.

So the merged CMP-Branch carries the alternate resolved branch target address
(or pointer to it) and some other confidential magic you should not discuss.

> > The CMP has a bit set that fires an interrupt if the branch prediction
> > was wrong.
>
> Not an interrupt.
>
> I've spent 20 years teaching people that branch mispredictions should be
> handled faster than interrupts.

Nice to know the entry level hardware guys make the same mistake as me. ;)

The problem with an interrupt is it takes to long to figure out what went
wrong and fix it, whereas the merged CMP-Branch knows and can help directly.
Or something like that.

You want the pipeline to keep moving, not stop it, the OoO part has other
ops before the bad branch that need to complete, retirement can throw away
ops off the path. Clear the incoming stream from adding more bad ops, and
use the merged CMP-Branch to feed new instructions in.

Better?

[Niels Jørgen Kruse]

Stephen Sprunk <ste...@sprunk.org> wrote:

> instructions, but the two seem to travel together. A fixed-size
> instruction format (eg. MIPS) capable of encoding three operands means a
> lot of bits are wasted, resulting in code that is roughly double the
> size of 2-operand, variable-length instruction sets (eg. x86, m68k).

IIRC years ago Anton Ertl posted executable sizes for various ISAs, that
disagree with your claim.

--
Mvh./Regards, Niels Jørgen Kruse, Vanløse, Denmark

[Terje Mathisen]

Sorry, but I think you're probably wrong here:

Such an idea could work well for asm hackers, doing very careful manual
register allocation for any critical inner loop, but compilers seems to
prefer much more orthogonal registers.

OTOH I would be very interested in any data from a system which
allocates a single bit on those instructions where it makes sense to
have both 2-operand and 3-operand versions:

The default is 2-operand, but if the bit is set you get an additional
instruction byte which encodes the third operand. Having 8 extra bits
would allow room for going from 2-operand with 16 regs (8 register bits)
to 32 regs and 3-operand (15 register bits), with a final spare bit to
handle any further extensions.

[Terje Mathisen]

Stephen Sprunk wrote:
> On 04-Feb-12 13:53, Terje Mathisen wrote:
>> Register pressure was in fact the main reason good asm programmers could
>> consistently beat the best compilers by a factor of 1.5 to 3 on most code.
>
> How much was the asm advantage on systems with less register pressure?

Significantly less!

Terje

PS. Even after OoO we managed to speed up one of the AES candidates by
3X on the PentiumPro, going from 32-bit C to 32-bit asm. The same code
in 64-bit mode gained far less, mostly due to having twice the registers
as well as 64-bit basic operations.

[Stephen Sprunk]

On 05-Feb-12 04:31, Niels Jørgen Kruse wrote:
> Stephen Sprunk <ste...@sprunk.org> wrote:
>> instructions, but the two seem to travel together. A fixed-size
>> instruction format (eg. MIPS) capable of encoding three operands means a
>> lot of bits are wasted, resulting in code that is roughly double the
>> size of 2-operand, variable-length instruction sets (eg. x86, m68k).
>
> IIRC years ago Anton Ertl posted executable sizes for various ISAs, that
> disagree with your claim.

Recent research seems to support it, though my "roughly double" may have
been overstating the case:

http://www.csl.cornell.edu/~vince/papers/iccd09/iccd09_density.pdf

Instruction length correlates very well (0.9381) with code size, and the
number of operands per instruction correlates fairly well (0.4982).

[Niels Jørgen Kruse]

Stephen Sprunk <ste...@sprunk.org> wrote:

> On 05-Feb-12 04:31, Niels Jørgen Kruse wrote:
> > Stephen Sprunk <ste...@sprunk.org> wrote:
> >> instructions, but the two seem to travel together. A fixed-size
> >> instruction format (eg. MIPS) capable of encoding three operands means a
> >> lot of bits are wasted, resulting in code that is roughly double the
> >> size of 2-operand, variable-length instruction sets (eg. x86, m68k).
> >
> > IIRC years ago Anton Ertl posted executable sizes for various ISAs, that
> > disagree with your claim.
>
> Recent research seems to support it, though my "roughly double" may have
> been overstating the case:
>
> http://www.csl.cornell.edu/~vince/papers/iccd09/iccd09_density.pdf
>
> Instruction length correlates very well (0.9381) with code size, and the
> number of operands per instruction correlates fairly well (0.4982).

That is for handoptimized assembler, not compiled code.

[EricP]

Stephen Sprunk wrote:
> On 05-Feb-12 04:31, Niels Jørgen Kruse wrote:
>> Stephen Sprunk <ste...@sprunk.org> wrote:
>>> instructions, but the two seem to travel together. A fixed-size
>>> instruction format (eg. MIPS) capable of encoding three operands means a
>>> lot of bits are wasted, resulting in code that is roughly double the
>>> size of 2-operand, variable-length instruction sets (eg. x86, m68k).
>> IIRC years ago Anton Ertl posted executable sizes for various ISAs, that
>> disagree with your claim.
>
> Recent research seems to support it, though my "roughly double" may have
> been overstating the case:
>
> http://www.csl.cornell.edu/~vince/papers/iccd09/iccd09_density.pdf
>
> Instruction length correlates very well (0.9381) with code size, and the
> number of operands per instruction correlates fairly well (0.4982).
>
> S
>

Hmmm... they were correlating to minimum instruction length.
I don't think that is very useful as an ISA may have only
a couple of one byte instructions (noop and halt),
and the rest all 2 or 3 bytes.
Average length would have been a useful measure.

Correlating fixed vs variable would have been interesting,
if only to confirm what everyone "knows" (fixed has lots of zeros).

The number of integer registers vs code size I would expect
to have a U shape, with the minimum from 16 to 31/32.

There might also be combination interactions.
Number of operands is low correlation,
but #operands with #registers is high because
3 operand might need 31/32 regs to avoid spillage.

Eric

[Paul A. Clayton]

On Feb 5, 3:17 am, Brett Davis <gg...@yahoo.com> wrote:
> In article <jgkgik$6j...@dont-email.me>,

And microMIPS (similar to Thumb2).

[Stephen Sprunk]

On 05-Feb-12 11:06, EricP wrote:
> Stephen Sprunk wrote:
>> On 05-Feb-12 04:31, Niels Jørgen Kruse wrote:
>>> Stephen Sprunk <ste...@sprunk.org> wrote:
>>>> instructions, but the two seem to travel together. A fixed-size
>>>> instruction format (eg. MIPS) capable of encoding three operands
>>>> means a lot of bits are wasted, resulting in code that is roughly
>>>> double the size of 2-operand, variable-length instruction sets (eg.
>>>> x86, m68k).
>>>
>>> IIRC years ago Anton Ertl posted executable sizes for various ISAs,
>>> that disagree with your claim.
>>
>> Recent research seems to support it, though my "roughly double" may
>> have been overstating the case:
>>
>> http://www.csl.cornell.edu/~vince/papers/iccd09/iccd09_density.pdf
>>
>> Instruction length correlates very well (0.9381) with code size, and the
>> number of operands per instruction correlates fairly well (0.4982).
>

> Hmmm... they were correlating to minimum instruction length.
> I don't think that is very useful as an ISA may have only
> a couple of one byte instructions (noop and halt),
> and the rest all 2 or 3 bytes.
> Average length would have been a useful measure.

True, though variable-length instructions do tend towards the low end,
so I'm not sure how much difference it would make.

> Correlating fixed vs variable would have been interesting,
> if only to confirm what everyone "knows" (fixed has lots of zeros).

Agreed.

> The number of integer registers vs code size I would expect
> to have a U shape, with the minimum from 16 to 31/32.

That is the conventional wisdom. However, 16-register code seems to
consistently beat 32-register code on size, so the minimum may be at 16.
OTOH, that could be a result of the correlation between #register and
other factors (below).

> There might also be combination interactions.
> Number of operands is low correlation,
> but #operands with #registers is high because
> 3 operand might need 31/32 regs to avoid spillage.

I don't see why that would be the case; you can always set the
destination in a 3-operand instruction to one of the sources,
effectively making it a 2-operand instruction, if you don't need to
preserve both sources. OTOH, a 2-operand instruction set would require
an extra instruction to preserve a source.

The correlation between #operands and #registers may be misleading, as
both correlate well with larger, fixed-size instructions: lots of bits
to burn, which apparently doesn't turn out to be productive very often.

[EricP]

Stephen Sprunk wrote:

> On 05-Feb-12 11:06, EricP wrote:
>> There might also be combination interactions.
>> Number of operands is low correlation,
>> but #operands with #registers is high because
>> 3 operand might need 31/32 regs to avoid spillage.
>
> I don't see why that would be the case; you can always set the
> destination in a 3-operand instruction to one of the sources,
> effectively making it a 2-operand instruction, if you don't need to
> preserve both sources. OTOH, a 2-operand instruction set would require
> an extra instruction to preserve a source.
>
> The correlation between #operands and #registers may be misleading, as
> both correlate well with larger, fixed-size instructions: lots of bits
> to burn, which apparently doesn't turn out to be productive very often.
>
> S
>

I was thinking that basically more registers means less spills,
but more registers requires larger register fields,
leaving less opcode space, forcing you to go to a longer
instruction sooner and increasing your average length.

For example, for a load-store ISA we could have
1, 2, and 3 byte instructions, not including immediate values.
2 bytes can only handle 2 operands.
At 3 bytes long we can do 3 operands.

Noop, halt and breakpoint must be one byte because they
can fall on any boundary.

For 16 registers we can have 1, 2 or 3 bytes with
both 2 and 3 operand forms in formats:
8
8-4-4
12-4-4-4

An 8 bit opcode gives us plenty of opcode space.
Any operation with no registers can be 1 byte,
particularly the branch and call instructions.

However for 32 registers the two 5 bit fields leave only
6 opcode bits. We run out of space sooner and have to
move to the longer 3 byte format:
8 (Noop, halt and breakpoint only)
16 (all other non-register instr)
6-5-5
9-5-5-5

Only Noop, halt and breakpoint can be 1 byte because we are so
short on opcode space. All others are 2 or 3 bytes.

So more registers means less spills,
but also longer average instruction length.

Eric

[Andy (Super) Glew]

I like it. I have had similar thoughts.

Although, if we want to stop short of a full stack machine, we might
consider having a stack like sub-language just used to express the
complex operations - Mark's (A*B)+(C*D) (which is not really complex),
my T(T(A)*T(B)+T(C)), to somewhat more arbitrary forms such as "whatever
can be expressed by two multipliers with two adders, and various MUXen
of arithmetic."

We might constrain the stack expressions to only handle computations
that can be mapped onto the particular execution unit structure. E.g.
at most 4 source pushes, 8 commands (2 muls, 2 adds, 4 logic), etc.

Possibly fixed length, padded, or possibly variable length. The latter
supports binary compatibility, so long as the next generation ALU is a
superset of the previous generation.

[Quadibloc]

On Feb 5, 8:34 am, Stephen Sprunk <step...@sprunk.org> wrote:

> Recent research seems to support it, though my "roughly double" may have
> been overstating the case:

Hmm. I wonder if you would actually like what I'm doing at

http://www.quadibloc.com/arch/arcint.htm

with the ISA of an imaginary computer. Like the IBM 360, it has 16-bit
register to register instructions and 32-bit memory reference
instructions; but in addition I use a lot of tricks to squeeze in more
instructions into the opcode space so that more instructions can be as
short as possible (for example, I have 16-bit relative branch
instructions for short distances, and 16-bit shift instructions).

(I tried posting this before, but it doesn't seem to be showing up.)

John Savard

[Quadibloc]

On Feb 5, 8:34 am, Stephen Sprunk <step...@sprunk.org> wrote:

> Recent research seems to support it, though my "roughly double" may have
> been overstating the case:

Maybe you would actually like the things I've been doing in the design
of an ISA for an imaginary computer:

http://www.quadibloc.com/arch/arcint.htm

Like the IBM 360, it has 16-bit register-to-register instructions and
32-bit register to memory instructions. But I've also used a lot of
other tricks to squeeze in as many instructions as possible in the
opcode space, so as to keep as many instructions as short as possible.

John Savard

[MitchAlsup]

On Sunday, February 5, 2012 3:59:33 PM UTC-6, Andy (Super) Glew wrote:
> I like it. I have had similar thoughts.
>
> Although, if we want to stop short of a full stack machine, we might
> consider having a stack like sub-language just used to express the
> complex operations - Mark's (A*B)+(C*D) (which is not really complex),
> my T(T(A)*T(B)+T(C)), to somewhat more arbitrary forms such as "whatever
> can be expressed by two multipliers with two adders, and various MUXen
> of arithmetic."

There is a lot of middle ground! The problem is that at one level, one is trying to express the multiplexers between the register file(s) and the function unit, independently of the other level where one is trying to express the actual function to be computed.

Imaging you had a instruction that could express the multiplexers functionality on the way to the function unit and then a second instruction to express the function to be performed after the data arrived.

Placing both requirements in one instruction creates a multiplicative effect in the number of instructions required. Whereas, expressing the functionality independently significantly reduces the complexity of "talking" to the hardware resources that will already exist.

Thus; one could express:

A<127:96> = B<127:92> * C< 31: 0>
A< 95:64> = B< 95:64> * C< 63:32>
A< 63:32> = B< 63:32> * C< 95:63>
A< 31: 0> = B< 31: 0> * C<127:96>

In 2 instructions. The first instructions annotates the selection pattern on the data, the second annotates teh computation on the selected data.

Mitch

[Erik Trulsson]

Brian Drummond <br...@shapes.demon.co.uk> wrote:
> On Thu, 02 Feb 2012 17:41:16 -0700, Chris Gray wrote:

>> Brett Davis <gg...@yahoo.com> writes:
>>
>>> A bit slice graphics chip is the wrong way to go, it was a dead end
>>> stop gap that had a tiny window of time to survive. Once DRAM got cheap
>>> enough to do a 16 bit true color frame buffer at reasonable resolutions
>>> it was dead.
>>
>> Was DRAM cost the only issue? I'm just a software guy, so I don't know.
>>
>>> The OS was an afterthought, in an age where software is what mattered.
>>
>> There you surely must be deliberately trolling! AmigaOS may have been
>> something that they didn't initially plan on doing (I don't recall),

> It was. From what I remember of the story, Amiga pretty much had the
> hardware prototyped, and no OS. Looking around for one, they found a
> (Cambridge?) university project, Tripos, which was quickly ported to the
> hardware.


Not quite. The OS was developed in parallel with the hardware and mostly
finished on time, with the execption of one important component, namely the
part which handled filesystems and such things. At this point they did
indeed quickly port Tripos to cover the missing parts. If you look at the
innards of AmigaOS you will quickly notice that dos.library is quite
different in design and calling conventions than the rest of the OS. Part
of the difference is that these parts (like Tripos before it) was written
in BCPL rather than in C or Assembler like the rest of the OS.


> SO from Amiga's POV it may have been an afterthought, but it was a well
> thought out project. (Perhaps from the Tripos POV, the hardware was the
> afterthought?)

> - Brian

--
<Insert your favourite quote here.>
Erik Trulsson
ertr...@student.uu.se

[Piotr Wyderski]

Brett Davis wrote:

> http://www.silabs.com/products/mcu/Pages/8051-microcontroller.aspx

Please, let it die... :-(

Best regards,
Piotr Wyderski

[Marven Lee]

cross-posted to alt.os.development

Erik Trulsson wrote:

> Brian Drummond wrote:
>> It was. From what I remember of the story, Amiga pretty much had the
>> hardware prototyped, and no OS. Looking around for one, they found a
>> (Cambridge?) university project, Tripos, which was quickly ported to the
>> hardware.
>
> Not quite. The OS was developed in parallel with the hardware and mostly
> finished on time, with the execption of one important component, namely
> the part which handled filesystems and such things. At this point they
> did indeed quickly port Tripos to cover the missing parts. If you look at
> the innards of AmigaOS you will quickly notice that dos.library is quite
> different in design and calling conventions than the rest of the OS. Part
> of the difference is that these parts (like Tripos before it) was written
> in BCPL rather than in C or Assembler like the rest of the OS.

I believe that Tim King wrote Tripos at Cambridge and he then went on
to write the HeliOS operating system at Perihelion for the Inmos
transputers. I remember reading in UK computer magazines about Atari's
ATW/Abaq workstations with transputers in, can't remember much about
them though.

AmigaOS had quite a nice design overall. In many ways the core
exec.library does resemble a microkernel except there is no memory
protection. But overall I prefer to think of it as a modular system
composed out of shared libraries. Of course it did do message passing,
usually for receiving GUI events or inside device drivers or file system
handlers.

The Amiga's device drivers had an interesting way of handling IO requests,
drivers had an entry point called BeginIO which was passed an IO request
structure. BeginIO wasn't called directly but through exec.library functions
DoIO and SendIO/WaitIO. The driver's BeginIO routine had the option of
handling a request synchronously in the caller's task context and returning
when it completed or handling it asynchronously by sending the message to
a task within the device driver and returning immediately. The caller would
then have to call WaitIO (or wait on a replyport) to determine when the IO
request had completed. Handling the request on the client's task removed
the overhead of task switching.

The Amiga's libraries were more like kernel modules that shared state among
processes that really should have been protected from user applications.
Instead of a trap to the kernel they were merely library calls.

Inside my kernel I use Amiga-style message passing and device IO but that
is only exposed to the kernel and drivers. I've got a Unix-like API for
user mode processes though the whole thing turned into a bit of a mess.

Perhaps AmigaOS could have gained memory protection and resource tracking
in a similar way by running all existing code, libraries, devices and
applications in supervisor mode, ie a monolithic kernel. Old applications
would be unprotected but new applications could be protected with
user-mode processes.

Some new mechanism would be needed to create user-mode processes with
separate address spaces. Perhaps it could be called unix.library and it
would act as the kernel entry point for all system call traps and exceptions
from new user-mode applications. It would act as a reference monitor,
maintaining lists of open files, memory, windows, etc and providing ways
of copying data to and from the kernel. It would then invoke the other
libraries inside the kernel to do the actual work. On a fatal exception
it could cleanup and close any resources.

Peter da Silva sort of described something similar in this post,
http://tinyurl.com/7ezpll2

Although old applications would run unprotected in the kernel, some of
them, namely command line utilities could be made to run in user-mode.
Looking through the Amiga newsgroup archives it seems that someone
made stripped down versions of exec.library and dos.library and used
them to run command line tools and C compilers on 68K Unix
workstations.

It is also a pity that not many Amigas came with an MMU. The 68000
remained in systems upto 1992 with the Amiga 600. The Amiga 1200
and 4000/030 in 92/93 had no MMU either.

--
Marv

[Anton Ertl]

nos...@ab-katrinedal.dk (=?ISO-8859-1?Q?Niels_J=F8rgen_Kruse?=) writes:
>Stephen Sprunk <ste...@sprunk.org> wrote:
>
>> instructions, but the two seem to travel together. A fixed-size
>> instruction format (eg. MIPS) capable of encoding three operands means a
>> lot of bits are wasted, resulting in code that is roughly double the
>> size of 2-operand, variable-length instruction sets (eg. x86, m68k).
>
>IIRC years ago Anton Ertl posted executable sizes for various ISAs, that
>disagree with your claim.

That posting was <2007Dec1...@mips.complang.tuwien.ac.at> (web:
<http://groups.google.com/group/comp.arch/browse_thread/thread/d397ad7278ff8f3b/aaffae6032f1e2ea?q=#aaffae6032f1e2ea>).

Here's the data from that posting (Linux packages only, the Hurd
result is funny).

.text
section
230024 dpkg_1.14.12_m68k.deb
249572 dpkg_1.14.12_amd64.deb
254984 dpkg_1.14.12_arm.deb
263596 dpkg_1.14.12_i386.deb
271832 dpkg_1.14.12_s390.deb
277576 dpkg_1.14.12_sparc.deb
295124 dpkg_1.14.12_hppa.deb
320032 dpkg_1.14.12_powerpc.deb
351968 dpkg_1.14.12_alpha.deb
361872 dpkg_1.14.12_mipsel.deb
371584 dpkg_1.14.12_mips.deb
615200 dpkg_1.14.12_ia64.deb

- anton
--
M. Anton Ertl Some things have to be seen to be believed
an...@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html

[nm...@cam.ac.uk]

In article <9pa1vr...@mid.individual.net>,

Marven Lee <marv...@gmail.com> wrote:
>Erik Trulsson wrote:
>> Brian Drummond wrote:
>>> It was. From what I remember of the story, Amiga pretty much had the
>>> hardware prototyped, and no OS. Looking around for one, they found a
>>> (Cambridge?) university project, Tripos, which was quickly ported to the
>>> hardware.
>>
>> Not quite. The OS was developed in parallel with the hardware and mostly
>> finished on time, with the execption of one important component, namely
>> the part which handled filesystems and such things. At this point they
>> did indeed quickly port Tripos to cover the missing parts. If you look at
>> the innards of AmigaOS you will quickly notice that dos.library is quite
>> different in design and calling conventions than the rest of the OS. Part
>> of the difference is that these parts (like Tripos before it) was written
>> in BCPL rather than in C or Assembler like the rest of the OS.
>
>I believe that Tim King wrote Tripos at Cambridge and he then went on
>to write the HeliOS operating system at Perihelion for the Inmos
>transputers. I remember reading in UK computer magazines about Atari's
>ATW/Abaq workstations with transputers in, can't remember much about
>them though.

He did a good part of it, though Martin Richards led the team, and
there were several people involved. It was an odd system, because
it had most characteristics of a true operating system (rather than
a run-time executive, as in the 1950s, MS-DOS etc.), except for
protection. As a result, it was not really very suitable for any
system that would be used for program development (any more than
MS-DOS or MacOS were), but was very suitable for packaged systems.
Whether or not that affected the success or failure of the Amiga
is something I can't say.

Wikipedia seems to be pretty accurate on it.


Regards,
Nick Maclaren.

[Nick Garnett]

On 06/02/12 13:12, Marven Lee wrote:
> cross-posted to alt.os.development

> I believe that Tim King wrote Tripos at Cambridge and he then went on
> to write the HeliOS operating system at Perihelion for the Inmos
> transputers. I remember reading in UK computer magazines about Atari's
> ATW/Abaq workstations with transputers in, can't remember much about
> them though.

It's strange how all this stuff gets mixed up after a few years.

Tim King didn't write Tripos, it was written by Martin Richards and a
team of graduate students at Cambridge in the late 70's early 80's. Tim
used Tripos at the University of Bath when he moved there and negotiated
a deal to exploit Tripos commercially when he moved to MetaComCo. Tim
ported Tripos to run on top of the Amiga kernel, making a number of
changes to meet Amiga's requirements and including some changes I had
made at Bath. Renamed AmigaDOS, it mainly supplied file system, console
and CLI/shell commands.

Tripos was commissioned as a backup plan to what was originally intended
to be the DOS component being developed elsewhere. That never
materialized and Tripos was used instead, despite the clunky interface
between the C/ASM Amiga code and the BCPL of Tripos.

Tim also didn't write Helios, I did.

The Atari thing was never a big success, it was a little too early in
the development cycle and both the hardware and software were fragile.


--
Nick Garnett eCos Kernel Architect
eCosCentric Limited http://www.eCosCentric.com The eCos experts
Barnwell House, Barnwell Drive, Cambridge, UK. Tel: +44 1223 245571
Registered in England and Wales: Reg No: 4422071

[Stephen Sprunk]

OTOH, from earlier in that same thread:

Anton Ertl wrote:
> .text
> section
> 33744 gzip_1.3.5-9_m68k.deb
> 39040 gzip_1.3.5-9_i386.deb
> 43940 gzip_1.3.5-9_sparc.deb
> 46044 gzip_1.3.5-9_arm.deb
> 48672 gzip_1.3.5-9_powerpc.deb
> 51468 gzip_1.3.5-9_hppa.deb
> 58864 gzip_1.3.5-9_alpha.deb
> 71872 gzip_1.3.5-9_mipsel.deb
> 71904 gzip_1.3.5-9_mips.deb
> 88256 gzip_1.3.5-9_ia64.deb

Yes, as noted the m68k and i386 packages use some asm, but it still
shows how density can vary.

AIUI, there's not much point in trying to hand-optimize asm code for
most RISCs because they're so simple a compiler can get close to
optimal, whereas compilers are nowhere near as good at optimizing for
CISC machines.

[Stephen Sprunk]

On 05-Feb-12 15:43, EricP wrote:
> Stephen Sprunk wrote:
>> On 05-Feb-12 11:06, EricP wrote:
>>> There might also be combination interactions.
>>> Number of operands is low correlation,
>>> but #operands with #registers is high because
>>> 3 operand might need 31/32 regs to avoid spillage.
>>
>> I don't see why that would be the case; you can always set the
>> destination in a 3-operand instruction to one of the sources,
>> effectively making it a 2-operand instruction, if you don't need to
>> preserve both sources. OTOH, a 2-operand instruction set would require
>> an extra instruction to preserve a source.
>>
>> The correlation between #operands and #registers may be misleading, as
>> both correlate well with larger, fixed-size instructions: lots of bits
>> to burn, which apparently doesn't turn out to be productive very often.
>

> I was thinking that basically more registers means less spills,
> but more registers requires larger register fields,
> leaving less opcode space, forcing you to go to a longer
> instruction sooner and increasing your average length.

That's roughly what I meant, though we apparently disagree about whether
the chicken or the egg came first.

Did larger instructions lead to more registers and operands, or did more
registers and operands lead to larger instructions? Were all three the
result of some _other_ cause, perhaps?

> So more registers means less spills,
> but also longer average instruction length.

Exactly, though the set of active registers is limited, so once you
reach a certain number, there will be no more spills and all you're
getting is longer instructions for no benefit. It seems that point is
somewhere between 16 and 32 registers.

[nm...@cam.ac.uk]

In article <jgostg$noh$1...@dont-email.me>,

Stephen Sprunk <ste...@sprunk.org> wrote:
>
>AIUI, there's not much point in trying to hand-optimize asm code for
>most RISCs because they're so simple a compiler can get close to
>optimal, whereas compilers are nowhere near as good at optimizing for
>CISC machines.

Few so-called RISCs are actually simple, especially when it comes
to memory efficiency, so hand optimising for that can really pay.
Areas where that is done include the BLAS and FFTs.


Regards,
Nick Maclaren.

[Anton Ertl]

Stephen Sprunk <ste...@sprunk.org> writes:
>AIUI, there's not much point in trying to hand-optimize asm code for
>most RISCs because they're so simple a compiler can get close to
>optimal

I have my doubts about that. E.g., read the compiler writer's guide
for the Alpha 21264, it's full of funny things that influence the
performance and for which I have not seen any papers on code
generation (and I have seen funny performance variations on a real
21264). Even if compilers address some of these things, I don't think
that they will do it in an optimal way. OTOH, some CISC
implementations (especially from AMD) seem more oriented towards
making a wide range of existing code run fast, so most code will
perform reasonably well.

Also, I remember reading about moving through memory instead of
reg-reg-moves for more performance in some kernel tuned for the P6
where the load and store ports were underutilized and the ports used
for reg-reg-moves were saturated. That kind of optimization is not
specific to RISC or CISC (there could also be a RISC with resource
limitations like the P6), and compilers generally don't do it.

[EricP]

Andy (Super) Glew wrote:
>
> I've spent 20 years teaching people that branch mispredictions should be
> handled faster than interrupts.
>

Why would this be so? I can see that an x86 would be
difficult to optimize for interrupts, because of things
like segment register switches. But on a simpler arch
like MIPS it seems that, hypothetically, an interrupt
could be, at worst the same cost as a mispredicted branch
(pipeline drain, fetch alternate path), and at best pipeline
the mode switch so it costs a predicted taken branch.

Eric

[Quadibloc]

On Feb 2, 6:29 pm, Mark Thorson <nos...@sonic.net> wrote:

> So I guess that means you wouldn't be pleased
> by instructions like A = (B + C) x (D + E)?
>
> If we had a reasonably comprehensive set of
> 4- and 5-operand instructions, wouldn't that
> considerably increase code density and lower
> decode bandwidth?

I just realized that my imaginary computer architecture, in its
pursuit of everything but the kitchen sink, does address the idea of
having instructions of this type...

http://www.quadibloc.com/arch/ar010201.htm
discusses Multi-Way Vector Operations, and

http://www.quadibloc.com/arch/ar0203.htm
discusses the Compose Pipeline Sequence and Fixed-Length Loop
instructions.

John Savard

[nm...@cam.ac.uk]

In article <rmVXq.16275$%17....@newsfe06.iad>,

Not answering for Andy.

A user-mode interrupt (sadly out of fashion) could and should be
handled for the cost of a mispredicted branch plus a function
call. That's the easy case.

Despite the fact that people claim that an interrupt does not
switch context, most architectures implement them so that they
execute in some totally privileged context. In addition to the
cost of changing state, the interrupt handler then needs to
sanitise the situation enough that it isn't going to trash
something visible to the interrupted code. And that logic
always has been a fruitful source of bugs.

And then there's the 'should'. Except for the specialised
systems that run almost entirely at one privilege level, any
half-competent system should minimise interrupts. They are
bad software engineering, if nowt else.


Regards,
Nick Maclaren.

[Joe keane]

In article <jgkgik$6jt$1...@dont-email.me>,

Stephen Sprunk <ste...@sprunk.org> wrote:
>Are there examples of a 3-operand, variable-length instruction set?

VAX?

>Or, better yet, a variable-length instruction set where the third
>operand is optional?

VAX?

[Marven Lee]

Nick Garnett wrote:

> Marven Lee wrote:
>> I believe that Tim King wrote Tripos at Cambridge and he then went on
>> to write the HeliOS operating system at Perihelion for the Inmos
>> transputers. I remember reading in UK computer magazines about Atari's
>> ATW/Abaq workstations with transputers in, can't remember much about
>> them though.
>
> It's strange how all this stuff gets mixed up after a few years.
>
> Tim King didn't write Tripos, it was written by Martin Richards and a
> team of graduate students at Cambridge in the late 70's early 80's. Tim
> used Tripos at the University of Bath when he moved there and negotiated
> a deal to exploit Tripos commercially when he moved to MetaComCo. Tim
> ported Tripos to run on top of the Amiga kernel, making a number of
> changes to meet Amiga's requirements and including some changes I had
> made at Bath. Renamed AmigaDOS, it mainly supplied file system, console
> and CLI/shell commands.

Oops! my mistake. A few months ago when I was looking up how AmigaDOS
used coroutines I should have looked up Tripos as well, then I would've
noticed Martin Richards name.

I was looking at ways of multithreading a single threaded file system
server and managed to "reinvent" coroutines. I was quite pleased with myself
until I realised Conway invented them a long time ago. I then learnt that
old versions of QNX and AmigaDOS had used them in their file systems.
I guess Tripos used them and that they weren't just added to AmigaDOS
as a way of merging it into the rest of the OS.


--
Marv

[EricP]

MitchAlsup wrote:
> On Wednesday, February 1, 2012 10:53:35 AM UTC-6, ChrisQ wrote:
>> What I never worked out was why Motorola split the 16 registers into 8 x
>> data and 8 x address, rather that a cleaner 16 general purpose set. Perhaps
>> it was a limitation in the process technology of the day, but still think
>> that the 68k was a real achievement.
>
> A) They ran out of instruction bits
> B) They could gain register file ports at low cost
> C) Microcode could use both register files independently and simultaneously
>
> Mitch

Microprogrammed implementation of a single chip microprocessor (1978)
Skip Stritter, Nick Tredennick
http://dl.acm.org/citation.cfm?id=804299

talks mostly about the 68000 microcode (2 level, vertical + horizontal).
However it does touch a little on the internal organization.

X = bus isolator

-------X-------------------X-------\16 addr bus
| | |
Bank 1 Bank 2 Bank 3
16 bits 16 bits 16 bits
8 High Addr Regs 8 Low Addr Regs 8 Low Data Regs
8 High Data Regs Arithmetic Low ALU
Arithmetic High | |
| | |
-------X-------------------X-------\16 data bus

"The register file is divided into three
sections as shown in Fig. I. Two buses connect
all of the words in the register file. The
register file sections are either isolated or
concatermted using the bi-directional bus
switches;. This permits general register transfer
operations across register sections. A
limited arithmetic unit is located in each
segment containing address register words and
a general capability arithmetic and logical
unit is located in the data low word section.
This allows address and data calculations to
occur simultaneously. For example, it is
possible to do a register-to-register word
addition concurrently with a program counter
increment (the program counter is colocated
with the address register words and carry out
from the aritemetic unit low is provided as
carry in to the arithmetic unit high).
Special functional units for bit manipulation,
packing and unpacking data are located in the
data section.

Two factors combined to suggest the desirability
of the configuration shown in Figure I.
The first was a very dense two-port static RAM
cell which conveniently supported a two-bus
structure. The second was the 16-bit data width
which made 16-bit segmentation of the registers
desirable."

Instruction register fields and alu function codes
are routed directly from the instruction register to
the register banks and ALU's, saving on microcode.

It doesn't say why they collocated the
high data and high address regs.

Eric

[Nick Garnett]

On 07/02/12 12:06, Marven Lee wrote:

> Nick Garnett wrote:
>> Tim King didn't write Tripos, it was written by Martin Richards and a
>> team of graduate students at Cambridge in the late 70's early 80's.

>

> Oops! my mistake. A few months ago when I was looking up how AmigaDOS
> used coroutines I should have looked up Tripos as well, then I would've
> noticed Martin Richards name.

A lot of this stuff is lost in the mists of time. Even those of us who
were there have difficulty separating the myths from the reality now.

> I was looking at ways of multithreading a single threaded file system
> server and managed to "reinvent" coroutines. I was quite pleased with myself
> until I realised Conway invented them a long time ago. I then learnt that
> old versions of QNX and AmigaDOS had used them in their file systems.
> I guess Tripos used them and that they weren't just added to AmigaDOS
> as a way of merging it into the rest of the OS.

Yes, coroutines were an integral part of the way Tripos worked. All the
system tasks, console handler, file handler, network handler, were
internally a collection of coroutines. The CLI originally ran any
commands as subordinate coroutines, I believe AmigaDOS eventually ran
commands as separate tasks to more closely duplicate Unix. Tripos
coroutines were essentially cooperative threads, each had a stack and a
control block. Unlike threads, transfer of control between coroutines
was explicit, to a specific destination coroutine. However, there were
tricks in the BCPL runtime that could allow a more thread-like behaviour.

[Brett Davis]

In article <wQcYq.14668$Au5...@newsfe23.iad>,

Int was 16 bits, as most data was 16 in that day,
addresses are 32 bits. With three 16 bit ALU's you
could dual issue an address op with a 16 bit data op.
I assume the decoder was not fast enough or smart
enough to do this, so the third ALU is just wasted.
Perhaps ran into technical problems, or there is
some other reason.

[EricP]

Brett Davis wrote:
> In article <wQcYq.14668$Au5...@newsfe23.iad>,
> EricP <ThatWould...@thevillage.com> wrote:
>
>>
>> X = bus isolator
>>
>> -------X-------------------X-------\16 addr bus
>> | | |
>> Bank 1 Bank 2 Bank 3
>> 16 bits 16 bits 16 bits
>> 8 High Addr Regs 8 Low Addr Regs 8 Low Data Regs
>> 8 High Data Regs Arithmetic Low ALU
>> Arithmetic High | |
>> | | |
>> -------X-------------------X-------\16 data bus
>>
>

> Int was 16 bits, as most data was 16 in that day,
> addresses are 32 bits. With three 16 bit ALU's you
> could dual issue an address op with a 16 bit data op.
> I assume the decoder was not fast enough or smart
> enough to do this, so the third ALU is just wasted.
> Perhaps ran into technical problems, or there is
> some other reason.

There are actually more registers than I have on that diagram
as there are is also the PC, status byte, and some temporary regs.

The 68000 was 32 bit address and data internally,
8 data regs, 8 address regs, program counter, status code byte.
However it used a 16 bit external data bus,
and only brought out 24 bits of address
(23 word addresses lines + 2 byte select lines).

In the above diagram, I think they mean that
Bank 1 and Bank 2 each have an adder/increment/decrement,
while Bank 3 has a full ALU + special functions.
It appears that to operate on high data values they would route
them from bank 1 to bank 3, and results back to bank 1.
That would appear to occupy both buses.

I just found it strange that they would use
3 banks and put the high data word in bank 1.
It seems more natural to use 4 banks:
1 and 2 for address with their adder/increment/decrement,
3 and 4 for data with a single full ALU,
as this would seem to offer more opportunity to overlap operations.

However co-locating high address and high data would
be denser than splitting them up, and perhaps they
didn't have enough real-estate to do that.

Eric

[Joe keane]

In article <jgeu27$9rg$1...@dont-email.me>,

Stephen Sprunk <ste...@sprunk.org> wrote:
>I'm a fan of load/store architectures and dislike mem-op-mem (and
>mem-op, for that matter) instructions in general, but the latter seem to
>be back in favor these days due to higher code density and therefore
>higher utilization of decode bandwidth.

The main difference i see is that you need a WMEM stage. This goes the
same place as WB when the result is memory. And then you need hazard
checking for nearby instructions.

For a load/store architecture, you can get away with using the same
pipeline slot for load and store, but i suspect you want something like
the above anyway.

>OTOH, I can't help but think decode bandwidth is limited mainly because
>mem-op(-mem) instructions already spit out so many uops that there's
>little benefit to making decoders wider, so it's a vicious cycle.

Anyway whether you write:

add r1,(r0)
add r2,4(r0)

or

load (r0),r3
load 4(r0),r4
add r1,r3
add r2,r4
store r3,(r0)
store r4,4(r0)

it seems to be six-and-a-half in terms of the uops.

Assuming you're blowing up instructions into uops, besides adding some
transistors in the decode, and saving some cache space, the choice of
RtM seems to have little effect on low-level operation.

PDP-11, 6502, 8086

[Stephen Sprunk]

On 07-Feb-12 11:02, EricP wrote:
> MitchAlsup wrote:
>> On Wednesday, February 1, 2012 10:53:35 AM UTC-6, ChrisQ wrote:
>>> What I never worked out was why Motorola split the 16 registers into
>>> 8 x data and 8 x address, rather that a cleaner 16 general purpose
>>> set. Perhaps it was a limitation in the process technology of the
>>> day, but still think that the 68k was a real achievement.
>>
>> A) They ran out of instruction bits
>> B) They could gain register file ports at low cost
>> C) Microcode could use both register files independently and
>> simultaneously
>

> Microprogrammed implementation of a single chip microprocessor (1978)
> Skip Stritter, Nick Tredennick
> http://dl.acm.org/citation.cfm?id=804299
>
> talks mostly about the 68000 microcode (2 level, vertical + horizontal).
> However it does touch a little on the internal organization.

> ...

> Instruction register fields and alu function codes
> are routed directly from the instruction register to
> the register banks and ALU's, saving on microcode.
>
> It doesn't say why they collocated the
> high data and high address regs.

I don't see any explanation at all in that article as to why 8 address
and 8 data registers rather than 16 general purpose registers. It looks
like, had they colocated the data register low words with the address
register low words as they did with the high words, there would be no
functional difference between the registers at all.

This leads me to think the distinction between register types is more a
matter of saving bits on instruction encoding than internal capability.

[Stephen Sprunk]

On 04-Feb-12 11:35, Paul A. Clayton wrote:
> On Feb 4, 1:14 am, Stephen Sprunk <step...@sprunk.org> wrote:
>> I'll admit my eyes glaze over when folks talk about FP execution; it's
>> all I can do, as a layman, to try to keep up with the evolution of
>> integer pipelines. The idea of FP loads being "free" is bizarre to me,
>> but I just now barely understand the idea of FXCH being "free", so my
>> thoughts on that aren't worth much--and I probably won't understand yours.
>
> Skewed integer pipelines are sometimes used to reduce
> the effective load-to-use latency for computations.
> By putting one or more do-nothing (or perform load)
> pipeline stages before the computational execution
> stage, a load can begin one or more cycles earlier
> (relative to a computation--this will not help the
> load-sourcing-to-load path).

This much I understand--though I thought modern CPUs cracked an
instruction into uops that went to different places, one for the load,
one for the op that depended on the load, and (if applicable) one for
the store that depends on the op. Ideally, this allows the load to be
executed while a previous op is tying up the execution unit.

It sounds like you're describing an earlier generation of CPUs that
didn't crack instructions into uops--and the entire pipeline would stall
waiting for a load, so it would make sense to put that in an earlier
pipeline stage. However, this seems to assume that memory is nearly as
fast as the core; at today's speed delta, this would only reduce an
interminable delay to a nearly-interminable one.

>> You still need at least one bit per operand to indicate it's
>> register-indirect rather than register-direct, don't you? And, no
>> matter how you slice it, a mem-op instruction is two uops and a
>> mem-op-mem instruction is three.
>
> If one only had loads for one source, then only one
> extra bit per instruction would be needed.

If the order of the sources matters, and it does for most instructions,
you'd need a second bit to indicate _which_ source was indirect, so you
might as well burn the same two bits allowing each source to be indirect
independently.

The order of sources matters somewhat less for 3-operand instructions,
but it still matters in many cases. And then you need _another_ bit to
indicate if the destination is indirect--though if you're willing to
burn several bits on a third operand, that probably isn't as important.

> If this
> operation was limited to the most common computation
> operations, then it might only cost a fraction of a
> bit. If it was encoded as a load instruction with
> the destination register being the zero register,
> then the next arbitrary instruction could use one
> of its register source name fields for a destination
> register name (if destructive operations are
> typical)--and using the zero register might
> indicate a load-op-store--or as an opcode extension.

Wait, so now you're using an entire extra instruction (however many bits
that costs) to encode an indirect operand? I must not be reading that
right.

>> I haven't figured out yet why that's a win--or even how it's possible.
>> The second instruction obviously has a direct dependency on the first,
>> so how can they execute as a single uop?
>>
>> Fusing them together for scheduling purposes makes sense, since they'd
>> likely end up traveling together anyway, but it seems like they'd need
>> to execute sequentially.
>
> As Brett Davis mentioned, for compare-and-branch, this
> is not the case. In other instances, delayed breaking
> of a complex operation into simple operations can
> reduce tracking overhead. In addition, a load-op has
> an entirely internal dependency chain (the result of
> the load can only wake-up [make ready for scheduling]
> its own operation), which could simply the scheduling.

If they're headed to the same execution unit, that seems fairly
obvious--the fusing is for tracking purposes, not to imply they execute
in parallel. However, I wasn't aware that a fused uop could head to the
load unit, then when the load was dispatched head to another unit for
the real op. If so, that would obviously make sense to reduce
scheduling overhead.

[EricP]

Robert Wessel wrote:
> On Wed, 01 Feb 2012 19:16:53 +0000, ChrisQ <blac...@devnull.com>
> wrote:
>> Fwir, there was a 360 on a couple of 68k devices using different microcode,
>> built by ibm, but you might be disappointed in the performance, even if you
>> could find one now.
>
>
> Shipped by IBM as the "XT/370". And it was a somewhat limited
> implementation - most of the privileged mode was not implemented, and
> it ran a customized version of CMS, and not any of the full OS's.
>
> IIRC, only one of the two 68Ks was re-microcoded, the other was stock.

I just stumbled across these:

The IBM patent for the re-microcoded 68Ks

Methods for partitioning mainframe instruction sets
to implement Microprocessor Based Emulation Thereof
http://www.google.com/patents/US4514803?dq=patent:4514803&ei=sJUxT-ahFITb0QHttbz0Bw

I don't have access to this IBM paper,
but the abstract looks like it is the xt370
and it is referenced by the above patent.

Microprocessor implementation of mainframe processors
by means of architecture partitioning (1982)
http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5390522

Eric

[Paul A. Clayton]

On Feb 7, 3:47 pm, Stephen Sprunk <step...@sprunk.org> wrote:
> On 04-Feb-12 11:35, Paul A. Clayton wrote:

[snip skewed pipeline]

> This much I understand--though I thought modern CPUs cracked an
> instruction into uops that went to different places, one for the load,
> one for the op that depended on the load, and (if applicable) one for
> the store that depends on the op.  Ideally, this allows the load to be
> executed while a previous op is tying up the execution unit.

Skewed pipelines are usually used for in-order processors,
though one could imagine an OoO processor delaying the
placement of an operation into the scheduler when it is
known that it cannot be ready for at least a little while.

> It sounds like you're describing an earlier generation of CPUs that
> didn't crack instructions into uops--and the entire pipeline would stall
> waiting for a load, so it would make sense to put that in an earlier
> pipeline stage.  However, this seems to assume that memory is nearly as
> fast as the core; at today's speed delta, this would only reduce an
> interminable delay to a nearly-interminable one.

The PowerPC processors used in the XBox360 and PS3 have
a skewed pipeline to reduce load-to-use latency without
requiring support for OoO execution. (Adding two
pipeline latches to hide two cycles of load latency is
less expensive [and less generally useful] than supporting
OoO execution, though it also increases the branch
misprediction penalty.)

I think at least one very recent x86 does not crack
load-op instructions at decode but at execution (so
effectively two &micro;ops take one slot in the scheduler).

[snip]

> If the order of the sources matters, and it does for most instructions,
> you'd need a second bit to indicate _which_ source was indirect, so you
> might as well burn the same two bits allowing each source to be indirect
> independently.

Most instructions? Of the commonly used instructions,
is not subtraction the only one for which order matters?
(I.e., add, compare, and, xor, or, and multiply are
commutative [or effectively so for compare].)

[snip]

> Wait, so now you're using an entire extra instruction (however many bits
> that costs) to encode an indirect operand?  I must not be reading that
> right.

Yes. If one is desiring load-op not for code density but
for its semantic content (single-use load), then such an
encoding makes sense. This has an advantage of any
general register operation being supported for single-use
result and being supported for the consumer of such a
result.

[snip]

> If they're headed to the same execution unit, that seems fairly
> obvious--the fusing is for tracking purposes, not to imply they execute
> in parallel.  However, I wasn't aware that a fused uop could head to the
> load unit, then when the load was dispatched head to another unit for
> the real op.  If so, that would obviously make sense to reduce
> scheduling overhead.

I think a relatively recent Intel x86 keeps the load-op
together, presumably using the same scheduler entry and
slightly modifying the contents after the load is
scheduled for execution (or perhaps using a special
wake-up mechanism for such load results since the
scheduler entry is known and unique--no need to
broadcast availability to all the entries in the
scheduler).