10

I am studying basic principles of instruction set architectures and am considering what it would take to not have any instruction decoding at all. I.e., all the control lines of the computer would be found directly in the bits of the instruction word?

As a corollary, then, every instruction execution would take exactly one cycle (perhaps with 2 or 3 phases within a cycle, but not several micro-instruction cycles).

I have seen one home-brewer with a relay computer talk about that idea, and it grew on me. But I wonder if it is even possible or if it is traded off against variable length instructions.

I have found that there are really 3 opposing forces:

  1. Instruction size constant one word vs. variable multiple words.
  2. Full word instruction operands for immediate values and absolute addresses vs. address segmentation scheme.
  3. Data vs. address bus same size, you can read an address in one memory fetch, vs. address bus bigger than data bus where you need to read an address in multiple memory accesses.

And these 3 are mutually opposing. You can't have full word instruction operands in a constant instruction, and certainly not if your data bus is smaller than your address bus. E.g., typical 8 bit computer with 16 bit address bus. So the 6502 had to be (1) variable word instructions, (2) full word immediate values, while (3) absolute address values need multiple memory fetches.

The PDP-8 for contrast had (1) constant word instruction sizes, (2) no way to have full word immediate values or addresses, requiring a segmentation scheme, but (3) data and address bus the same size, or rather, address bus is completely separate.

And to that I add now:

  1. Instruction decoding mapping instruction word to control line states vs. instructions that have their control line immediately in their bits.
  2. Single (or 2-3 phase) vs. variable (multi) step micro-coding.

I know there is the entire RISC vs. CISC debate, but even a RISC processor will have multiple execution cycles for an instruction.

I wonder, was there ever a computer in use that needed no instruction decoding, i.e., where the control lines were immediately the bits of the instruction word?

This would only be possible in wider than 8 bit computers. I think the PDP-8 had a little bit of that, but still not quite. At least a pretty substantial hard wired instruction decoding gate network was there to interpret the bits of the the different instruction groups.

If you ave a 32 bit word size, then it could be possible to fit all the control lines into a single word. But still, I find that some of the control lines might have to be repeated to be used in different phases For example, now that I need a full 24 or 32 bit instruction word just for the control lines, I have to load any operands in additional fetches from the instruction pointer, then to go through indirect addressing I will need another fetch from data memory to be interpreted as an address for yet another fetch.

From your experience with odd stuff developed in the past, do you have examples for some of the less conventional ideas I brought up here?


UPDATE: I received a lot of feedback asking to define my terms better. I will try this here without changing my above text. So let's do a glossary:

Control Line: any logic line that controls a logic device, e.g., register output enable, register load, register asynchronous clear, counter increment, counter reset, counter decrement, memory write-enable, tri-state buffer output-enable, bus-transceiver direction, ALU function selection lines, etc. Usually there are dozens of these control lines all over a CPU and the point of instruction decoding is to set the state of these control lines based on the current instruction and other status lines (e.g., flags for the conditional branches, etc.)

Instruction Decoding: an instruction word is loaded into the instruction register, and that plus various status lines, and finally a micro-instruction counter will be the input of a state-control table. Input is the state lines and output is the control lines.

When I say "no decoding" in this context means that there is no need for such a state-control table, because the instruction word is comprised plainly of the bits of the control lines, but especially the number of microinstruction cycles is 1 or constant, not variable. I.e., every instruction takes the same number of cycles, without wasting any cycles either.

Cycle - a clock cycle, consisting of at least 2 phases, and 2 instantaneous moments. They are: rising edge (instantaneous moment), high state of clock (phase), falling edge (instantaneous moment), low state of clock.

Phase - given that any square wave clock signal has these 2 phases (high, and low) and their rising and falling edge moments, many processors require derivative signals. Sometimes called phi-2 or phi' (prime), etc. These are obviously necessary to subdivide a single clock cycle into multiple sub-steps in which different things happen.

An example for different things happening in the phases and moments of a normal square wave clock: rising edge: registers clock in the current state of the data bus or internal data bus, synchronous counters step at the rising edge. Falling edge: that's where a memory address latch may hold the address lines on a shared address/data bus so that in the low phase of the clock signal the data from memory appears on the bus while the address is held in the latch.

Microinstruction Cycle: when instructions are executed in multiple micro-instruction steps, for example:

  1. IR = *IP // load instruction from instruction pointer
  2. DP = *IP // load absolute address into data pointer
  3. DP = *DP + Y // resolve indirect address adding the Y index
  4. AC = AC + *DP + C // add with carry data from memory to accumulator register

Stuff like that.

