Name: Computation structures
ISBN: 9780070681477

What Hacker News says

nxobjectJun 2026

> So I guess my question is: what do you see as the reasons why you'd pick a particular school of micro control flow as a microcode engine implementer?

For a comprehensive answer, a good vintage introductory digital design textbook is Ward and Halstead's 1989 Computation Structures, from the "peak CISC" era! [1]

There, the second (vertical) type is often used for highly complex instructions/fancy addressing modes, that you might want to implement with some sort of procedure abstraction, loops, working memory, etc. A "luxury" vertical microcode engine would have facilities like "microprocedure calls", a micro-stack and workspace RAM, a micro-ALU, dispatch table micro-instructions. The authors use the suggestive term "interpretive microcode".

String instructions come to mind as a complex example; non-register machine architectures (stack machines); tagged data architectures that have instruction-level polymorphism (e.g. Lisp machines).

The culminating project of Ward and Halstead is an elaborate two-level microcode system (vertical on horizontal/second on first). I think the first Motorola 68k had this architecture -- here is the patent. [2]

It's genuinely a fun read. The "write an micro-interpreter for your CISC ISA" approach is hopelessly out of date now that we need pervasive microarchitectural parallelism, and have HDLs.

[1] https://www.amazon.com/Computation-Structures-Optical-Electr...

[2] https://patents.google.com/patent/EP0011412A1/en?inventor=Ha...

thread

monocasaJun 2026

So, I've read Computation Structures. And agreed, an absolutely fantastic text. [0]

However, my question is kind of orthogonal to vertical versus horizontal microcode.

As a counter example I'd point to the microcode format of the system 370/145, which while pretty clearly being something that would be described as vertical microcode also doesn't have implicit control flow [1]. It's a little on the wide side for vertical microcode at 32 bits, I'll grant you, but it has an op field(s) with about a dozen variants that then is used to further decode the other fields, at an overall decode complexity comparable to a RISC arch. Horizontal microcode looks more like 'these specific bits just always plug into this mux, and are simply set to some default if unused in this specific operation, reducing decode to essentially wires'. That being said, it also doesn't have an incrementer on the program counter, with the last byte of instructions encoding a (conditional) branch to the next instruction[2].

For another example, I'd point to modern microcode formats in Intel and AMD cores. They pretty universally have a vertical microcode instruction format (though grouped into triads or quads of instructions typically) then paired with explicit, dedicated microprogram control flow field for the group. The uops there are pretty wide at 48-64 bits typical, but they sort of need to be to fit immediates that are common for 64 bit archs, and also fit into that RISC like level of decode complexity you see in vertical microcode. [3]

[0] - As an aside, if you like Computation Structures, I'd recommend The Anatomy of a High-Performance Microprocessor: A Systems Perspective by Shriver and Smith as well. The mad lads stuck a surprising amount of the RTL for the AMD K6 in that book, albeit translated into some custom academic langauge. That mid 90s era design of a multi instruction per clock CISC decoder dumping a speculative instruction stream into an OoO RISC like backend is arguably just as much peak CISC as the early 80s given that it won against the UNIX RISCs by the early 2000s and survives to this day with remarkably few tweaks relatively speaking. CISC seems to be kind of like the Roman empire; any time it starts losing the war, it just unashamedly starts integrating the concepts of its competitor it's losing to. Which is great in this case. That's called good engineering.

[1] - Pages A2-A5 for an overview, chapter 4 for a more in depth discussion. https://www.bitsavers.org/pdf/ibm/370/fe/3145/SY24-3581-1_31...

[2] - Though it does have an explicit far jump/call instruction for control flow outside that window addressable by that byte, and a couple other bits sometimes depending on the instruction format.

[3] - https://www.usenix.org/system/files/conference/usenixsecurit... and https://github.com/chip-red-pill/uCodeDisasm

thread

p1eskMay 2026

Here’s a great book explaining microprogramming from ground up: https://www.amazon.com/Computation-Structures-Optical-Electr...

Easy to find a free pdf

thread

nxobjectSep 2024

Just to add a few more resources – ye olde digital design books are really fun to learn how (sequenced) microcoding was seen as one of the highest-level tools in the toolkit of digital design in general up to the early/mid 80s:

– "Computation Structures", an old MIT course book, which uses a pedagogical processor similar to a microcoded PDP-11 or a 68k, to illustrate microcoding as the highest level of digital design – the processor they implement used a two-level microcoded processor to implement two types of processor on the same microcode interpreter engine, complete with built-in monitor/debugger.

– "The Art of Digital Design", an older course text, which culminates in the implementation of a PDP-8 clone;

Finally, if it helps look up more literature, another name for microprogramming in the literature is "interpretive microcoding" – one that makes the distinction between ye olde microprogramming and modern "microoperations" pretty clear.

It also clarifies why two-level micro-coding might exist, especially in the microarchitecture of the original 68k: you write in high-level microcode an engine interpreting a target ISA; this high-level microcode interpreter is then interpreted by low-level microcode that directly activates control lines. Two levels of interpretation seems baroque, but somehow it was fast enough for 68k workstations.

thread

imakwanaOct 2020

For learning below courses and books are very helpful:

1) Online courses: Computation Structures: Parts 1, 2 and 3 - all course materials available on EdX MIT as well as MIT OCW

2) Books: a) Computer Systems: A Programmers Perspective and b) Computer Organization: Hardware/Software Interface

3) Practice Verilog HDL programming for small/medium complexity building blocks such as FIFOs, RAMs, bridges, etc using free simulators like Xilinx ISIM. Courses such as Coursera's Hardware Description Languages for FPGA Design are a good starting point. Lookup most starred repos on Github in verilog and systemverilog languages.

thread

imakwanaSep 2020

Highly recommend these references:

1) Computer Organization and Design: The Hardware/Software Interface by David Patterson and John Hennessy

2) Computation Structures course and associated course material from MIT OCW, checkout links [1], [2] and [3]

[1] https://computationstructures.org/

[2] OCW MIT 6.004 : https://ocw.mit.edu/courses/electrical-engineering-and-compu...

[3] EdX MIT 6.004 - 3 part course on computation structures: https://www.edx.org/course/computation-structures-part-1-dig...

thread