CA Midterm1

CA Midterm1 Review

L01: Great Ideas in Computer Architecture

1. Anything can be represented as a number.
2. Moore’s Law: The number of transistors on a chip doubles every two years.
   • Prediced based on observation of the trend in the number of transistors on a chip.
3. Amdahl’s Law: The speedup of a program using multiple processors in parallel computing is limited by the time needed for the sequential fraction of the program.
   • $S_{\text{speedup}} = \frac{1}{(1 - f) + \frac{f}{n}}$
     • $f$: fraction of the program that must be executed sequentially
     • $n$: number of processors
   • Execution time after improvement = Time affected/Amount of Parallelism + Time not effected
4. Memory Hierarchy: The more regularly used, the closer to CPU, the faster it will be.
   • CPU registers is the fastest, SSD is slowest.
5. Parallelism/Pipeline: Divide the work into multiple stages and execute them in parallel, then join them together.
6. Performance Measurement and Improvement
   • Performance: The amount of work done in a given time.
   • Performance Improvement: Increase the performance by increasing the speed of the CPU, increasing the number of CPUs, or increasing the number of instructions executed per cycle.
7. Dependability via Redundancy
   • Redundancy to avoid a failing piece causing the whole system to fail.
   • Applies to everything from datacenter to storage to memory to instructors(datacenters, disks, memory bits).

L02: Info Representation

1. Binary

• Bit: The smallest unit of data.
  • 4-bit: 1 nibble, 8-bit: 1 byte, 16-bit: 1 half word, 32-bit: 1 word.
• Everything can be represented as a number.
  • Images, sounds, videos, etc. are all represented as numbers.
  • Not necessarily binary,i.e., the assertion that everything in a computer is represented as binary is false.
• Least Significant Bit(LSB Bit 0) and Most Significant Bit(MSB Bit 31).

2. Signed Integers

• Totally three ways to represent signed integers.
  1. Sign-Magnitude: The leftmost bit is the sign bit, 0 for positive, 1 for negative. Others stay the same.
     • The range is $-2^{n-1}-1 \leq x \leq 2^{n-1} - 1$
     • Arithmetic unfriendly
  2. One’s Complement: Positive numbers are the same as the binary representation, negative numbers are the bitwise NOT of the positive number.(Flip all the bits)
     • It still has a signed bit.
     • The range is $-2^{n-1}-1 \leq x \leq 2^{n-1} - 1$
     • Arithmetic unfriendly
  3. Two’s Complement: The negative number is the bitwise NOT of the positive number plus 1. Positive one stay unchanged.
     • The range is $-2^{n-1} \leq x \leq 2^{n-1} - 1$
     • Arithmetic friendly

3. Floating Point Numbers

• FP32 - Special cases: - **Overflow**($>2.0\times 2^{128}, <-2.0\times 2^{128}$): $\pm \infty$ - All exponent = 1s and All mantissa = 0s - **Underflow**($<1\times 2^{-127},>-1\times 2^{-127}$) - Denormalized: Let exponent all 0s, representing -126, and mantissa has no implicit leading 1. - Range ($-2^{-23}*2^{-126}\sim 2^{-23}\times 2^{-126}$) - **NAN**: $0\times \infty$, $\sqrt{n},n<0$, $\frac{0}{0},\frac{\infty}{\infty}$

L03, L04 C Language and Memory Management

1. Process of Compilation

   • C Pre-processing: Handling Macro, Function-like macro(#define), text editing(Removing comments, #include)
   • Parser&Semantic Analysis:
     • Recognize each code word as a “token”
     • Record the location of each token
     • Organize tokens as AST tree
     • Report errors
   • Code Generation & Optimization:
     • Generate IR(intermediate representation)
     • IR to Assembly

2. Memory Management

   • *p = malloc(size_t size): allocate a block of uninitialized memory
   • *p = calloc(size_t num, size_t sum): allocate num*sum bytes zero-initialized memory
   • *p = realloc(void* ptr, size_t size): reallocte a block of uninitialized memory(realloc a nullptr is the same as malloc)

3. Segments

   • Stack: function invocations(start from 0xFFFFFFF)
   • Heap: dynamic memory allocation(malloc, free…)
   • Static Data(global and static bariables, allocated in compile time)
   • Code: same as text segment, saving all code

L08 CALL

1. Assembler: Change assembly language code to object code and information table.

   • Replace pseudo-instructions with real instructions
   • Encode logical and arithmetic operations
   • Encode PC-relative branches and jumps(two-pass assembler)
     • Pass 1: remember positions of labels (in symbol table)
     • Pass 2: Use label positions to generate machine code

2. Linker: Combine multiple object files(*.o) into one executable file.

   • Function call(multiple files): external references
   • Static data(global)
   • Relocate text segments, data segements from differnt files
   • Resolve addresses
     • External function reference(jal)
     • static data reference(auipc, Itype,Stype)

3. Loader: Load the executable file into memory and start the program.

   • loading is OS’s job

L09, L10 Digital circuits and systems

1. Digital systems
   • NMOS: on when $V_{Gate}=1$
   • PMOS: on when $V_{Gate}=0$
   • Synchronous Digital System(SDS) contains combinational digital system and sequential digital system.
2. Combinational logics
   Some Boolean Algebra easy to forget
   • $X+YZ=(X+Y)(X+Z)$
   • $X=(X+Y)X=X+XY$
3. Sequential logics
   • Estimating the max frequency
     • $t_{clk-to-Q}+t_{comb}\le T_{clk-period}-setuptime$
     • $t_{comb}+t_{clk-to-Q}\ge holdtime$
     • How to build a FSM circuit?