(MUST DO) Review of EE360, "Digital Logic"

Objectives

• List the topics from EE360, "Digital Logic", in which you should be proficient in order to succeed in this course

Important Topics from EE360

• Convert numbers between decimal, binary, and hexadecimal representations

• Perform binary addition using 2’s complement format

  • Describe sign extension

• Describe how English characters are encoded using ASCII

• Convert between English characters and ASCII codes

• Implement a combinational logic circuit

  • Complete a truth table from a problem description

  • Use K-maps to reduce the truth table into minimum SOP

  • Draw the circuit

• Explain the function of a multiplexer and a decoder

• Design an 8-bit full-adder from logic gates

• Describe the organization and usefulness of an FPGA

• Implement an FSM

  • Draw/navigate a state diagram

  • Convert a state diagram to a state table

  • Determine Boolean expressions for the next state/output logic from the state table

  • Draw the schematic to realize the FSM

• Describe the function and organization of a register based on D flip-flops

• Explain basic memory organization (i.e. how to compose larger and larger pieces of memory, starting with a single flip-flop).

• Define address space and addressability

Video Notes

• Disregard the last part of the video about the old EE360 exam! I grew a bit self-conscious about posting an old EE360 exam to this website so you are not actually required to do that anymore. Instead, complete the "Must do" exercise below, which uses a different list of questions from a publicly available website as a facsimile of an old EE360 exam.

Additional Resources

• “Digital Electronics” videos from Bill Kleitz (this is the textbook used for EE360)

• “Introduction to Computing Systems”, Chapters 2 and 3

