When preparing for an exam, it is always nice to know some details about the exam. This document should help you to adequately prepare for the exam on Computer Organization after the spring-2016 edition of this course.
The exam is a written exam with a duration of 90 minutes. You typically get 4 questions to different topics. Each of these 4 questions might contain several sub-questions. For each of the 4 questions you can earn up to 25 points. You need to have at least 51 points in order to pass the exam.
On the course web you find the details of previous exams. It is a good start to have a look at these question. I would like to emphasize, though, that the course material has changed this year. Not too much, but still.
For instance, the chapter on “pipelining” is no longer part of the course material. Moreover, I have not discussed memory technologies (like static memory, dynamic memory, DDR, etc.) this year.
Instead, I have tried to change the course material such that it better connects to the course on operating systems and on all programming courses.Therefore, I added material on switching contexts, preemptive multi-tasking, shared data, and some more. In the practical, we had a close look at the stack and its typical use.
I sketch necessary knowledge and to some extent also typical questions in the text below. I have structured it along the chapters of the course material. Thus, you can always look up the course material in case you are in doubt of what a certain concept or question is about.
The questions you can find below will in most cases not be given in a 1-to-1 way in the exam. But, if you are able to understand the concepts and can answer the questions, you certainly will also be able to master the written exam.
Feel free to discuss and ask around. Feel free to ask us. However, don’t ask questions of the type “What is the answer to question x-y”. Try to answer the question by reading the course material, or checking out the presentation slides. Of course, you might also want to check out the video material which we have used in the last years. Be careful, though, here and there are changes between TOY before 2016, and TOY as of 2016.
And now for the details:
Chapter 1
– You need to be familiar with terms like CPU, main memory, reading, writing, instructions, instruction set, assembly language, assembler, simulators, types of instructions, addressing modes, pointers, address of some data, data at some address.
– You need to understand the binary number system.
– You need to understand the representation of natural numbers in the binary number system.
– You need to understand that there are always limits in the range of numbers which can be represented in the implementation of a digital system.
– You need to understand how to represent signed numbers with the 2’s complement.
– You should understand simple logic instructions like AND, OR, XOR; and how to invert bits by using XORs.
– You should understand, how the TOY computer recognizes a positive number.
Chapter 2
– You need to understand how to transform simple C-programs into their assembly-language equivalents.
– You need to understand how to simplify for-loops and while-loops.
– You need to understand how to code if-then-else at assembly-language level.
– You need to understand how to work with an array of elements at assembly-language level.
– You need to understand the use of a compiler and an assembler.
Chapter 3
– You should understand the characteristics of the various layers of abstraction which we are using in this course: functional layer, register-transfer layer, logic layer (and be able to name also electrical layer and physical layer).
– You need to understand the essence of truth-tables.
– You need to be able to develop truth-tables from simple problems like adding, if-then-else, etc.
– You need to understand how to sum several bits.
– You need to understand how to stack adders in order to sum multi-digit numbers.
– You need to understand the 2’s complement and its use.
– You should be able to describe “combinational time delay”.
– You need to know the typical logic gates and their truth-tables.
– You need to be familiar with multiplexors.
– You need to know the term “minterm”.
– You should be aware of the concept of simplifying logic functions. I will not ask you to simplify in an exam, however.
– You need to know the essence of “feedback”.
– You should be able to understand how to “latch bits”.
– You must know the function of a “master-slave flip-flop”.
– You need to know how to build a flip-flop from 2 multiplexors (and an inverter). You should also be able to analyse why such a flip-flop does what it does.
– You should be able to describe the use of “asynchronous reset”.
Chapter 4
– You should be able to explain the essence of a finite state machine. That is state, initial state, next-state logic, output logic, feedback.
– You should be able to derive an structural diagram from a state diagram, and vice versa.
– You should be able to explain the distinction between Moore machines and Mealy machines.
– You should be able to explain the potential difficulties when connecting several finite-state machines.
Chapter 5
– You should be able to work with algorithmic state machines. In an exam question, these ASMs will always be simple enough such that the truth tables involved stay small.
– You should be able to transfer an ASM diagram into a structural description on register-transfer layer and/or on logic layer, and vice versa.
– You should be able to transfer an ISE model into an ASM diagram.
– You should be able to draw the timing diagram when simulating an ASM diagram with some input values.
Chapters 6, 7, and 8
– You should be able to understand ASM diagrams of simple TOY computers.
– You should be able to implement a missing instruction in this ASM diagram.
– You should be able to derive from a simple ASM diagram the data-path or parts of it.
– You should be able to derive the controller from a simple ASM diagram.
– You should be able to understand a C-model of a simple TOY computer with, for example, 4 instructions and show its equivalent ASM diagram.
– You should be able to trace a simple assembler code clock cycle for clock cycle though using the ASM diagram of a simple TOY computer.
– About ISE models: You should be able to describe the function of an ISE model. I will not ask you to write ISE models, but I might ask you to analyze an ISE model, or derive the equivalent ASM diagram from it.
– You should be able to explain the use of a test-bed in Verilog, or tell the main components of a typical test-bed.
– You should understand the instructions “shift left” and “shift right”. In particular, you should be able to tell the difference between “logical shift right” and “arithmetical shift right”.
– You should be able to understand the 3 addressing modes “immediate”, “direct” and “indirect”. You should be able to give examples and analyze their behavior.
– Whenever “bubble-sort” pops up in a question, you should not have any difficulties in understanding this sorting algorithm.
Chapter 9: TOY with I/O
(9-1)
A simple computer consists of CPU, main memory, standard-input unit, standard-output unit. These 4 components are connected through the bus. The main memory holds 256 words with 16 bits each. The CPU outputs 1 control wire called “write”.
Both, standard input and standard output are mapped to address 0xFF. Show the details of the bus connecting the 4 components. Explain your solution.
(9-2)
A simple computer consists of CPU, main memory, and standard-input unit. These 3 components are connected through the bus. The main memory holds 256 words with 16 bits each. The CPU outputs 1 control wire called “write”.
The standard-input unit has a data register and a control register. The data register is mapped to address 0xFF and the control register is mapped to address 0xFE. Show the details of the bus connecting the 3 components. Explain your solution.
(9-3)
The standard-input unit of a simple computer consists of a data register and a control register. Explain how the control register helps the program running on the CPU to get correct data from standard input.
(9-4)
A program reads data from standard input and outputs all data on standard output. As soon as the program reads a 0 from standard input, the loop stops. This is the code in C:
char c;
int main() {
while ((c = getchar()) != EOF)
putchar(c);
}
Data from standard input are mapped to address 0xFF. Data for standard output are mapped to address 0xFF, too. The program polls the control register (mapped to address 0xFE) of the standard-input unit to find out about the availability of new data. Show a code in TOY assembly language. Explain your solution.
(9-5)
What do we mean when we talk of booting a simple computer like TOY? Sketch a program for TOY which can be used to boot an image from standard input. You can use TOY assembly language or pseudo-code. What does the image look like in your example?
(9-6)
Explain the concept of “switching memory banks”. As an example you should use a computer consisting of TOY, main memory (with 256 words) and a second memory bank (with 256 memory words). Show the connecting bus in detail.
(9-7)
Given is an ASM diagram as shown on slide 7 of the presentation slides from “Week 7: TOY with IO (and some history) 2016” (file “RO_2016_Presentation9_for_web.pdf”). Show the details of the data-path with respect to the program counter. Explain your solution.
(9-8)
Given is an ASM diagram as shown on slide 7 of the presentation slides from “Week 7: TOY with IO (and some history) 2016” (file “RO_2016_Presentation9_for_web.pdf”). Show a diagram of register file containing R0…RF at register-transfer layer. Name the inputs and outputs of the register file.
Chapter 10: TOY with stack
(10-1)
Standard TOY has two instructions called “Jump and link” (JL) and “Jump register” (JR). How can these be used for calling a sub-routine? What happens after the sub-routine has been executed? What are the limitations with this method of calling sub-routines? Explain your answer.
(10-2)
Standard TOY has two instructions called “Jump and link” (JL) and “Jump register” (JR). Why is it impossible to use these two instructions for recursively calling a sub-routine? Explain your answer by showing an example.
(10-3)
We have expanded the standard TOY with new instructions “PUSH”, “POP”, “CALL”, and “RET”. We called this new computer “S-TOY”. What are the benefits of this change? Explain your answer with an example.
(10-4)
In “S-TOY” (“TOY with stack”) we use the CPU register RF as the stack pointer. What is the stack? Explain how to create the stack. How big is the stack? Can the stack grow? Can the stack shrink?
(10-5)
In an assembler code for S-TOY (“TOY with stack”) there is a sub-routine starting at the symbolic address S. This is the code:
S PUSH R1
RET
The main program calls this sub-routine. What happens? Explain.
(10-6)
In an assembler code for S-TOY (“TOY with stack”) there is a sub-routine starting at the symbolic address S. This is the code:
S LDA R1 1
PUSH R2
ADD RF RF R1
RET
The main program calls this sub-routine. What happens? Explain.
(10-7)
You are using S-TOY (“TOY with stack”). Why is it problematic to initialize the stack pointer with the instruction “LDA RF 0”?
(10-8)
You are using S-TOY (“TOY with stack”). Why is it problematic to initialize the stack pointer with the instruction “LDA RF 0”?
(10-9)
You are using S-TOY (“TOY with stack”). Explain how S-TOY executes the code shown below. What are the contents of the CPU registers R1, R2, and RF after the execution of the code?
10: 7FF0 ; LDA RF 0xF0
11: 7101 ; LDA R1 1
12: F014 ; CALL SR1
13: 0000 ; HLT
14: F017 ; SR1 CALL SR2
15: 1111 ; ADD R1 R1 R1
16: E000 ; RET
17: 0202 ; SR2 POP R2
18: E000 ; RET
(10-10)
In addition to the stack pointer RF, we have defined CPU register RE as the base pointer. Why is is useful to have a base pointer? Explain your answer by giving an example.
(10-11)
What is the prologue and what is the epilogue of a function?
(10-12)
What is the difference between global and local variables? Explain the difference at assembly-language level or machine-language level.
(10-13)
The following C-code contains a global and a local variable. Translate this C-code to assembly language for the S-TOY computer (“TOY with stack”):
int a;
int main() {
int b;
a = 1;
b = 2;
}
(10-14)
The following C-code contains a global and a local variable. Translate this C-code to assembly language for the S-TOY computer (“TOY with stack”).
int main() {
int a;
a = 1;
}
int sub() {
int a;
a = 2;
}
(10-15)
The S-TOY computer (“TOY with stack”) has a new address mode called “base plus offset”. Explain the use of this addressing mode by giving an example. Why is it simple to expand indirect addressing with this new mode?
(10-16)
Explain what we mean by “call by value”. Give an example in C-code. Give a sketch at assembly-language level. Explain your code examples. How does a sub-routine know whether the parameters are passed by “call by value”?
(10-17)
Explain what we mean by “call by reference”. Give an example in C-code. Give a sketch at assembly-language level. Explain your code examples. How does a sub-routine know whether the parameters are passed by “call by reference”?
(10-18)
Function parameters are usually passed from the caller to the callee on the stack. Show how we can get rid of these parameters after they have been used. Why do we need to get rid of these parameters?
(10-19)
Think of a recursive function call; the function has a local variable. As an example think of this C-code:
int main() {
fak(5);
}
int fak(int n) {
int f;
if (n>1) {
f = n*fak(n-1);
return f;
}
else
return 1;
}
How can we distinguish between the many values of f? Explain your answer by sketching the code at assembly-language level.
Chapter 11: “Interrupt, timer, context switch, and shared resources”
(11-1)
What is an “interrupt”? What is a “pending interrupt”? When is A-TOY answering an interrupt? What happens when A-TOY answers an interrupt? What happens after A-TOY has answered an interrupt? Can there be a “pending software interrupt”?
(11-2)
What happens if an interrupt-service routine modifies the return address? Is this useful or is it a disaster? Explain your answer.
(11-3)
Why is it useful to have the instructions ION and IOF? Give examples.
(11-4)
Why should the register “Interrupt-enable” (IEN) be 0 at startup time?
(11-5)
How can A-TOY find out, whether an interrupt comes from the timer or from the standard-input device?
(11-5)
What is a “timer interrupt”? How do we create a timer interrupt. Why is it useful to have a timer interrupt? Explain the whole mechanism behind setting up a timer, the details within the timer device, and reacting to the timer interrupt.
(11-5)
Explain the term “context switch” in connection with a very simple computer system like A-TOY. How do we create a context switch? Use pseudo-code or assembly code for sketching the actions around a context switch.
(11-6)
How can an operating system run two processes alternating in time slices? Sketch the code in assembly language or pseudo-code.
(11-7)
What is a queue? What are the two main operations on a queue? Sketch the code for these operations. You may use a very simple queue with a maximum of 4 entries.
(11-8)
What is a scheduler? Sketch the operation of a simple scheduler which is able to run two child threads alternating in A-TOY. How can the scheduler be run again once a child process is running in the CPU?
(11-9)
Think of two processes running in A-TOY. These two processes access a shared variable. Which problems occur? Explain the problem in detail. Sketch a solution to this problem.
(11-10)
Can two processes which run in A-TOY share one code? Explain.
Chapter 12: “Fast CPU and slow memory”
(12-1)
Explain how two finite-state machines running with different clock rates can exchange data. Which roles do we usually distinguish when two machines exchange data?
(12-2)
A CPU is usually faster than main memory. Explain two typical methods of how to overcome this problem.
(12-3)
What do we understand under the technical term “protocol”? Give an example.
(12-4)
Given is an ASM diagram which shows the fetch-phase of a CPU which has no handshake protocol. The task is to change this ASM diagram such that the CPU can handle the handshake protocol.
(12-5)
Given is an ASM diagram which shows the execute-phase of the instruction LD of the CPU of basic TOY which has no handshake protocol. The task is to change this ASM diagram such that the CPU can handle the handshake protocol when executing the instruction LD.
Chapter 13: “Cache memory”
(13-1)
What do we mean with “directly mapped” in connection witch cache memory?
(13-2)
Given is a system consisting of an H-TOY-CPU (TOY with handshake protocol), a directly mapped cache, and main memory. The CPU fetches the next instruction. What happens in detail? Which situations are possible?
(13-3)
Explain the concept of “principle of locality” in connection with cache memory.
(13-4)
The cache memory needs to be able to “speak” the handshake protocol in two directions: Towards the CPU and towards main memory. What is the difference between the two?
(13-5)
How can one find out about the optimal size of cache memory?
(13-6)
Why do we need “tag” and “valid bit” inside a cache module?
(13-7)
What is a “two-way associative cache”? Explain the difference in comparison to a “directly mapped cache”.
(13-8)
What are “cache levels”? What do we understand under the term “average access speed”? What is “hit-ratio”? How do we compute the latter two? Give examples.
(13-9)
Why does cache efficiency depend on the code? Explain your answer.
(13-10)
What happens if a cache is too small? What happens if a cache is too large?
(13-11)
What do we usually mean with “least-recently used” in connection with cache memory? Explain in detail.
(13-12)
Why do we talk about “cache statistics”? Can we not measure the efficiency of cache memory exactly?
(13-13)
Why must addresses mapped to devices other than main memory not be cached? How does the cache memory get to know whether an address is mapped to main memory or not?
Chapter 14: “Arbitrating memory accesses of 2 CPUs”
(14-1)
Given are 2 CPUs with handshake interface and 1 memory module with handshake interface. The task is to show the details of how to connect the three modules.
(14-2)
Develop an ASM diagram of an arbiter which can handle 2 active partners who want to access one main memory. Explain your solution. Expand the ASM diagram such that the arbiter can now handle 3 active partners accessing 1 main memory.
(14-3)
Which problems arise when two CPUs access the same instructions in main memory? Which problems arise when two CPUs access the same data in main memory?
(14-4)
What is the purpose of a lock when two programs which access shared data in memory run on two separate CPU kernels? Describe in detail.
(14-5)
We have argued that the instruction XCH is useful for building the code for a semaphore or a lock. The instruction XCH exchanges the value between a CPU register and a value in main memory. Which implications has this instruction with respect to the arbiter?
Chapter 15: “Direct memory access”
(15-1)
Consider a DMA controller which connects auxiliary memory to the bus. Why has this DMA controller an address input and an address output?
(15-2)
Consider a DMA controller which connects auxiliary memory to the bus. The DMA controller has 4 registers mapped to addresses 0xF0, 0xF1, 0xF2, and 0xF3. Show how to build a system consisting of CPU, main memory, and DMA controller, all connected through a bus. Show the details of the bus.
(15-3)
Explain the mechanics of a DMA controller. Why do we need an arbiter if a DMA controller is part of the computer system?
(15-4)
Why is it useful to have a DMA controller? Would it not be better to let the CPU do the same job?
(15-5)
In the course material you can find the implementation of a simple DMA controller. What would happen, if the CPU would order this DMA controller a data transfer while the DMA controller is still busy with another data transfer?
Chapter 16: Virtual memory
(16-1)
What are the difficulties of expanding TOY from 8-bit addresses to 16-bit
addresses. How did we solve these difficulties? How did we change the
instruction set?
(16-2)
V-TOY and XL-TOY can address a paged memory with 16-bit addresses. We have
chosen a page size of 128 words. Explain how we still can operate with an
instruction size of 16 bits only.
(16-3)
V-TOY can handle a virtual memory space of size 2^16. This memory is organized
in pages of size 128. Explain the organization of the page table. Where in
main memory do you put your page table? How does the MMU get to know about
this location?
(16-4)
V-TOY uses a page table for translating 16-bit addresses. The page size is 128.
Let’s assume that the base address of this page table is 0x0400. On which address
would the MMU find the translation for virtual address 0x1234?. How would the
MMU figure out, how to translate this virtual address, or, alternatively,
issue a page fault?
(16-5)
The CPU of V-TOY has an input called “page fault”. Who produces this signal?
What is the value of this signal? How does the CPU react to this input?
(16-6)
What is a TLB-hit? How often does it occur? Why is it a huge advantage to have
a 2-way TLB?
(16-7)
What happens when the CPU of V-TOY gets an active “page fault” during the execution of
some instruction. How does this differ from the situation that the CPU gets an
active page fault when fetching an instruction. Explain.
(16-8)
What are the benefits of using virtual memory management? Explain in particular,
why virtual memory management helps to make the compilation of source code
simpler.
(16-9)
Explain the concept of swapping. What is its connection to virtual memory
management?
(16-10)
What is the distinction between virtual memory space and physical memory space?
Explain the benefits of using two different memory spaces. Explain the
problems.
Computer Organization @ IAIK.tugraz 