Why did finite-state controller with datapath win?

Question

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:

1. We don't use it: there are various implementations of computation in use; this is just one of the more important ones.
2. 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.
3. 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.

Answer 1

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

1. 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).
2. 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.

1. 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).
2. 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.
3. 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.

Answer 2

FSM+Datapath, in this context, is a design technique of logic design. Any real-world sequential circuit can be modeled as an FSM, but in practice only sequential control logic is modeled as an FSM. For example, a D Flip-Flop can be modeled as an FSM, i.e. in terms of explicit states and their transitions, or it can be modeled in terms of logic gates, or a behavioural description with implicit states. Whichever method you use for modeling a D Flip-Flop, the D Flip-flop remains an FSM, but only when the design is expressed in terms of explicit states and their transitions, do we say the flip-flop has been designed using the FSM design technique. Similarly, only when a logic design is modeled using the explicit flow of data, do we term it as datapath design technique.

To answer the question of why FSM+Datapth became the dominant technique, we should look into some of the alternatives to FSM+Datapath that exist, and why these alternatives failed.

Synchronous logic vs. Asynchronous logic

FSM + Datapath is a term often used for synchronous logic design of sequential logic. While asynchronous FSMs do exist, the most common ones are synchronous. Asynchronous logic does not use a clock for synchronization, while synchronous logic uses a global clock for synchronization of operations. In synchronous logic, the FSM changes its state on the active edge of the clock. So the operation is predictable and it is regular. The change of state happens at regular intervals of time, since the clock frequency is constant (varying clock frequency dynamically is also possible, but let's keep things simple for our discussion). In asynchronous FSM, change of state is not synchronized with a clock. Synchronous logic is much easier to design. The logic is less complex, so it is easy to get a correct design using synchronous logic. This is the reason all the processors we use in daily life are synchronous.

Top-down methodology vs. bottom-up methodology

The bottom-up methodology focuses on designing the circuit from the bottom-up, i.e. from transistors to gates to the final circuit. The top-down methodology focuses on designing the circuit from higher-level abstractions, such as behavioral descriptions and flow-diagrams. While the bottom-up methodology works well for smaller design blocks, it does not scale up for large designs such as processors. This is the reason a top-down methodology is used for processor design. In practice, smaller functional blocks are designed bottom-up, and the entire system is designed top-down, and the 2 meet in the middle, i.e. the system is broken down into smaller blocks, which are designed from the bottom up.

A top-down methodology has 3 advantages over a bottom-up methodology:

1. Promotes regularity: This refers to designing a complex unit using simpler units repeatedly. For example: Designing a 4 bit adder using 4 1-bit adders.
2. Promotes design reuse: The top-level design can contain many units, which can be broken down into even more units. Different design units can have a common design for the lower-level design units. For example, both a 4-bit adder and a 4-bit multiplier can have a common design of a 1-bit adder. Multipliers can be built from shifters and adders.
3. Ease of design: The designer does not get lost in a sea of gates when designing a complex unit. The processor architect (system-level processor designer) can split the design work among multiple teams, so design work can be done in parallel.

All these factors result in far lesser design time for a top-down methodology than a bottom-up methodology. As time-to-market is crucial in the semiconductor industry, this resulted in top-down methodology becoming the methodology of choice.

Motivation for Finite State Machines

For controlling sequences of operation, it is natural to think of it in terms of how the machine should behave, rather than how the machine should be implemented using logic elements such as Flip-Flops and combinational logic. This led to the evolution of FSM design technique. In this technique, the FSM is implemented using gates and flip-flops, from the behavioral description of the FSM, in a top-down design methodology. The behavioural description of the FSM contains explicit states and state transitions in the FSM Design technique.

Motivation for Datapath

For operations in which I need to move my data around, for example from register to memory or register to register, it is natural to think about how the data should flow. By thinking this over, I can then draw an abstract diagram of the datapath. This led to the evolution of the datapath design technique. In the datapath design technique, the datapath is implemented using combinational logic and registers, from the datapath diagram, in a top-down design methodology. The behavioural description of the datapath contains explicit flow of data in the Datapath Design technique.

Putting it all together: Motivation of FSM+Datapath for processor design

So while the FSM design technique excelled at designing control logic of sequences, the datapath design technique excelled at designing logic to support the flow of data. Coming to the processor, it is natural to split the design of a processor into 2 parts:

1. The sequence of operations: Fetch data from memory, decode the instruction and then execute it, finally write it back. We use control signals to signal the completion of one operation and flow control (such as branching). This control of sequences can be designed naturally using the FSM design technique.
2. The flow of data: How data should flow from register to memory or register to ALU and so on. This can be designed naturally using the datapath design technique.

Availability of EDA tools:

The availability of Electronic Design Automation (EDA) tools played a crucial role in enabling a top-down design methodology and the synchronous design philosophy, since EDA tools had great support for logic synthesis (automatically generating logic gates from a behavioral description) for synchronous designs, and also had great support for logic synthesis from an abstract, behavioural textual description written in a special computer language called a Hardware Description Language.

Summary and conclusion:

Synchronous logic became the dominant design technique simply because it was easier to design working machines. FSM design technique by itself is limited in usefulness, since it would be difficult to create an FSM for the entire processor, because this would result in a very large and complex FSM that is difficult to debug or read. Sequential control of the processor can be designed naturally using the FSM Design technique, so only the sequential control of the processor is designed using the FSM design technique. The rest of the processor is designed using the datapath design technique, since the dataflow aspect of the processor is easy to model as a datapath. The availability of EDA tools further motivated the design of processors using abstract, behavioural descriptions such as FSMs and datapaths.

Related Question: Mathematical models of computation that capture more advanced OS and CPU design features