Computer Laboratory

Supervisions

Supervision questions: Computer Fundamentals

This is the set of questions for my supervisions in Computer Fundamentals. I will typically email you a list of question numbers before each supervision, but if not, attempt the next two or three. (More questions will appear here as I set them, so come back if you want to make an early start on some of the future work.)

Administrativa & handing in work

I expect you to make a good attempt at producing solutions to the relevant questions before each supervision. I prefer submissions by email (PDF or text format). Please submit your work 24 hours before the supervision. If you want to submit a hard copy of the work to student administration, please hand it in before 17:00 two days before the supervision (i.e. before Wednesday, 17:00 for a Friday afternoon supervision) as I will have to scan it. Remember that Student Administration is closed on weekends.

When emailing me regarding supervisions, please only use my lab address, or your email will be misfiled and may slip by unnoticed:

The mark allocation (whilst very approximate) should give you a rough idea of how you should divide your time between the questions, as well as how much credit I expect a similar question to be worth in the exam. It will also serve as a guide for me when marking the questions.

If there is a particular part of the course you would like explaining, or questions you have about the lectures (independent of whether they are covered by the questions or not), please let me know in an email before the supervision so that I can prepare appropriately.

Supervision 1: Computer Organisation, History and Data Encodings

  1. In a brief table, outline the progression of early computer technology. Your table should look a bit like the following:
    Machine Type Logic technology Memory technology
    Babbage engines mechanical wheels and strings none
    ...
    EDSAC stored program vacuum tubes (3k) mercury delay lines
    ...
    Intel 4004 microprocessor silicon transistors DRAM
    Your table should include at least the following machines:
    • Babbage engines
    • IBM 601
    • Zuse Z3/4
    • Bletchley Park's "Colossus"
    • ENIAC
    • EDSAC
    • DEC PDP-11 or PDP-9
    • Intel 4004
    • Intel 8086
    Note that the lecture notes do not supply all the information required to fill in the table and that you may have to use extra resources (generally, Wikipedia tends to be quite good on these topics; while you should not cite Wikipedia in publications, using it to look things up for supervision work is fine!) to fill it in.
  2. [18 marks]
  3. What is the difference between executing and interpreting program code? [3 marks]
  4. For each of the components in the diagram on slide 13 of the lecture notes, write one sentence explaining its function and role inside a computer. For example: "The sound card is used to convert digital audio data received via the bus into an analogue electric representation of sound waves that can be played back by speakers." Please consider the register file, control unit and execution unit in the processor to be seperate components. [8 marks]
  5. Explain why a "Harvard architecture" is not necessarily an alternative to, but can be an implementation of a "von Neumann architecture". [4 marks]
  6. Explain the what difference between SRAM and DRAM is in terms of
    • implementation technology,
    • persistence properties,
    • speed,
    • and cost.
    [4 marks]
  7. Convert the following numbers to the respective other bases (two out of hexadecimal, decimal and binary):
    • 1100 0000 1111 1111 1110 11102
    • 1011 1010 110110
    • 4887910
    • IAD16
    [8 marks]
  8. What is the difference between one's complement and two's complement representations of signed binary numbers? Why do you think two's complement has been widely adopted? [2 marks]

Supervision 2: Further Computer Organisation and MIPS Assembly

Note: For some of the exercises in this section, you will need to use the SPIM MIPS simulator. If you use Windows, you can download it directly here. For other operating systems (Mac OS X or Linux), you will need to get the source code and build it yourself according to the instructions on the page. Please let me know if you have any issues building or running it.

  1. What are condition codes used for in a CPU and how do they relate to assembly language? [3 marks]
  2. What is the difference between little endian and big endian? What is meant by ".. and burns a considerable number of CPU cycles on a daily basis..." on slide 33? [3 marks]
  3. What is the advantage of using direct memory access (DMA) compared to using interrupts and how do they relate? [3 marks]
  4. Name four kinds of data that are encoded in different ways using binary in the memory of a computer. [4 marks]
  5. What are the three kinds of assembly instructions in MIPS? Why do you think instructions are grouped into categories like this? [3 marks]
  6. Why do procedure calls in assembly exist and how are they used? (Please give a high level description, starting by e.g. "In order to call a procedure, we first need to store the values of all registers that we wish to preserve across the call (especially $ra in the case of nested procedures), then we ..."). Explain what the term "stack" means. [5 marks]
  7. Why do you think software is not commonly written in assembly code any more? Can you think of any possible exceptions? [3 marks]
  8. By adapting the program given on slide 63 of the course handout, write a MIPS assembly program that prints "Hello, [your name]!" and exits. [2 marks]
  9. Note: I consider this question to be quite hard and time-consuming. Please do not worry if you can only make a partial attempt. A partial (or even a non-working) answer is much better than none as it helps me to understand the ways in which you are thinking!
    Further adapt the program from the previous exercise to implement the following behaviour:
    Please enter 1 to greet, 2 to change name, anything else to exit.
    Please choose an option: 1
    Hello, 
    Please enter 1 to greet, 2 to change name, anything else to exit.
    Please choose an option: 2
    Please enter your name: Malte
    Please enter 1 to greet, 2 to change name, anything else to exit.
    Please choose an option: 1
    Hello, Malte
    
    Please enter 1 to greet, 2 to change name, anything else to exit.
    Please choose an option: 0
    [end]
    

    In other words:

    • On launching it, the program prints an instruction string.
    • It then reads an integer from the console that indicates which option to choose.
    • If option 1 (greet) is chosen, the program should print "Hello, ", then the name stored in memory and finally a new line character ("\n").
    • If option 2 (change name) is chosen, the program should read a name from the console using the read integer syscall and store it in memory.

    Here is a number of hints that may help you:

    • The syscall table on slide 76 of the course handout will be useful.
    • Syscall 8 (read string) writes the string received to the memory address at $a0, so you should use the la instruction to load that address first.
    • By using .space n, where n is a number, e.g. 10, reserves memory space for n characters. Use this to get yourself some memory to use as a buffer in the read string syscall.
    • In order to go back to the "main menu" of your program, you probably want to have a main: label and branch to it using j main at the end of each of your code blocks.
    • You probably want labels and code blocks for each bit of functionality (greet, change name and exit).
    • If you need to use general-purpose registers, use the notation $t0, $t1 etc., rather than $0 and $1 used in the notes. Some versions of SPIM seem to have issues with that notation.
    • Do not forget that $0 always holds the value 0.
    [20 marks]
  10. (a) Write a MIPS program that calculates the first eight Fibonaci numbers and outputs them to the console using system call 1 (print int). [Hint: The crucial realisation here is that we can calculate Fibonaci numbers by setting a0 = 0, b0 = 1, then repeatedly doing an+1 = an + bn and bn+1 = an for n = 0, 1, ...]. Note: Please implement this yourself and do not just paste the example code from the course handout. What I am asking you to do is a simpler implementation than the one provided there – I do not expect you to use stack frames or procedure calls.
    (b) What is the last Fibonaci number that you can calculate before hitting an arithmetic overflow exception?
    [10 marks]
  11. Super-optional exercise for the keen: Do Tick 2 from the optional assembly ticks on slide 86 of the course handout. One way of implementing this would be to use Selection Sort on 10 registers loaded with values, and another would be to use the same, but store the values in memory and load them every time. Which one do you expect to perform better? Which is more scalable? (For bonus credit, implement both and measure the time they take. You can do this for example using the *nix command time (e.g. time ./spim -file tick2.s) on the Linux command line version of SPIM).