Comp 1313 Systems 1 Flashcards
What is a combination circuit?
An Interconnected set of gates whose output is a function of the input at a time.
What is a tri-state?
A gate with a extra input that disables the gate, used to prevent short-circuits.
How would I make a two variable Karnaugh Map?
- Create a table using your two variables, e.g A on top row and B on the first column
- Fill the next row/column with the possible values of the variables.
- Use the expression to calculate what result in 1, and place these in the table.
- Draw rectangles of size 2^n boxes around the ones. They cannot be diagonal and must be as big as possible.
How do you decipher a Karnaugh Map?
- Take each box
- If the digit in the heading stays the same keep it, otherwise discard the box
- The boxes left represent the expression
Why can’t machine code be run on different machines?
As different CPU’s have different instruction sets.
The clock is an electronic pulse. So when does the CPU perform an action?
On a clock edge
What is RISC?
Reduced Instruction Set Computer
What is CISC?
Complex Instruction Set Computer
How can runtime be calculated?
Runtime = instruction-time x cycles per instruction x Number of instructions
What is the difference between RISC and CISC?
RISC often has one instruction per cycles, while CISC instruction are more complex and therefore can take multiple cycles.
CISC will look much nicer than RISC code.
CISC aims to reduce Ninstr while RISC reduces the cycles per instruction
What is a register?
A group of flip-flops that can store multiple bits. Used as temporary storage on the processor.
What is a shift register?
They shift a bit every single clock cycle along the register. This is used to convert between serial and parallel data.
How many registers (general purpose) are needed?
16ish
Where are registers on the memory hierarchy?
Top
What is a general purpose register?
They store the CPU’s current required data.
How big is a register (general)?
Word length or more depending on if it has a specific purpose (e.g storing floating points)
What are the 6 types of registers?
Address only
General purpose
Condition Code
Status/flags
Control
Special
What can be stored in an address only register?
Just a memory address
What is the purpose of a Condition Code register?
Set of individual bits that indicate if an error has occurred.
Can a condition code register be written to be a program?
Not usually, but they can be read from
What is a Status/FLAGS register?
A register contain condition code or the sign of a result, an overflow indicator.
What are control registers?
A set of registers that are hidden by the CPU. This includes the MBR, MAR and others.
The PC is the only control register readable by assembly
What is a special register?
An additional register used for a specific function, like storing vectors. Usually implemented on CPU’s that have a specific purpose.
What is a pipeline?
Overlapping instructions with the aim to complete one instructions per cycle rather than one stage per cycle (if that).
Similar to an assembly line.
What can ruin pipelining?
Branching
How can we deal with branches?
Multiple streams
Prefetch Branch Target
Loop buffer
Branch Prediction
What is Prefetching the Branch target
Prefetch the branch target and a few instructions after before the actual branch
What is loop buffering?
Very fast memory that store the last n instructions, maintained in the fetch stage of the pipeline.
Check the buffer before fetching, and then load the buffer instead.
Good for small loops
What is Branch predicition?
Predict where you’re going to branch.
This involves predict that you either will always branch here or will never branch here.
If so we either prefetch the next instruction or the branch instructions.
How can we improve branch prediction?
Predicting by Opcode. As some are more likely to jump than others (75% success rate)
Taken/Not taken switch, use previous execution history to detirmine if it’s going to jump.
What is overloading?
Operators have different meanings in different algebras.
How many bits can be stored in a register of length n?
2^n-1
What are some benefits of biased offset?
Eliminates negative values
Simplifies comparison operations
Symmetrical range about zero
Facilitates floating point
Simpler conversion between systems
What does two’s complement avoid?
Avoids the double representation of zero
How to convert to two’s complement?
Flip every bit and then add one
How to convert to biased-n?
Add the bias to the original number and then convert to an unsigned binary number
What is biased-n?
Shifting by a bias so that 0000… would be -128 and 1111… would be 128
What is superscalar?
Doing simple commands at the same time using multiple arithmetic units.
Basically not vector or array logic
What is true data dependency?
When one instruction is dependant on another instruction happening previously and thus cannot execute together.
What is procedural dependency?
Can’t execute instructions after a branch with instructions before, otherwise we waste processor time.
What is resource conflict?
Two or more instructions request the same resource at the same time.
How can resource conflict be resolved?
By duplicating the resource
What is instruction level parallelism?
Instructions in a sequence are all independent of each other, so their execution can be overlapped.
Governed by data and procedural dependency.
What is machine parallelism?
Ability to take advantage of instruction parallelism.
What is an instruction issue?
Where the order of instructions, fetched, executed, memory and registers changed.
What is an In-order issue?
Issuing instructions in the order the occur
This is inefficient
Instructions could stall if required
What is an out-of-order issue?
Decouple, decode pipeline from the execution pipeline.
Continue to fetch and decode until the pipeline is full, when a unit becomes available then we use it.
What are the result of out-of-order issue?
We need additional logic to ensure that our code isn’t destroyed by being executed out of order.
What is antidependancy?
One instruction cannot happen before another, as the first instruction modifies the other instruction’s operands.
What is register renaming?
Avoid antidependancy by dynamically allocating registers as they are needed to have copies of the original values before have the code reference that version of the registers. These are stored in register specifically for this.
Avoiding pipeline stalls.
What is machine parallelism?
Duplication of resources with out-of-order issues.
Need instruction window length large enough to “see” instructions incoming.
What is speculative execution?
If there is a unit free we can do instruction that may be needed. And dispose of their results if they are not.
Out of order execution can provide this, but, leads to the meltdown vulnerability.
What are the two main families of OS?
Microsoft Windows and UNIX-like
What do OS provide programmers?
An easy and convenient interface with the system.
It is essentially a mediator between programs and hardware.
Why does the OS conceal complexity?
To protect users and programmers from having to work with horrendous complexity. (IP, Compilers, Drivers)
To protect users and programmers from the details of the hardware through an interface.
What does the kernel provide?
Memory management
Task management
File management
Device management
What is kernel memory management?
Allocation of memory and management of virtual memory
Also restricts access helping with programming errors and malware.
What is kernel task management?
Launching processes
Maintaining the process table in memory
Performing time slicing and context switching
Handling interrupts
What is kernel file management?
Respond to program request to open files
Set and check permissions
Handle buffering
What is kernel device management?
Use drivers to respond to request to use devices.
What essential features are required for an OS?
Memory protection
Timer
Privileged instructions
Interrupts
What is scheduling?
Making effective use of the processor because the processor is much faster than memory or I/O devices, so scheduling is required so that other task can be completed while one waits.
What is context-switching?
The state of a running process is saved, and another process given processor resources
What does PCB stand for?
Process Control Block
Comes with an:
Identifier
State
Volatile environment
Priority
I/O status
Accounting information.
What are the types of scheduling?
Long-term
Medium-term
Short-term
I/O
What is swapping?
When space becomes available processes are loaded from disk and when they are stalled or finished they are removed.
What is partitioning?
How do we distribute a set of processes (of unknown and varying sizes) onto fixed memory.
What are fixed partitions?
Partitions of memory of a fixed size
What are variable partitions?
Partitions allocated as required, may lead to fragmentation
What are the three types of address involved in partitioning?
Logical Address, location relative to beginning of the program
Physical address, the actual location in memory
Base address, current starting location of the process
What is paging?
We divide memory into lots of small, equal chunks (frames)
Divide processes into chunks (pages) of the same size as these frames
Then we can map pages to frames efficiently (in terms of memory)
How do we link a logical and physical address?
Through the page table
Why do we need page tables?
Page tables show exactly what pages belong to what process, by translating base address to physical address.
What is demand paging?
Each page of a process is swapped in only when it is needed.
This makes it possible for a program to be larger than memory as only pages required are loaded, a page fault is triggered to inform the OS that a new page is required.
What are the advantages and disadvantages of demand paging?
Advantages:
More processes can be maintained
Time is saved
Disadvantages:
This uses swapping, so one page in and one out.
Thrashing can occur - Where the processor spends most of it’s time swapping pages.
T/F The process table can be paged out
True
What is the TLB?
Translation lookaside buffer
Every logical access requires two physical access, page table entry and the actual access
Most systems have cache reserved for TLB
What is segmentation?
Allowing the programmer to view memory as a series of address spaces or segments.
Good for handling growing data structures
Recompilation independently without requiring an entire set of programs to be recompiled
Sharing among processes
Protection
What is simultaneous multithreading?
One core can look like two with extra instructions but sharing execution units allowing separate threads to run.
What is power management?
Using a separate microcontroller to monitor power
Can shut-off cores and boost cores when required.
What is a turbo boost?
We can turbo-boost a core for short burst or if we are only running a single core.
Used widely.
1 or 2 cores active at 5Ghz
or 3-4 active at 4.8
or 5-8 active at 4.7
In modern systems, is RAM connect to the CPU or the Chipset on the motherboard
Directly to the CPU.
What is NUMA?
Non-Uniform Memory Access
Multiprocessor systems with separate blocks of RAM to reduce bottlenecks and is good with large numbers of cores
What is an NPU?
Neural Processing Unit
specialist unit in a CPU for neural net calculations
What is the hybrid architecture?
Using a mix of performance and efficency cores.
As processes using less resources can run on E cores
E cores are much smaller than P cores
What is a network?
Multiple computer that are connected together and can share information/resources
What is a WAN, LAN, MAN and PAN?
Wide Area Network
Local Area Network
Metropolitan Area Network
Personal Area Network
What are the two network models? And why are they layered?
OSI
TCP/IP
Abstraction, so we don’t need to know about the hardware.
What are the layer of TCP/IP?
Application
Transport
Internet
Network Access (Link)
What is the End-to-End concept?
The network is responsible for best-effort connections
End-hosts are responsible for reliability and security
What is the Network Access Layer?
Deals with local link
With a unique MAC address
Ethernet
What is the internet layer?
Handles next-hop routing provides unique addressing
Passes to the correct devices, transport layer.
What is IPv4?
32 bit IP address
Variable length header with a minimum of 20-bytes
We have run out of IPv4 addresses
What is NAT and NAPT?
Sharing one IPv4 address between multiple computers
Breaks the end-end principle
Doesn’t solve the exhaustion problem
What is IPv6?
128-bit address with a 40-bytes header
Written in hex
What is a subnet?
A logical subdivision of a network
What is routing?
When there is a change in IP spaces, at the internet layer, packets are changed to have new IP addresses and converted between networks.
What is the Transport layer?
Provides host-to-host communication using TCP and UDP
What is TCP?
Acknowledgements
Guanteed arrival in correct order
20-bytes header
What is UDP?
No acknowledgements required
No guarrentee on order
8-bytes header
What is flow control?
Preventing a fast sender overwhelming a slow responder
What is congestion control?
Reduces send rate to cope with network congestion.
How does TCP implement flow control?
Sliding window protocol
The sender should only send if the receiver indicates that it has suitable buffer space
How does TCP implement congestion control?
Sender sends a small packet and increases size until a packet is lost.
Sender restarts the cycle of sending with a lower threshold
What is the application layer?
Software that uses the networks, generally using pre-made libraries themselves.
What is ICMP?
A protocol used for diagnostic and control purposes or generated in response to error in IP
What addressing does the Transport layer use?
Port number
What is ADR / NDP?
Address Resolution Protocol
Neighbour Discovery Protocol
Operates at the link layer
Translates IP addresses to MAC addresses
What is DNS?
Domain Name Service provides a way to map symbolic domain names to an IP address
Reliable and resilient distributed service
At the application layer
What devices can be used to expand a network?
Hubs
A multi-port repeater
All packets sent to all connected devices
Switches
connect multiple devices on one network segment
Switches are at the Link layer
They forward only to the specific required port
Why are we monitored?
So network owners need to know what is happening
Government want to know what people are doing
How can we stay anonymous?
VPNS create a logs anyway and their exit points can be monitored
ToR- The Onion Router
Routing traffic through a random series of hops, all encrypted.
What is an instruction set?
List of all commands that a processor can execute
It is per processor
What are the elements of an instruction?
Operation Code
Source operand reference
Result reference
Next instruction reference (usually implicit)
What are the instruction types?
Data processing
Data movement
Program flow
Why do we have shifting a rotating instructions?
For shifting:
Bit masks
Unpacking data
Fast integer arithmetic
For rotating:
cryptography
How can I/O be accessed by instruction set instructions?
May be specific instructions
May be done with data movement instructions
May be done by a separate controller
How many addresses should we have per instruction?
More addresses:
More complex instructions
More egisters
Reg-Reg operations are quiker
Fewer instruction per program
Fewer addresses:
Less complex instructions
More instructions per program
Faster fetch/execution of instructions
Comprimise!
What is RISC and CISC?
Complex Instruction Set Computing
Multiple cycles per instruction
Reduced Instructions Set Computing
One cycle per instruction (usually)
What is endianness?
There is no consistency in ordering bytes
What is big endian?
Most significant byte in the lowest numerical address
Memory dumps are left to right
Stores strings and integers in the same order
But has to perform an extra operation to convert 32 bit to 16 bit addresses
What is little endian?
Least significant byte in the lowest address
What are the four types of Instruction Set Architecture?
Accumulator
Stack
Register-memory
Register-Register
What is the accumulator ISA?
The accumulator is the input and output store
A can be loaded
B can then be added
The result can be stored
What is the stack ISA?
Operands are pushed onto a stack and then an instruction POPs them off, performs the operations and pushes them back.This requires an extra pointer, and memory transfer requires extra operations.
What is register-register ISA?
Operand LOADed from memory to registers
Instructions use operands stored in registers
Memory transfer requires extra operations.
What are the pros/cons of the types of ISA?
Accumulator
Short instructions
High memory traffic
Single temporary storage location
Stack
Simple
Short instructions
Stack cannot be randomly accessed
Bottleneck in stack
Register
Easy code
Compiler optimisations
Fast access to temporary values
Operand must be names
Longer instructions
What does the status register do?
Shows information about an instruction, if problems occured, the result of previous instructions, etc.
What is the link register?
The return address of a branch is placed in the link register so that a subroutine can return back
Why do return addresses use a stack?
This allows the occurance of multiple subroutines.
What is the memory cycle time?
Time required for memory to recover before next access
What is the storage hierarchy?
Register
L1 Cache
L2 Cache
Main Memory
Disk cache
Disk (SSD)
HDD
Optical
Tape
What is DRAM?
Dynamic RAM
Requires refreshing or charges will leak
Simple and small, less expensive
25GB/s
DDR5
Two 32 bit channells
38GiB/s up 96GB
What is SRAM?
Static RAM
Bits stored as on/off gates using 4-6 transistors
No charge leak so no refreshing
More expensive and more complex
What is ROM?
Read-only memory
BIOS anbd basic system programs
Why is error correction required?
DRAM looses data, 25K failures per Mbit per billion hours
What are Hard and soft failures?
Hard
Permanent defect
Soft
Random, non-destructive
No permanent damage
Detected and maybe fixed by Error Correcting Code
What is cache?
Small block of fast SRAM on the CPU where memory requests are sent (NOT DRAM)
Why is latency important for memory?
As DRAM takes at least 5 clock cycles to provide data
How does cache operate?
CPU reads a memory location
Address goes to cache
If present cache will provide (hit)
Otherwise, block read required from RAM to cache (miss)
Then this is delivered
Why is cache split into instruction and data?
As they have different access patterns
Why is a level 2 cache used?
As bigger caches have longer latency so they need to be split
How many levels of cache are used in total?
3
What is the memory connection?
N words of equal length with unique address
What is the CPU connection?
Reads instructions and data
Sends controls signals to othe units
Defines a chip plug
What are the bus structures?
Control/Address/Data
PCIe
Serial ATA
Universal Serial Bus
What is a shared bus?
A common communication pathway
Signals might be separate, multiplexed, serialised
This convers the conventual parallel bus.
How wide is a general parallel bus?
64 bit
What does address bus width detirmine?
Maximum memory capacity
What does the control bus contain?
Control and timing information
Controls access to other buses
How can a module get to use a shared bus?
- Obtain the use of the bus
- Transfer data
- Synchronise and acknowledge
What is PCIe?
Peripheral Component Interconnection Express
Serial bus with multi- GiBytes/s lanes
v5 - 4 GiByte/s
Uses 16 lanes for GPU cards
How does PCIe work?
Packets are sent over serial links
ACK/NACKS protocol used for data safety
Using multiple lanes to gain bandwidth
It is similar to a network with layers and addressing
What is used for hard-disk connectivity?
SATA - 500MB/S
SAS - 1.2GB/S
Fibre channel - 100 MB/S - 25 GB/S (long distance)
SCSI 10 - 640 MB/S
iSCSI
SAS
What is USB?
Universal Serial Bus
For low-high speed I/O devices
Allows for 127 devices
USB4 - 10-40 Gbit/s
How does USB work?
Assumes a root hub connected to the main bus
Cables have 4 wire
2 data lines
0 is a transition in voltage and 1 is the absence of a transition
Every 1 msec, the hub broadcasts a frame
What are the 4 types of USB frame?
Control
Isochronous
Bulk
Interrupt
What is BIOS?
Basic input/output system
Firmware on the motherboard to start and test hardware and boot OS.
Stored in flash and looks for a bot-loader
What is UEFI?
A replacement for BIOS to boot services and runtime services and can have graphics
What does the chipset define?
The paths/buses between componants
What are the average speeds for each item?
DDR5: 10GB/S
PCIe V3: 1GB/S
PCIe V4: 2GB/S
V5: 4GB/S
Nvme SSD: 5GB/S
Sata SSD: 500MB/S
2.5Gbe: 200MB/S
Wifi 6: 100MB/s
Ethernet: 100MB/S
DMI V4: 16GB/S
HDD: 100MB/s
CPU: ~50 Gflops
What is a magnetic disk?
A metal disk coated in magnetic material
They store data on multiple platers with one head per side, all aligned. Data is striped per cylinder to reduce head movement. Data is organised into concentric rings with gaps between rings.
How is the speed of a HDD determined?
By the seek time.
Access time = seek time + latency
Why is throughput a problem? And how is it mitigated?
Disk throughput will often be slower than the connection speed of the wire, on disk-cache can be used to store whole tracks.
What is MTBF?
Mean Time Between Failures
HDD: 114 yrs
What is an SSD?
Solid State Drive
non-volatile NAND logic with fast access times.
Over millions of writes the flash blocks can fail. File systems are used to deal with SSD problems and erase unneeded blocks, but only by block.
Why do SSDs have controllers?
To perform interface addressing, error detection and correction.
To change some bytes a block has to be read and modified.
What is the speed and capacity of Blu-ray?
70MiB/s read
15-30GiB average
128 GiB maximum
What is a jukebox?
A collection of disks or tapes (blu-ray) which can be interchanged to read/write. Usually used for backup.
What is iSCSI and SAN?
Internet Small Computer System Interface
TCP/IP over normal Ethernet that backs up data
Storage Area Network
Block accessed with 16GBi/s fibre channel
What is a microcontroller?
A self-contained computer on a single chip featuring a slower clock.
What does having no MMU mean for a microcontroller?
They can’t run a real operating system
How much power do microcontroller use while active?
< 10mA
How can microcontrollers be programmed?
Bare-metal programming
Embedded OS
Real-time
What is bare-metal programming?
Write C code, compile it and then flash it to the micro-controller.
When is real-time microcontroller programming used?
Used when the timing is crucial and must be guaranteed.
What is system-on-chip?
Integrating most of a computer onto a single chip. Includes radio, co-processor, interface drivers and more.
What is the hypervisor?
Software placed between the OS and hardware, that tells the OS what is and isn’t hardware.
What is virtualisation?
Using a hypervisor to emulate hardware, above the hardware.
What is a VMM?
A Virtual Machine Monitor is a layer of software that emulates the hardware of a complete computer system.
Why is binary translation needed?
The machine code of the above OS may not be for the instruction set of the hardware.
What is Paravirtualisation?
Changing the guest OS so that it cooperates with the Virtual Machine.
When does a VMM expose hypercalls?
Activate and deactivate the interrupts
Change page tables
Accessing virtualised peripherals
What is Hardware assisted virtualisation?
Allows the VMM to run privileged code.
It is not translated.
How does HAV begin?
New instruction that switches the CPU into non-root mode.
Processor state is loaded from the guest state of the VM scheduled to run.
The control transferred from VMM to the VM.
How does HAV end?
Saves the process state in the guest state area of the running VM.
Loads the processor state from the host-state area.
Transfer control to the VMM.
What is KVM?
Linux device driver for hardware virtualisation.
What is QEMU?
Uses binary translation via Tiny code generator for efficient emulation.
What is a lightweight container?
Use the kernel of the host system to run only the code needed instead of having a full OS.
What are the typical use cases of a VMM?
Freezing an older OS/demo service
Trying new OS.
Working on system installation scripts.
Migrating between VMs
Disaster recovery
What is Flynn’s Taxonomy?
Classification of computer architectures.
Four classification based on number of instruction and data streams
But vector processing is missing.
What is SIMD processing?
Do they same thing to many data objects
Require special CPU hardware and supporting software.
What can SSE be used for?
Image processing
Video processing
Array/vector processing
Text processing
What does SSE stand for?
Streaming SIMD Extensions
What is SSE?
128-bit registers that can be packed with various data types.
What processing model does a GPU use?
SIMD
What is SMP?
Symmetric Multiprocessors
A MIMD system where multiple CPUs share main memory and I/O
Hardware manages contention.
Describe a typical SMP system
Each processor has its own L1 and L2 cache
Connected by a system bus
Main Memory, I/O, etc are also connected to the bus.
What is Heterogenous Multi-processing?
Combining big performance cores with little efficiency cores.
What is Simultaneous Multithreading?
Hardware multi-threading on superscalar CPUs.
Execute multiple instructions at the same time using redundant execution units in the processor.
What is Task parallelism?
Split the code up, onto separate CPUs
What is the embarrassingly parallel problem?
Very easy to split tasks into parallel subtasks
What is Data parallelism?
Split the data to make independent parallel tasks
What are GPUs used for?
Video compression
Video transcoding
Image compression
Modelling
AI
Number-crunching
What is a CUDA core?
A core containing a floating point unit and maybe an integer unit
Could have a Special Function Unit for trigonometric operations
Why are DRAM chips arranged around the GPU?
As the bandwidth needs to be huge.
What is a tensor core?
A core for AI acceleration
For fused multiply-add operations
Why do some GPUs not need outputs?
Cards designed for number-crunching, especially in data centres don’t have outputs
What is Moore’s law?
The number of transistors within a system doubles every two years
What is Amdahl’s law?
The speed of a system is limited by it’s bottlenecks, there is a fancy equation for this.
What is SMT?
Simultaneous multithreading
What are the four parallel classifications?
SISD: Single Instruction Single Data
SIMD: Single Instruction Multiple Data
MISD: Multiple Instruction Single Data
MIMD: Multiple Instruction Multiple Data
How are 3D objects represented?
A collection of Vertices, Edges and Faces
How many reserved IPs are there?
2
The router and broadcast
What is the length of a MAC address?
48 bits
In an IPv6 address, what does :: mean?
Where 0s are, but, have not been included
How many CUDA cores are in a GPU?
~20,000
What are the two binary formats of IEEE 754?
Single (32 bits) and double (64 bits)
How many bits are in a IEEE 754 single mantissa?
23 bits
How many digits of precision do you get with double IEEE 754?
15-17 digits
What are the 6 steps for converting a number to binary IEEE 754 representation?
Convert your number to binary
Normalise the number
Determine the sign bit
Calculate the exponent
Calculate the mantissa
Combine all the parts together
What is Pulse Width Modulation?
An on/off signal used by motors and LEDs.