Detailed schedule and resources for COMP251

Class 1: Monday, August 27

Minilab:

• Read, then run each of the methods in CodeParadoxes.java. Make sure you clearly understand the output you would expect from an "ideal" computer (whatever that means!). Then make a note of the different output that was actually produced.
• Choose one of the code paradoxes you just observed. (I recommend choosing the infinite loop, unless you already know the answer.) By editing, debugging, and investigating the code, see if you can come up with an explanation resolving the paradox. If you cannot fully explain the paradox, at least try to determine some of the circumstances which trigger it.

We may also have time to discuss the paradox in SheepTracker.java.

Class 2: Thursday, August 30

• The Knob & Switch Computer Assembly Language
• The Knob & Switch Computer with Assembly Programming

Challenge 1: implement MM[9] = MM[8] - MM[7] on the knob and switch computer above.

Challenge 2: find out as much as you can about the hardware of the computer you're working on (CPU specs, memory specs, disk drive, and anything else you can think of).

If there's time, we'll do a quick mini-lab that will get you started on Homework exercise 1.5, using SmallProgram.java as a starting point. As a reminder, here are some basic terminal commands useful for compiling a Java program:

• pwd: print working directory i.e. print the name of the directory you are currently in
• cd somewhere: change directory to the folder "somewhere" e.g. cd Desktop if you have saved your Java file on the desktop.
• ls: list contents of current directory
• ls -l: detailed listing of current directory
• ls -l *.java: list details of all Java files in the current directory
• ls -l SmallProgram.*: list details of all files whose names start with "SmallProgram"
• javac SmallProgram.java: compile the Java file SmallProgram.java
• java SmallProgram: run the main method in SmallProgram
• Don't forget, you can use the up-arrow key to go back to previous commands. And you can use the tab key to complete most commands.

Class 3: Monday, September 3

Minilab 1:

• code: unsigned.c
• to compile, use gcc -o unsigned.exe unsigned.c (ignore the warning message)
• to run, use ./unsigned.exe
• attempt the challenges given as comments in the code

• code: ascii.c
• attempt the challenges given as comments in the code

• Create a short text file containing a few characters, such as your name.
• View the contents of the file in hexadecimal using the UNIX command "od -x filename"
• Experiment with other options to od, e.g. -o and -s. Read the man page ("man od") for more details.

Class 4: Thursday, September 6

Class 5: Monday, September 10

Class 6: Thursday, September 13

Class 7: Monday, September 17

Announcement: solutions to homework assignment 1 are now available on Moodle.

The textbook's table 2.2 (page 63 in 2nd edition, page 71 in 3nd edition) is extremely important, but difficult to understand. Here's my explanation of the table.

Minilab using SignedIntExperiments.java:

1. Don't try to understand the code. Skip to the main method, and make sure you understand its output.
2. Do the challenge exercise in the comments at the end of the code.
3. Now go back and try to understand the code, especially makeBitString().

As discussed in the lecture, Java gives no warnings about integer overflows. This article discusses one way of adding such warnings to Java -- it is rather advanced, and requires you to learn something about Java byte code, but if you're interested in this kind of thing, is well worth it.

Minilab code: FloatingPointExperiments.java

Some further experiments to try at home:

1. Compute (0.1+0.2)+0.3 and 0.1+(0.2+0.3) in Java. Are they the same? Explain your result.
2. Write some Java code that will initialize a double to 1.0, then repeatedly multiply its value by 10, printing out the result each time. What happens? Why? Can you explain the exact time at which things start to go wrong?

Class 8: Thursday, September 20

Today's lecture notes on Boolean algebra and logic gates.

For interest only: Some brief excerpts from George Boole's Laws of Thought (1854).

Minilab 1: Use TruthTable.java to check your own computation of the truth table for a Boolean function of three variables.

Minilab 2: If we have time, we will acquaint ourselves with SimCir, a nifty circuit simulator by Kazuhiko Arase. Instructions:

1. Download simcir.zip by clicking on the "binary" link on the SimCir page.
2. If it does not unzip automatically, double-click on simcir.zip; you should now see simcir.jar and a few other files.
3. Double-click on simcir.jar. (If that doesn't work, use the command line "java -jar simcir.jar".)
4. Create inputs A, B, C by dragging the "toggle switch" tool, then double-click to rename.
5. Send some power to the inputs by dragging the "D.C. 5V" tool, and connecting it to each of the inputs.
6. Create an output by dragging the "LED" tool.
7. Connect the inputs to the output using your favorite circuit. Click on the inputs to toggle them on or off. Check that the output lights up when you expect it to.

Class 9: Monday, September 24

Today's lecture notes on combinational circuits.

Some beautiful JavaScript demos of important circuits by Ken Bigelow: half and full adders, multiplexer, decoder.

Circuit puzzles from the textbook authors.

Minilabs: See previous class for instructions on installing and using SimCir. Then use SimCir for the following (save these in separate files for later use):

• create a 1-to-2 decoder in SimCir
• create a 2-to-1 multiplexer in SimCir
• build a ripple carry adder with several digits in SimCir
• expand your decoder and multiplexer to more digits

Class 10: Thursday, September 27

• Lecture notes on sequential circuits.
• An explanation of the instability of the SR flip-flop.
• More circuits by Ken Bigelow:
  • SR flip-flop
  • SR flip-flop with a clock
  • edge-triggered SR flip-flop -- how does this differ from the immediately previous link, "SR flip-flop with a clock"? What are its advantages and disadvantages?
  • ripple counter -- how does this differ from the binary counter studied in class? What are its advantages and disadvantages?
• circuit puzzles handout

Class 11: Monday, October 1

An interesting experiment with word sizes: can we explain the output of the program WordSizeExperiment.c, in terms of the word size of the machine it is run on? Additional exercise: (i) add some code that performs a similar comparison of the cost of performing addition on bytes; (ii) run the same experiment using multiplication rather than addition.

Check out the Intel spec for examples of what kinds of registers are present (fig 3-1 on p59 is a great place to start; see also the 64-bit setup in fig 3-2).

Class 12: Thursday, October 4

Today's lecture notes on introduction to assembly language.

You'll need the MARIE simulator from the textbook's student resource page. Steps to create and run an assembly language program:

1. run MarieSim.jar
2. in simulator: File | Edit
3. in editor: Type program
4. in editor: File | Save (saves text file as *.mas; if it does not automatically give your file a ".mas" extention, then manually add ".mas" to the end of the filename)
5. in editor: Assemble | Assemble current file (creates machine language file as *.mex)
6. [optional] in editor: Assemble | Show assembly listing
7. in simulator: File | Load (load the .mex file)
8. in simulator: Run | Run (you can experiment with single stepping)

Here's a zip file containing a simple example program that adds two numbers, and another program that we will discuss in class: simpleAdd.zip.

Class 13: Monday, October 8

Today's lecture notes on assemblers and symbol tables.

Here's a zip file containing a simple example program demonstrating the skipcond instruction: simpleSkip.zip.

Here's a much more readable version of the same program using labels: simpleSkip2.zip.

Class 14: Thursday, October 11

Class 15: Thursday, October 18

Today's lecture notes on subroutines and loops.

ZIP file of assembly language demos for the JumpI, AddI, JnS, and Clear instructions, and a subroutine.

Fixed version of subroutine demo: subroutineDemo2.zip

Instructions for minilab:

1. Download the above zip file of assembly language demos.
2. Extract and open the file subroutineDemo.mas in MARIE.
3. Run the code and make sure you understand the result.
4. Complete the challenge exercise given at the bottom of the code listing. That is, alter subroutineDemo.mas to achieve the result X=(4*X-1)*4*4.
5. Write subroutine that multiplies two positive integers X and Y, storing the result in Z.
6. Use your answer to write an assembly program that computes the product of five numbers.
7. Can one subroutine call another subroutine? Give examples or counterexamples.
8. Can a subroutine call itself? Why or why not?

Class 16: Monday, October 22

Please take the mid-semester survey.

Project 3 has been posted -- please read it and bring any questions to the next class.

Today's lecture notes on further assembly language (specifically, describing one reason we learn assembly language, and self-modifying code).

Demo of the importance of understanding assembly language: Counter.java. The strange behavior of this program can only be explained by understanding the instruction set of the computer on which it's run.

Demos of self-modifying code.

Special homework question (label this as "class 16 homework"): Write a MARIE assembly language program with the following properties. There is a location labelled N storing a positive integer n. There is a label Array marking the start of an array containing n integers. There is a location labelled Value storing an integer value. There is a label Answer that will store the answer of the computation. The program must output (i.e. store in Anwser) the number of elements of the array which are greater than value. You may assume that Value and all elements of the array are nonnegative [added 11/5/12]. The program must use the subroutine you wrote as the solution to the textbook exercise 4.20 (2nd ed.)/4.32 (3rd ed.). Important hint: manipulating arrays in MARIE requires some special tricks. Look carefully at arrayDemo.zip in order to understand the techniques you will need.

Class 17: Thursday, October 25

Today's lecture notes on real world architectures.

Examining this java program in the Eclipse debugger shows some aspects of the call stack: StackDemo.java.

Examining the assembly language from the following C programs gives some interesting clues about real-world assembly language: variables.c, subroutine.c, loop.c.

The Intel spec contains all the gory details of a real assembly language. Glance at this for interest only; there is nothing in this document that you need to know.

Class 18: Monday, October 29

Class 19: Thursday, November 1

Today's lecture notes on instruction set design.

Here is a C program we can use to determine the endianness of the lab machines: endian.c.

• To compile, use gcc -o endian.exe endian.c
• Ignore any warning messages.
• To run, use ./endian.exe

Suggested extra practice exercises (3rd edition): Ch 5, exercises 1a, 1b, 4, 8, 17. Solutions are in the back of the textbook.

Class 20: Monday, November 4

Today's lecture notes on pipelining and real-world ISAs.

Suggested extra practice exercises (3rd edition): Ch 5, exercises 19 and 25.

Java bytecode minilab

Here is a simple Java program that we can compile, then disassemble, to understand something about Java bytecode: Mult.java.

Here are the steps to follow for this minilab:

• Compile the Java source code: javac Mult.java. As you know, this produces a Java class file called Mult.class.
• Disassemble the Java class file: javap -c Mult. This will show on the screen the complete listing of JVM instructions (also known as Java bytecode) in the class file. For convenience, save the bytecode in a text file called bytecode.txt so you can examine it later. Do this by redirecting the output using the ">" character:

  javap -c Mult > bytecode.txt

• View the raw contents of the Java class file. To do this, we will use a simple program called "od" which stands for "octal dump." The precise command line to use is: od -Ax -t x1 Mult.class. This will show on the screen a listing of the binary content of the class file. The left-hand column shows the hexadecimal addresses within the file, and in each row we see 16 bytes of the file's contents displayed in hexadecimal. Again, let's use redirection to save the output to a text file so we can easily examine it later:

  od -Ax -t x1 Mult.class > rawBytes.txt

• Now open the two text files bytecode.txt and rawBytes.txt in any text editor, such as TextEdit. Notice the sequence of instructions 4-6 in bytecode.txt is iload_1, iload_2, imul. As you can see from the Java bytecode listings on Wikipedia, the opcode for iload_1 is 1b, the opcode for iload_2 is 1c, and the opcode for imul is 68. So, verify that the sequence "1b 1c 68" occurs somewhere in the file rawBytes.txt. What other Java bytecode instructions can you find?
• If you are interested, read a little bit about Java bytecode on Wikipedia. One interesting point is that the instruction set employs a stack, and so there are many instructions that do not need any explicit operands. For example, the imul instruction doesn't need any operands. It simply pops the two top elements off the stack, multiplies them together, and pushes the result back onto the stack.

Class 21: Thursday, November 8

Today's lecture notes on memory systems and performance.

A simple program for empirically determining cache sizes: CacheTimer.java. Compile it, then run using the commandline java CacheTimer N, where N is the size of an array of integers whose random access time you want to estimate.

Some cool results from CacheTimer.java.

Class 22: Monday, November 12

Class 23: Thursday, November 15

Class 24: Monday, November 19

Today's lecture notes on cache mapping schemes.

The caching worksheet should help you to understand the three main cache mapping techniques.

Class 22: Monday, November 26

Today's lecture notes on virtual-memory.

A worksheet to help understand virtual memory: vm-worksheet.pdf.

A C program that can provide some interesting experimentation with virtual memory: bigarray.c.

Class 26: Thursday, November 29

Today's lecture notes on I/O and disk systems.

Class 27: Monday, December 3

Class 28: Thursday, December 6

Brief discussion of whether or not the course achieved its goals and what were the high-level lessons of the course: a presentation on this topic is available.

Remainder of time: individual work on final project instead. Also, revision for final exam: bring any questions to class.