Why did finite-state controller with datapath win?

I just finished watching the 1986 SICP lectures, and the concepts are rolling around in my head.

My question: why is "finite-state controller with datapath" the implementation of computer programs we use?

I can think of a few of types of answers, which have different emphases:

• We don't use it: there are various implementations of computation in use; this is just one of the more important ones.

• We don't use it: it is a pedagogical abstraction which isn't a total lie, but when you get into microarchitecture, the trade-offs at multiple levels of design yield implementations which defy simple categorization.

• This model has arisen over time through a selection process, with selection pressures from economics and managability of design.

Types 1 and 3 are enticing to me, because these would endeavor to explain the comparative advantages of FSCwD compared to other models/implementations of computing. (And explain what those other models are along the way.)

Note I'm not asking about models of computation as such, as those are about how to model computation conceptually, not how to model the implementation of computation on hardware.

Lastly let me say I am aware that a thorough answer to this question would constitute a whole book or more; therefore I am looking for "leads" in my search (search terms, particular books or articles). I've been searching things like

• Models of computation

• FSM with datapath

• Processor design

etc, but none of them have so far have compared various models of implementation.

This is a very good question, which I don't think I can completely answer.
What I can try to do is

• give some history of how the idea emerged (although I haven't been able to discover as much of the story as I'd like).

• provide an explanation of why FSM+datapath is a valuable abstraction technique. (Note: an explanation, not the explanation)

I don't think I'll be able to satisfactorily answer what other alternative design abstractions might have been possible, or why FSM+datapath might be preferable (or not) to those other design abstractions.

Historically, I've found at least 3 inter-related lines of thought that seem to have come together in

Christoper R Clare; Designing Logic Systems Using State Machines, McGraw-Hill, 1973.

This book is considered the origin of the idea of Algorithmic State Machines (ASMs) that are now taught in most intro digital design books, and was based on ideas that Tom Osborne developed while desigining and implementing his prototype of what became the HP 9100A.

I think there were several ideas "floating around" in the 1950's and 60's that influenced Osborne's ASMs.

• The idea of using microprogramming as in M.V. Wilkes and J.B. Stringer; Microprogramming and the design of the control circuits in an electronic digital computer, Proc. Cambridge Phil. Soc., pt.2, vol. 49, pp. 230-238, April, 1953. (You can find an online copy as Chapter 28 of Bell and Newell).

• The idea of Register Transfers. These were introduced (as far as I know) by Irving S Reed in a series of technical reports at the beginning of the 1960s, and then popularized in the book T. C. Bartee, I. L. Lebow, I. S. Reed, Theory and Design of Digital Systems, McGraw-Hill, 1962. An early paper on synthesizing circuits from Register Transfer specifications was H. Schorr, "Computer-Aided Digital System Design and Analysis Using a Register Transfer Language," in IEEE Transactions on Electronic Computers, EC-13(6):730-737, Dec. 1964, doi: 10.1109/PGEC.1964.263907. An overview paper that covers a lot of the variants is M. R. Barbacci, "A Comparison of Register Transfer Languages for Describing Computers and Digital Systems," in IEEE Transactions on Computers, C-24(2):137-150, Feb. 1975, doi: 10.1109/T-C.1975.224181.

• The idea of Control Flow Graphs from the compiler community. This subfield really started blossoming in about 1970 with the publication of Frances E. Allen's "Control flow analysis", in Proceedings of a symposium on Compiler optimization, July 1970, Pages 1-19.

Microprogramming may have been an important influence because it showed both that (a) you could decompose relatively complicated operations into multiple steps, and (b) that the resulting state machine transition functions could be relatively easily implemented (using something like a ROM instead of ad-hoc combinational logic networks).

Register Transfers are important for describing datapaths. Note that when you decompose a problem into a finite-state controller + datapath, most of the state is actually in the datapath. The Register Transfer description of the datapath operation abstracts the specification in two key ways. First it groups the datapath state bits into chunks that are operated on together (for example an 8-bit register), and discusses the state transitions on those chunks in abstract terms. Consider the register transfer:

R_a <- R_b + R_c

If registers R_a, R_b, and R_c each have 8 bits then you are describing a set of state transitions on a state machine with 24 bits, so 2^24 possible start states, and the transitions for each of those start states to its next state.

Second, Register Transfers break the state up into a bunch of independent chunks. That is, the transitions on R_a are independent from the transitions on R_b are independent from the transitions on R_c. For the parallel transfer R_a <- R_b+R_c; R_d <- R_e-R_f, we know that only the bits of R_a and R_d are changing. R_b, R_c, R_e, and R_f are not changing. These two advantages (that each register is multiple bits and that the registers are independent of one another) gives us leverage to describe state machines with enormous state spaces with just a few lines of "code".

Finally, the control flow graph (or the similar Algorithmic State Machine) allows you to talk about the sequence of states, and conditional state transitions of an algorithm independently of the complicated state transitions that are happening in the data path. That is: we can reason abstractly about sequences of operations without worrying about the concrete values stored in the datapath.

StackExchange Computer Science Q#141994, answer score: 6