CSCI 237

Computer Organization

Home | Schedule | Assignments | Links | Slack | Williams CS

The table below lists practice problems that test topics we emphasized in class. We recommend completing these practice problems to reinforce the course material in prepration for quizzes and exams. Some questions have answers in the textbook, but the TAs and instructors are available to answer any questions that you have about the material. You're encouraged to work together on these problems.

Problem Page Topics Covered (Notes)
PP1 PP1 Practice Problems 1
- - How do you include libraries in C? What is the return type of main? How do you compile a C program?
- - Write a C program that takes a positive integer as a command line argument and sums together that many numbers read from stdin before printing the sum to stdout.
- - Write a C program that declares an integer array of 10 elements, initializes the elements of that array to random values between 0 and 100 inclusive (see driver.c from lab 1 for help with random number generation), prints out the contents of the array, and prints out the median value in the array to stdout.
- - What is the 8 digit binary representation for 15? 16? 31? 32? 255?
2.17 65 Converting Hexadecimal to binary representations; unsigned vs. twos-complement.
-- -- Write the 16-bit twos-complement representation of the following numbers: -1, 2864, -1573
- - If w bits are able to store the two's complement representation of a positive whole number, can the negation of that number also be stored in w bits using two's complement representation? If w bits are able to store the two's complement representation of a negative whole number, can the negation of that number also be stored in w bits using two's complement representation?
2.61 (A, B) 129 C and bitwise representations of integers.
PP2 PP2 Practice Problems 2
2.22 79 Sign extension. (Equation 2.3 is on page 64)
2.23 80 Arithmetic shifting.
2.24 82 Effect of truncating on signed/unsigned.
2.29 93 Signed addition; overflow.
2.30 94 Overflow.
- - How can overflow be detected when adding/subtracting 2 unsigned numbers? 2 signed numbers?
2.68 132 C and bitwise representations of integers.
- - Why does a machine's endianness (i.e. little endian vs. big endian) matter when dealing with ints but not with chars?
- - Consider the following C code snippet. Draw a picture of each of the variables indicating what is stored in each. 
	    int val = 4, val2 = 0, val3 = 12;
	    int *ptr;
	    ptr = &val;
	    val2 = *ptr;
	    int **ptr2 = &ptr;
	    val3 = **ptr2;
- - Consider the following C code snippet. Draw a picture of each of the variables indicating what is stored in each. 
	    int arr[4];
	    arr[0] = arr[1] = arr[2] = arr[3] = 0;
	    int *ptr;
	    ptr = arr;
	    *ptr = 7;
	    *(ptr+1) = 5;
	    ptr[2] = 10;
	    ptr = &arr[3];
	    *ptr = 100;
Consider the following C code snippet. Draw a picture of what the memory associated with argv looks like when the program is invoked with the command "./hello Donuts! Yum!". Indicate what is stored in each memory cell. What will be stored in the variables c and d? 
	    int main(int argc, char *argv[])
	    {
	         if(argc == 3){
                     char c = argv[1][3];
	             char d = argv[2][4];
                 }
            }
PP3 PP3 Practice Problems 3
2.45 111 Binary fractional values
2.47 117 IEEE Floating point encoding/decoding.
2.48 119 Bitwise representation of floating point numbers
- - Consider the decimal value -718.40625.
  1. Convert this number to its IEEE single precision (32-bit) floating point representation.
  2. Convert the 32-bit binary number from the previous problem to hexadecimal.
- - Consider the hexadecimal value 0xC295D000.
  1. Convert the hexadecimal number to a 32 bit binary number.
  2. Assume this 32 bit number is an IEEE single precision (32b) floating point number. What is its decimal floating point value?
- - Write down the binary representation of the decimal number -316.5625 assuming IEEE single-precision floating point format.
- - Why did the IEEE floating point designers choose to use biased representation for the exponent field? What is the benefit of using a biased representation instead of two's complement representation?
- - In the IEEE floating point standard, representable numbers are denser closer to zero than they are at distant locations on the numberline of representable values. Why?
PP4 PP4 Practice Problems 4
3.1 182 Addressing/Operand Forms
3.2 185 Operand sizes
3.5 189 Assembly -> C conversion
3.6 192 Load Effective Address
3.7 193 Assembly -> C conversion
3.8 194 Arithmetic Operations
3.10 197 Assembly -> C conversion
- - Suppose %rsp is storing 0x100. You then push the contents of %rbx onto the stack followed by pushing the contents of %r8 onto the stack. What memory addresses are the contents of %rbx stored at? What memory address are the contents of %r8 stored at?
3.58 311 Assembly -> C conversion
3.11(A) 197 Assembly Tricks
PP5 PP5 Practice Problems 5
3.13 204 Comparisons
- - What causes the values of the condition codes to be set?
3.16 212 C if/else ↔ C goto code
3.18 213 if/else ↔ assembly
3.23 223 Compiler optimizations and mapping ASM -> C
3.24 224 while loops ↔ assembly
3.26 228 Loop translations
3.27 231 C for loop ↔ C goto code
3.28 231 for ↔ assembly
3.30 236 Switch Statements
- - How do conditional move instructions potentially improve performance? When can they negatively impact performance? When can their use result in erroneous behavior?
3.60 312 C <-> Assembly Loop transformations
PP6 PP6 Practice Problems 6
3.33 246 Procedure Arguments, Registers, & the Stack
- - Where is the 7th argument to a function call stored?
3.34 253 Local storage & caller/callee saved registers
- - If a function intends to use a callee-saved register, what must it do to ensure the application functions correctly?
- - What happens on a call instruction?
- - Which values in function() must be stored on the stack before the function call to bar() in the following code? Assume all register call conventions are followed and that you know nothing about what bar() does. 
            void function(int a, int b, int c){
	          int result = 0;
                  result = bar(a, b) + bar(a, c);
	          return result;
            }
