Best friends with Computer Architecture?

You bet!

(MUST DO) Programming Basics

Objectives

• Describe the process of systematic decomposition

• Convert problem descriptions into flowcharts

• Write short machine-code programs (~10 LOC) for the LC-3

• Create sequential, conditional, and iterative constructs using LC-3 instructions

Video Notes

• @03:30: I say that the first subtask executes before the second because it “occupies memory higher up”. I was referring to the fact that the first subtask is graphically “higher” than the subtask below, but don’t confuse this with the actual memory addresses of the two subtasks, which go from low to high.

Additional Resources

• “Introduction to Computing Systems”, Section 6.1

• How to Solve Coding Problems with a Simple Four Step Method (Free Code Camp)

• Flowcharting programs that I like

  • Flowgorithm.org: Let's you draw flowcharts easily and even converts them into any of over 18 programming languages, including C++, Java, and Python (LC-3 assembly is not included, unfortunately!).

  • Draw.io: Drafting program to create lots of different types of diagrams.

  • ASCIIFlow.com: Let's you draw basic shapes and lines using ASCII art to easily copy/paste into code files. Probably not the best software for creating/editing a flowchart, but the ability to paste a final flowchart directly into your assembly files is pretty cool.

Exercises

• End-of-chapter questions 6.1-13, 18, 26

• Draw a flowchart for a process you’re familiar with (e.g. picking some music to listen to, driving to your favorite restaurant, doing a hobby, etc). Be as specific or as general as you want, but try to be as accurate as you can (i.e. be sure to include all of the conditionals and/or iterations you would normally take during that process).

• True or false (for each line below): This line of pseudocode can be converted directly into LC-3 machine code (i.e. into a single line of LC-3 machine code).

  • Reset R0 to 0

  • Display the value of R1

  • Subtract R2 from R1 and place the result in R0

  • Decrement the counter (in R4)

• Describe the process of sequential decomposition in terms your non-engineering parents could understand.

• Compare and contrast the conditional and the iterative constructs.

• Draw a flowchart to depict the process you use for [getting ready in the morning, getting ready for bed, cooking your favorite meal, planning a trip, planning a party, buying a present for someone]. The finished flowchart must have 5-10 boxes (not including the start/end boxes) and must use both the conditional and the iterative constructs at least once each (be creative if your normal process wouldn’t necessarily include a conditional or iterative construct).

• Write a program in LC-3 machine code to [increment, decrement, add, find the max of, find the min of, AND, OR, XOR] the list of numbers starting at memory location x3100. The final number in the list is [at memory location [x3105-x310F], marked by a 0, marked by xFFFF, at an address specified in memory location [x30F0-x30FF]].

(MUST DO) Assembly Language

Objectives

• Define an assembly language

• Write short (~10 LOC) programs in LC-3 assembly language

  • Describe the instructions in the LC-3 assembly language

  • Describe the pseudo-ops in the LC-3 assembly language

Video Notes

• I don't think I mention at all in the video that comments (textual notes embedded in a program) are marked by a semi-colon, ";", like below. If the assembler encounters a semi-colon, it will completely ignore anything that comes after it on that line.
  ; This is a comment
  A few good notes about writing code comments are:

  • Don't explain what something is doing, explain why it's doing it
    ADD R0, R0, R1 ;Add R1 to R0 <-- BAD! This is redundant.
    ADD R0, R0, R1 ;Add the offset to the <-- Better; there's some explanation
    ;base register here
    ADD R0, R0, R1 ;Get the address of <-- Even better! Now we know what the
    ;the next value in purpose of this line of code is.
    ;memory to operate on

  • Don't write comments for anyone else, write them for yourself in 4 weeks when you re-read your code and think, "What the heck was I doing here?!"

  • Start your code by writing comments that resemble pseudo-code. This gives you a skeleton onto which you can attach the actual code (helping to avoid the "blank page" syndrome) and it alleviates much of the need to comment the code when it's finished later on!
    ;*********************************************************
    ;* Program to multiply two numbers in R0 and R1 together *
    ;*********************************************************
    ; Clear a register to use as the accumulator (R2)
    ; Add the multiplicand to the accumulator (R2 <-- R2 + R0)
    ; Decrement the multiplier (R1 <-- R1 - 1)
    ; Repeat until the multiplier reaches 0

• @08:15: I mentioned that labels are optional (@04:40) and this is true even for the three assembler directives that set aside memory locations: .FILL, .BLKW, and .STRINGZ! The only application I can think of for this, though, is if you wanted to create an array of pre-computed values (the Python code would look something like "myList = [0,1,2,3,4]"). In that case, you can use .FILL to set the contents in memory to the initial values and only provide a label, the array name, for the first element, like this:
  myList .FILL 0
  .FILL 1
  .FILL 2
  .FILL 3
  .FILL 4
  If you didn't care that the array had any initial values, though, (i.e. "myList = [0,0,0,0,0]") you would just use the much simpler .BLKW:
  myList .BLKW 5

