Systems Architecture 1

Question 1

Define the “stored program computer” aka the Von Neumann architecture

Answer 1

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.

Question 2

What is the fetch execute cycle?

Answer 2

A CPU works by fetching instructions and executing them in an endless loop.

Question 3

What is a memory address?

Answer 3

An address in memory, where a bit is stored.
The address is represented as a number

Question 4

Count to 12 in binary

Answer 4

0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1111

Question 5

Define the hexadecimal system

Answer 5

A system from A - F and 0 - 9.

Question 6

How do you convert binary to hexadecimal?

Answer 6

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

Question 7

How do you convert hexadecimal to decimal?

Answer 7

Multiply each digit by 16 to the power of the index of the number.

25 = 5 * 16^0 + 2 * 16^1 = 2 + 32 = 34

Question 8

What is a half adder? What does it’s truth table look like?

Answer 8

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

Question 9

What is a full adder? What does it’s truth table look like?

Answer 9

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

Question 10

What is gate delay and how do you calculate it?

Answer 10

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.

Question 11

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?

Answer 11

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

Question 12

In the truth table of a Boolean function with five inputs, how many rows would you expect to see,not countingthe header row?

Answer 12

The formula is 2 ^ Row number

So 2^ 5 = 32

Question 13

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)?

Answer 13

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

Question 14

Which of the following statements is/are true?

1. Any combinational circuit can be built from only AND and OR gates.
2. Any combinational circuit can be built from only NOR gates.
3. From only NAND gates it is not possible to build an XOR gate.

Answer 14

2. 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.

Question 15

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 |

Answer 15

It is a NOR gate, as the only output of 1 is when both inputs are 0.

Question 16

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.

Answer 16

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

Question 17

Convert theoctal(base 8) numeral “1234” to decimal (base 10).

Answer 17

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

Question 18

What is de Morgan’s first law? What does it state?

Answer 18

The first law is Negation of a Conjunction. that states A & B is the same as NOT A OR NOT B

Question 19

What is de Morgans’s second law? What does it state?

Answer 19

The second law is Negation of a Disjunction, that states A OR B is the same as NOT A & NOT B

Question 20

What is the Stack Pointer? And where does it point to?

Answer 20

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)

Question 21

Define two’s complement arithmetic

Answer 21

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.

Question 22

In two’s compliment, count from 0 to 7

Answer 22

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111

These are the only available positive integers in binary.

Question 23

In two’s compliment, count from -1 to -8

Answer 23

1111, 1110, 1101, 1100, 1011, 1010, 1001, 1000

Question 24

What is 1101 + 0101

Answer 24

1101 = -3
0101 = 5
=> -3 + 5 = 2 == 0010

Question 25

What is the formula for calculating a floating-point number in binary?

Answer 25

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).

Question 26

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]?

Answer 26

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

Question 27

How do you convert a decimal number to binary?

Answer 27

1. Divide decimal by 2 and note the remainder. 2. Repeat steps until 0 is the quotient. 3. Write the remainders in the reverse order with the LSB first. 4. 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

Question 28

Express 2 1/4 as binary

Answer 28

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

Question 29

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?

Answer 29

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)

Question 30

Define bitwise shifting

Answer 30

Bitwise shifting is an operation that moves the bits of binary numbers left or right. It is visualised by << or >>. It effectively multiplies the or divides the number by 2. 5 = 00000101 5 << 1 is 00001010, which is decimal 10

Question 31

Define big and little endian

Answer 31

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.

Question 32

A program is running on a big-endian 32-bit CPU, 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. 1. 00 47 6f 21 2. 47 6f 21 00 3. 21 6f 47 00 4. 21 00 6f 47 5. 00 21 6f 47

Answer 32

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.

Question 33

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?

Answer 33

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

Question 34

Define a cache

Answer 34

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.

Question 35

Define virtual addressing

Answer 35

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.

Question 36

What is the process of mapping a virtual address to a physical address?

Answer 36

1. 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, 2. 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. 3. 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. 4. 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.

Question 37

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.

Answer 37

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.

Question 38

The physical memory is split into physical pages (aka page 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?

Answer 38

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

Question 39

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? 1. 0x1624B673 2. 0x1624B680 3. 0x1624B68A

Answer 39

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.

Question 40

Define a heap and it's properties

Answer 40

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

Question 41

We have a heap in which each object points to at least one other object. True/False: It must be the case that this heap contains two objects that point to the same number of other objects.

Answer 41

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.

Question 42

Define threading and concurrency

Answer 42

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.

Question 43

Do all threads in one process share the same address space?

Answer 43

They do, all threads in a process share the same virtual address space, this means that they can access the same memory .

Question 44

What is the text segment?

Answer 44

A text segment is a portion of a programs memory that contains the executable instructions or machine code for the program.

Question 45

Define garbage collection

Answer 45

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.