Main topics for Comprehensive Core Exam

 

Moore’s law and it’s implications to computer architecture

 

Performance measurements:

 

What is Amdahl’s law?

 

What is ISA? Examples?

 

Main reason behind RISC architecture and 80/20 rule

 

Pipeline hazards—what are they and how they are handled

 

RAW, WAW, WAR hazards

 

How Tomsulo’s algorithm works—dynamic scheduling, register renaming

 

Dynamic branch techniques—software and hardware

 

VLIW—trace scheduling

 

Why cache?

 

Principle of locality

 

Cache block placement, replacement, write through, writeback, write buffer

 

Victim cache

 

 

Below are some of previous midterm exam and final which may give you some ideas:

 

CSCI 620 Computer Architecture   MIDTERM EXAM       Spring 2006

Note: Closed book, Closed notes

3x5 cards are allowed

                                                Name: _____________________________

 

Q1: (6 points)

a) State the Moore’s Law.

 

 

 

b) What is the impact of the law to computer architecture?

 

 

 

 

Q2: (4 points) In the discussions of RISC vs CISC, what is the “80/20 rule”?

 

 

 

 

Q3: (6 points) When we measure the performance of computers(not CPUs), we often discuss the following two measures: 1) Response time 2) Throughput. Point out the difference between them.

 

 

 

 

 

 

 

Q4: (4 points) CPU performance —for unloaded system—is measured by CPUtime

What is CPUtime ? Define it clearly.

 

 

 

 

Q5: (4 points) What is SPEC CPU2000?

 

 

 

Q6: (6 points) The number of instructions in CISC machines only increases. State two main reasons why it only increases—(not decreases).

 

 

 

 

Q7: (6 points)

1) “Make common case faster” is the outcome of whose law?

 

 

2) Give two examples where the law is applied (or can be applied).

 

 

 

 

 

 

 

Q8: (5 points) Intel CPUs are said to be “CISC(externally) but RISC(internally)”. Describe what is meant by it including the phrase “Moore’s law”.

 

 

 

 

 

 

Q9: (3 points) In the history of computer architecture, the effort to support high level languages directly by hardware failed. Why?

 

 

 

Q10: (6 points) Assume that you are an architect responsible for designing “Addressing modes”. Describe the strategy you would take in the design.

 

 

 

 

 

 

 

 

 

 

Q11: (4 points) What is “forwarding(bypassing)” in a pipelined processor?

 

 

 

 

 

Q12: (4 points) Most of the modern processors require precise exceptions. What is “precise exceptions”?

 

Q13: (10 points) Consider the following code sequence:

 

            DIV.D             F0, F2, F4

            ADD.D           F6, F0, F8

            S.D                  F6, 0(R1)                    # S.D –Store Double word

            SUB.D                        F8, F0, F14

            MUL.D           F6, F10, F8

 

1)      From the above code, identify all the dependences according to their kinds; (True) Data Dependences, Antidependences, Output Dependences.

2)      Among them, the “name dependences” can be eliminated by register renaming. Rewrite the above code so that they will not have any name dependences. Assume that we have two temporary registers, S and T.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Q14: (5 points) Scoreboarding improves ILP. What is the key idea of scoreboarding?

 

 

 

 

 

Q15: (6 points) Fill in the blanks:

RAW hazards are due to ____________ Dependences.

WAR hazards are due to ____________ Dependences.

WAW hazards are due to ____________ Dependences.

 

 

 

 

 

 

 

 

 

Q16: (21 points)The MIPS machine with Tomasulo’s Algorithm is given below:

 

 

Op – Operation to perform in the unit (e.g., + or – )

Qj, Qk – Reservation stations producing source registers

Vj, Vk – Value of source operands—temp regs for renaming

Busy – Indicates reservation station and FU is busy

Register result status –  Indicates which functional unit will write each register, if one exists.  Blank when no pending instructions will write that register.

 