• @10:48: “comma, for the next opcode” should be “comma, for the next operand”

• @11:20: I state that things like .FILL can be intermixed with code, but this isn’t actually true! The reason is that the assembler will convert that directive into a literal value and store it in memory in exactly the place in code where it was typed in the assembly file. If the LC-3 starts executing this function at memory location x3000, then it will incorrectly interpret the data value as an instruction. All data values (i.e. .FILL, .BLKW, and .STRINGZ directives) should only be placed at the end of the function, after a HALT, RET, or RTI instruction and before the .END directive.

Additional Resources

• “Introduction to Computing Systems”, Sections 7.1 and 7.2

• If you know a little bit of C, this resource from Colorado State University will help you translate C-style programming idioms into LC-3 assembly language.

Exercises

• End-of-chapter questions 7.1, 3, 5, 7-9, 11, 12, 14-31, 33-37

• Convert a previously written flowchart or machine code program to assembly language. Add meaningful comments.

• Which opcodes require zero operands? One? Two? Three? More?

• What’s the difference between .FILL and .BLKW?

• Describe a valid label in LC-3 assembly (i.e. give some examples of invalid labels and describe why they are invalid).

• Write a single line of assembly to [add R3 and R4 and place the result in R2, load R1 with the value in memory at location x4000, inform the assembler that the end of the program has been reached].

• Write a program in LC-3 assembly code to [increment, decrement, add, find the max of, find the min of, AND, OR, XOR] the list of numbers starting at memory location x3100. The final number in the list is [at memory location [x3105-x310F], marked by a 0, marked by xFFFF, at an address specified in memory location [x30F0-x30FF]].

(SHOULD DO) The Assembly Process

Objectives

• Describe the assembly process

• Describe the purpose and usage of the symbol table

Additional Resources

• “Introduction to Computing Systems”, Sections 7.3 and 7.4

Exercises

• End-of-chapter exercises 7.2, 4, 6, 10, 13, 32

• Construct the symbol table for a previously written LC-3 program (such as Figures 4.7, 5.13, 5.15, 5.17, 6.6, 6.9, 6.11, 7.1, or 7.2).

• Describe the assembly process. What’s the purpose of the symbol table? Why are two passes required?

• Describe the purpose of the linker.

(MUST DO) Intro to the LC-3 Simulator

Objectives

• Describe the purpose of the simulator and what is being simulated

• Use the simulator to write, assemble, load, and run an LC-3 program

Additional Resources

• LC-3 Simulator

• LC-3 Tutor

Exercises

• Follow along with the LC-3 tutorial in “Patt_IntrotoComputing_3e_Guide to Using LC3Tools” (specifically Chapter 3).

• Enter a previously-written assembly program into the editor of the simulator. Assemble, load, and run the program. Do the results match your expectations?

• Write an assembly program that uses at least 6 different LC-3 instructions and 4 different assembler directives. Run your program and ensure that the results match your expectations.

(SHOULD DO) Debugging

Objectives

• Describe a systematic process of debugging

• Describe some debugging “anti-strategies”

• Use a simulator/interactive debugger to fix erroneous code

Additional Resources

• “Introduction to Computing Systems”, Section 6.2

• Blogs

  • How to Debug (John Regehr)

• Books

  • Debugging (David Agans)

    • Website

    • Book

  • If I Only Changed the Software, Why is the Phone on Fire?

  • Debugging by Thinking: A Multidisciplinary Approach

  • Why Programs Fail: A Guide to Systematic Debugging

  • Debug It!: Find, Repair, and Prevent Bugs in Your Code

Exercises

• Enter the sample programs in Section 6.2.2 into the LC-3 simulator and follow along with the textbook as it describes the process of using the interactive debugger to find and fix the programming errors.

  • Why do the author's place the breakpoints where they do?

  • What is the "smoking gun" (i.e. the wrong value or incorrect operation that pointed to the erroneous code) for each problem?

• End-of-chapter questions 6.14-17, 19, 21-27

• Read How to Debug (John Regehr). Does anything in that article clarify or amplify your previous understanding of how to debug?

• Recall a recent error you made while programming. Describe how you identified the error, how you found the error, how you fixed the error, and what the error was. Add the error to your list of things to check in future debugging situations. What could you have done differently next time to have avoided the error or at least to have found it faster?

(ASPIRE TO DO) Intro to the LC-3 Microarchitecture Simulator

Objectives

• Describe the purpose of the simulator and what is being simulated