• “Basic Computer Architecture” (Chapters 2, 6, and 7; we'll use this textbook heavily in Unit 5!)

• Crash Course Computer Science (the first few videos discuss digital logic concepts pertinent to this class)

• Computation Structures, Lessons 1-6

• The Organic Chemistry Tutor (example video)

• Neso Academy (example video)

• Ben Eater

Exercises

• Complete the digital logic problems here.

• Review old EE360 HWs and exams or attempt the HWs and exams from a prior year.

• “Introduction to Computing Systems” end-of-chapter exercises from Chapters 2 and 3

• “Basic Computer Architecture” end-of-chapter exercises

  • Chapter 2 (1-10)

  • Chapter 6 (8-28)

  • Chapter 7 (1-3,7)

(SHOULD DO) History of Computing

Objectives

• Describe the qualities that define a "modern computer"

• Describe the capabilities of the following computers and describe how each one advanced computing technology

  • Tabulating Machine

  • Analytical Engine

  • Harvard Mark 1

  • Colossus Mark 1

  • ENIAC

• Identify the key inventors/contributors of the above machines and of the less-well-known contributors below

  • Alan Turing

  • Ada Lovelace

  • Joan Clarke

  • Grace Hopper

  • The "ENIAC Girls"

  • Katherine Johnson

  • Evelyn Boyd Granville

  • Roy L. Clay, Sr.

  • Clarence Ellis

  • Mark Dean

  • John Henry Thompson

  • Kimberly Bryant

Additional Resources

• "Introduction to Computing Systems", Section 1.4.1

• History of Computing (from "Computer Organization and Design, ARM edition")

• History of Computing (Britannica)

• 7 black pioneers in computer science [infographic]

• History of Computing (Wikipedia)

• Books

  • The Thrilling Adventures of Lovelace and Babbage: The (Mostly) True Story of the First Computer

  • The Soul of a New Machine

  • The Innovators: How a Group of Hackers, Geniuses, and Geeks Created the Digital Revolution

  • Racing the Beam: The Atari Video Computer System

  • The Apollo Guidance Computer: Architecture and Operation

  • Rise of the Rocket Girls: The Women Who Propelled Us, from Missiles to the Moon to Mars

  • Rocket Girl: The Story of Mary Sherman Morgan, America's First Female Rocket Scientist

Exercises

• Complete the table below.

• Pick one of the lesser-known contributors to computer architecture from the last list in the lesson objectives and write a short paragraph about their contributions.

• Read one of the “History of Computing” articles, either on Britannica or Wikipedia. They’re a great length after the “Crash Course Computer Science” videos, that go just a little bit deeper without being book-length!

• Add one of the books from the “Additional Resources” section to your wish list. Or just go and buy it!

(SHOULD DO) Turing Machines

Objectives

• Define a "computer"

• Describe the Universal Turing Machine

Additional Resources

• Crash Course Computer Science: "Alan Turing"

• "Introduction to Computing Systems", Sections 1.5 and 1.6

• "Basic Computer Architecture", Sections 1.1-1.3, 1.6.2-1.6.4, 1.6.7

• "On Computable Numbers, with an Application to the Entscheidungsproblem" (Turing)

  • Alan Turing's classic paper where he describes Universal Turing Machines, though he just calls them "Universal Machines"

  • The "entscheidungsproblem" is the German word for something called the "halting problem", which is this: if a computer can process the text of a computer program, can it determine if that computer program will ever halt or if it will continue to run forever? It turns out that no such computer exists, and Alan Turing comes up with a beautiful reason why! Watch the video in the first bullet above for a description of it.

Exercises

• End-of-chapter exercise 1.13

• “Basic Computer Architecture”, Exercises 1.9-1.12

(ASPIRE TO DO) Building an Automated Calculator

Objectives

• Describe how memory and a counter can be added to an arithmetic circuit to provide:

  • Temporary storage, and

  • Automatic control

• Describe how memory is built from flip-flops

Video Notes

• The two terms below are important to know, though I didn't belabor them in the video

  • Address space: How many items can be stored in a piece of memory. In the 4x1 and 16x1 pieces of memory, the address space of each one is 4 and 16, respectively.

  • Addressability: How many bits can be stored in each memory location. In the 16x1 and 16x8 pieces of memory, the addressability of each one is 1 and 8 bits, respectively.

Additional Resources

• Getting Logisim

• Automated-Calculator.circ

Exercises

• Download Logisim and the Automated Calculator circuit. Build 64x8 or 256x8 RAM components (try to do it without looking at the 64x1 and 256x1 circuits!). Add one of these to the "Calc_ROM" circuit and make any other required edits to that circuit (including to the instructions!) to support these larger memory cells. Paste screenshots of (1) your completed memory circuit and (2) your updated “Calc_ROM” circuit below.

• What features do you think the "Automated Calculator" is missing before it could be considered a full computer?

• Edit the memory in the final circuit (“Calc_ROM”) to perform the following operations (in order):

  • Store 5 in M[7]

  • Store 7 in M[12]

  • Add the values in M[7] and M[12]

  • Store the result of the addition in M[0]

• Devise a sequence of instructions for "Calc_ROM" that will effectively clear a spot in memory, regardless of what value was stored there previously.

• Edit the ALU to:

  • perform other useful functions such as AND, OR, XOR, NOT, and right shift.

  • perform 16-bit operations instead of 8-bit.

  • provide outputs that indicate if the result of an operation is (1) zero or (2) negative.

• Add a "Clear" button that resets the entire memory block to all zeros. Does it make sense for there to be an instruction that can operate that button? If so, implement it.

Additional Resources

• "Introduction to Computing Systems", Sections 1.3.1, 1.5, 1.7, 4.1

• "Basic Computer Architecture", Section 1.7

• "Preliminary Discussion of the Logical Design of an Electronic Computing Instrument" (Burke, Goldstine, von Neumann)

  • von Neumann's classic paper, in which he describes the "von Neumann Model"

Exercises

• "Introduction to Computing Systems", Exercises 4.1, 4.5 (parts a, b.1, b.2, b.4, and d)

• Research the von Neumann and Harvard architectures. What are the advantages and disadvantages of each one?

• There are many other types of computer architectures, such as stack machines and GPUs. Research a few and compare and contrast them to what you know about the von Neumann and Harvard architectures.

(MUST DO) The Little Man Computer

Objectives

• Describe the “Little Man Computer” (LMC), including it's components, instruction cycle, and instruction list

• Define "opcode" and "operand"

• List the three types of instructions in the LMC

Video Notes

• "Microprocessor Fundamentals" (left/first video)

  • @07:15 (and at multiple other times): I refer to the instruction cycle as being "Fetch - Decode - Execute - Access memory - Write back to memory", whereas "Introduction to Computing Systems" describes it differently. Both are correct (which one is more correct depends on how the computer accesses memory), but we'll use the cycle described in our textbook in this class: "Fetch - Decode - Evaluate Address - Fetch Operands - Execute - Store Result".

  • @14:30: To be completely correct, I probably should have also placed the halt instruction, "000", in memory locations 008 and 012.

Additional Resources

• The Little Man Computer - Paper Computers #2 (YouTube)

• The Little Man Computer (Wikipedia)

  • A few LMC simulators are located at the bottom of the above page

• LMC worksheet

Exercises

• Write a program for the LMC that gets two numbers from the inbox, multiplies them together, and then writes the result to the outbox (hint: 5*4 = 5+5+5+5). Optionally test it on a simulator (bottom of that page) to ensure correctness and then write the final code below.

• Write the following programs for the LMC. Test them on a simulator (bottom of that page) to ensure correctness. Compare your answers with the answer listed in the video notes here.

  • Take in four numbers from the Inbox and put them to the Outbox in reverse order.

  • The first number in the inbox tells you how many will follow, then add the rest up.

  • Divide the first number in the inbox by the second, end up with a quotient and some remainder. Push the quotient to the outbox, then push the remainder to the outbox.

• Compare the LMC to the "Automated Calculator". What are their similarities and differences? What about the LMC makes it a full computer that the "Automated Calculator" is lacking?

• What's an instruction that it seems the LMC is lacking? Write a program to perform that function using just the instructions available to you on the LMC.

Additional Resources

• Hack_ALU.circ

• HackCPU instruction reference

• Hack Computer (Wikipedia)

• The Elements of Computing Systems: Building a Modern Computer from First Principles

• NAND2Tetris.org

• NAND Game (a "playable" version of the "Elements of Computing Systems" book)

Exercises

• Prove that the opcode 010011 does, in fact, result in X-Y (the opcode bits are, in order, zx-nx-zy-ny-f(x)-no).

• Visit NANDGame.com and press the “Skip level” button until you get to the level titled “Machine Code” (it’s the first level after all of the “Hardware” levels). Complete that problem and then paste a screenshot of the completed level below.

• Write the following programs for the HackCPU. Compare your answers to another students' or, if you have the time, download the HackCPU emulator from the publisher and test your program with that!

  • Load four numbers into the A register and put them back to the A register in reverse order.

  • The first number in the A register tells you how many will follow, then add the rest up.

  • Divide the first number in the A register by the second, end up with a quotient and some remainder. Push the quotient to the A register, then push the remainder to the A register.

• Prove that each of the opcodes does, in fact, result in their outputs listed (see the Wikipedia article; for the ALU depicted in the lecture notes, the opcode bits are, in order, zx-nx-zy-ny-f(x)-no).

• Compare the HackCPU to the LMC. What are their similarities and differences? What features does the HackCPU have that make it more suitable for real-life software development?

• What's an instruction that it seems the HackCPU is lacking? Write a program to perform that function using just the instructions available to you on the HackCPU.

(MUST DO) LC-3 Datapath 1

Objectives

• Identify the components in the LC-3 and describe their function

• Describe the signals that control the LC-3 components

Video Notes

• @13:37: I mention that the clock signal goes to the FSM that runs the Control Unit and that this is the only place on this diagram where the clock is used. This might be the most important place the clock goes (since it's used here to drive the FSM that controls the LC-3) but I should note that the clock also goes to any other sequential circuit in the LC-3, i.e. every one of the other registers in the LC-3. This includes the actual "Register File" as well as smaller registers like the MDR or the IR.

• As (I believe) was mentioned in the video, the value going into the 2-input multiplexer on the left side of the control unit is not "PC + 1" but rather "PC". This distinction will be clarified further in "LC-3 Datapath 2".

Additional Resources

• "Introduction to Computing Systems", Sections 4.1 and 4.2

Exercises

• "Introduction to Computing Systems", Exercises 4.2-4.4, 4.16-4.18

• By my count (which could be wrong!), there are 13 control signals in Figure 4.3. List their names, possible values, and what each value means.

• Describe the process of reading from memory. Make sure to include in your description the terms MAR, MDR, MEM.EN, R.W, and GateMDR.

(MUST DO) Intro to the LC-3 Instructions

Objectives

• Describe the format and operation of 5 LC-3 instructions:

  • ADD

  • AND

  • LD

  • BR

  • TRAP

• Describe the hardware and control signals required to implement those instructions.

• Describe the three different categories of LC-3 instructions: Operate, Data movement, and Control.

• Describe the instruction cycle for the LC-3.

Additional Resources

• "Introduction to Computing Systems", Section 4.3

• "Introduction to Computing Systems", Appendix A

Exercises

• "Introduction to Computing Systems", Exercises 4.5.c, 4.6-4.15, 4.19

• In Section 4.4 (discussed in the "A Multiplication Program" lesson), the authors show how these 5 instructions can be used to create a program that multiplies two numbers together. See if you can beat them to the punch by writing that program yourself! (Hint: 5*4 = 5+5+5+5.)

(SHOULD DO) A Multiplication Program

Objectives

• Trace a program written for the LC-3 in machine code

• Show how the PC offset is calculated for LD and BR instructions

Additional Resources

• "Introduction to Computing Systems", Section 4.4

Exercises

• In Figure 4.7 (the multiplication program), which instruction clears R3 and how is it accomplished?

• “Slowpoke Larry” thinks the multiplication program is too efficient, so he adds some instructions that have no real effect on the LC-3, called NOPs (pronounced like “no ops”, short for “no operations”). His new program is below.

  • Identify the NOP instructions used above and describe how they have no real effect on the LC-3.

  • Fill in the missing values above to complete the program.

• There are at least 2 other "NOPs" that can be made from the LC-3 instructions you've learned so far. Can you think of them?

• Is there a problem if either or both of the numbers being multiplied are 0? If so, edit the multiplication program to account for this problem.

• Is there a problem if either or both of the numbers being multiplied are negative? If so, edit the multiplication program to account for this problem.

• Write a "DivideBy7" program that loads a number into R0 and divides it by 7. The program should store the quotient in R1 and the remainder in R2 when it's finished. (Hint: If multiplication can be approximated with repeated additions, it should follow that division can be approximated with repeated subtractions!)

• Write a "PowerOf2" program that multiples a number by an integer power of 2 (e.g. 2, 4, 8, 16, etc). Consider this: It's possible to multiply a number by 2 with a single one of the instructions you've learned so far! The program should load the number to be multiplied into R0 and it would be easiest to load the exponent of 2 into R1 (e.g. if multiplying by 8, "3" would be loaded into R1). The result may be placed anywhere, including R0.

(MUST DO) The Rest of the LC-3 Instructions

Objectives

• Define “instruction set architecture” (ISA) and describe the ISA for the LC-3

• Describe 8 of the remaining 10 LC-3 instructions*

  • Define “opcode”

  • Describe the LC-3’s 5 addressing modes

• Compare and contrast computer “architecture” and computer “organization”

• Compare and contrast reduced (RISC) and complex (CISC) instruction set computers.

• (*: The last 2 instructions will be discussed in Unit 3)

Additional Resources

• "Introduction to Computing Systems", Sections 5.1-5.4.1, 5.4.3, 5.4.4, and Appendices A and B

• "Basic Computer Architecture", Chapters 4 and 5

• Addressing Modes (Wikipedia)

Exercises

• "Introduction to Computing Systems", Exercises 5.1, 5.4-5.33, 5.42-5.46, 5.48-5.50, 5.52 (you can ignore “JSR” and “RTI”, as we’ll cover those instructions in Unit 3)

• Print page 148 from "Introduction to Computing Systems" and put it somewhere you can easily reference it. Annotate as necessary. (Don't forget that you can can find complete information about the LC-3 ISA in Appendix A!)

• There are 6 instructions that set the condition codes (a.k.a. the NZP register). What are they?

(SHOULD DO) Character Count Program

Objectives

• Trace a medium-length LC-3 program (18 lines of code with 7 different instructions)

• Identify how to perform the following operations on the LC-3:

  • Subtract one register from another

  • Test two numbers for equality and execute one of two branches of code based on the result

  • Get an ASCII character from a user and print an ASCII character to the display

  • Control the execution of a loop using either (a) a counter or (b) a sentinel value

Additional Resources

• "Introduction to Computing Systems", Sections 5.4.2 and 5.5

Exercises

• "Introduction to Computing Systems", Exercises 5.3, 5.25

• An excerpt from the Character Count program (Figure 5.17) is shown below. What is the effect of these instructions, i.e. what do they accomplish (in a single expression)?

• The flowchart for the Character Count program (Figure 5.16) is depicted below. For each shape in that flowchart, annotate which lines of code in Figure 5.17 correspond to that shape. For example, the first shape corresponds to the first line of code, at x3000.

• Modify the Character Count program so that:

  • It counts the number of mismatching characters.

  • It repeats indefinitely until the user enters a character to indicate that the program should terminate (e.g. "!" or "0").

• Write a "Divide" program that divides a number in R0 by a number in R1. The program should store the quotient in R2 and the remainder in R3 when it's finished. (Hint: Recall that division can be approximated with repeated subtractions!)

  • Update the "Divide" program to be able to handle zeros.

  • Update the "Divide" program to be able to handle negative numbers.

(SHOULD DO) Design Trade-offs

Objectives

• List architectural and organizational features of the LMC, HackCPU, and LC-3

• Describe the factors that affect a computer’s performance and power usage

• Describe the purpose of benchmarks and list a few

Additional Resources

• "Introduction to Computing Systems", Appendix B (x86 ISA)

• "Basic Computer Architecture", Chapters 4 (ARM ISA) and 5 (x86 ISA)

• ISA Comparison (from "Computer Organization and Design, ARM edition")

Exercises

• Complete the table below that compares the LMC, the HackCPU, and the LC-3 (ignore the column for the HackCPU if you haven’t completed that lesson).

• Assume that a benchmark program has been written to test the performance of the LMC and the LC-3. On the LMC, the program compiles into 1,513,273 machine instructions. Further, let’s assume that the clock on the LMC can run at 100 kHz. On the LC-3, the program compiles into 997,207 instructions. Further, let’s assume that the clock on the LC-3 can run at 1 MHz and that the program consists of 71% instructions that take 5 clock cycles to complete, 21% instructions that take 7 clock cycles to complete, and 8% instructions that take 9 clock cycles to complete. Which computer has better performance running the benchmark program?

• Can you think of any ways other than those listed in the "Must do" exercise in which the LMC, HackCPU, and LC-3 are similar or different?

• Read about the ARM ISA in "Basic Computer Architecture" (Ch. 4), the x86 ISA in "Introduction to Computing Systems (App. B)/"Basic Computer Architecture" (Ch. 4), or review your notes from EE360 about the 8085. How does the LC-3 compare to these other architectures? Can you identify any other architectural features that are similar or different?

(MUST DO) LC-3 Datapath 2

Objectives

• Complete a basic design of the LC-3

• Trace the execution of an instruction in the LC-3 at the microarchitecture level

Additional Resources

• "Introduction to Computing Systems", Section 5.6

Exercises

• "Introduction to Computing Systems", Exercises 5.2, 5.34-5.41, 5.47, 5.51-5.53

• Figure 5.18 shows IR[15:9] going to the FSM. If IR[15:12] corresponds to the opcode, for which instructions does the Control Unit care about IR[11:9] and what do they mean?

• Annotate Figure 5.18 by marking each tri-state buffer, register, control signal, and instructions bits. Add any other notes or annotations that you feel should be on this diagram.

• Trace each of the 13 LC-3 instructions we've covered thus far on Figure 5.18. Identify which instructions use each different logic block (e.g. Which instructions use ADDR2MUX? Which instructions use the sign-extension block en route to the SR2MUX?).

  • In particular, see if you can figure out which instruction(s) might need the "SR1MUX"!

• By my count (which could be wrong!), there are 21 control signals in Figure 5.18. List their names, possible values, and what each value means.

Going Further

• At M[x0006] is a modified instruction, not "HALT" but an instruction that's encoded as "x0FFF". What does this instruction mean and what is it doing?

• Complete the two circuits with the "_shell" suffix. Try to finish them without looking at my solution! Make sure to use "Register_file_shell" in your new "Processing_Unit_shell" circuit and also "Processing_Unit_shell" in the "LC-3" circuit.

What to Submit

1. Your completed .circ file, named according to the following format: "Lab1_<LastName_Partner1>_<LastName_Partner2>_<Section>.circ".