Computer Organization and Architecture Test 2

Data:

Main Memory = MM = 32 GB = 2³⁵

Block size = BS = 8 KB = 2¹³ B

Cache size = CS

tag = 10 bits

Formula:

number of bits = ⌈log₂ (size)⌉ 

MM = tag + line + bs  (in bits)

CS = BS × number of  lines

Calculation:

35 = 10 + line + 13

line = 12 bits

number of lines = 2¹²

CS = 213  × 212 B = 2²⁵ B = 32 MB

Important Points:

1 G → 2³⁰

1 M → 2²⁰

1 K → 2¹⁰

Concept:

Fully associative mapping:  In this type of mapping, block of memory can be mapped to any cache line

available that time.

Explanation:

Given:

Memory block requests are: 5, 4, 26, 8, 20, 7, 26, 8, 17, 36, 46, 23, 8, 4, 17, 26, 9

So, at the end of mapping with LRU replacement policy, memory block 17 maps to cache line 6.

Concept:

Address field in a typical instruction format is small. To reference a large range of locations in Main Memory, a variety of addressing techniques are employed.

Absolute addressing mode:

• In this, the address part specifies the effective address of the operand. It is also known as direct addressing. If A = contents of an address field in instruction then Effective address = A.
• It is used to declare global variables in a program and used for branch instructions.

Indirect addressing mode:

• In this address, part specifies a location, contains the effective address of an operand.
• Effective address = (A). It allows to refer the large address space but requires two memory cycles.

Base register addressing mode:

It is the form of displacement addressing. In this, the referenced register contains the main memory address and the address field contains a displacement. Effective address = offset + base register.

Stack addressing:

Stack is a linear array of locations. Stack pointer is maintained in a register which references to stack locations in memory are in fact register indirect addresses. Stack mode of addressing is a form of implied addressing.

     C1A5 =1100 0001 1010 0101

& 93C6 = 1001 0011 1100 0110

____________________________

      8184 = 1000 0001 1000 0100

The content of accumulator register in hexadecimal after the execution of the program is 8184

Important Point:

In instruction address in mentioned not data

Formula:

\(Speed\;up = \frac{{execution\;time\;without\;pipeline}}{{execution\;time\;with\;pipeline}}\)

Explanation:

Given:

Delay of stage S1 = 10 ns

Stage delays are represented as :

Execution time with pipeline (Tp) = max {all stage delays}

= 10 ns

Execution time without pipeline(Tn) = sum of all stage delays

= 10 + 5 + 10 + 5 + 10 = 40 ns

\(Speed\;up = \;\frac{{40}}{{10}} = 4\)

Data:

Memory unit = 512 K words

1 word = 32 bits = 4 B

Binary instruction code stored in 1 word of memory

Instruction divided as follows,

Calculation:

Addressing mode = 1 bit for direct or indirect

Register code = ln (256) = 8 bits

Since, registers are already addressed, only memory needs to be addressed

Address part = ln (512 K) = 19 bits

Operation mode = 32 – 1 – 8 – 19 = 4 bits

Therefore, bits for addressing mode part, opcode part, register code part and the address part = (1, 4, 8, 19)

Data:

Cache block size = 512 bytes

Memory latency = 32 ns

Bandwidth = 4 GB/s

Formula:

Total latency = memory latency + block access time

Calculation:

4 GB → 1 sec

\(4 B \rightarrow \frac{1}{ 10^{9}s} \rightarrow1\ ns\)

\(512\; B \rightarrow \ 128 \ ns\)

Block access time is 128 ns

Total latency = 32 + 128 = 160 ns

Concept:

Direct mapping : In this mapping technique, a main memory block has fixed location in cache i.e. ith block of a page is mapped to ith block of cache.

Fully associative mapping : A main memory block can be placed at any line of cache.

Set- associative mapping :A main  memory block can be placed with k alternatives in a set.

Explanation:

Number of tag bits are maximum in fully associative mapping and minimum in direct mapping and size of tag comparator is directly proportional to the number of tag bits.

Example:

Main memory address = 32 bits

Cache size = 128 KB

Block size = 32 B

For direct mapping:

Tag size = 15 bits

14 bit tag comparator is used.

For fully associative :

Tag bits = 27

For set – associative (4- way) , tag bits are = 17 bits

A memory reference takes 240 ns, so it means 240 ns to access the page table and another 240 ns to access word in the memory. So, a paged memory reference will take 480 ns.

Also, it is given that 75% of all page table reference is found in associative registers.

So, for 75% of the time, it will take 240ns and for the rest of the 25%, it will take 480 ns.

Effective access time = 0.75 × (0 + 240) + 0.25 × (240 + 240)

                                   = 180 + 120 = 300 ns

Statement a:  Correct:

RISC has pipelined implementations with the goal of executing one instruction per machine cycle.

Statement b:  Incorrect

RISC has fixed length instruction formats

Statement c:  Incorrect

c – RISC can perform only Register to Register Arithmetic operations

Statement d:  Correct

d – RISC has efficient instruction pipeline

   0110 1001

+ 0100 1101
_____________

