Computer Architecture

Home| Course| Syllabus

Schedule

See Calendar

The schedule is preliminary and can be changed.

Lectures are divided into 3 sessions of 30 minutes with a short break in-between. The first part is a summary where I sort out the important concepts to remember from your self-reading (see syllabus). We may also do some quiz so always bring pen and paper just in case. The two remaining sessions are lectures on the topics of the day.

The reading directions on this page are for after the lecture. You are expected to read your self-read sections before the upcoming lectures. You are expected to have a quick look at the topics of the day before the lecture (see reading), typically 10 min, and then read the sections in detail after the lecture. You are invited to bring the book to take notes in it and mark what is important and/or take notes.

Lecture 1: Introduction, integers.

Exercise session:

• Read the pdf distributed to you, chapter 1 "Beyond the Desktop".
• Read chapter 1 (textbook).
• Make sure you have VirtualBox installed and working. Download and install (preferrably) the Ubuntu image located here. You should do that before the exercise session to save time. Username: "shepard", password: ".changeme." (change it).
• Have a look at chapter 2 (textbook).

Lecture:

• Introduction to the course.
• Integer representation.

Reading: Sections 2.1 and 2.2.

Slides: Introduction, Chapter 1 summary, Integers.

Lecture 2: Integers, floats

Exercise session:

• Problems 2.55, 2.56, 2.57, 2.58, 2.61 (hint: use !!x).
• Write the C code to extract bit n from an integer (0 ≤ n < 32).
• Write the C code to set to 1 bit n in an array of integers (we may have n ≥ 32).
• Write the C code to set to 0 bit n in an array of integers (we may have n ≥ 32).
• Solutions.

Lecture:

• Integer arithmetics.
• Floating points.

Reading: Sections 2.3 and 2.4.

Slides: Integers, Summary self-reading, Floats.

Lecture 3: Program and data encoding

Exercise session:

• Make sure to have solved 2.44 and 2.54 while reading.
• Problems 2.62, 2.64, 2.70, 2.74, and 2.83.
• Write a function to count the number of bits in an integer.
• You can try problem 2.65 if you want a challenge.
• Solutions.

Lecture:

• Program encoding.
• Accessing data.
• Arithmetic and logical operations.

Reading: Sections 3.1, 3.2, 3.3, 3.4, and 3.5.

Slides: Summary self-reading, Machine level programming I.

Lecture 4: Control and procedures

Note: For those who had problems with the Debian image, I have made a new image with Ubuntu with proper kernel modules installed. Unfortunately I couldn't do it for the Debian image, it was not working. I used 7-zip to compress it.

Exercise session: Use this manual to implement inline-assembly functions.

• Write C functions to rotate left and right integers. Your functions should have the following signatures:

  int rot_left(int number, unsigned int count); int rot_right(int number, unsigned int count);

• Re-implement these functions using inline assembly (hint: use rol and ror).
• Implement using inline assembly functions to set, reset, and test bit n in a bit string (represented as an array on ints, hint: use bt, btr, bts).
• Implement in C and then using inline assembly a function to return the position of the 1st bit set in an integer, e.g, pos(1)->0 and pos(12)->2. Return -1 if 0 is used as the argument. Hint: use bsf.
• After you have tried to write your code, download this solution and compile it with -O2 first and then with -O3. Compare the obtained codes, in particular look for the function calls.
• Advanced: Comment out "memory" in the clobber list of asm_test_bit in the solution. Recompile with -O2 and -O3, test and compare the binaries. Explain.

Notes:

• You may be tempted to use a debugger if you want to debug your code. To do this, use the -g flag when you compile and do not use any optimization flag. Then use kdbg as a debugger.
• You may be tempted to look at the assembly generated by the compiler. Two ways to do that: 1) compile with -S and look at the .s result, or 2) disassemble your object file (if compiled with -c) or the whole program with objdump -dC.
• Do not use explicit argument numbering in assembly, e.g., %0, %1, etc, because you will get it wrong. Tell the compiler to associate a name to whatever argument you want to use and use that name. The syntax is:

  [name] "register constraint" (expression)

  More explanations and examples can be found here.
• Don't panic. You can continue on these exercises next time.

Lecture:

• Control and procedures.

