Intro to Computer Systems Final

Intro to Computer Systems notes generated from textbook

What is the principle of locality?

The principle of locality is a key concept that enables effective use of a memory hierarchy. It reflects the tendency for programs to access memory locations non-uniformly, with clusters of frequently accessed locations that change slowly over time.

What are the two main types of locality?

Temporal locality: Recently referenced items are likely to be referenced again in the near future. Spatial locality: Items with nearby addresses to a recently referenced item are likely to be referenced soon.

What does temporal locality result from?

Temporal locality arises from common program features like looping constructs, temporary variables, stacks, and frequently called subroutines. These cause the same data locations to be accessed repeatedly over a short period of time.

What does spatial locality reflect?

Spatial locality reflects the tendency for programs to access instructions sequentially and access data items stored close together, such as elements of an array or fields of a record. Nearby memory locations are likely to be referenced close together in time.

How do locality properties enable the memory hierarchy to improve performance?

Locality allows the memory hierarchy to store frequently accessed instructions and data in smaller, faster memories closer to the processor (like caches). This reduces the overall access time compared to always accessing slower main memory.

What observation did Denning make about locality based on memory references?

Denning observed that locality is based on the assertion that memory references made in the near future are likely to be to locations that were recently referenced or locations near recently referenced items.

What are the main characteristics used to categorize memory systems?

Computer memory systems can be categorized according to several key characteristics: Location (internal vs external), Capacity, Unit of transfer, Access method, Performance metrics, Physical type, Physical characteristics.

What is the difference between internal and external memory?

Internal memory is located within the processor or very close to it (like registers, cache, and main memory). External memory is located further and accessed via I/O controllers (like SSDs, HDDs, etc.).

What units are used to measure memory capacity?

Memory capacity is usually measured in bytes (B) or words. For example, a memory chip might store 4 GB or 1 million 64-bit words.

What is the unit of transfer in a memory hierarchy?

The unit of transfer is the amount of data moved between levels of the hierarchy in a single operation, which could be small (like a word), medium (like a block), or large (like a page).

What are the different access methods used by memory systems?

Random access, Sequential access, Direct access.

What key metrics are used to measure memory performance?

Access time (latency), Cycle time, Transfer rate (bandwidth).

What are the common physical types of memory?

Semiconductor (e.g., SRAM, DRAM), Magnetic (e.g., hard disks), Optical (e.g., CDs).

What physical characteristics are used to categorize memories?

Key characteristics include Volatility, Erasability, and Write capability.

What is the fundamental challenge in designing memory for a computer system?

The trade-off between capacity, speed, and cost.

How does the memory hierarchy help address the challenge in designing memory?

Divides the memory system into levels optimized for different points in the capacity/speed/cost trade-off.

What are the typical levels in a memory hierarchy and their characteristics?

From smallest/fastest to largest/slowest: CPU registers, L1 cache, L2 cache, L3 cache, Main memory (DRAM), SSD, HDD.

What are the key ideas that make the memory hierarchy work?

Temporal locality, spatial locality, caching.

How does the cost per bit and access time change as we move up the memory hierarchy?

Cost per bit increases while access time decreases.

How big should each level of the hierarchy be?

It's a trade-off between cost and performance.

What happens on a memory access in the memory hierarchy?

The processor checks successively larger levels until the data is found.

How is data exchanged between levels of the memory hierarchy?

Data is moved between adjacent levels in blocks.

What is a cache miss and why do they happen?

A cache miss occurs when the processor requests data from the cache but it is not there, requiring a fetch from a slower memory level.

How do cache misses affect performance?

Cache misses stall the processor, depending on miss penalty and miss rate.

What are the different types of cache misses?

Compulsory misses, Capacity misses, Conflict misses.

How do cache size, block size, and associativity affect miss rate?

Cache size affects capacity misses, block size impacts spatial locality, and associativity reduces conflict misses.

What are the key ideas behind multilevel caches?

They exploit temporal and spatial locality using a hierarchy of caches.

How do we measure the performance of a multilevel cache system?

Using Average Memory Access Time (AMAT).

What's the bottom line for multilevel cache design?

Caches exploit locality and differ in hit rates and access times, tailoring to workload needs.

What is cache size and how does it affect performance?

Cache size refers to the total amount of data the cache can hold; larger caches reduce misses.

What is the cache mapping function and what are the main types?

It determines where a memory block is placed in the cache; types include Direct mapped, Fully associative, Set associative.

What is the cache replacement policy and why is it important?

It decides which block to evict from a full cache; affects both hit rate and complexity.

What are the main cache write strategies and their trade-offs?

Write through propagates changes immediately; Write back reduces memory traffic.

What is the line or block size and how does it affect performance?

It's the unit of data transfer between cache and memory; larger sizes can exploit locality but may increase transfer times.

What are the main cache performance metrics?

Hit time, Miss penalty, Miss rate, leading to Average Memory Access Time (AMAT).

What are the key takeaways for cache design?

Maximize performance through trade-offs regarding locality, cache size, associativity, and optimization techniques.

What is the purpose of the cache mapping function?

Determines where a memory block can be placed in the cache, affecting hit rate and complexity.

What are the three main types of cache mapping functions?

Direct mapped, Fully associative, Set associative.

How does direct mapped cache work?

Each memory block maps to one cache location based on its address.

What are the advantages and disadvantages of direct mapped cache?

