CSE 130 Part 5

0.0(0)
studied byStudied by 0 people
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/33

encourage image

There's no tags or description

Looks like no tags are added yet.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

34 Terms

1
New cards

What are the prefixes of kilo, mega, and giga? What are their sizes (base10)?

Kilo: k, 10³

Mega: M, 106

Giga: G, 109

2
New cards

What are the prefixes of milli, micro, nano? What are their sizes (base10)?

Milli: m, 10-³

Micro: μ, 10-6

Nano: n, 10-9

3
New cards

What is throughput?

How many tasks can be done per second

4
New cards

What is latency?

How long one task takes

5
New cards

What is energy efficiency?

How much useful work is done per unit of energy

6
New cards

Compare intrinsic and technology-dependent issues

Intrinsic: algorithmic, design-wise issues (e.g. branch prediction)

Technology-dependent: limited by current technology/hardware (e.g. battery life)

7
New cards

What is capacity?

Amount of a resource that is available

8
New cards

What is utilization?

Percentage of capacity being used

9
New cards

What is overhead?

Resource that is wasted

10
New cards

What is useful work?

Resource spent on actual work for a given workload

11
New cards

Pipelining vs Concurrency in terms of latency and throughput

Pipelining

  • Latency: Sum of all modules’ latency

  • Throughput: Min of all modules’ latency

Concurrency

  • Latency: Averaged latency by weight and module latency

  • Throughput: throughput x N (using identical modules)

12
New cards

When can input throughput and output throughput differ?

When using compression or decompression

13
New cards

Can physical data transfer be faster than over the network?

Yes, for large datasets

14
New cards

In networking, what is one example of improving performance?

HTTP pipelining
Throughput = p/RTT → Throughput = cwnd/RTT

15
New cards

In memory, what is one consideration for performance?

Latency-throughput curve— where increasing throughput can improve performance up to a point, beyond the saturation threshold, latency increases significantly and degrades performance

16
New cards

In a hard disk example, what are three ways to improve performance?

  1. Batching: handle requests as a group to amortize fixed overhead

  2. Dallying: delay a request (e.g. delay disk write because user may save again soon)

  3. Speculation: read next likely data early

17
New cards

What is burst?

A brief increase in the request rate above average

18
New cards

Why does overload happen?

When incoming request rate > average throughput for one stage. Buffers will fill up, and requests wait in the buffer → increased latency

19
New cards

What is Amdahl’s Law (Law of Diminishing Returns)?

Total speedup = 1 / ( (1-P) + P/S ) where S = speedup for the portion, P = % of the portion

20
New cards

What are 4 steps of designing for performance?

  1. Measure the system if it needs to be faster

  2. Measure again to find the bottleneck

  3. Predict the impact of removing the bottleneck

    a. Can it be removed? How effective?

    b. If not, can we redesign it?

  4. Implement new solution, repeat

21
New cards

What is workload?

Tasks processed by a system

22
New cards

We can measure performance on… (3)

  1. Real workload

  2. Simulated system

  3. Benchmarks + real traces

23
New cards

Caching vs memoization

Caching has a bounded size, whereas memoization does not

24
New cards

What is locality of reference?

Clustering of memory references in both time and address space

25
New cards

What are the two types of locality of reference?

Temporal: recent items likely to be referenced again soon

Spatial: near items likely to be referenced

26
New cards

What is a working set?

Set of items used during an interval

27
New cards

What happens when working set » primary storage?

Thrashing— frequent overwriting of primary storage

28
New cards

Write-through vs Write-back

Write-through: writing to cache and then to secondary storage immediately

Write-back: writing to cache and to secondary storage later when evicted

29
New cards

What is cache coherency?

Consistency of data across multiple caches in a system

30
New cards

What is associativity? What are the three types?

Which data can be stored in each cache slot

  1. Fully associative: data can be anywhere in the cache

  2. Direct-mapped: each data is mapped to exactly one cache line

  3. N-way associative: cache divided into sets, each set contains N cache lines

31
New cards

What is fetch policy?

When/how to fetch data (on-demand or by prediction)

32
New cards

What are the five types of removal policies?

  1. Least recently used (LRU ): every time data is used, place/move it to the head, push the rest down

  2. FIFO: place it at head if not in queue, remove the tail

  3. Clock: second chance page replacement with a circular pointer (only evict if reference bit is 0, put at head if 1)

  4. Not recently used (NRU): remove elements in the following order

    1. Not referenced, not dirty

    2. Not referenced, dirty

    3. Referenced, not dirty

    4. Referenced, dirty

  5. OPT— optimal algorithm, used for comparison

33
New cards

What is Belady’s anomaly?

For some removal policies, more cache ≠ higher hit ratio!

34
New cards

What are the three types of a cache miss?

  1. Compulsory miss— first reference (cannot be prevented)

  2. Capacity miss— can be prevented by infinite cache size

  3. Conflict miss— can be prevented by a fully-associative cache