Reading: Sections 3.6 and 3.7.

Slides: Summary self-reading, Machine level programming II, Machine level programming III.

Lecture 5: Data allocation

Exercise session:

• Finish up the exercises from the previous sessions.
• Make sure you do practice problem 3.12.
• Problems 3.54 and 3.56.
• Solutions.

Lecture:

• Data allocation.
• 64-bit extension.

Reading: Sections 3.8, 3.9, 3.10, 3.11, 3.12, and 3.13.

Slides: Summary self-reading, Machine level programming IV, Machine level programming V.

Lecture 6: Introduction to Y86

Exercise session:

• Compile this example with -g (and no optimization flag). Run it in kdbg with the register view open. Click on the + to see the assembly in the code window. You can replace the rand() call by some constant interesting values, e.g., 0xffffffff or 0x11111111, etc. What is the function doing? How does it work?
• Exercise 4.43, 4.44.
• Solutions.
• Do practice problems.

Lecture:

• Y86 instruction set.
• Micro/macro code.
• Logic design.

Reading: Sections 4.1, and 4.2.

Slides: Summary self-reading, Processor architecture I.

Lecture 7: Implementing Y86

Exercise session:

• You will use the processor simulator distributed on the web-page of the book. I have compiled it for you on the VirtualBox image. If you need to compile it yourself you need to do the following.

  sudo apt-get install tklib tk-dev flex bison

  Edit the Makefile in the root and set

  TKLIBS=-ltk -ltcl TKINC=-I/usr/include/tk

  and run make.
• Try the sequential simulator and understand what it is doing on different examples present in the distribution of the simulator. Ignore the middle part of the simulator for the moment (rA, rB, etc).

Lecture:

• Sequential implementation.
• Pipelining.

Reading: Sections 4.3 and 4.4.

Slides: Summary self-reading, Processor architecture II, Processor architecture III.

Lecture 8: Y86 cont.

Exercise session:

• In the light of the previous lecture, you can now redo the exercise from last time but looking at the center part of the simulator and the tables in the book to see the updates on the internal registers rA, rB, etc.
• Try to use the pipeline version of the simulator afterward.

Lecture:

• Pipelined Y86.

Reading: Section 4.5.

Slides: Processor architecture III, Processor architecture IV, Wrap-up.

Lecture 9: RAM, Memory hierarchy

Exercise session:

• Now you can examine the center part of the pipeline simulator on some examples and understand forwarding.
• Exercises 4.47 and 4.48.
• Simplified exercise 4.46. How would you use cmov to encode:

  if (*a < *b) {   int t = *a;   *a = *b;   *b = t; }

  Here a and b are pointers to int. Be careful that cmov is quite restricted for its arguments as is the real one on x86.
• Solutions.

Lecture:

• Amdahl's law.
• RAM.
• Locality.
• Memory hierarchy.
• (Cache memory).

Reading: Chapter 5 (check the syllabus for the sections), Sections 6.1, 6.2, 6.3, 6.4, and 6.5.

Slides: Chapter 5 summary, memory hierarchy, and cache memories.

Lecture 10: Virtual memory, cache memory

Exercise session: Section 6.6. Experiment with the different matrix multiplications and generate the memory mountain for your laptop (see source code on the student site). You are also invited to try the ect tool.

Lecture:

• Cache memory.
• Virtual memory introduction.

Reading: Chapters 7. Sections 9.1, 9.2, 9.3, 9.4, and 9.5.

Slides: cache memories, Chapter 7 summary, VM concepts.

Lecture 11: Virtual memory

Exercise session:

• Exercises 6.30, 6.31, 6.32, 6,33, 6.34.
• If you're fast try 6.35, 6.36.
• Solutions.

Lecture:

• Virtual memory.

Reading: Sections 9.5, 9.6, and 9.7.

Slides: VM concepts, VM systems.

Lecture 12: Closing, exam

Exercise session:

• Exercises 9.11, 9.12, 9.13.
• Practice problems of chapter 9.
• Solutions.

Lecture:

• Processes.
• Exam preparation. You should come prepared with questions on the exam or the course.

Reading: Chapter 8.

Slides: Processes.

Re-exam

Information on the re-exam can be found here. You are advised to study the master copy of the exam here.