CS 240 Lab 3: Arithmetic Logic

Peter Mawhorter

How do Computers Work?

How do Computer Circuits Work?

  • When you press the power button, some wires in the computer are powered with +5V, based on the transistors, which implement a series of logic gates. The logic gates are organized into common units called “chips” or “integrated circuits” (ICs).

  • A clock creates cycles of high and low voltage, which creates patterns of activation over time determined by the chips. Buttons or other inputs may also create be woven into these patterns.

How do Computers Represent Things?

  • High/low voltage patterns in groups of wires represent numbers using binary. These numbers can also represent symbols via an encoding like ASCII.

  • Specialized chips create patterns of voltage from inputs to outputs which, when interpreted as binary, correspond to things like “counting” or “addition.”

But what about… ?

  • Integrated circuits put together gates to perform various functions. Which circuits are used in a CPU, and what are their functions?
  • How do the integrated circuits for basic binary operations like addition or multiplication work?
  • How are clock signals generated & managed in the computer?
  • How is memory implemented using gates?
  • How can we change what a computer does by writing a program, instead of having to re-wire it?

How does the OS Work?

  • When you boot the computer, it launches an operating system, which provides things like graphical or text interfaces for controlling the computer.
    • Most computers have graphical interfaces and either a touch screen or a mouse, possibly in addition to a keyboard.
    • Servers don’t have any direct inputs, but allow for remote connections, where input & output is via text.
    • A text interface for controlling a computer is called a “shell” or “command line.”

How does the OS Work?

  • Whatever interface you use, you will log in, and then proceed to launch individual programs to do specific stuff, like browse the web or edit a file.
    • Programs are just another kind of file, and we can create new programs using things like text editors and compilers.

But what about… ?

  • How does the “boot” process work? Where does the operating system actually start?
  • What language does the “shell” use? Why are shells still around when we have graphical interfaces?
  • How does one program launch another? How does the OS keep track of programs that are running? How do two programs run at the same time?
  • How do compliers actually work? How does our text written in a programming language turn into a program, and what does a “program” actually consist of?

The datapath for the HW architecture. At the left, we start with the PC, which is a single register and which gets input from a line we’ll get to later called “PC input”. The PC feeds into the read address input of instruction memory, which outputs an instruction (16 bits) to the right. The PC also feeds into an adder whose other input is the number 2, and this gets forwarded to the branch-equal (or BEQ) mechanism. Back to the instruction, it gets split into bits 0-3, 4-7, 8-11, and 12-15. Bits 12-15 go to the control unit, drawn as a circle, which generates “Mem,” “Branch,” “Mem store,” “Reg Write,” and “ALU Control” outputs. We’ll see those pop up later, for now going back to the Instruction Memory outputs, bits 0-3 and 4-7 go into a 2x1 mux which feeds the write address of the register file, and which is selected by the “Mem” control signal. Bits 0-3 also bypass the Register file, go through a sign extender to become 16 bits, which we’ll call “offset.” This offset feeds into another 2x1 mux for the second ALU operand that’s also controlled by the “Mem” signal, as well as going to a shift-left-by-1 to become the second input to the first adder in the BEQ mechanism mentioned before. This BEQ mechanism adds the PC + 2 to the offset and then selects between that result and the original PC + 2 result using a 2x1 mux which is selected by an AND result combining the “Branch” control signal and the “Zero” output of the ALU. The result of that mux is the PC input mentioned right at the beginning. That wraps up destinations for the “offset,” backing up to the instruction bits, bits 4-7 also go to the Read address 2 for the Register file, while bits 8-11 go to the Read address 1. The only other Register file input is the Write Data, but we’ll get to that later. With two read addresses specified, along with a write address, the register file takes the “Reg Write” control signal as its “Write Enable” input, and outputs “Read data 1” and “Read data 2.” Read data 1 is 16 bits and goes straight in as the first operand of the ALU. Read data 2 (also 16 bits) is the second input to the mux described earlier that feeds the second ALU operand (whose other input if you recall is the sign-extended bits 0-3 of the instruction itself). Read data 2 is also forwarded to the Data Memory as its “Write Data” input (more on that in a second). This takes care of the outputs of the register file; with two operands to work with, the ALU also gets the ALU control signal from the control unit, and produces the aforementioned “Zero” output plus a 16-bit result. The ALU result serves as input to the Data Memory “Address” input, and also goes to a 2x1 mux below data memory which connects back to the “Write Data” input of the register file we mentioned earlier. That mux is controlled by the “Mem” signal from the control unit, and its other input is the “Read Data” output of the Data Memory, so either the ALU result or a piece of data whose address is specified by the ALU result will get written to a register file (if “Write Enable” is on, of course). As mentioned previously, the Data Memory also gets Write Data input from the Register File’s Read Data 2 output. It’s third and final input is a “Write Enable” which comes from the “Mem store” control unit signal. As already mentioned, its only output (“Read Data”) feeds into a mux and (if selected) back to the register file’s write input. And that’s the end of the datapath! 