3.35 254 Recursion
3.36 256 Arrays and addressing
3.37 257 Array/pointer/address ops and assembly
3.41 268 Struct data types
- - Explain why reordering the fields in a struct can change the amount of memory needed for an array of that struct type.
3.64 316 Multi-dimensional arrays and memory layouts
- - Suppose you had a single dimension array of ints with 100 elements. How could you use this array to represent a two dimensional array with 2 rows, where each row contained 50 entries? How would you convert the two dimensional indices, row_index and col_index, to a single value used to index into the single dimension array?
3.65 317 Arrays ↔ pointers
PP7 PP7 Practice Problems 7
4.1 360 Encoding Y86_64
4.2 360 Decoding Y86_64
4.4 370 C ↔ Y86_64
4.13 387 Instruction Processing Stages
- - Why is the latency of an instruction longer in a pipelined datapath versus a single cycle datapath?
- - What is a pipeline register and what does it do?
- - What is the ideal change in clock cycle time obtained when switching from a single cycle datapath to a n-stage pipelined datapath? What prevents us from actually achieving that ideal clock cycle time?
- - What is one way of reducing the stall time due to data hazards?
4.28 417 Pipeline stages impact on latency and throughput
4.29 418 Pipeline datapath throughput and latency
- [PDF][Solns] RAW dependences, data hazards, pipeline execution
- - What are 4 impediments to a n-stage pipelined datapath's throughput being 1 instruction / (1/n of the single-cycle datapath's clock cycle time)?
PP8 PP8 Practice Problems 8
- - Is it helpful to know that a branch is predicted taken if you do not know the branch target?
- - Suppose you have a highly predictable branch. Why might the prediction for that branch in the branch history table be wrong despite the branch being highly predictable?
- - Consider the following Y86-64 code snippet. Draw a pipeline diagram of its execution assuming a data-forwarding pipeline that uses a predict not taken scheme. For each conditional branch instruction, a comment indicates whether the branch is taken or not. 
	         irmovq $1, %r9
	         irmovq $0, %rax
                 subq %r8, %rsi
	         jle L1                # taken         
		 addq %r9, %rax
            L1:  mrmovq (%rdi), %r10
                 addq %r10, %rax
                 addq %r9, %r8
		 subq %r8, %rsi
		 je done              # not taken
		 addq %r9, %r8
           done: rmmovq %rax, (%rdi)
6.8 609 C code and spatial locality
6.9 616 Cache parameters
6.10 624 Direct-mapped caches
6.12-6.15 628 Set-associative caches
PP9 PP9 Practice Problems 9
9.1 805 Virtual Address Sizes
9.2 807 Page Table Entries
9.3 816 Address Translation
9.4 824 Address Translation with TLBs
- - Suppose you had a two level page table. Each page is 8KB and each PTE is stored in 4B. How many PTEs can be stored in a page? How many virtual pages are there in this virtual address space? If virtual addresses are specified using 35 bits, how many level 2 page tables would there be? How many valid entries would there be in the level 1 page table?
- - Suppose addresses were specified using 46 bits. Each page is 8KB and each PTE is stored in 4B. How many level two page tables would be needed in this system? Can the level one page table fit into a single page?
- - Suppose addresses were specified using 46 bits. Each page is 8KB and each PTE is stored in 4B. Suppose a three level page table is being used. How many level 3 page tables would exist? How many level 2 page tables exist? How many valid entries would exist in the level 1 page table?
PP10 PP10 Practice Problems 10
9.6 849 Implicit free lists: Block size & header values
9.7 852 Minimum block sizes
9.10 864 Fragmentation and segregated lists
9.15 879 Block sizes and alignment with implicit free lists
9.16 879 Block sizes and alignment with explicit free lists
- - How do boundary tags enable higher amounts of coalescing than only using headers in dynamic memory allocation?
- - When an implicit free list is used in a dynamic memory allocator, what is the worse case running time for finding a free block? When an explicit free list is used, what is the worst case running time for finding a free block?
PP - Some Additional Practice Problems for Final Exam Studying
- - What is a process? How is it related to a virtual address space?
- - Some exceptions can be recovered from while others cannot. On a PageFaultException, what does the operating system do in order to make it possible for the application to continue execution?
- - What is an interrupt? What initiates an interrupt and what responds to an interrupt? How is an interrupt different from an exception? What is a system call?
N/A [PDF][Sample Solutions] More cache questions
- - How does increasing the block size while keeping cache capacity constant change the number of bits needed for the tag, index, and block offset fields?
- - How does changing the associativity while keeping cache capacity constant change the number of bits needed for the tag, index, and block offset fields?
- - Why does increasing a cache's set associativity potentially decrease its miss rate? Explain why increased set-associativity can increase cache access time.
- - What is the meta data stored in a direct mapped cache? What is the meta data stored in a cache with set associativity greater than 1?
- - What happens when data is not yet in memory? Where is it? How does the system discover its not in memory, find it, and bring it into memory? (Consider the steps taken when the system includes a processor, memory management unit, TLB, and a memory hierarchy.)
- - How do caches exploit locality (both spatial and temporal)?
- - How can physical memory/DRAM be viewed as a cache? What is it caching?
- - What information is stored in each page table entry?