• Use the simulator to write, assemble, load, and run an LC-3 program

Additional Resources

• LC-3 editor

  • You'll need the software above to write programs that work on the microarchitecture simulator; the LC-3 Tools software is too new.

  • Once downloaded, run the program called "LC3Edit.exe" and enter your code.

  • Don't enter more than one set of .ORIG/.END assembler directives (the editor can't process more than one set) and don't enter the TRAP instruction (the simulator won't process it).

  • Once you've entered your code, click the "asm" button at the right of the row of buttons at the top of the window.

• LC-3 microarchitecture simulator

Exercises

• Enter a previously written assembly program into the editor of the simulator. Assemble, load, and run the program. Can you predict what is going to happen on each clock cycle?

(MUST DO) Subroutines

Objectives

• Describe the LC-3 instructions that allow for procedure calling

• Describe the effect of those instructions on processor state

• Write LC-3 programs that call subroutines and can be called as subroutines, taking into account caller- and callee-saved registers

• Trace an LC-3 assembly language program that makes subroutine calls

Video Notes

• The callee-saved registers are probably more accurately defined as "any used by the subroutine, not including any registers used to return values to the calling program." In other words, if a subroutine returns a value in R1, then it needn't save and restore that value (how would it restore the value anyways, if there's already a return value in R1?). Regarding registers that are used as inputs to the subroutine, it is up to the programmer whether or not they should remain unchanged and that decision should be reflected in the subroutine's documentation.

• For example, imagine a MULTIPLY subroutine that multiplies two values in R0 and R1.

  • The documentation for the subroutine should specify if R0 and R1 (the input values) are affected at all when the subroutine runs.

  • If the return value is placed in R2, then there's no need for the subroutine to save and restore R2.

  • If the subroutine uses any other register (i.e. R3-R7), however, then it needs to save and restore those values.

Additional Resources

• “Introduction to Computing Systems”, Section 8.1

• Subroutine_test.asm

Exercises

• End-of-chapter questions 8.11, 14

• Assume that a subroutine called FOO is written which [squares, doubles, negates, etc] a number in R1. Write a program to perform FOO on a series of numbers. What else do you need to know about the return value of FOO to call it correctly? Make an assumption about that and document it.

• Write the subroutine FOO to do the thing you picked above.

• Figure 4.7 depicts a multiplication program. Rewrite this program to be a subroutine and then write another program to perform exponentiation which calls the multiplication program repeatedly to perform x^y (e.g. 5^4 = 5 * 5 * 5 * 5).

• Edit the above exponentiation program so that it is a subroutine. Then write a program to call the exponentiation subroutine. It's like subroutine inception!

• Write a subroutine in LC-3 assembly language and then a program that calls that subroutine. Use either simulator to run your code; can you predict what is about to happen on each clock or instruction cycle before it happens? Can you identify every change that happens to the processor as a result of the JSR(R) and RET instructions?

• Ask a friend to write a subroutine, such that you don’t know exactly how it’s implemented. What’s important for you two to agree on in order for you to use that subroutine correctly, despite not knowing the complete implementation? Write a program that uses that subroutine and check that you can call it correctly. Then switch roles.

• How does the execution of JSR(R) change the state of the processor (i.e. which registers and/or memory locations are changed as a result of the JSR(R) instruction and what are their new values)? What are the differences between JSR and JSRR?

• Write a subroutine called FOO to do something useful. Other than its name, what about the arguments to and return value of FOO does another programmer need to know in order to call it correctly?

(MUST DO) Stacks

Objectives

• Describe a stack and the push/pop operations

• Determine the values in a stack after a number of various push/pop operations, accounting for overflow and underflow

• Describe how a stack can be implemented on the LC-3

• Trace an LC-3 assembly language program that utilizes a stack

Additional Resources

• “Introduction to Computing Systems”, Section 8.2

• Stack simulator

Exercises

• End-of-chapter questions 8.1-9

• A stack of infinite size is subjected to the following operations:
  

00) PUSH A

01) PUSH B

02) PUSH C

03) POP

04) PUSH D

05) POP

06) POP

07) PUSH E

08) PUSH F

09) POP

10) POP

• If the stack starts empty, what does it look like after the above operations?

• Were there any operations that caused underflow? Which ones?

• What is the smallest size of stack that would be needed for this series of operations in order to eliminate any overflow?

• • What would be the output stream for this series of operations if the size of the stack was half (rounded down) of what it would need to be from (c) to eliminate any overflow?

• What is the purpose of R6 in implementing a stack on the LC-3? What is R6 called when it’s used in this manner?

• If the input sequence for a stack is [A], what sequence of PUSH and POP operations would result in the following output stream: [B]? Write the LC-3 assembly instructions to implement that series of PUSHes and POPs (you may assume that the stack pointer has been initialized correctly and that the stack is large enough to hold all of the values).