Advantages: Simple and fast. Disadvantages: Lower hit rate due to flexibility issues.

How does fully associative cache work?

A memory block can be placed anywhere in the cache, searching all locations in parallel.

What are the advantages and disadvantages of fully associative cache?

Advantages: Highest flexibility and hit rate. Disadvantages: Complex and slower access time.

How does set associative cache work?

Divides cache into sets for flexible placement with reduced conflict misses.

What are the advantages and disadvantages of set associative cache?

Advantages: Balance of flexibility and simplicity. Disadvantages: More complex than direct mapped.

How is the cache organized in a set associative scheme?

Organized as a 2D array of sets and blocks.

What are the key factors in choosing a cache mapping function?

Cache size, workload characteristics, performance requirements, power and cost budget.

What is the main goal of cache performance optimization?

To minimize Average Memory Access Time (AMAT).

What factors affect cache hit time?

Cache size, associativity, technology.

What is cache miss rate and what affects it?

It's the fraction of accesses that result in a miss, affected by program behavior and cache design.

What is miss penalty and what affects it?

Miss penalty is the time to fetch data on a miss, affected by memory technology and architecture.

What are some common cache optimization techniques?

Multi-level caches, out-of-order execution, non-blocking caches, prefetching, victim caches.

What is the CPU time formula and how does it relate to cache performance?

CPU time = (CPU clock cycles + Memory stall cycles) × Clock cycle time, showing cache performance impact.

What is the role of cache performance models?

Analytical tools for estimating cache performance metrics and optimizing designs.

What is the basic element of semiconductor memory?

The memory cell, which can represent binary 1 and 0.

What are the three functional terminals of a memory cell?

Select, control, and data.

What is the difference between DRAM and SRAM?

DRAM stores data as charge on capacitors and requires refreshing; SRAM uses flip-flops and does not.

What are the types of ROM?

ROM, PROM, EPROM, EEPROM, Flash Memory.

How are memory chips organized?

Into arrays of memory cells.

What is the purpose of chip packaging?

To mount memory chips on packages with pins for connection.

How can memory modules be organized?

To form larger systems, such as 256K 8-bit words with multiple chips.

What is interleaved memory?

Organized to allow simultaneous servicing of multiple requests, increasing rates.

What are the main objectives of an operating system (OS)?

Convenience and efficiency.

What services does an OS provide as a user/computer interface?

Program creation, execution, I/O device access, file access, system access, error detection, accounting.

How does an OS function as a resource manager?

It directs the processor in the use of system resources.

What are the types of operating systems?

Batch systems, interactive systems, multiprogramming systems.

What were the main problems with early systems?

Scheduling issues and inefficiencies.

How did simple batch systems improve processor utilization?

By batching jobs and using a monitor for sequencing.

What is multiprogramming?

Keeping multiple jobs in memory simultaneously to maximize utilization.

What is time-sharing in operating systems?

Allowing multiple users to interact with the system simultaneously.

What is swapping in memory management?

Moving processes between memory and storage to keep the processor busy.

What are the two types of partitioning in memory management?

Fixed-size partitions and variable-size partitions.

What is paging in memory management?

Divides memory into pages, corresponding to frames in memory.

What is virtual memory?

Allows processes to execute larger than available physical memory using demand paging.

What is page replacement?

Replacing an existing page in memory with a new page.

What is the Translation Lookaside Buffer (TLB)?

A cache for recent page table entries to speed up address translation.

What is segmentation in memory management?

Divides memory into segments of varying sizes representing logical units.

What are the elements of a machine instruction?

Operation code (Opcode), Source Operand Reference, Result Operand Reference, Next Instruction Reference.

What is the purpose of the Operation Code (Opcode) in a machine instruction?

Specifies the operation to be performed.

What does the Source Operand Reference indicate in a machine instruction?

Indicates the input for the operation.

What does the Result Operand Reference specify in a machine instruction?

Specifies where to store the result of the operation.

What is the Next Instruction Reference in a machine instruction?

Tells where to fetch the next instruction after the current one.

What are the common types of instructions in a machine instruction set?

Data Processing, Data Storage, Data Movement, Control.

What are the types of data transfer instructions?

Register to Register, Register to Memory, Memory to Register, Memory to Memory.

What are the common arithmetic operations provided by most machines?

Add, Subtract, Multiply, Divide.

What are addresses in the context of machine instructions?

Addresses reference memory locations and can be considered as unsigned integers.

What are the common types of numerical data in computers?

Binary integer, binary floating point, decimal.

What is packed decimal representation?

Each decimal digit is represented by a 4-bit code, with two digits per byte.

How are characters represented in computers?

Characters are represented by bit sequences using ASCII and EBCDIC codes.

What is logical data?

Logical data treats each bit of a word as an independent unit.

What are the common types of operations in machine instructions?

Data transfer, arithmetic, logical, conversion, I/O, system control, transfer of control.

What is involved in a data transfer operation?

Moving data between memory, registers, or I/O devices.

What are the basic arithmetic operations provided by most machines?

Add, subtract, multiply, and divide.

What are logical operations used for?

Manipulating individual bits of a word.

What is a conversion operation?

Changing the format or operating on data formats.

What is the purpose of I/O operations?

Handling data transfer between the CPU and peripheral devices.

What are system control operations?

Instructions that control the operation of the CPU and manage resources.

What is involved in transfer of control operations?

Changing the sequence of execution, such as jumps and calls.