What's decoding anyway? There has also been discussions about whether deriving some states from others is decoding or not? And whether register addresses have to have one line per register. I would say no. Register addresses may be a multi-bit binary number, and the register may decode that with a comparator to derive their line signal if the comparator find its address on the control line bus. In a more monolithic design, a 3-to-8 line decoder would also be "allowed" as it is not state dependent but only changes the "representation" of the register address from a binary number to a single line. Likewise, simple gating is "permitted". Just not complex state-control-transition tables.

RISC is the thing: By now I have studied more about RISC processors and it is clear to me now that RISC processors allow doing exactly that. With this approach, each instruction takes one cycle, and instead of short instruction words and micro-coding, we have long instruction words and no micro coding. I can see how it is possible to have 2 cycles per instruction one instruction fetch and one instruction execution.

Loading from absolute address would require two instructions, not two cycles of one instruction.

  1. load absolute address as an immediate value into data pointer
  2. read memory from data pointer.

Two instructions, each requiring 2 cycles: load the instruction, then load the data. Interesting that thinking this way there isn't even absolute addressing modes any more. Only immediate or implicit.

And in that model, indeed there are no "instructions" but only registers output to or loaded from the various busses and enabling certain transformation steps along the data path (inversion, sum, and, etc.)

  • 1
    Any Von-Neumann architecture that has an instruction which loads a register from memory -- or an instruction which stores a register to memory -- will need at least two memory access cycles for those instructions. One cycle to fetch the instruction, and another cycle to perform the load/store. Caching can reduce how often this happens, but can't completely eliminate the two memory access cycles. – DrSheldon Dec 8 '19 at 22:31
  • 1
    Lots of earlier CPUs were microcoded, and quite a few of them (e.g. the PDP-11) allowed modifying the microcode. So there was an "ISA" for the microcode, which drove all control lines directly, which was then used to program the "real" ISA. Does that count? – dirkt Dec 9 '19 at 4:50
  • 1
    If the CPU has more than 1 register, even selecting between them would be decoding. So there probably were no CPUs nor microcode instructions sets that completely avoid decoding. – lvd Dec 9 '19 at 9:03
  • 1
    Suppose you had N registers; then N distinct 'select' bits in the instruction word would surely count as not decoding. Not that I am aware if that was ever done. – another-dave Dec 9 '19 at 12:35
  • 2
    I'm sure it probably has been done, but I would note that this would be very unlikely for a designer to have done historically. For most applications until recently, the limited size of computer memory was the main design limitation for almost all applications. To systematically try to save a handful of transistors in the processor by avoiding denser instruction encoding, at the cost of several bits in every instruction word, would have been downright unthinkable. – RETRAC Dec 9 '19 at 17:11
11

Horizontal Microcode works exactly as you describe - one bit for each possible internal control line (Vertical Microcode saves instruction bits by encoding sets of N mutually-exclusive control lines with log(N) bits, with appropriate demultiplexers in place). In theory one could use this as the primary instruction level, but of course it would be very expensive. Whether anyone actually did this I cannot say. But it wouldn't surprise me.

|improve this answer|||||
  • Yes, that's where I was getting. I found that the number of control lines is one issue, but then also any multiplexing requires multiple steps. For example, if address bus and data bus are shared, then all memory accesses requires 2 steps: first latch in the address then read the data. Even if you have separate address and data bus, you still have a sequence of fetches for things like indirect addressing. But then OK, RISC does not have indirect addressing... – Gunther Schadow Dec 9 '19 at 21:17
  • I'm linking an interesting article. danluu.com/risc-definition – Gunther Schadow Dec 9 '19 at 21:33
  • 1
    Steve Wozniak's floppy disk controller design worked like that, using a 256x8 PROM to convert four control inputs and four state inputs to four control outputs and four state outputs. Three of the outputs were wired to the mode-control and LSB inputs of a shift register, while the MSB output of the shifter was connected as one of the control inputs to the PROM. – supercat Dec 11 '19 at 16:38
10

(Preface: The question is a bit misleading, as many of the conditions implied are not well defined. See below)


First candidate: Transport Triggered Architectures

Transport Triggered Architectures are not only a special case of single instruction architectures, but should this the 'no decoding' requirement quite nicely. Its only instruction is to transfer a data item between source and destination ports in a single cycle. Instruction is made up solely from addresses of both ports. Functionality is realized according to the port used. In such a system, an accumulator could be addressed by three different ports for Load, Load Inverted and Add. Adding two numbers (R1=R1+R2) would look like

(transfer) Reg1 (to) Accuport
(transfer) Reg2 (to) Addport
(transfer) Accuread (to) Reg1

Each of these instructions would execute in a single cycle.

RISC