0 1001 0110

Overflow = C_in ⊕ C_out = 1 ⊕ 0 = 1

Carry = 0

Tips and Tricks:

0110 1001 + 0100 1101 = 105 + 77 = 182

Range for 8 bits in 2’s complement is (-2^8-1 to 2^8-1 - 1) = -128 to 127

182 doesn’t falls in the range hence overflow occurs

Data:

Size of main memory: 16 MB

Size of cache memory: 64 KB

Block/line size: 256 B

The cache memory has been designed as 4- way set associative.

Calculation:

The memory is Byte- addressable.

Main memory size = 16 MB = 224 B. That means physical address generated by CPU would be represented

using 24 bits.

Cache memory size = 64 KB = 216 B

Block size = 256 B = 28 B. i.e. word would be represented by 8 bits

Therefore, Number of cache lines ÷ blocks = 216 ÷ 28 = 28

Since, the cache memory is 4-way set associative.

Hence, number of sets = 28 ÷ 22 = 26. i.e. 6 bits would be required for set/index.

Therefore, Number of bits for tag = 24 – (6 +8) = 10 bits

Hence, the 24 bit address generated by CPU would have following components:

Physical Address A1 = 0x 42C8A4. Converting it into binary gives:

Physical Address A2 = 0x 546888. Converting it into binary gives:

Physical Address A3 = 0x 6A289C. Converting it into binary gives:

Physical Address A4 =0x 5E4880. Converting it into binary gives:

Thus it can be observed that A2 and A3 map to same set.

Also, address A1 and A4 map to same set.

Tips and Tricks:

The following approach should be adopted to quickly solve this question and save a lot of time:-

The number of bits for tag in a K- way set associative memory can be calculated directly as:

(log2 (Main memory size in Bytes) – log2 (Cache memory size in Bytes)) + log2 K

Data:

Physical address space (PS) = 4096 MB = 2³² B

Cache size (CS) = 512 KB = 2¹⁹ B

Block size (BS) = 16 word = 2⁴ B

set associativity = 8

Formula:

number of bits = ⌈log₂ n⌉ 

Number of lines in cache =  \(\frac{CS}{BS}\)

Number of sets in cache = \(\frac{number\; of\; lines}{set\; associativity}\)

PAS = tag + set + block offset .....(in bits)

Calculation:

Number of lines in cache =  \(\frac{2^{19}}{2^4} = 2^{15}\)

Number of sets in cache  =  \(\frac{2^{15}}{8} = 2^{12}\)

32= x + 12+ 4

x = 16

∴ tag = 16 bits

The number of bits for the tag field is 16.

Important Point

word length = 32 bit

PAS = 2³² B

1 word = 1 byte

Frequency = 1 GHz

∴ Time = \(\frac{1}{{1GHz}} = 1ns\)

1 Clock = 1 ns

1 instruction = 2 Clock (C)

Time taken with branch = \(8C \times \frac{{30}}{{100}} \times {10^{10}}\)

\(8 \times 1ns \times \frac{{30}}{{100}} \times {10^{10}} = 24s\)

Time taken without branch = \(2C \times \frac{{70}}{{100}} \times {10^{10}}\)

\(2 \times 1ns \times \frac{{70}}{{100}} \times {10^{10}} = 14s\)

Given:

Number of surfaces = 16

Number of tracks per surface = 128

Number of sectors per track = 256

Number of bytes per sector = 512

Capacity of the disk = number of surfaces ×number of tracks × number of sectors × number of bytes per sector

 = 2⁴ × 2⁷ × 2⁸ × 2⁹ = 2²⁸ bytes = 256MB

Number of bits for sector = 2⁴ × 2⁷ × 2⁸ = 2¹⁹ sector (19 bits)

a) Given: format overhead = 64 bytes/sector

Total format overhead = 2¹⁹ × 64 = 2¹⁹ × 2⁶ = 2²⁵ = 32 MB

Formatted disk space = total disk space – formatting overhead

= 256 – 32 = 224 MB

b) Given disk is rotating at 2400 rotations per minute.

2400 rotations in = 60 × 10³ msec

1 rotation in = (60 × 10³ )/2400 = 25 msec

Data transfer rate = \(\frac{{16\; \times \;256\; \times \;512\; \times \;1000}}{{25}} = 80MBps\)

Data:

Instruction Fetch:

T₁ = 2 ns, T₂ = 5 ns and T₃ = 100 ns

H₁ = 0.9 and H₂ = 0.8

Data Fetch:

T₁ = 1 ns, T₂ = 5 ns and T₃ = 100 ns

H₁ = 0.9 and H₂ = 0.8

Formula:

T_avg = T₁ + (1 - H₁) T₂ + (1 – H₁) (1 – H₂) T₃

Calculation:

Instruction Fetch:

T_avg = 2 + 0.1 × 5 + 0.1 × 0.2 × 100

∴ T_avg = 4.5 ns 

For 80% instruction fetch

T_avg = 0.8 × 4.5 = 3.6 ns

Data Fetch:

T_avg = 1 + 0.1 × 5 + 0.1 × 0.2 × 100

