FSM models are well suited to capture the control flow and decision making of algorithms, however, they lack hierarchy; this gives rise to severe limitations when dealing with complex control systems

state explosion

• the size of the state space of a product FSM is the product of the state space sizes of the component FSMs; even worse, if these have independent transition conditions, the number of conditions of the product FSM grows exponentially

exception handling

• exceptions are conditions that require transition to an exception handling state regardless of the current state of the machine when they occur; adding exception transitions to a given transition diagram often obfuscates the main course of control

runtime flexibility

• the hardwired control flow defined by an FSM cannot be changed in any other way than replacing the implemented FSM with another one; the motivation for greater model flexibility is tied to that for greater hardware flexibility

a more flexible control is obtained by microprogramming it

• the fixed schedule by an FSM controller is replaced by the variable one that is determined by a microprogram, composed of microinstructions, each of which is translated into datapath control signals

the first idea of microprogramming was proposed by Maurice Wilkes, in 1951, but it found wide application starting from the sixties, to become dominant in the subsequent decade with the diffusion of CISC architectures (Complex Instruction-Set Computer)

• in this idea, the microprogram is an interpreter, resident in a small control store
• the microinterpreter fetches machine instructions from main memory (that here are seen as higher-level instructions) and executes each of them by a microroutine, that is a sequence of low-level microinstructions
  • the microarchitecture of a CISC processor thus takes the shape of a "processor inside the processor", with a fixed microprogram which, during every machine cycle, fetches an instruction and executes the microroutine that is determined by decoding the opcode of the fetched instruction

starting from the eighties, RISC architectures (Reduced Instruction-Set Computer) have competed with CISC ones, to become dominant eventually

• microprogramming is still a very useful technique to increase the flexibility of hardware design

CSAR (Control Store Address Register): analogue of the conventional Program Counter

• clock cycle determined by the critical path through the microprogrammed architecture

the format in figure 6.4 is not optimal, as the address field is only used for jump instructions–it may be used for other purposes with other instructions

here is an example of microprogrammed control of a datapath that includes: an ALU with shifter unit, a register file with eight entries, an accumulator register, and an input port

table 6.1 presents an example of microinstruction encoding for the given architecture (first part):

table 6.1 (second part):

using the encoding defined in table 6.1, a microinstruction is formed by selecting a function for each module in the datapath and a next address for the Address field (with a suitable don't care value for this whenever Nxt is null)

complex control operations, such as loops and if-then-else statements, can be expressed as a combination (or sequence) of RTL instructions

• as an example, let's develop a micro-program that computes the GCD of two input numbers using Euclid’s algorithm

the microprogram is written in a symbolic RTL notation that immediately translates to microinstructions in a similar way as in the previous example

Schaumont, Listing 6.1 - Micro-program to evaluate a GCD