RISC instructions sets can be made to have all instructions operating in a single cycle. Heck, with a few exceptions, which easy could be removed, even an AVR as used in many Arduinos might qualify :))

VLIW

The basic idea for single bits or bit groups directly controlling function units is part of several VLIW architectures. The idea is present since very early computer architectures, like the 1955 Zuse Z22, where separate bits encode separate functions, so an instruction can be done in a single drum revolution - or even faster. Z22 instructions were always single machine words. See this answer for some details.


The question is a bit misleading, as many terms are used in a loose fashion without exact context, like

what it would take to not have any instruction decoding at all.

What does 'no decoding' mean in this context? Should each bit just trigger a single (or a group) of units, or can such a signal be made of a group of bits, decoded by a simple static n:m decoder?

I.e., all the control lines of the computer would be found directly in the bits of the instruction word?

What does directly mean? Must it be a 1:1 relation, or can 4 bits control 10 lines?

As a corollary, then, every instruction execution would take exactly one cycle

What is a cycle? a single clock, or can it be a fixed number of clocks?

Or is this about memory cycles?

(perhaps with 2 or 3 phases within a cycle,

What's a phase? Would any classic 4 phase system fit as well?

but not several micro-instruction cycles).

So is this question about microcoded vs. random logic?

I have found that there are really 3 opposing forces:

Instruction size constant one word vs. variable multiple words.

If multiple 'phases' are allowed, then multiple words could be read. One per phase.

Full word instruction operands for immediate values and absolute addresses vs. address segmentation scheme.

Not really clear how this contradicts anything. Addresses could be also be built from multiple instructions.

For example assume a 16-bit CPU. Instructions are 16 bits. Loading a (16 bit) register with a 16-bit value, like an address, can be done by using two 8 bit loads, one moving its payload into the upper half of the target register, one into the lower. Or have automatic sign extension on 8-bit load. Or both. That way all values from -128..+127 will need only one instruction to load.

All of this is used by many RISC CPUs in many variations.

Data vs. address bus same size, you can read an address in one memory fetch, vs. address bus bigger than data bus where you need to read an address in multiple memory accesses.

There is no inherent need to have address size different to data size. Only if made an arbitrary requirement.

And these 3 are mutually opposing. You can't have full word instruction operands in a constant instruction,

No, but there is no need to do so.

and certainly not if your data bus is smaller than your address bus.

Again, no need to do so.

So the 6402

6402? I assume this is meant to read 6502.

had to be (1) variable word instructions, (2) full word immediate values, while (3) absolute address values need multiple memory fetches.

Within the design they have chosen, yes, but these were design decisions, not anything mandated by inherent contrary issues.

The 8008 in contrast did not have any 16 bit loads, despite the use of HL as 16 bit memory address. Each constant address had to be moved into HL with two instructions loading either part.

The PDP-8 for contrast had [...]

Again, these were design decisions made by DEC, not anything inherent to CPU design.

Instruction decoding mapping instruction word to control line states vs. instructions that have their control line immediately in their bits.

This sentence doesn't make any sense.

Single (or 2-3 phase) vs. variable (multi) step micro-coding.

See above.

but even a RISC processor will have multiple execution cycles for an instruction.

Not necessarily. It is quite possible to create RISC instruction sets that are made up from only single word instructions, all executing within a 'single cycle'. The question isn't whether it's possible, but whether it makes sense.

I wonder, was there ever a computer in use that needed no instruction decoding, i.e., where the control lines were immediately the bits of the instruction word?

Again, what kind of decoding is this about?

This would only be possible in wider than 8 bit computers.

Why? The same way a 16-bit address can be made up from two 8-bit loads, it can be made up from 16 one-bit load instructions.

I think the PDP-8 had a little bit of that, but still not quite. At least a pretty substantial hard wired instruction decoding gate network was there to interpret the bits of the the different instruction groups.

A n:m decoder is neither a big issue nor much of a performance issue. Just think about ALU operations - there are many possible, but only a few make sense at the same time (if the hardware would be able to do them at simultaneous at all). So why create an encoding that wastes codespace? Combining mutually exclusive functions into a bit group is a quite sensible way to save code size.

From your experience with odd stuff developed in the past, do you have examples for some of the less conventional ideas I brought up here?

Don't get me wrong, but I have a hard time to see anything in your write-up that hasn't been solved many times before. Most of the points mentioned (as I understand them) have been thought about and used quite often.

In total this feels a bit as if there is a confusion between what a cycle is, a phase and an instruction. Further it's about decoding in decoding bit fields vs. decoding as a pipeline stage. Pipelines may be another part of the 'Gordian knot' you'll try to cut - and not at least the basic duality of instruction cycles vs. instruction throughput.