∴ T_avg = 1 + 0.5 + 2 = 3.5 

For 20% Data fetch

T_avg = 0.2 × 3.5 = 3.5 ns = 0.70

Total_avg = 3.6 ns + 0.7 ns = 4.3 ns

Important Points:

In two level in serial manner,

T_avg = H₁T₁ + (1- H₁)(T₁ + T₂)

T_avg = T₁ + (1- H₁)(T₂)

Similarly, three level in serial manner

T_avg = H₁T₁ + (1 - H₁)H₂(T₁ + T₂) +(1- H₁)(1 - H₂)(T₁ + T₂ + T₃)

T_avg = T₁ + (1- H₁)T₂ + (1 - H₁)(1 -H₂)T₃

i = 0

i = 1

∴ the output of I4 will be available after 20 ns

Option 1: TRUE

In daisy chaining method of interrupt handling, the devices are connected serially in such a manner that nearest device to the CPU has the highest priority, followed by the next device and so on.

Option 2: FALSE

In vectored interrupt, vector address is given to the CPU to identify the source of interrupt. For example, in 8085 µP, RST 4.5 is a vectored interrupt. Here, 4.5 is the interrupt vector which gives the vector address as 4.5 × 8 = (36)10 = (0024)16

Option 3: TRUE.

In polling method, the CPU polls each device to check status bits to find out if the device has raised any interrupt. It is a software method.

Option 4: FALSE

In DMA mode, either the CPU or the DMA controller would gain control of the system bus a time, but not both. Accordingly, the CPU would be either in busy state or Hold state. It would be in busy state until I/O device prepares the data and would go to Hold state when I/O device starts transferring data to main memory via DMA controller.

Data:

1 word = 4 bytes

Cache block size: 16 word

Frequency = 100 MHz clock

\(1\;cycle = \frac{1}{{100\;M\;Hz}} = {10}^{-8} s\)

In case of miss,

To accept the starting address = 1 cycle

To fetch all the eight words of the block = 5 cycles

To transmit the words of the requested block = 2 cycle/word

Formula:

\(Bandwidth = \frac{{data\;tranfer\;}}{{Total\;cycles\;}}\)

Calculation:

In the case of a cache miss, 8 words need to be transmitted

∴ Total cycles = 1 + 5 + 2× 16 = 38 cycle

Data transfer for a block = 16 word = 16 × 4 bytes = 64 bytes 

\(Bandwidth = \frac{{64\;byte}}{{38\;cycle\;}}\)

\(Bandwidth =\frac{64} {38×{10^{-8}}}\)

Bandwidth = 16.84 × 10⁷ bytes/sec

Important points:

SI unit of Hz: s^-1

Given:

10 platters each with 2 recording surface.

Total surfaces = 10 × 2 = 20

Number of tracks = 1000

Number of sector per track = 32

Address for a sector is represented as :

1^st cylinder = 10 × 2 × 32

We have to find the sector no. for <200, 8, 20>

So, 200 cylinder = 200 × 10 × 2 × 32 + 8 × 32 + 20

= 128000 + 256 + 20

= 128276

So, the address <200, 8, 20> corresponds to sector no. 128276.

Data:

Each instruction = 32 bit

Number of instructions which are supported = 70

Maximum value by unsigned operand = 8191

Formula:

In bits,

Opcode + R + R + Immediate Operand = 32

Calculation

Number of bits needed for opcode = ⌈ log2(70)⌉ = 7 bits

The maximum value of unsigned immediate operand = 8191

2n – 1 = 8191

2n = 8192 = 213

∴ n = 13 bits

7 + R + R + 13 = 32

2R = 12

∴ R = 6 bits.

Given:

T_avg1(average access time) = 50 ns

Hit ratio H₁ = 0.6

L1 memory is 4 times faster than L2.

Effective average access time = level 1 access time + (1- hit ratio)× level 2 access time

When H₁ = 0.6 and T_avg1 =  50 ns

Let level 1 access time is T₁.

Level 2 access time is T₂.

T₂= 4T₁

T_avg1 = T₁ + 0.4 × 4 × T₁

50 = 2.6T₁

T₁ = \(\frac{{50}}{{2.6}} = 19.23 \;ns\)

Now, when T₁ = 19.23 ns

New average access time = T_avg2 = \(50 + \frac{{40}}{{100}} \times 50 = 70\;ns\)

New hit ratio will be :

70 = 19.23 + (1- H) × 4 × 19.23

H = 0.3399

\({H} = \frac{{0.3399-0.6}}{{0.6}} \times 100 = -43.35\%\)

So, there is a decrease of ≈ 44%

Concepts:

During burst transfer, data equal to count of the register could be sent at a time.

Data:

Data count register = 2³² bits

File size = 31245 GB

Formula∷

Minimum number of times the DMA controller needs to get the control = \(\lceil\frac{{File\;size}}{{Data\;count\;register}}\rceil\)

Calculation:

Minimum number of times the DMA controller needs to get the control =  \(\lceil\frac{{31245\;GB}}{{{2^{32}}}}\rceil\) = 7812