Studied by 17 people
This covers the entirety of content for CS132 (at least for the 23/24 cohort).
Represent the value 13 (Base-10) in binary (Base-2)
1101
Represent the value 17 (Base-10) in Hexadecimal (Base-16)
11
Represent the value 11 (Base-10) in Octal (Base-8)
13
What issue do we come across when trying to add the following numbers together?
10011101 + 11110011
Overflow (There aren’t enough bits to store the result)
Signed Magnitude and Two’s complement are two ways of representing negative numbers. Which is considered more efficient and why?
Two’s Complement, as there is only one representation of the value 0 (Signed Magnitude has 2: +0 and -0). Both have a similar range.
Which method of representing negative numbers is typically used for shifting all values by some constant?
Two’s Complement Biased. The bias is subtracted from the number’s value. For a number of n bits, usually the bias is equal to 2^(n-1).
Why do most systems NOT use fixed point fractional numbers?
We don’t have any control on the precision of the decimal value represented, and the value may be difficult to translate to other systems.
What are the three components of a floating point number?
Sign - Defines if the number is positive or negative.
Exponent - The scale/precision of the number
Mantissa - The value of the number
What is the name of the common standard for storing floating point numbers?
IEEE Standard 754-2008
Floating points can be either 16, 32, 64 or 128 bits long.
Write the truth table for a NOT Gate.
0 → 1
1 → 0
Write the truth table for an OR Gate.
0 + 0 → 0
0 + 1 → 1
1 + 0 → 1
1 + 1 → 1
Write the truth table for an AND Gate.
0 . 0 → 0
0 . 1 → 0
1 . 0 → 0
1 . 1 → 1
Write the truth table for an XOR Gate.
0 ⊕ 0 → 0
0 ⊕ 1 → 1
1 ⊕ 0 → 1
1 ⊕ 1 → 0
Write the truth table for a NAND Gate.
0 . 0 → 1
0 . 1 → 1
1 . 0 → 1
1 . 1 → 0
Write the truth table for a NOR Gate.
0 + 0 → 1
0 + 1 → 0
1 + 0 → 0
1 + 1 → 0
Write the truth table for an XNOR Gate.
0 ⊕ 0 → 1
0 ⊕ 1 → 0
1 ⊕ 0 → 0
1 ⊕ 1 → 1
Which logic gate can be used to create any other?
NAND
Simplify the boolean expression: (A + A) . (A + B)
→ A + (A . B)
→ A
Application of Associative Law, followed by Absorption Law.
What does an “X” mean on a Karnaugh map? Why is it useful?
A “Don’t care” value. These are values where the output can be safely disregarded, allowing for the simplest logic expression to be formed.
A 1-bit half adder takes two input values and returns a sum bit and carry bit. Each output requires one logic gate. State the gates needed to give each output.
Sum - XOR
Carry - AND
A 1-bit full adder takes three inputs: A, B, and Carry_in. We can chain 1-bit full adders together to get an N-bit adder, where the carry bit of each adder is chained into the Carry_in of the next. What value do we pass to Carry_in for the first full-adder?
0
To turn an N-bit full adder into a full adder/subtractor, we can add another input to the called Z, which is enabled when we want to perform A-B, and disabled when we want to perform A+B. Where do we apply the input Z?
(1) The Carry_in of the first 1-bit full adder.
(2) In an XOR gate with every bit of B.
When accessing data, we typically need to identify locations based on addresses. Likewise, we need to index locations using addresses. What two logic circuits let us do this?
Encoder (Locations → Addresses)
Decoder (Addresses → Locations)
Sometimes we have situations where we have multiple sources of input, and need a way of switching between them. We may also want to take an input signal and assign it to one of a set of outputs. Which two logic circuits let us do this?
Multiplexer (Multiple Inputs → One Signal)
Demultiplexer (One Input → Multiple Outputs)
What is the difference between Computational Logic and Sequential Logic?
Computational Logic produces output, only depending on its inputs.
Sequential Logic produces output based on its inputs and its current state.
What logic circuit allows us to store one bit of data?
D-Type Latch
What kind of inputs are “S” and “R” on a Flip-Flop?
Active Low (i.e. a 0 indicates an active/enabled line)
Suppose we have a circuit consisting of 8 D-Type Latches. All latches share the same clock signal, and each latch has its own input line (A_n), and output line (Q_n). What is the name of this circuit?
8-Bit Register
Suppose we have a circuit consisting of 8 D-Type Latches. All latches share the same clock signal, and we have one input, D, which feeds into the input of A_1. The output of each latch feeds into the next, and is outputted (Q_n), except for the last, where the output only goes to Q_8. What is the name of this circuit?
8-Bit Shift Register
Suppose we have a circuit consisting of 8 D-Type Latches. A clock signal is fed into the input of the first latch. Each latch has the inverse of its output (¬Q_n) wired to its input (A_1). Each non-inverted output is given as Q_n, as well as having its inverse passed into the clock input of the next latch. What is the name of this circuit?
8-Bit Counter
Three-State Logic allows for three types of signal: High, Low and _______.
Enabled
Where are Three-State buffers commonly used on a computer system?
Buses
What are two factors related to Physics which are not modelled in theoretical scenarios?
Propagation - We cannot simply “combine” two outputs, as one output may feed into another as an input, leading to short-circuits.
Delay - We model changed between high and low as being instantaneous. In reality, there is a delay of about 1 nanosecond.
Programmable Logic Arrays (PLAs) allow use to program certain logic circuits into an integrated circuit. What arrays of logic gates do they use, and how is it possible to enable and disable certain inputs?
NOT Array - Each input line is passed through a NOT gate to give its inverse, allowing it to be used where necessary.
AND Array - A series of AND gates which may take more than 2 inputs.
OR Array - A series of OR gates which may take more than 2 inputs.
There are also small fuses which can be broken in order to disable some inputs where needed. This enables the “programming” of the circuit.
What are the steps involved for running an instruction on a processor?
Fetch, Decode, Execute
What is the most common computer architecture?
x86 (Generally x86_64 as most devices are now 64-bit)
NOTE: Many devices also run ARM assembly as well, including mobile phones and recent MacBooks
How does an assembly program run on a computer system?
It is converted to machine code by an Assembler, which translates into various signals across the system.
What does the following RTL code do?[MAR] ← [PC][PC] ← [PC] + 1
[MBR] ← [MS(MAR)]
[IR] ← [MBR]
[CU] ← [IR(opcode)]
Fetches an instruction from Main Memory (RAM)
RISC-V assembly uses six types of instruction. What are these called, and what do they perform?
R - Arithmetic and Logic
I - Bit Shifts and Instruction Loading
S - Storing
B - Branching
U - Special Case Instructions
J - Jumps
Assembly instructions usually consist of four components. Labels can be used to reference instructions in a human-readable format, and comments can be added. What are the remaining two components, and what are they for?
Opcode - The actual instruction that needs to be performed
Operand(s) - The data to pass into the instruction (e.g. numbers to be added together)
Some RISC-V instructions have two versions, one with an “I” at the end, such as “ADD” and “ADDI”. What is the difference between these two types of instruction?
Hint:ADD x1, x0, x2ADDI x1, x0, 12
The “I” versions of instructions allow for Immediate Addressing, i.e. allows for a constant value to be passed to an instruction, instead of referencing an address in memory.
What are the four primitive data types available in C?
Char - 8-bit representation of an ASCII character
Int - 32-bit representation of a whole number
Float - 32-bit decimal number stored in IEEE format
Double - 64-bit decimal number stored in IEEE format
(Others include long, short, signed and unsigned integers.)
Fill in the missing keyword of the following C code:______ bottle {
int volume;
int fullness;
char liquid;
};______ bottle waterBottle = {.volume = 500, .fullness = 495, .liquid = ”w”};
struct
Struct exists as the closest relative to a class/object which is common to OOP. Structs can only contain variables, and all data is public.
State the output of the following:int x = 25;char y = 'Z'printf(“x has value %d .“, x);if (x > 20) { printf(“%c”, y);}return 0;
x has value 25 .Z
What is the value x in the C code?int* x; int y = 36;x = &y;
x is the pointer for y. It is the address for the location of the value of y in memory.
What do malloc, calloc and realloc each do?
Malloc - Specify the number of bytes to store on the program’s heap.
Calloc - Clear a number of bytes from the program’s heap.
Realloc - Change the size of a byte allocation.
You can free up memory that has been taken up by the heap or stack of a C program by passing the pointer of the data into which function?
free
Define an array of integers in C.
(Don’t specify any values.)
int * arr = (int *) malloc(5*sizeOf(int));
What are the items of the memory hierarchy, in order of access time (Fast to Slow)?
Registers - Built into processors
Cache - Made up of multiple levels, built next to processors on current CPUs
Main Memory - RAM, which is placed outside the processor
Magnetic Disk - Secondary Storage, which has higher capacity
Optical Disc/Tape - Slower access times, used for backups
Which of Registers, Cache, Main Memory, Magnetic Disk, Optical Disc and Tape are Random Access and Volatile, or Sequential Access and Non-volatile?
Random Access and Volatile - Registers, Cache, Main Memory
Sequential Access and Non-volatile - Magnetic Disk, Optical Disk
Give the formula for cache hit rate (and hence the formula for miss rate)
h = no. times the word is in cache ÷ Total no. of memory references
Miss Rate = 1 - h
Give the equation for cache average access time.
Avg. = Hit Time + (Miss Rate × Miss Penalty)
RAM usually comes in two forms: DRAM and SRAM. How are each of these different?
SRAM - Static RAM - Uses Six Transistors and Two Capacitors to store a single bit. No refreshing is needed, but this is more expensive.
DRAM - Dynamic RAM - Uses One Capacitor and One Transistor to store a single bit. It is much cheaper than SRAM, but has to be constantly refreshed. Most DRAM resultantly has a clock speed, often referred to as the refresh rate.
DRAM is more commonly used for Main Memory.
Suppose we want to organise 256 memory cells, outputting to 8 data lines. How many address inputs are required for the address decoder?
5 Address Lines (256 / 8 = 32 output lines, log_2(32) = 5 address inputs)
Suppose we are organising 256 memory cells using a 4-bit address decoder (So an address input consists of 4 bits). How many data outputs are needed?
16 Output Lines (256 / (2^4) = 16 Outputs)
Typically, Memory is organised into ICs. These use 22 address lines and one data line. How much memory does one IC store?
4 Mb (Megabits)
What is Noise, and where can it come from?
Noise is unwanted information and interference. It can occur due to thermals, other electrical components and transmission circuitry.
What are the two types of error checking, and where are they most suitable?
Parity Bits - Use a single bit as a summary for a regular sequence of bits. Best for single, rarely occurring errors.
Checksums - Use multiple parity bits on a chunk of data. Best for frequent errors, which are likely to occur in bursts.
Determine the bit “X” for both Odd and Even parity in the 8-bit sequence X110 1011
Odd - 0110 1011
Even - 1110 1011
How does an HDD store data?
An HDD is a magnetic form of data storage.
It uses multiple ferromagnetic discs layered together, each with its own read head.
On each disk, there are multiple tracks, each with their own sectors. Each sector stores a preamble, a data chunk and ECC.
What is an HDD’s approximate read time?
13 microseconds (0.013 ms)
How does an optical disk store data?
Hint: Think CDs, DVDs, Blu-ray, etc.
The surface of an optical disk contains grooves called “pits” and “lands” which affect how light reflects off the surface at certain points. These grooves are used to reflect laser light in order to read the data, the position of the reflection determining a high or low value.
Each 8 bits are mapped to a 14-bit symbol which allows for large amounts of ECC.
It is possible to access input and output devices using memory addresses in some computer systems. What is this method of organising I/O referred to as?
Memory Mapped I/O
State the pros and cons of memory mapped I/O.
+ Easy to implement - no additional hardware or instructions needed.
+ Possible to use any of the processor’s existing memory addressing modes.
- Limits how much memory can be used/included on a system.
We can use a particular component on a system, which can request use of the data and address buses, so that the lines are cleared for use by I/O. What is the name of this component?
Direct Memory Address Controller (DMAC)
List the steps taken when I/O is given access to the address and data buses by a DMAC.
IO sends a request to DMAC
DMAC sends a request to CPU
CPU initialises DMAC
DMAC requests use of the buses
CPU sends a DMA acknowledgement and hands control
DMAC sends acknowledgement to IO.
Describe the difference between detached and integrated DMA.
Detached - All components are directly connected to the address and data buses.
Integrated - DMACs act as intermediate componented for IO. This allows for a DMAC to control one or more IO devices on their own.
Having IO connected to the same buses as the CPU and other components can be inefficient. Instead, we can separate IO and other components into what two buses? And where would we place a DMAC?
System and IO bus.
The DMAC would be connected to both buses, to interface with both IO and the CPU.
What are the two operating modes of DMA, and how are they distinct?
Cycle Stealing - The DMAC will use the system bus when it detects that it is not being used by the CPU
Burst - The DMAC requests use of the system bus for a set amount of time, “locking out” the CPU
What are the three main types of polling?
Polling - Regularly check if the I/O device is ready
“Busy Wait” Polling - Check if the I/O device is ready, wait if not, then poll again.
Interleaved - If I/O is not ready, perform some other task(s) until ready.
Polling is very simple to implement, only requiring the use of loops. What are the main issues with polling?
Repeatedly checking I/O can consume a lot of power and waste time, which is not ideal in low/limited power devices.
Interleaving with other tasks can lead to delayed responses, which is unideal in real-time situations.
Explain the process of handshaking.
The IO device contacts the CPU once they are ready to perform a task. The CPU will then send a response to state that the data it is sending is valid for that device. Once both of these predicates are satisfied, data transmission occurs.
The 6522 VIA chip is a specialised chip used for handshaking. This chip interfaces with the CPU on an address and data bus. What lines does this chip connect to IO with?
Hint: Describe the lines used in a single port, CA
CA1 Control - Ready Control Line (IO Device is ready)
CA2 Control - Valid Control Line (CPU is sending valid data)
Data Bus
What happens when a CPU is sent an interrupt signal?
The CPU pushes the values in its registers onto a stack to “set aside”. It will then run the required interrupt code and pop the values in the stack and replace them in the appropriate registers.
The 6502 is a processor commonly used in computers in the 1970s and 80s. It has the lines IRQ and NMI. What are these lines for?
Interrupt Request (IRQ) - Used to signal that an interrupt is required. (i.e., Tells the 6502 to stop what it is doing)
Non-Maskable Interrupt (NMI) - Flag to state that a given interrupt cannot be disabled or “masked out”. (i.e., states if the current interrupt is too important to ignore)
What does it mean when we say interrupts can be “nested”?
An interrupt can occur inside an interrupt. What this means is, if some interrupt has a higher priority than the interrupt currently taking place, then that interrupt can pause the current one. So this new interrupt is finished, then the original, then the processor returns to its main program.
Give the pros and cons of interrupts.
(+) Fast Response times
(+) No Wasted CPU time/power
(-) Control must be maintained by the processor
(-) Requires more complex hardware and software
List the five methods of handling I/O
Memory-mapped I/O
Polled I/O
Handshaking
Interrupts
Direct Memory Addressing (DMA)
List the common components of a processor.
A set of registers (For data and addresses)
A bus that connects all components
A Program Counter (PC)
An Instruction Register (IR)
A Control Unit (CU)
An Arithmetic Logic Unit (ALU)
List the inputs and outputs of a Control Unit (CU).
Inputs
Opcode ← IR
Clockin
Flags ← CCR
Outputs
Function Lines → ALU
Read/Write → Memory
Enable → Various Components
Clockout → Various Components
List the inputs and outputs of an Arithmetic Logic Unit (ALU).
Inputs
Function Lines ← CU
P and Q ← Bus
Outputs
F(P,Q) → Bus
Carry Line → CCR (For overflow)
What does it mean for something to be Turing Complete?
Something is Turing Complete if it is able to solve any computational problem, when ignoring constraints such as runtime, memory and power.
What is the difference between a macro and a micro instruction?
Macro Instructions represent an action that may take place in a single line of assembly/machine code.
Micro Instructions represent each movement of data between registers and components in the processor. These help to represent how many clock cycles may be needed to perform a given macro instruction.
What are the two main ways of designing a Control Unit (CU)?
Hardware - Using Logic Circuits and Boolean Logic
Microprogrammed - Each machine code instruction maps to a microinstruction
As part of the design of a Hardware-based Control Unit (CU), we need to use a certain component. This component has a clock and reset line as inputs, and n outputs. Each clock cycle enables one output line in order 1, 2, …n. The reset line starts the outputs at 1 again. What is the name of this component?
Sequencer
What applications are hardware-based and microprogrammed Control Units best suited for?
Hardware - Portable applications where power efficiency and speed are highly important. These are complex to design and inflexible, so the use case should be well-defined.
Microprogrammed - Applications where the given system needs to be highly flexible in what instructions it can carry out. These are easier to debug and extend, but instructions take longer to run.
How does a Microprogrammed Control Unit handle a machine code instruction?
Each opcode is mapped to a specific microprogram.
The Control Unit consists of a “micro-processor” with its own micro-memory, micro-IR, micro-PC, etc.
What do CISC and RISC stand for? Give an example of a processor architecture that uses each of these concepts.
RISC → Reduced Instruction Set Computing
RISC-V, ARM
CISC → Complex Instruction Set Computing
x86, x86_64
How does RISC architecture define the number of machine code instructions made available to the user?
RISC intends to do everything with as few instructions as possible. As such, the instruction set of RISC processors is small, and each instruction can be performed very quickly. More complex operations will need to be manually implemented.
What are the pros and cons of RISC (Over CISC)?
(+) More Energy efficient
(+) Generally faster than CISC
(-) More complex to design and build
(-) Difficult to extend or patch
How does CISC architecture define the number of machine code instructions made available to the user?
CISC intends to simplify programming for the user, so there may exist many different instructions which each perform more complex operations. Use of a microprogrammed CU typically allows for this.
What are the pros and cons of CISC (Over RISC)?
(+) Quicker and easier to design and build
(+) Easier to update or patch
(-) Generally slower than RISC (Must compensate with clock speed)
(-) Requires more power
What is a thread?
A thread is an execution context which includes a stream of instructions. Where we have a process, we may be able to split it into multiple threads in order to speed up computation.
How can a system be “multithreaded”?
A multithreaded system is one that can make use of multiple threads at the same time. This is typically achieved by allowing the execution of a thread, while another awaits access to I/O or memory, for example.
What is the relationship between a process and a thread?
A process can use as many threads as it wants. A processor can switch between processes, but not threads, so it is possible for threads to become starved.
What issues can arise from multithreading?
A-Level Hint: Database Access encounters similar issues.
Race Conditions - Multiple threads may access the same data at the same time, leading to inconsistent or unexpected results.
This can be fixed by locking data
Deadlock - Multiple threads lock the same data, disallowing access inappropriately.
This can be avoided with good implementations
Starvation - Lower priority threads are not scheduled and so may not execute.
This can be fixed by explicitly switching threads as needed
What is a core?
A core is a processor within a CPU that can run code independently. It is typical that most modern processors have at least four cores. Server processors (e.g. Xeon and Epyc) can have hundreds!
What does having a multicore system enable?
Parallel processing, i.e. a dual-core CPU can do double the work of a single-core CPU in the same amount of time. We can allow threads to run on separate cores, for example.
It should be noted that applications have to be written to specifically support a multicore system.
How many threads can we currently run on a single core?
Two, because of Hyperthreading.
This is why you may see the terms “Physical Cores” and “Logical Cores”. Physical refers to the actual number of cores on the processor die, and logical refers to the number of theads that can be simultaneously run.
What are some Engineering Limitations which may be causing Moore’s Law to become less applicable?
The size of the laser used to create dies (14nm)
Size of copper interconnects
Transistor size (Smaller means more noise)