The schematic diagram of the full CPU.

The CPU connections listed as a table:

Component Inputs Outputs
PC
  • Next Address from BEQ Logic
  • PC to read address of Instruction Memory
  • PC + 2 to next address for BEQ Logic
Instruction Memory
  • Read Address from PC
  • 16-bit Instruction splits into
    • Bits 12-15 go to the Control Unit
    • Bits 8-11 go to Read Addr 1 of Register File
    • Bits 4-7 go to:
      • Read Addr 2 of Register File
      • Register File Write Addr Mux
    • Bits 0-3 go to:
      • Register File Write Addr Mux
      • Sign extend to 16 bits and then:
        • ALU 2nd Operand Mux
        • Shift left 1 into Offset for BEQ Logic
Control Unit
  • Bits 12-15 of Instruction
  • Reg Write signal goes to Write Enable of Register File
  • ALU Control signal goes to control inputs of ALU
  • Branch signal goes to BEQ Logic Branch input
  • Mem Store signal goes to Write Enable of Data Memory
  • Mem signal goes to:
    • Register File Write Addr Mux
    • ALU 2nd operand Mux
    • ALU/Memory result Mux
Register File
  • Read Addr 1 from bits 8-11 of Instruction
  • Read Addr 2 from bits 4-7 of Instruction
  • Write Addr from Register File Write Addr Mux (either bis 0-3 or 4-7 of instruction)
  • Write Data from Final Result Mux (either ALU Result or Data Memory Read Data output)
  • Write Enable from Reg Write output of Control Unit
  • Read Data 1 goes to ALU 1st Operand
  • Read Data 2 goes to:
    • The ALU 2nd operand Mux (along with sign-extended instruction bits)
    • The Write Data input for Data Memory
Arithmetic Logic Unit (ALU)
  • 1st operand from Read Data 1 of the Register File
  • 2nd operand from the ALU 2nd operand Mux (either Read Data 2 from the Register File or bits 0-3 of the instruction after sign extension to 16 bits)
  • ALU Control output from Control Unit
  • 16-bit result goes to:
    • Address input for Data Memory
    • Final Result Mux (along with Read Data from Data Memory)
  • Zero flag goes to Zero input to BEQ Logic
Data Memory (RAM)
  • Read Address from ALU result
  • Write Data from Register file Read Data 2 output
  • Write Enable from Control Unit Mem Store signal
  • Read Data result goes to Final Result Mux (along with ALU result)
BEQ Logic
  • Next Address from PC + 2
  • Offset from bits 0-3 of instruction after sign extend and shift left by 1
  • Branch from Control Unit
  • Zero from ALU Zero Flag
  • Adds PC + 2 and Offset inputs and then selects that result or the original PC + 2 result using an AND between the Branch and Zero inputs. Takes this result as the Next Address and feeds it back to the PC.

Check-in

Self-directed learning:

  • Shell
  • C
  • Putting the pieces together

Outline

Lab Projects

Project Details

  • Details and example ideas
  • Propose by lab 5 at the latest (short conversation in lab).
  • Demo by lab 7 at the latest (short demo in lab).
  • Can get help from tutors/instructors but not from each other.

Project Assessment

  • Demo in lab (interactive conversation).
  • Explain learning & effort, we will ask questions.
  • We’ll recommend A-/A/A+ but you can negotiate.
    • We could ask for specific extension/fix.
  • Can self-assign up to B+ without a lab project.

Directing Signals

Multiplexer

A multiplexer (or mux) selects one of 2n2^n inputs, using nn “select” wires whose activation pattern is interpreted as a binary number.

  • An A×BA\times B mux has AA input groups with BB wires each
  • Each input group (& the output) has BB wires
  • So an 8x2 mux has 16 inputs in 8 groups of 2, 3 select inputs, and 2 outputs.

2x1 Multiplexer

