Systems Architecture 1 Flashcards
Define the “stored program computer” aka the Von Neumann architecture
A stored-program computer is a computer that stores program instructions in electronically, electromagnetically, or optically accessible memory. This contrasts with systems that stored the program instructions with plugboards or similar mechanisms.
What is the fetch execute cycle?
A CPU works by fetching instructions and executing them in an endless loop.
What is a memory address?
An address in memory, where a bit is stored.
The address is represented as a number
Count to 12 in binary
0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1111
Define the hexadecimal system
A system from A - F and 0 - 9.
How do you convert binary to hexadecimal?
We take the binary number and count from the rightmost index in 1, 2, 4, 8, 16, 32, 64, 128, 256
1011 = 1 + 2 + 0 + 8 = 11 => B
How do you convert hexadecimal to decimal?
Multiply each digit by 16 to the power of the index of the number.
25 = 5 * 16^0 + 2 * 16^1 = 2 + 32 = 34
What is a half adder? What does it’s truth table look like?
An unit with two inputs A and B and two outputs, SUM and CARRY.
A | B | S | C
1 | 1 | 0 | 1
0 | 1 | 1 | 0
1 | 0 | 1 | 0
0 | 0 | 0 | 0
What is a full adder? What does it’s truth table look like?
A unit with three inputs A and B and CARRY-IN, two outputs, SUM and CARRY-OUT.
A | B | C| S | C
1 | 1 | 1 | 1 | 1
1 | 1 | 0 | 0 | 1
1 | 0 | 1 | 0 | 1
1 | 0 | 0 | 1 | 0
0 | 1 | 1 | 0 | 1
0 | 1 | 0 | 1 | 0
0 | 0 | 1 | 1 | 0
0 | 0 | 0 | 0 | 0
What is gate delay and how do you calculate it?
The gate delay is the time it takes for a logic gate to process an input change and produce a corresponding output change.
It is calculated by breaking down each component i.e full or half adder to it’s logic gates and adding the delays together.
You are asked to build a ripple-carry adder for 12-bit numbers, using full adders built from XOR, AND and OR gates in the standard way, and a half-adder in the lowest bit. How many gate delays are there on the longest path between the least significant bit’s input and the top bit’s carry output?
First break down the question.
12 bits
LSB for the half adder
11 bits for the full adders
A full adder has 2 gate delays as it is made from two half adders.
A half adder has 1 gate delay.
So 11 * 2 + 1 = 23 gate delays
In the truth table of a Boolean function with five inputs, how many rows would you expect to see,not countingthe header row?
The formula is 2 ^ Row number
So 2^ 5 = 32
Consider an instruction set featuring many general-purpose registers. It includes a store-to-memory instruction, which takes a value stored in some source register, and stores it to memory at a given address (the address is also held in a register). The instruction supports a “base plus offset” addressing mode, giving it the following form.
STB source_register, offset(address_register)
The encoded instruction takes in total32bits. Of those,6represent the opcode STB (including selecting the given addressing mode);5 bits identify the source register, and5bits identify the address register. What is the maximum value ofoffset, assuming that it represents an unsigned integer (i.e. zero or a positive number)?
We need to break down the question first.
We know that:
32 bits make up the instruction
6 for the opcode
5 for the source register
5 for the address register
We are looking for the maximum value
6 + 5*2 = 16
32 -16 = 16
So as it is an unsigned integer, the maximum value is all bits active.
2^16 -1 = 65535
Remember -1 because we start counting from 0.
COMPUTER STUPID
Which of the following statements is/are true?
- Any combinational circuit can be built from only AND and OR gates.
- Any combinational circuit can be built from only NOR gates.
- From only NAND gates it is not possible to build an XOR gate.
- True - The NOR gate is functionally complete meaning that any boolean function can be constructed using NOR gates.
The NOR gate is a combination of OR and NOT gates, which only outputs 1 when both inputs are 0.
What is the name of the logic gate which has the following truth table?
input 1 | input 2 | output |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
It is a NOR gate, as the only output of 1 is when both inputs are 0.
Moore’s Law states that the number of transistors on a manufactured integrated circuit (chip, die) doubles roughly every 18 months.
Assuming this is true, how many years does it take for the number of transistors to increase by a factor of 100?
Your answer may include decimal places, but only needs to be correct to within one year.
We can start by expressing 100 as a power of 2, which is approximately 6.64
Then as 18 months in years is 1.5, we work out:
6.54 * 1.5 = 9.96 which is approximately 10 years
Convert theoctal(base 8) numeral “1234” to decimal (base 10).
Ocatal base 8 can be worked out by multiplying each index by 8^i, i is the position of the number.
4 * 8^0 = 4
3 * 8^1 = 24
2 * 8^2 = 128
1 * 8^3 = 512
= 668
What is de Morgan’s first law? What does it state?
The first law is Negation of a Conjunction. that states A & B is the same as NOT A OR NOT B
What is de Morgans’s second law? What does it state?
The second law is Negation of a Disjunction, that states A OR B is the same as NOT A & NOT B
What is the Stack Pointer? And where does it point to?
The Stack Pointer is a special purpose register that keeps track of the top of the stack in memory.
The stack is LIFIO (last in first out)
Define two’s complement arithmetic
Two’s compliment arithmetic is the process computers use to add numbers together to perform arithmetic operations.
If a binary number begins with 0, it is a positive integer: 0011
if a binary number begins with 1, it is a negative integer: 1011
For 0, it is represented with: 0000
The term ‘compliment’ refers to positive numbers starting from 0000 and negative numbers starting from 1111.
In two’s compliment, count from 0 to 7
0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111
These are the only available positive integers in binary.
In two’s compliment, count from -1 to -8
1111, 1110, 1101, 1100, 1011, 1010, 1001, 1000
What is 1101 + 0101
1101 = -3
0101 = 5
=> -3 + 5 = 2 == 0010
What is the formula for calculating a floating-point number in binary?
value = mantissa * 2^exponent
- The mantissa holds the main numeric value (often in fractional form).
- The exponent determines how much the mantissa is scaled (shifted left or right).
- In 8-bit format, the mantissa is 4 bits, and it’s stored in two’s complement (which means it can be positive or negative).
In an 8-bit floating-point representation where the 4 high-order bits are a signed mantissa and the 4 low-order bits are a signed exponent, and using two’s complement for signed numbers, which of the following represents the fraction -1/2 [The fraction in words: negative one-half]?
Start by breaking down the question.
- We have an 8 bit number
- 4 high-order bits as the mantissa (numeric value)
- 4 low-order bits as a signed exponent
- It represents a fraction -1/2
So the fraction is a half, and as twos compliment’s largest positive integer is 7 (the 8th number) => 1/2 is equal to 4/8 which is 3, represented in binary as 0011 but as this is negative fraction we use the negative signed version which is 1100.
Then to find the exponent which as this is - 1/2 there is no exponent => the exponent is 2^0, represented as 0000 in binary.
Finish with our 8 bit format of 1100 0000
How do you convert a decimal number to binary?
- Divide decimal by 2 and note the remainder.
- Repeat steps until 0 is the quotient.
- Write the remainders in the reverse order with the LSB first.
- The number is written in base 2
Work out 13 as binary:
1. 13/2 is 6 rem 1 1 is the LSB
2. 6/2 is 3 rem 0 0
3. 3.2 is 1 rem 1 1
4. 1/2 is 0 rem 1 1 is the MSB
13 is 1101_2
Express 2 1/4 as binary
Convert 2 1/4 to decimal which is 2.2.5
Work out 2.25 in base 10
Convert 2 first, 2/2 = 1 rem 0, so 10_2 in binary
Then convert 0.25, as it is negative, we multiply.
0.25 * 2 = 0.5, we take the integer part of 0.
0.5 * 2 = 1, integer part is 1.
0.25 in binary is .01_2
Combine both to form 10.01_2
Then normalise, by shifting, as we moved the point one place, we shift the point one to the left.
We now have 1.001.
Now we convert to 8-bit floating point representation:
high order bits (mantissa): 1.001_2 is close to 1001
low order bits (exponent): 1, which is 0001
2 1/4 = 1001 0001
You are modifying an n-bit ripple-carry adder (calculating A+B) so that it can also perform subtraction (A-B) using two’s complement. The initial design uses full adders only.
A colleague has pencilled in one change: when performing a subtraction, the adder’s Carry In input should be set to 1 (whereas for addition, it is always 0).
What other changes are necessary for this to perform subtraction correctly?
This is a commonly used trick in ALU’s.
The question is asking you to modify an add function to be able to perform subtraction using two’s compliment.
We know that negative numbers are created by flipping all the bits of a number and adding 1 to the result.
Show as A - B = A + (- B)
So setting the carry in to 1 will ensure that the addition is negative or 0 if positive.
So the key change needed is to add a new ‘Subtract’ control with an XOR that does the following:
- If subtract is 0: Normal addition (B is unchanged)
- If subtract is 1: Each bit is flipped (- B)
Define bitwise shifting
Bitwise shifting is an operation that moves the bits of binary numbers left or right.
It is visualised by «_space;or»_space;.
It effectively multiplies the or divides the number by 2.
5 = 00000101
5 «_space;1 is 00001010, which is decimal 10
Define big and little endian
In a big-endian system, the most significant byte (MSB) of data is stored at the lowest memory address, and the least significant byte (LSB) is stored at the highest address.
A program is running on a big-endian 32-bitCPU, and represents character strings using the ASCII character set, with one byte per character and using a NUL (zero) byte as a terminator. The program contains the string “Go!”.
Which of the following correctly shows how the string is represented as bytes in memory? In each case, each byte is written as a two-digit hexadecimal number, with the byte’s address in memory**increasing from left to right.
- 00 47 6f 21
- 47 6f 21 00
- 21 6f 47 00
- 21 00 6f 47
- 00 21 6f 47
First we break down the question.
We do not need to know the exact ASCII character code, but as it is a big endian system, we know that the largest byte will be stored first.
47 6f 21 00 is the correct answer, as it is in descending order.
Consider a 64-bit processor whose clock has a frequency of 1 GHz, and can perform one addition and one branch in a single clock cycle. Suppose you have written a tiny two-instruction program which adds 1 to a register (initially zero) and branches immediately back to the addition. If you start the program running and leave it for a year, roughly what value will the register hold when you return?
First we break down the question, we have a 64 bit processor with 1GHZ clock speed, that performs one addition and branch per cycle.
Each cycle increases the register by 1.
We know that clock frequency is 1GHZ so that is 1,000,000,000 cycles per second or 10^9 cycles.
Seconds in one year are 60 * 60 * 24 * 365 = 31,536,000 seconds
Cycles/s are 31,536,000 * 10^9 = 3.1536 * 10^16.
As each cycle increases the register by 1, the total after a year is:
3.1536 * 10^16 or 31.5 quadrillion
Define a cache
A cache is a small, high-speed memory unit located within or close to the CPU, designed to store frequently accessed data and instructions.
When the CPU needs data, it first checks the cache:
If the data is found, it’s called a cache hit, leading to faster retrieval.
If the data is missing, it’s a cache miss, requiring retrieval from slower main memory (RAM).
Caches optimise performance by leveraging locality of reference, meaning recently accessed data or nearby data is likely to be used again. This follows patterns such as the 80/20 rule (Pareto principle), where 20% of memory accesses account for 80% of execution time.
Define virtual addressing
Virtual addressing allows a process to use memory independently of the physical RAM, creating an abstraction layer between software and hardware.
- Virtual Memory: Each process gets its own address space, managed by the OS.
- Translation: The MMU (Memory Management Unit) converts virtual addresses to physical addresses.
- Page Tables: The OS maintains mappings of virtual pages to physical frames.
What is the process of mapping a virtual address to a physical address?
- The virtual address is divided into two parts, the page number and offset. The page table stores the mappings from virtual pages to physical frames,
- The page table entry PTE tells the OS whether the page is present in RAM (if it contains the physical frame number) or not present (page fault) then the OS will load it from disk.
- A TLB (Transition lookup buffer) is a small cache inside the CPU that stores recent page translations. If the virtual address is in the TLB (HIT), translation is fast, else MISS then the MMU must check the page table.
- If the page is in memory, the physical address is calculated as:
physical address = physical frame + offset.
Then the CPU can access the correct location in RAM.
Convert the virtual address 0x107 into a physical address by using the following page table:
0x00-> 0x0
0x10-> 0x0
0x20-> 0x0
Write the physical address in the same format as above without a special prefix.
REMEMBER 0x means hexadecimal
Hex to dec is multiplying by 16 to the power of the index
The first thing to do is to assume a page size of 0x100, which is 256 bytes.
The virtual address given is 0x107, so the page number is:
0x107 / 0x100 which is 263 / 256= 1 remainder 7.
So the virtual page number is 0x1 and the offset is 0x7
As the virtual page 0x1 is not mapped, however if 0x10 maps to 0x0 in the table, means that page 0x1(which is 0x10 on hexadecimal) maps to physical page 0x0.
We can compute the physical address using the formula:
physical address = (physical address * page size) + offset
This is (0x0 * 0x100) + 0x7 = 0x007
The answer is 0x07 as in standard hexadecimal format, we can negate the extra 0’s as it is a 3 digit address.
The physical memory is split into physical pages (akapage frames), which have equal size. Suppose we know that on our system, the number of page frames in the physical memory equals the number of bytes in a page frame. We also know that physical addresses have 24 bits. How many bytes are in a page frame?
Start by breaking down the question:
- Physical memory is divided into page frames of equal size
- The number of page frames = the number of bytes per page frame
- Physical addresses are 24 bits
The total addressable memory is 2^24 bytes which is 15MB
Define key variables
- P = number of bytes per page frame
- N = number of page frames
The problem statement says that N = P
Find the page frame size
We know that total memory = number of page frames * page frame size, so:
Total memory = P * P => 2^24 = p^2
Solve for P
Take the square root for both:
P = 2^24 squared = 4096 which is 4KB
Each page frame is 4KB
Better way is to use power laws and square 2^24 so it becomes 2^12
On a 32 bit architecture, objects are aligned on 4 byte boundaries, which means that objects start at addresses that are multiples of 4. A reference to an object is always the address of the start of the object.
Which of the following addresses are valid references to an object?
- 0x1624B673
- 0x1624B680
- 0x1624B68A
In hexadecimal, if the last bit is divisible by 4 then it is a multiple.
In this case it would be a valid object address, so 0x1624B680.
Define a heap and it’s properties
A heap is a type of tree based data structure, that is used for dynamic memory allocation.
There are two types, min and max heap. The max heap’s parent node is always greater than or equal to its children and the min heap’s parent is always smaller than or equal to its children.
A heap’s properties are:
- It is a complete binary tree, meaning that all levels are filled
- The heap property ensures efficient insertion and deletion operations
We have a heap in which each object points to at least one other object.
True/False: Itmustbe the case that this heap contains two objects that point to the same number of other objects.
This is the pigeonhole principle, n > m.
let
nnn = total number of objects in heap
- As each object must point to at least one other object, the number of objects that each object can point to ranges from 1 to n - 1n - 1n - 1, possible distinct outgoing pointers.
- However, there are nnn objects, which is one more than the n - 1n - 1n - 1 possible values and according to the principle, at least two must point to the same number of other objects.
Therefore it is true.
Define threading and concurrency
Threading refers to the execution of multiple threads (lightweight processes) within the same program. Each thread runs independently but shares the same process resources like memory and file handles.
- Single threading: a program runs with only one thread, executing tasks sequentially
- Multi-threading: multiple threads execute concurrently, improving performance by parallelising tasks
Concurrency is the concept of multiple tasks making progress at the same time, but not necessarily executing simultaneously. It enables efficient CPU utilisation by switching between different tasks.
Do all threads in one process share the same address space?
They do, all threads in a process share the same virtual address space, this means that they can access the same memory .
What is the text segment?
A text segment is a portion of a programs memory that contains the executable instructions or machine code for the program.
Define garbage collection
Garbage Collection (GC) is the process of automatically reclaiming memory occupied by objects that are no longer needed by a program. It helps prevent memory leaks and optimises memory usage by freeing up space that is no longer in use.