(SHOULD DO) Strings

Objectives

• Using ASCII encoding, convert English letters and the numbers 0-9 into binary values and back

• Describe the purpose of the nul (i.e. zero) terminator in marking the end of a string in memory

Additional Resources

• “Introduction to Computing Systems”, Section 8.5

Exercises

• Convert your favorite quote, phrase, or catchword to ASCII. If that message were located starting at memory location x3100, what would the memory values look like for that message and how many memory locations are needed to store the complete message?

• Write a subroutine to:

  • Convert an ASCII character in R0 from lower-case to upper-case

  • Convert an ASCII character in R0 from upper-case to lower-case

  • Convert an ASCII character in R0 (0-9) to an integer

  • Convert an integer in R0 (0-9) to ASCII

  • Count the number of characters in a string

  • Capitalize the first character in a string, if it isn’t already

  • Verify that a string contains only [alphabetic, numeric, alphanumeric, non-whitespace, non-control] characters

(ASPIRE TO DO) Recursion

Objectives

• Define recursion

• Identify a recursive function and describe it’s “base case”

• Explain how a stack is needed to support recursion

Video Notes

• @03:25: My notes show R1, R0, and R7 as being pushed on to the stack, in that order. To more exactly match Figure 8.14 from the textbook, I should have shown those registers being saved in this order: R1, R7, R0. This matches the code from Figure 8.14 that comes after "JSR FACT", in which R0 is popped off the stack first (to compute n * (n - 1) ) and then R7 is popped off the stack (to get the return linkage).

• @03:25: To clarify, R1 and R0 are callee-saved registers and R7 is a caller-saved register.

Additional Resources

• “Introduction to Computing Systems”, Section 8.3

Exercises

• End-of-chapter questions 8.10, 13

• Enter the code from Figure 8.14 (recursive FACT) into the LC-3 simulator. Add code to call that subroutine with a large enough value that FACT gets called at least 3 times (don’t forget to initialize the stack pointer!). Set an appropriate breakpoint and run the program so that you can see a minimum of 3 function calls in the program stack (i.e. the stack looks like it does on the right hand side of Figure 8.15). Take a screenshot of the stack and paste it below. Annotate each item in the stack, describing what it is and showing that it matches the values listed in Figure 8.15 (i.e. the value for something like “n+1” is actually equal to the variable n plus 1).

• Enter one of the recursive formulas from Section 8.3 into the LC-3 simulator and follow along with the textbook as they are traced. Pay particular attention to how the contents of the stack change with each recursive call and return.

• Write a recursive function in LC-3 assembly (some examples are here; “Count Down and Up” is probably the easiest to get started with) and test to make sure it works. Then try to write an iterative solution for the same problem. Which was more straightforward?

(ASPIRE TO DO) Queues

Objectives

• Describe a queue and the insert/enqueue and remove/dequeue operations

• Determine the values in a queue after a number of various insert/remove operations, including accounting for wraparound, overflow, and underflow.

• Determine if a queue is full or empty

Additional Resources

• “Introduction to Computing Systems”, Section 8.4

• Queue simulator

Exercises

• End-of-chapter questions 8.1-9, replacing “stack”, “PUSH”, and “POP”, with “queue”, “INSERT”, and “REMOVE”.

  • What size of queue is needed so that there are no overflow errors? Complete the exercises using that size of a queue and again with queues of various sizes that are less than that value.

• A queue of infinite size is subjected to the following operations:
  

00) INSERT A

01) INSERT B

02) REMOVE

03) INSERT C

04) INSERT D

05) INSERT E

06) REMOVE

07) INSERT F

08) REMOVE

09) INSERT G

10) INSERT H

• If the queue starts empty, what does it look like after the above operations?

• Were there any operations that caused underflow? Which ones?

• What is the smallest size of queue that would be needed for this series of operations in order to eliminate any overflow?

• What would be the output stream for this series of operations if the size of the queue was half (rounded down) of what it would need to be from (c) to eliminate any overflow?

• Why can a queue with N spots only hold N-1 pieces of data?

• Are the following queues full, empty, or neither?

Going Further

• Write another subroutine that's more difficult or more complex! Refer again to the list here or come up with another one on your own.

• What are some other ways to document software? (There are lots, but of late I'm partial to the C4 model.) See if you can find another way to compare against what you've done here or if you can improve upon it in some way.

What to Submit

• Your documentation that includes the descriptions of your high-level algorithm, detailed algorithm, and demonstration code.

• Your commented assembly file, with the subroutine and demonstration code.

• OPTIONAL: Any supplemental files, such as draw.io files, image files, etc.