Jun 192011
 

I wrote a list of ten items all software programmers must know about hardware. Today, I want to provide a small quiz for you to evaluate yourself. Some questions are very simple but they exist to test the fundamentals. Enjoy!

The answers to the self assessment are available here.

1. (a) How many things can you tell apart using 5 bits?

(b) Convert the 6-bit value 101110  to decimal, assuming its an unsigned number?

(c) Convert the 6-bit value 101110  to decimal, assuming its a 2′s complement number?

(d) If I define a floating point format as follows:

1 – sign bit             3 – exponent bits             3 – mantissa bits             bias = 3

What is the value of 1001111 in decimal?

2. (a) Convert the unsigned decimal number 143 into hex

(b) How will you implement the ‘==’ C operator in hardware?

3. (a) For a 2MB 8-way associative cache with a block size of 64B and perfect LRU replacement, calculate the number of sets in the cache.

(b) How many cache misses will the following code incur if the processor had the cache described in (a)?

int A[128];int B[128];    for i = 0 to 127:
  sum += A[i] * B[i]

(c) How can I reduce the number of cache misses?

A. Blocking

B. Increasing the cache size

C. Multi-threading

D. Not possible

4. I ran an experiment and found that my code runs marginally faster  on a machine with MSI cache coherence compared to a machine with MESI cache coherence. What property of the code can make MESI protocol slower than MSI?

5. Suppose we have a virtual address space of 10-bits and a physical address space of 7-bits. Each page is 32-bytes. Assume that frame 0 in physical memory is reserved for the page table. The remaining pages are managed by the OS for demand paging. A random replacement policy is used for paging. How many page table entries are required? How many bits are required in each page table entry?

6. A 2-level branch predictor has a 10-bit global history register. How much storage (in bytes) is required to implement this branch predictor?

7. (a) If I use a hash table with chaining to design a telephone directory, how many bytes of memory will be needed to save this telephone directory?

You can assume that:

All names are unique 20 byte strings
Phone numbers are 10 decimal digits

Each pointer is 4-digits

Linked lists are used to resolve collisions in the hash table

The hash table has 128 buckets

Each bucket only stores a pointer to a linked-list of all elements in that bucket .
The directory contains 1 million entries

 

(b) Suppose I replace the hash table with binary tree, how much space will then be required? (do not count the pointer to the root).

8. Compile the following line of C-code:

A[B[i++]]++;

You can assume that:

Elements of A and B, and variable i are all 4-byte unsigned integer value.

The machine has 8 32-bit registers named r0-r7

Address of A and B are in registers r0 and r1 respectively.

Value of i is in r2.

9. Optimize the following assembly code to use the fewest possible instructions and registers:

LOOP Load r1, [r0] ; load r1 from memory
     add  r2, r2, r3
     sub  r4, r2, r2
     add  r5, r2, r3
     brn  LOOP

10. When executing the following code on a 128-core multicore chip, I see a speedup of only 40x. What could be the reason?

for i = 0 to 1000000000:
  sum += A[i] + B[i]   // A and B are arrays of 4-bytes integers

Please leave a comment if you have any questions. Thanks!

The answers to the self assessment are available here.

  12 Responses to “Computer Science Self-assessment Quiz”

  1. cant view answers . I am getting the following err

    “You do not have permission to preview drafts.”

  2. Chopping the section “?preview=true&preview_id=733…” off the end of the URL to the answers page will reveal it.

    Most of these questions are above my head, (though I was pleased I could guess my way through the 2s compliment question, given that it’s ten years since I’ve touched the stuff), but I don’t seem to agree with the answers for 1b and 2a. (And having checked, neither does my calculator.)

  3. GOOD!

  4. I think it’s possible to remove the loop in Q9 altogether. Something like this?

    add r1, r2, r3
    idiv r1, r1, r3
    sub r4, r2, r2
    sub r1, r4, r1
    imul r1, r1, r3
    add r2, r2, r1
    add r5, r2, r3
    Load r1, [r0]

    I’m assuming that the machine has an integer multiply and divide, and that the loop terminates, and that it’s expected that all registers must contain the same values on exit as in the example code.

  5. What and whatnot with the internet marketing are planning! Email is among the most most basic things computer users use on a regular basis. That’s pretty the way the math works accessible.
    becgn
    http://sadas22323sdsddasdadaasdas.com
    tht ze qocf

  6. Great looking internet site. Think you did a bunch of your very ownyour very own html coding
    nhl 17 http://irakyat.my/forums/topic/12151/cheap-fifa-17-coins-to-farming-it-by-themselves/view/post_id/14328

 Leave a Reply

(required)

(required)

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>