[TUHS] Encoding an ISA: Random Logic vs. Control Stores

[TUHS] Encoding an ISA: Random Logic vs. Control Stores

[pbirkel]

I believe that the PDP-11 ISA was defined at a time when DEC was still using
random logic rather than a control store (which came pretty soon
thereafter).  Given a random logic design it's efficient to organize the ISA
encoding to maximize its regularity.  Probably also of some benefit to
compilers in a memory-constrained environment?

I'm not sure at what point in time we can say "lots of processors" had moved
to a control store based implementation.  Certainly the IBM System/360 was
there in the mid-60's.  HP was there by the late 60's.

-----Original Message-----
From: TUHS <tuhs-bounces@minnie.tuhs.org> On Behalf Of Larry McVoy
Sent: Monday, November 29, 2021 10:18 PM
To: Clem Cole <clemc@ccc.com>
Cc: TUHS main list <tuhs@minnie.tuhs.org>; Eugene Miya <eugene@soe.ucsc.edu>
Subject: Re: [TUHS] A New History of Modern Computing - my thoughts

On Sun, Nov 28, 2021 at 05:12:44PM -0800, Larry McVoy wrote:
> I remember Ken Witte (my TA for the PDP-11 class) trying to get me to 
> see how easy it was to read the octal.  If I remember correctly (and I 
> probably don't, this was ~40 years ago), the instructions were divided 
> into fields, so instruction, operand, operand and it was all regular, 
> so you could see that this was some form of an add or whatever, it got 
> the values from these registers and put it in that register.

I've looked it up and it is pretty much as Ken described.  The weird thing
is that there is no need to do it like the PDP-11 did it, you could use
random numbers for each instruction and lots of processors did pretty much
that.  The PDP-11 didn't, it was very uniform to the point that Ken's
ability to read octal made perfect sense.  I was never that good but a
little google and reading and I can see how he got there.

...

--lm

Re: [TUHS] Encoding an ISA: Random Logic vs. Control Stores

[Ron Natalie]

Indeed, the early PDPs (10/15/20) had no microprogramming at all.   Even 
the early microprogrammed ones used "random logic" to implement that.    
It would take ten years before large scale integration took over.    The 
PDP-11/44 in 1979 was the last of the discrete logic CPUs.


------ Original Message ------
From: pbirkel@gmail.com
To: "'TUHS main list'" <tuhs@minnie.tuhs.org>
Cc: "'Eugene Miya'" <eugene@soe.ucsc.edu>
Sent: 11/30/2021 3:07:15 AM
Subject: [TUHS] Encoding an ISA: Random Logic vs. Control Stores

>I believe that the PDP-11 ISA was defined at a time when DEC was still using
>random logic rather than a control stor

Re: [TUHS] Encoding an ISA: Random Logic vs. Control Stores

[arnold]

Can someone please explain why it's called "random" logic? Discrete
logic I understand (more or less), but I've not heard the term "random"
used in this context before now.

Thanks,

Arnold

"Ron Natalie" <ron@ronnatalie.com> wrote:

> Indeed, the early PDPs (10/15/20) had no microprogramming at all.   Even 
> the early microprogrammed ones used "random logic" to implement that.    
> It would take ten years before large scale integration took over.    The 
> PDP-11/44 in 1979 was the last of the discrete logic CPUs.
>
>
> ------ Original Message ------
> From: pbirkel@gmail.com
> To: "'TUHS main list'" <tuhs@minnie.tuhs.org>
> Cc: "'Eugene Miya'" <eugene@soe.ucsc.edu>
> Sent: 11/30/2021 3:07:15 AM
> Subject: [TUHS] Encoding an ISA: Random Logic vs. Control Stores
>
> >I believe that the PDP-11 ISA was defined at a time when DEC was still using
> >random logic rather than a control stor
>

Re: [TUHS] Encoding an ISA: Random Logic vs. Control Stores

[Ralph Corderoy]

Hi Arnold,

> Can someone please explain why it's called "random" logic? Discrete
> logic I understand (more or less), but I've not heard the term
> "random" used in this context before now.

I'm more used to ‘hard-wired’ logic versus ‘micro-programmed’ for
microcode but random logic in a known term in this context:

    https://en.wikipedia.org/wiki/Random_logic

    Random logic is a semiconductor circuit design technique that
    translates high-level logic descriptions directly into hardware
    features such as AND and OR gates.  The name derives from the fact
    that few easily discernible patterns are evident in the arrangement
    of features on the chip and in the interconnects between them.

-- 
Cheers, Ralph.

Re: [TUHS] Encoding an ISA: Random Logic vs. Control Stores

[Jon Steinhart]

arnold@skeeve.com writes:
> Can someone please explain why it's called "random" logic? Discrete
> logic I understand (more or less), but I've not heard the term "random"
> used in this context before now.

Well, as a recovered random logic designer, I think that the name comes
from there being no particular structure to the logic.  Many parts of
logic design are very regular, think memory.  But that regularity doesn't
exist when, for example, decoding irregular instructions.

Re: [TUHS] Encoding an ISA: Random Logic vs. Control Stores

[Humm]

Quoth Jon Steinhart:
>arnold@skeeve.com writes:
>> Can someone please explain why it's called "random" logic? Discrete
>> logic I understand (more or less), but I've not heard the term "random"
>> used in this context before now.
>
>Well, as a recovered random logic designer, I think that the name comes
>from there being no particular structure to the logic.  Many parts of
>logic design are very regular, think memory.  But that regularity doesn't
>exist when, for example, decoding irregular instructions.

Now that’s a “random” definition.

-- 
Humm

Re: [TUHS] Encoding an ISA: Random Logic vs. Control Stores

[Jon Steinhart]

Humm writes:
> Quoth Jon Steinhart:
> >arnold@skeeve.com writes:
> >> Can someone please explain why it's called "random" logic? Discrete
> >> logic I understand (more or less), but I've not heard the term "random"
> >> used in this context before now.
> >
> >Well, as a recovered random logic designer, I think that the name comes
> >from there being no particular structure to the logic.  Many parts of
> >logic design are very regular, think memory.  But that regularity doesn't
> >exist when, for example, decoding irregular instructions.
>
> Now that’s a “random” definition.
>
> -- 
> Humm

OK, I'll try again.  For anybody familiar with Portland, Oregon, it's the
difference between driving in Northwest where there's a rectangular grid
numbered in one direction and alphabetical in the other, and approaching
the Ross Island Bridge from the west side which appears to be designed by
someone following a goat while tripping their brains out.  One can address
Northwest Portland quite easily unlike getting onto the Ross Island Bridge.

Re: [TUHS] Encoding an ISA: Random Logic vs. Control Stores

[Henry Bent]

[-- Attachment #1: Type: text/plain, Size: 1382 bytes --]

On Tue, 30 Nov 2021 at 18:10, Jon Steinhart <jon@fourwinds.com> wrote:

> Humm writes:
> > Quoth Jon Steinhart:
> > >arnold@skeeve.com writes:
> > >> Can someone please explain why it's called "random" logic? Discrete
> > >> logic I understand (more or less), but I've not heard the term
> "random"
> > >> used in this context before now.
> > >
> > >Well, as a recovered random logic designer, I think that the name comes
> > >from there being no particular structure to the logic.  Many parts of
> > >logic design are very regular, think memory.  But that regularity
> doesn't
> > >exist when, for example, decoding irregular instructions.
> >
> > Now that’s a “random” definition.
> >
> > --
> > Humm
>
> OK, I'll try again.  For anybody familiar with Portland, Oregon, it's the
> difference between driving in Northwest where there's a rectangular grid
> numbered in one direction and alphabetical in the other, and approaching
> the Ross Island Bridge from the west side which appears to be designed by
> someone following a goat while tripping their brains out.  One can address
> Northwest Portland quite easily unlike getting onto the Ross Island Bridge.
>

So - and as I say this as someone who has no direct experience with this
level of logic - everything is directly addressable but the difference is
in how you get there?

-Henry

[-- Attachment #2: Type: text/html, Size: 1903 bytes --]

Re: [TUHS] Encoding an ISA: Random Logic vs. Control Stores

[Jon Steinhart]

Henry Bent writes:
> On Tue, 30 Nov 2021 at 18:10, Jon Steinhart <jon@fourwinds.com> wrote:
>
> > Humm writes:
> > > Quoth Jon Steinhart:
> > > >arnold@skeeve.com writes:
> > > >> Can someone please explain why it's called "random" logic? Discrete
> > > >> logic I understand (more or less), but I've not heard the term
> > "random"
> > > >> used in this context before now.
> > > >
> > > >Well, as a recovered random logic designer, I think that the name comes
> > > >from there being no particular structure to the logic.  Many parts of
> > > >logic design are very regular, think memory.  But that regularity doesn't
> > > >exist when, for example, decoding irregular instructions.
> > >
> > > Now that's a "random" definition.
> > >
> > > --
> > > Humm
> >
> > OK, I'll try again.  For anybody familiar with Portland, Oregon, it's the
> > difference between driving in Northwest where there's a rectangular grid
> > numbered in one direction and alphabetical in the other, and approaching
> > the Ross Island Bridge from the west side which appears to be designed by
> > someone following a goat while tripping their brains out.  One can address
> > Northwest Portland quite easily unlike getting onto the Ross Island Bridge.
> >
>
> So - and as I say this as someone who has no direct experience with this
> level of logic - everything is directly addressable but the difference is
> in how you get there?

Sorry my analogy didn't work.  Look at a photomicrograph of a chip; at least
to me it's pretty obvious where the random logic is located.

Here's another try.  In a microcoded machine, the same hardware is used for
every microinstruction.  In random logic, custom designed circuitry is used
for each special case.

Re: [TUHS] Encoding an ISA: Random Logic vs. Control Stores

[pbirkel]

Said Jon:

" In a microcoded machine, the same hardware is used for every
microinstruction.  In random logic, custom designed circuitry is used for
each special case."

Best way to get a handle on the distinction is to read up on the originator
of the concept, Maurice Wilkes:

https://en.wikipedia.org/wiki/Maurice_Wilkes
https://amturing.acm.org/info/wilkes_1001395.cfm

The original paper:

http://www.cs.princeton.edu/courses/archive/fall09/cos375/BestWay.pdf

"The Best Way to Design an Automatic Calculating Machine" (1951)

-----

Re: [TUHS] Encoding an ISA: Random Logic vs. Control Stores

[ron minnich]

I used to design hardware in those days, and had a soldering iron and
a PDP 11/45 board on the same bench, unsuccessfully, so here goes.

It's interesting to consider the PDP-8 and -11, and the progression of
hardware. The -11 was way different than the -8: I still have some -8
boards, on which you can see the transistors and such needed to
implement state and gates. The -11s had TTL. At the time, a package
with four logic elements was a big deal.

so the -8 had "a gate per 2x3 inch card" or so. The -11 had about 8x11
boards with, by my count on the 11/20, around 100+ gates (I've got
some cards still ...). Again, multiple logic elements in a 14-dip were
an amazing step forward.

If you look at those boards, you see lots of 14-DIP with quad NAND,
AND, NOR, 2 flops per package, and that's about it. In this world,
where a gate costs about $1, you think about everything. Look
carefully, and you can see the traces were laid out by hand; some of
us remember the rooms full of light panels and the red tape you used
to lay out the board.

Not that I designed CPUs, but having used this gear, lived in the
culture, I'd argue that bit layouts of instructions did in fact
matter. The TTL MUX parts were yet to appear. The board layout,
package design, cost of a wire, instruction format: all to some extent
intertwined. You could look at the hardware design and draw a
connection right back to instruction coding. It was all of a piece.
The luxury of a ROM or MUX that picked instructions apart for you? Not
at that time.

As for random logic ... the things we did back then. The discipline of
design for test, which we take for granted today as JTAG, was some
time in the future. And some of you no doubt remember the unibus ...
and the practice of "margining the bus." I.e., slow it the hell down
so maybe it would not get data errors. Or maybe, even, "let's put a
cap here to add some delay constant" -- people really did that stuff.
It's amazing anything worked. But when a gate costs a buck, you do
what you do.

On Tue, Nov 30, 2021 at 10:30 PM <pbirkel@gmail.com> wrote:
>
> Said Jon:
>
> " In a microcoded machine, the same hardware is used for every
> microinstruction.  In random logic, custom designed circuitry is used for
> each special case."
>
> Best way to get a handle on the distinction is to read up on the originator
> of the concept, Maurice Wilkes:
>
> https://en.wikipedia.org/wiki/Maurice_Wilkes
> https://amturing.acm.org/info/wilkes_1001395.cfm
>
> The original paper:
>
> http://www.cs.princeton.edu/courses/archive/fall09/cos375/BestWay.pdf
>
> "The Best Way to Design an Automatic Calculating Machine" (1951)
>
> -----
>

Re: [TUHS] Encoding an ISA: Random Logic vs. Control Stores

[Ron Natalie]

There seems to be confusion here about microcoding vs. discrete 
logic/LSI.    All but the initial 11/20 (and its variants) are 
microcoded.   That is there is a programmed sequence of operations in 
the execution of the individual instructions.   The less popular 11/60 
even featrued a writable control store.

All of the early PDP-11s were built out of discrete logic.   Relatively 
simplistic combinations of various logic chips, gates, flip flops, etc.. 
   A lot of these were encapsulated into the DEC "Flip Chips" small 
circuit boards to do common sets of operations.   While this is by 
modern standards, crude, it doesn't preclude microcoding and other 
advanced tasks.    I worked on a supercomputer built that way (Denelcor 
HEP built largely out of Motorola 10800-series ECL chips).

As I previously stated, the 11/44 was the last of the discrete logic 
PDP's in 1979.    The later systems were all large scale integrated 
circuit based.  First starting with the LSI-11/03 on the Q bus, quickly 
followed by the 11/23 and the Unibus 11/24.

Re: [TUHS] Encoding an ISA

[Warren Toomey]

All, I think it's time to move the ISA and random logic threads over to COFF :-)

Thanks!
	Warren