A 2x1 multiplexer circuit diagram, showing how it’s implemented. Inputs D0 and D1 each connect to a separate AND gate. The other inputs of those and gates connect to the S selector input, but with a NOT gate on the way for the AND gate connected to input D0. This means that switching S back and forth switches which AND gate gets power from the S input, but only one of them does at a time. Both AND gates connect to an OR gate whose output is the circuit output. 

8x1 Multiplexer

A diagram showing a mutiplexer as multiple wires that come in, one of which is connected to the output wire, with the select inputs controlling which connection is made. This isn’t actually how it’s implemented using transistors, but it’s a good analogy. 

We can imagine that the select inputs change which input wire (or wire group) is connected to the output.

S2 S1 S0 Q
0 0 0 D0
0 0 1 D1
0 1 0 D2
0 1 1 D3
1 0 0 D4
1 0 1 D5
1 1 0 D6
1 1 1 D7

D0-D8 are the Data inputs

Demultiplexer

A demultiplexer (or demux) is the inverse of a multiplexer: it steers an input value (or group) onto one of 2n2^n outputs based on nn select inputs.

  • The unused output lines are low/0.

1x4 Demultiplexer

The symbol for a 1x4 demux: input D comes in on the left which is the short end of a trapezoid. Select inputs S0 and S1 come in from the bottom, and outputs Q0 through Q3 go out from the right (the wide end of the trapezoid). 

S1 S0 Q3 Q2 Q1 Q0
0 0 0 0 0 D
0 1 0 0 D 0
1 0 0 D 0 0
1 1 D 0 0 0

D is the data input

Untangling Binary

Decoder

A decoder takes an nn-bit binary number on nn wires and outputs a high signal on one of 2n2^n wires with the rest low.

  • Also known as a “1-hot” encoding where “hot” refers to high-voltage.
  • Only one of the outputs is active at a time
  • Numbers M×NM\times N refer to inputs/outputs and NN is always equal to 2M2^M: you can have a 2x4 or 3x8 decoder, but a 3x5 decoder doesn’t make sense.

2x4 Decoder

A circuit diagram for the 2x4 decoder, showing inputs D0 and D1 at the top, with outputs Q0 through Q3 on the right-hand side. The inputs each split to go through a NOT gate on one side, creating wires that extend down carrying both the normal and inverse of each input signal. These normal/inverse wires feed into four AND gates (one per output) where each AND draws from the normal/inverse lines for D0 and D1 such that it will be activated when the two bits match the binary value of the output. So for example, Q0 is connected to both NOT lines, meaning that it will be high when D0 and D1 are both low. Q1 is then connected to the normal line for D0 and the NOT line for D1 so it turns on when D0 D1 is 0 1. This pattern continues for Q2 and Q3. 

3x8 Decoder Table

D2 D1 D0 Q7 Q6 Q5 Q4 Q3 Q2 Q1 Q0
0 0 0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 1 0 0
0 1 1 0 0 0 0 1 0 0 0
1 0 0 0 0 0 1 0 0 0 0
1 0 1 0 0 1 0 0 0 0 0
1 1 0 0 1 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0

Encoder

An encoder is the opposite of a decoder: it takes 2n2^n inputs where only one is on at once, and has nn outputs which encode the position of the input that was on in binary.

  • Behavior is undefined if all inputs are off or more than one is on.
  • Numbers M×NM\times N refer to inputs/outputs and MM is always less than or equal to 2N2^N: you can have a 4x2 or 8x3 encoder, or even a 5x3 encoder, but you can’t have a 5x2 encoder (not enough bits of output).

4x2 Encoder

A 4x2 encoder circuit diagram. Input D0 is not connected to anything, input D1 is connected to an OR gate along with D3 to produce output Q0, and input D2 is connected to a second OR gate (also along with D3) to produce output Q1. 

Note the disconnected input: when that’s the high input, neither output is on.

Addition

Half-Adder

A half-adder adds two one-bit values to get a 1-bit result, plus a 1-bit carry-out (which is 1 when both inputs are 1).

  • Can’t use it for addition because it has no carry-in option

Full Adder

A full adder uses two half-adders to implement addition for 1 bit, with a carry-in and a carry-out.

  • With 3 inputs, the max result is 11, which only needs 2 outputs.
  • A “ripple-carry” adder for multiple bits hooks the carry-out from one adder into the carry-in of the next. This is how we add multi-bit numbers.

Adder Diagrams

Ripple-Carry