CSAPP Final Review

Overview

Q1 Data (Int & Float)

Summary

1. Data in Machine

2. Bit Manipulation

3. Signed and Unsigned Integer

4. Float Representation

Scientific Notation & numerical form

IEEE 754 float representation

rounding

calculation

(addition)

(multiplication)

conversion & casting

Quick Note for Exam

1. Integer

   • Check the range;

   • Number representation might be UNABLE, but number expression might not if the numbers in the expression are valid in range;

   • unsigned and signed in same expression, then signed will be implicitly changed into unsigned (bit pattern keeped but reinterpreted);

   • signed Tmax 01…1;

   • signed Tmin 10…0;

   • -Tmin and -0 equal themselves;

2. Float

   • total bits = s + e + f, where s, e, f stand for sign bit, exp bits, and frac bits respectively;

   • bias = $2^{exp-1} - 1$;

   • e = exp - bias for normalized, = 1 - bias for denormalized (1 stands for the implicit leading ‘1’ of float representation);

   • float = $(-1)^s * 2^e * 1.frac$ for normalized, = $(-1)^s * 2^e * 0.frac$ for denormalized;

   • denormalized: exp all 0; (special 0: exp all 0, frac all 0);

   • inf: exp all 1, frac all 0;

   • NaN: exp all 1, frac not all 0; (-NaN with a sign bit 1);

   • NaN op Any = NaN, -NaN op Any = NaN;

   • -NaN != NaN;

Q2 Data (Structure)

Summary

1. Data Size

2. Data Alignment

3. Array Distance

Quick Note for Exam

• sizeof(int **) is 8 bytes, but sizeof(int [a][b]) is a*b*4 bytes (in 64-bit machine)

Q3 Assembly

Summary

1. Assembly Basic

2. Opration

3. Control in Assembly

Quick Note for Exam

• Assembly variables, except the rax (return), rbx & rbp (callee saved), rsp (stack pointer), rdi & rsi & rdx & rcx & r8-r15 (argument & others), are all on stack

• testl src1, src2 => set CCs src1 & src2, without changing the dst (src2)

• Number of control loops can be easily counted by backward jumps.

• Be cautious when calculating the execution number of loops!

  Is the code be executed?

  What about the initialized and step out value of loop control variable?

  Is the loop inner loop? (then the cnt should be outer * inner)

Q4 Cache

Summary

4.1 Locality

4.2 Caching

4.3 Cache Performance

Quick Note for Exam

• Cache accessing time: L1 access time + L1 miss rate * (L2 access time + (… + Ln miss rate * Memory access time) )

Q5 Malloc

Quick Note for Exam

• no need to extend heap if having enough space;

• if having no block satisfying new needed block size, then malloc a new block with the size we need. cannot coalesce the new block with origin ones.

Q6 Virtual Memory, Paging and TLB

Summary

1. Access Overview

2. Table Lookaside Buffer

3. Multi-level Page Table

Quick Note for Exam

• Page Table map to the whole Virtual Address;

• TLB is a cache for physical memory;

• Page Table is a cache for virtual memory;

• Given a virtual address, first search in TLB, if hit, then found PPN; if not hit, go to the page table for next thorough search (for PPN), if valid, PPN found, if read-write role miss, page fault；then evict one entry in TLB, fill it with current entry VPN (and role stuff).

• True physical address = PPN + VPO;

• Number of entries a page table can hold: page table size / pointer size in that machine;

Q7 Process, IO, Q8 Concurrency

no enough time to make a summary for it

Acknowledgment

Most pictures are from CMU 18613 Slides.