An example diagram is given below. Explain the parts that are pointed by arrows from the diagram. For example: The first arrow (Write Result (for LD instruction) = 4 ) means that “At cycle 4, the LD instruction is finished—F6 is loaded(written-back)”

 

 

 

Now, you explain all other arrows:

 

a)      Arrow 2 means:

 

 

b)      Arrow 3 means:

 

 

c)      Arrow 4 means:

 

 

d)      Arrow 5 means:

 

 

e)      Arrow 6 means:

 

 

f)        Arrow 7 means:

 

 

 

 

 

Final Exam      CSCI 620 Computer Architecture                Spring 2006

Note: Closed book, closed notes. 3x5 cards are allowed.

 

                                                Name:______________________________

 

Q1(9 points): Clever instruction scheduling improves ILP.

a)      There are two scheduling alternatives; Static scheduling & Dynamic scheduling. What is the difference?

 

 

 

 

b)      What are the advantages of Dynamic scheduling over Static scheduling?

 

 

 

 

 

c)      What are the advantages of Static scheduling over Dynamic scheduling?

     

 

 

 

 

 

Q2(4 points): Software(compiler) intensive approaches for improving ILP are more likely seen in  embedded systems. Why?

 

 

 

 

 

Q3 (5 points): Cache memory exploits the concept of “Locality of Reference”. Discuss how?

 

 

 

 

 

 

 

 

 

 

 

 

Q4(5 points): A diagram for 2-bit Branch History Table is given below:

Explain the basic idea of this scheme.

 

 

 

 

 

 

 

Q5(5 points): Describe the main idea for VLIW (Very Long Instruction Word).

 

 

 

 

 

 

 

Q6(3 points): In class, we discussed: For a memory, if the size is increased, then the speed slows. Why?

 

 

 

 

Q7(20 points): For cache memory, the block placement(where can a memory block be placed in a cache?) can be done one of three ways:

1)      ____________________ 2) ___________________ 3) _________________

 

Explain each of the above:

1)

 

 

2)

 

 

 

3) Compare the 3 schemes:

Name of the scheme

Advantages

Disadvantages

 

 

 

 

 

 

 

 

 

 

Q8(4 points): Following diagram is for the Miss rate with increasing block size assuming that the total size of cache is fixed.

Discuss why the Miss rate increases as the block size increases.

 

 

 

 

 

 

 

 

 

 

 

Q9(10 points): The diagram for the Alpha 21064 Data Cache  is given below:

 

 

(a)    What kind of cache organization is it?

 

 

(b)    The numbered circles indicate the steps for Reads & Writes. Explain the operations of the cache for each numbered steps in detail for “read operation” only. Include the CPU, Vitim buffer, and Lower-level memory in your explanations.

 

 

 

 

 

 

 

 

 

Q10(4 points): What is “Content Addressable Memory”? Where is it used inside CPU?

 

 

 

 

 

Q11(6 points): Compiler techniques to increase ILP or reducing cache misses often rely on the technique called “Profiling”.

a)      Describe what is “Profiling”.

 

 

 

b)      If you are going to develop a program to do the “Profiling”, what kinds of information would your program produce as a result of profiling. List them.

 

 

 

 

 

 

Q12(10 points): Block diagram of “Tournament Predictor with  2-bit counter is given below.

a)      Describe the main idea of a “Tournament Predictor”.

 

 

 

 

 

b)      Explain why we are making the transition that is pointed by an arrow.

 

 

 

 

 

 

 

 

 

Q13(8 points): When compiler unrolls a loop with a large number of iterations, what factors should the compiler consider? List at least three.

 

 

 

 

 

 

 

 

 

 

Q14(3 points): What is “Victim cache”?

 

 

 

 

Q15(3 points): What is the main idea of Non-blocking cache or  lockup-free cache ?

 

 

 

 

 

Q16(1 points): What is the single most important thing that you learned in this course?