CS3350B Computer Organization Chapter 2: Synchronous Circuits Part 3: State Circuits
Alex Brandt
Department of Computer Science University of Western Ontario, Canada
Monday February 08, 2021
Alex Brandt
Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 1 / 37
Outline
1 Digital Signals
2 The Clock
3 Flip-Flops and Registers
4 Finite State Machines
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 2 / 37
Digital Signals
We digitalize an analog (voltage) signal to encode binary. “High” voltage ⇒ 1.
“Low” voltage ⇒ 0.
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 3 / 37
Transmitting Digital Signals
For our purposes:
Transmission is continuous. There’s always something on the wire. Transmission/switching is effectively instantaneous.
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 4 / 37
Grouping Signals To Encode Many Bits
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 5 / 37
Signals and Circuits
Unfortunately for us, combinational circuits cause propagation delay.
The more complex the circuit the longer the delay.
Every gate adds some delay.
2 5 3 -3 2123
4650
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 6 / 37
Dealing with Delay
Problems with propagation delay:
Inputs transmit (change) instantaneously, but output does not.
When can the next circuit read the output and ensure it is getting the correct value?
Synchronize the circuits via a clock.
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 7 / 37
Outline
1 Digital Signals
2 The Clock
3 Flip-Flops and Registers
4 Finite State Machines
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 8 / 37
The Clock Signal
The clock is a digital signal which has a precise timing for switching between 1/0.
Synchronous circuits use the clock to sync their executions, decide when to read inputs/outputs.
ë Heartbeat of a synchronous system.
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 9 / 37
How to Synchronize
Circuits usually synchronize to the rising edge of the clock.
ë The transition from 0 to 1.
ë Depending on the system, can instead sync on the falling edge.
0,0 1,0 0,1 1,0
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 10 / 37
Clock Multipliers
We know that CPU and memory operate at difference speeds. So how do they synchronize?
One central clock used.
Central clock is as slow as the slowest component. Faster components use a clock multiplier.
A clock multiplier multiplies the central clock frequency so that a component has many internal cycles for a single clock cycle of the entire system.
Note: this is simply a technicality of implementation. Generally, we still discuss speeds based on frequency the CPU experiences. Our old metrics still work as they always have.
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 11 / 37
Outline
1 Digital Signals
2 The Clock
3 Flip-Flops and Registers
4 Finite State Machines
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 12 / 37
Circuits that Remember
Sometimes values on a wire (i.e. a bit) cannot be maintained indefinitely on that wire. Values must change.
Computer memory is circuits which remember.
Circuits implement memory but are also used within other circuits to hold state.
ë Modular design.
Flip-flop: a circuit which implements a single bit of memory.
ë All flip-flops based on a simple design: inputs, combined with current state, give next state.
ë Essentially, the implementation of static RAM (SRAM). Register: a storage for multiple bits of memory.
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 13 / 37
Edge-Triggered Flip-Flop
A flip-flop which looks at its input on the edge of clock. ë Rising edge or positive edge (usually), or
ë Falling edge or negative edge.
This is a delay flip-flop
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 14 / 37
D Flip-Flop
Delay flip-flop: takes input and, with some delay, sets output equal to the input.
ë Simplest (conceptually) flip-flop.
ë Requires constant updating to maintain state.
ë Grabs input on rising edge and outputs that until next clock cycle. ë Current state does not affect next state.
D Q Q𝑛𝑒𝑥𝑡 0-0 1-1
Flip-flops usually produce next state and negation of next state simultaneously.
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 15 / 37
T Flip-Flop
Toggle flip-flop: if input is 1, toggle current state.
ë Uses current state to determine next state.
ë 𝑇 ≡ 0 ⇒ “Hold”. Next state is same as current.
ë 𝑇 ≡ 1 ⇒ “Toggle”. Next state is opposite of current.
T Q Q𝑛𝑒𝑥𝑡 000 011 101 110
Alex Brandt
Chapter 2: Synchronous Circuits, Part 3: State Circuits
Monday February 08, 2021
16 / 37
SR Flip-Flop
Set-Reset flip-flop
ë Two inputs, S (set), R (reset), synchronized by a clock. ë 𝑆≡1⇒“Set”. Nextstateis1.
ë 𝑅≡1⇒ “Reset”. Next state is 0.
ë 𝑆 ≡ 0 ∧ 𝑅 ≡ 0 ⇒ “Hold”.
S R Q Q𝑛𝑒𝑥𝑡 00-Q 01-0 10-1 11–
Can not have both 𝑆 and 𝑅 set to 1…
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 17 / 37
SR Technicalities
E “enable” ⇐⇒ clock
𝑆 ≡ 𝑅 ≡ 𝐸 ≡ 1 ⇒ 1 + 𝑄 ≡ 0 ≡ 1 + 𝑄 ⇒ 𝑄 ≡ 𝑄 ???
We get undefined behaviour. This is weird and can destabilize the system.
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 18 / 37
JK Flip-Flop
JK flip-flop
ë Two inputs, J (set), K (reset), synchronized by a clock. ë Same as SR except with toggle.
ë 𝐽 ≡ 1 ∧ 𝐾 ≡ 1 ⇒ “Toggle”.
J K Q Q𝑛𝑒𝑥𝑡 00-Q 01-0 10-1 11-𝑄
Alex Brandt
Chapter 2: Synchronous Circuits, Part 3: State Circuits
Monday February 08, 2021
19 / 37
Registers
A register is just a collection of flip-flops. Technically, this is a shift register.
𝑛-bits ⇒ 𝑛 flip-flops.
Clock pulse connected to all flip-flops.
Can be encoded using any type of flip-flop.
This example is a parallel in, parallel out register.
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 20 / 37
PIPO Registers
Parallel In, Parallel Out Register: All inputs bits come in in parallel, and output bits get output in parallel.
Most common.
Input/output of each flip-flop is independent. Can be encoded using any type of flip-flop.
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 21 / 37
SIPO Registers
Serial In, Parallel Out Register: One input bit at a time, output all bits at once.
Input bit moves through chain of flip-flops. Transitions at each clock.
This example uses D flip-flops.
Sometimes it is useful to clear the entire register without waiting 𝑛 cycles for 𝑛 bits of data to shift out.
Additional control signals can be used to set all flip-flops to 1 (𝑆) or all flip-flops to 0 (𝑅).
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 22 / 37
SISO/PISO Registers
Serial In, Serial Out Register: A linear chain of flip-flops. Output of one flip-flop is the input of the next.
One input bit and one output bit.
Kind of like a conveyor belt of bits.
Parallel In, Serial Out Register: A linear chain of flip-flops + control circuits.
Data loaded in parallel: 𝑛 flip-flops load 𝑛 bits at once. Data output in serial: Acts as SISO for output.
ë Output one bit at a time.
ë Bits are shifted one over on each output.
Requires clock and additional write/shift control signal.
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 23 / 37
Timing a Flip-Flop
All gates/circuits introduce propagation delay.
For flip-flops this propagation delay is called clk-to-q delay.
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 24 / 37
Timing a Flip-Flop: Data Stability
Input to a flip-flop must have a stable value around the rising edge of the clock.
ë Before the rising edge: setup time. ë After the rising edge: hold time.
setup
hold
Despite how it’s shown here, hold time is less than clk-to-q delay.
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 25 / 37
Putting it all Together: Accumulator
An accumulator: continually adds input value to its stored value.
This doesn’t work.
Would spin once per circuit’s propagation delay, not once per input. Need clock to synchronize reading from input.
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 26 / 37
Clocked Accumulator
Insert register to store output.
Only need to clock the register, not the combinational circuit.
Clock on register determines when output of circuit actually gets stored.
Alex Brandt
Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 27 / 37
Timing the Accumulator
Clock must be slow enough to include: Adder delay,
Clk-to-q, Setup time.
adder delay
setup
clk-to-q
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits
Monday February 08, 2021
28 / 37
Synchronous Circuits: Clock Frequency
(Max Clock Freq.)
Min. Clock Period = Combinational Circuit Propagation Delay
+ Setup Time + Clk-To-Q
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 29 / 37
Pipeline for Performance (1/2)
Delay of adder and shifter is very long.
Forces clock cycle to be very long.
Slows down other circuits in this synchronous system.
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 30 / 37
Pipeline for Performance (2/2)
Split add and shift into two different tasks.
Insert register between to store results temporarily. Increase clock frequency.
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 31 / 37
General Synchronous Systems
All systems follow a general pattern:
A chain of logic circuit blocks, separated by registers, controlled by a single clock.
Foreshadowing for MIPS pipeline.
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 32 / 37
Outline
1 Digital Signals
2 The Clock
3 Flip-Flops and Registers
4 Finite State Machines
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 33 / 37
Finite State Machines: Introduction
We know FSMs from logic, formal languages, complexity.
Each state of the machine is a
node.
Inputs trigger change of state and an output.
This is a Mealy machine: outputs occur on transitions. Moore machines are equivalent.
ë Output is based on current state.
Alex Brandt
Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 34 / 37
Finite State Machines: As Circuits
FSMs have three components: state, input, output. Just like synchronous circuit.
Registers, input bits, output bits.
Clock controls when inputs read ⇒ transitions. PS: present state, NS: next state.
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 35 / 37
Finite State Machines: Implementing The Logic
Next state and output is always just some Boolean combination of input and output. Use our normal 4-step process:
1. Build a truth table, 2. Get canonical form, 3. Simplify,
4. Draw circuit.
0⇑1 1⇑1
1⇑1
Chapter 2: Synchronous Circuits, Part 3: State Circuits
PS In NS Out 00 0 01 0 001011 01-100 10 0 10 1 10 1 11 1 11 0 10 0 11 1 11 1
Monday February 08, 2021
0⇑0
0 1 2
0⇑1 1⇑1 1⇑0
0⇑0
3
Alex Brandt
36 / 37
FSMs are Synchronous Systems are FSMs
Essentially every synchronous system can be modelled by an FSM. ë Would become absurdly large in most circumstances.
A valid design strategy for integrated circuits and specialized hardware includes:
1 Turn problem into FSM.
2 Turn FSM into truth table. 3 Turn truth table into circuit.
Full Example: An elevator-controlling circuit.
ë https://www.cs.princeton.edu/courses/archive/spr06/ cos116/FSM_Tutorial.pdf
Alex Brandt Chapter 2: Synchronous Circuits, Part 3: State Circuits Monday February 08, 2021 37 / 37