It may be helpful to specify exactly what your goals are ... there is a good chance that already preparing a new question with strict definitions may clear up the difference between requirements added at will vs. technological implications.

|improve this answer|||||
  • 2
    Shades of the Amiga's copper. – Brian H Dec 8 '19 at 23:50
  • @BrianH Jup, HAM is as well a great example here. After all, timing was absolute fixed by memory bandwith. – Raffzahn Dec 8 '19 at 23:52
  • I can see that one can gripe about every half sentence I wrote, reminds me of email lists. But it's a bit hard to reply to this, as this here is no discussion thread. || You cannot have single word instructions will full word immediates or absolute addresses when your address bus width is not smaller than your data path width. You will require the operand words to come in additional fetches from IP. Of course that's a design decision, but you cannot have both. PDP-8 decided to do single size instructions, most others have multi word instructions. Etc. – Gunther Schadow Dec 9 '19 at 21:07
  • @GuntherSchadow Well, would you prefer a lengthy text without references? Also, if it's already set, that address size has to be equal or larger than data size, as well as that full word immediates (data address) within an instruction are mandatory, then there can't be any examples as it's simply impossible. Then, what's the question? – Raffzahn Dec 9 '19 at 21:56
  • @Raffzahn, I think you are seeing this all too combative. This is supposed to be fun. "if it's already set, that address size has to be equal or larger than data size, as well as that full word immediates (data address) within an instruction are mandatory, then there can't be any examples as it's simply impossible." -- well, like I said, these are principle constraints, but between them obviously a lot is possible. It's coming out here. By now I learned that if you avoid indirect addressing, at least you can pull the instruction opcode bits and one operand only, no decoding of opcode needed. – Gunther Schadow Dec 10 '19 at 4:51
6

The Pilot ACE, commercialized as the English Electric DEUCE, had an instruction set which looks pretty peculiar to modern sensibilities.

It had no explicit 'opcode' field, instead just source and destination addresses (as well as 'next instruction' address and timing-related fields).

The address fields surely required some decoding, but then again it's difficult to believe any 32-register arrangement can afford 32 separate bits to select a register.

But if this question is really about determining which operation was to be executed then I think the no-opcode format of DEUCE fits the bill.

|improve this answer|||||
  • 1
    This appears to be similar to what @Raffzahn started out describing. No instruction, only source and destination. And I suppose if only one operand is ever memory or immediate value, then the source or destination can be represented by the control line states itself. Such as, register select, load-enable, some bus bufferes, data routers, etc. – Gunther Schadow Dec 10 '19 at 4:55
1

Pretty much any One Instruction Computer architecture could be described this way. In such machines, there is no opcode field, and the operation performed each time is sufficiently flexible to have several different effects depending on the operands given.

If the operation implemented is Decrement And Conditionally Branch (which has been shown to be Turing complete), the operands would be the memory location to be decremented, and the two addresses to branch to in the zero and non-zero cases. It should be easy to see how this can be implemented with no decoding, just a basic control sequencer.

A more flexible design might specify the control inputs to an ALU, the addresses of two input operands to that ALU, two addresses in which to place the result depending on a selectable status bit, and a status field to update based on the ALU result. If the program counter is itself made addressable (as many early CPUs did, up to and including the ARM), you then effectively have a no-decoding CPU that can do arithmetic and conditional branches fairly efficiently, albeit with a rather large instruction word.

|improve this answer|||||
1

The EDUC-8 derived its control lines directly from an instruction and did not use any form of microcode ROM. It was a serial processor so a fixed number of timing cycles were required for each instruction. The only extension to the timing cycle were for Examine and Deposit related to operation of the front panel's memory examination or data entry from switches. I would argue these two are manual operations unrelated to program execution. The circuits and construction details are available at: https://ia601209.us.archive.org/26/items/Educ-8/educ8.pdf

|improve this answer|||||
  • Wow! That's a PDP-8 rebuild. Nice find! – Gunther Schadow Dec 16 '19 at 23:52
  • The article talks about microinstructions though, so I will assume it just uses discrete logic instead of a ROM? Yes, this is talked though in the middle column of page 40. So it's not quite what I was looking for, but nevertheless an awesome find! – Gunther Schadow Dec 17 '19 at 0:00
  • The circuit diagram for the control and timing logic is in the November 1974 issue. On Page 49 it shows the instruction is shifted into an 8-bit serial to parallel converter which becomes the instruction register. The instruction set opcodes are shown on Page 65 of the February 1975 issue. The opcodes of the Memory Reference Instructions are 'decoded' on page 49 as Q0, Q1, ... of the Instruction register. – PDP11 Dec 17 '19 at 2:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.