Solution

Since X is a pointer variable, in implementing pointers we use indirect addressing.

Solution

Cycle time in a pipelined processor = max of all stage delays + buffer delay

Buffer delay is the same as the latch latency.

In this case cycle time of the resulting processor = max( 6ns, 4ns, 10ns, 5ns, 5ns) + 2

= 10+2 = 12ns

Solution

Size of each word = 16 bits = 2 bytes

Number of words = 32MB/2B = 16M words = 2^24

So, no. of bits required for the memory address = 24

Solution

A is true. As the number of sets gets decreased, the number of possible cache block entries that a set maps to gets increased. So, we need more tag bits to identify the correct entry.

B is true. If associativity is doubled, keeping the capacity and block size constant, then the number of sets gets halved. So, the width of the set index decoder can surely decrease.

C is true. Width of the way-selection multiplexer must be increased as we have to double the ways to choose from.

D is false. The main memory data bus has nothing to do with cache associativity.

Solution

Number of sets in cache = x.

A block numbered i will be mapped to set number (i mod x). Since it is k-way set associative cache, there are k blocks in each set. It is given in the question that the blocks in consecutive sets are sequenced. It means for set-0 the cache lines are numbered 0, 1, .., k-1 and for set-1, the cache lines are numbered k, k+1,... k+k-1 and so on. As the main memory block i will be mapped to set (i mod x), it will be any one of the cache lines from (i mod x) * k to (i mod x) * k + (k-1).

Solution

Register renaming is used to eliminate hazards that arise due to WAR (Write After Read) dependencies. Hence option D is the answer.

Solution

Block size =16B

Total No. of Blocks=256

Memory block Number = Byte address / Block Size = 2800/16 = 175

In Direct Mapped cache,

Cache block Number = Memory block Number mod(Total Number of block in cache)

= 175 mod 256 = 175

Solution

A is false. Bypassing can’t handle all RAW hazards, consider when any instruction depends on the result of LOAD instruction, now LOAD updates register value at Memory Access Stage (MA), so data will not be available directly on Execute stage.

B is true. Control hazards are caused due to branch instructions. By using branch prediction we can reduce the stalls due to control hazards.

C is true as resource conflicts result in structural hazards.

Solution

Cache access time = 4 ns

Main memory access time = 50 ns

Average memory access time=h1*t1+(1-h1)*(t1+t2) = t1+(1-h1)t2

⇒ 4 ns+(1-0.8)(50 ns) = 4+0.2*50

⇒ 4 + 10 = 14ns

Solution

We know FIFO (First-In-First-Out) algorithm suffers from Belady’s anomaly. From the given 3 algorithms LILO (Last-In-Last-Out) is nothing but FIFO algorithm, so LILO suffers from Belady’s anomaly.

In a random replacement algorithm since the page to be replaced is selected at random, it may behave like a FIFO algorithm so even it may suffer from Belady’s anomaly.

Solution

Using the address value at the program counter (PC), we are loading the current instruction to be executed and the PC value is incremented to point to the next instruction.

Solution

Each instruction has 32 bits. To support 200 instructions, the opcode must contain 8-bits. Register operand1 requires 5 bits, since the total registers are 30, Register operand2 also requires 5 bits. So, 32 - (8+5+5) = 14 bits are left over for immediate operand.

Using 14 bits the maximum value possible for the immediate operand = 2^14-1 = 16383

Solution

Number of clocks per one instruction, CPI = 2 × 0.15 + 3 × 0.1 + 4 × 0.4 + 5 × 0.2 + 3 × 0.15 = 0.3+0.3+1.6+1+0.45 = 3.65 clocks

Since each clock is 12ns, the total execution time for 10^9 instructions = 10^9 × 3.65 × 12 ns = 43.8 s

Solution

It is given that average references per instruction = 1.6

For 1000 instructions total number of memory references = 1000 * 1.6 = 1600

These 1600 memory references are first accessed in the L1.

Since the miss rate of L1 is 0.2, for 1600 L1 references the number of misses = 0.2 * 1600 = 320

We know when there is a miss in L1 we next access the L2 cache.

So number of memory references to L2 = 320

It is given that there are 8 misses in L2 cache. Out of 320 memory references to L2 cache there are 8 misses.

Hence the miss rate in L2 cache = 8/320 = 0.025

The hit rate of L2 = 1-0.025 = 0.975

Solution

In fully associative mapping the entire cache is considered as one set and the given main memory block can be in any block in the cache.

Block-0 will go to the 1st cache block, then block-4 will be in 2nd cache block, the next block-0 is a cache hit, block-2 will be in 3rd cache block, the next block-4 will be a hit. Block-3 will be a miss and it will replace block-0 by applying FIFO replacement algorithm. Block-1 will be a miss and it replaces block-4 and block-0 is also a miss and it replaces block-2. In total there are 6 misses.

Cache size : 3 blocks

Total number of misses : 6

Solution

It is given that the program starts at address 168. Before executing the program PC will get assigned to this address, so PC value will be 168 at the beginning of execution of this program. Each instruction is of size 64 bits = 8 Bytes, so PC can get incremented by 8 memory locations at a time. So a legal PC value has to be a multiple of 8. From the given options 408 is the answer.

Solution

Let Cache access time be X,

It is given that cache memory is 30 times faster than the main memory, so main memory access time will be 30X .

Speed up factor = (Time taken to get data Without Cache)/(Time taken to get data with Cache)

Time taken to get data Without Cache = Time taken to access the main memory = 30X, because in the case of without cache we need to access main memory only.

Time taken to get data with Cache = h1t1+(1-h1)(t1+t2),

here h1 = cache hit ratio = 0.9,

t1 = cache access time = X

t2 = main memory access time = 30X

= 0.9X + 0.1(30X+X) = 0.9X + 0.1(31X) = 0.9X + 3.1X = 4X

Then speed up will be 30X/4X = 7.5

Solution

Block size = 64B = 26B, block offset = 6 bits.

Number of cache lines = 64KB / 64B = 1K = 210.

Number of sets = 210/4 = 28

SET number needs 8 bits.

Since the address is 32 bits.

No. of TAG bits = 32 - 8 - 6 = 18 bits

A 4-way set associative cache needs two kinds of multiplexers.

In a set associative cache we need two kinds of MUXs. One type for set selection(decoder) and the other for OR gate which is also called way selection multiplexer. If it is a k-way set associative cache then we need one k-to-1 MUX which is also called as the way selection multiplexer. As we are given the latency of the 4-to-1 MUX as 0.8ns we consider it, and since there is no information about the set selection multiplexer we ignore it.

Apart from the way-selection MUX delay there is also delay of the comparator.

There are 18 tag bits so we need comparators of size 18 bits. Delay due to the comparators = 18/5 ns

H1 = 18/5 + 0.8 ns = 3.6 + 0.8 ns = 4.4 ns

Direct mapped cache:

Block offset = 6 bits

As there are 2^10 blocks in the cache, BLOCK number will need 10 bits in the direct mapped cache.

So, out of 32 bit address no. of TAG bits = 32 - 10 - 6 = 16 bits.

In the direct mapped cache here we need only the MUX used in decoder. Just as we ignored the delay of MUX used in decoder in set associative cache in the direct mapped cache also we are ignoring the delay of the MUX used in decoder.

So H2 = 16/ 5 nsec = 3.2 nsec

Difference = H1 – H2 = 4.4 – 3.2 = 1.2 nsec

Solution

Cache block size = 4 words

Word size is 2 bytes

It is given that the memory system has a clock of 10MHz frequency.

From this, there are 10M clock cycles in one second.

One clock cycle time = 1 / 10M = 1/(10*10^6) = 0.1 microseconds

It is given that on a cache, the memory controller takes 1 cycle to accept the starting address of the block. And it takes 2 cycles to fetch all the four words of the block. And it transmits 1 word per cycle.

So there are 3 components in servicing each cache miss in this case:

Accepting the address of a block + fetching the data of all the words in the block + transmitting each word of the block.

Time taken = 1 cycle to accept the address + 2 cycles to fetch the four words in the block + 4 * 1 cycle to transmit four words

= 1 + 2 + 4 = 7 clock cycles

Since each clock cycle is 0.1 microseconds, total time taken = 7 * 0.1 = 0.7 microseconds

Solution

Given cache size is 32 KB and line size is 128B, so no. of lines in the cache = 32KB / 128B = 2^15 / 2^7 = 256

Also size of each element = 8B, so no. of elements in a single line = 128B / 8B = 16

It is mentioned that the 2-D array is stored in row-major order. And since 16 elements are stored in one cache line for every 16 accesses there will be one cache miss.

So, no.of cache misses = total elements in the array / no. of elements in the cache line

= 512 * 512 / 16

= 16K = 16,384 misses

Solution

FIFO:

No. of Page faults with FIFO = 6

LRU:

No. of Page faults with LRU = 9

Optimal:

No. of Page faults with Optimal = 5

∴ Optimal < FIFO < LRU.

Solution

The device speed is 16 KB/sec. In one second 16 KB of data is transferred by the device.

Time needed by this device for transferring 1 byte of data = (1/16K) seconds = (1/16*1024) = 61.035 microseconds

Here 61.035 microseconds is the data preparation time for one byte. And time taken by the processor to handle each interrupt is given as 50 microseconds.

So, for every 61.035 microseconds of data preparation of the interrupt 50 microseconds is taken by the processor to handle that interrupt.

So, fraction of processor time consumed by this I/O device = 50 / 61.035 ~= 0.819 ~= 0.82

Solution

It is given that cache size = 512 KB

Cache block size = 32 Bytes

So, the number of blocks in the cache = 512K / 32 = 16 K

It is an 8-way set associative cache. Each set has 8 blocks.

So, the number of sets in cache = 16 K / 8 = 2 K = 2^11.

So, 11 bits are needed for accessing a set. Inside a set we need to identify the cache block.

Since cache block size is 32 bytes, block offset needs 5 bits.

Out of 32 bit address, no. of TAG bits = 32 - 11 - 5 = 32-16 = 16

So, we need 16 tag bits.

Solution

It is given that cache size = 512 KB

Cache block size = 32 Bytes

So, number of blocks in the cache = 512K / 32 = 16 K

It is an 8-way set associative cache. Each set has 8 blocks.

So, number of sets in cache = 16 K / 8 = 2 K = 2^11.

So, 11 bits are needed for accessing a set. Inside a set we need to identify the cache block.

Since cache block size is 32 bytes, block offset needs 5 bits.

Out of 32 bit address, no. of TAG bits = 32 - 11 - 5 = 32-16 = 16

So, we need 16 tag bits.

It is given that in addition to address tag there are 2 valid bits, 1 modified bit and 1 replacement bit.

So size of each tag entry = 16 tag bits + 2 valid bits + 1 modified bit + 1 replacement bit = 20 bits

Size of cache tag directory=Size of tag entry×Number of tag entries

= 20×16 K

= 320 Kbits

Solution

It is given the disk has 6000rpm.

6000 rotations in 60 seconds.

Time taken for 1 rotation = 60/6000 seconds = 1/100 seconds

Each track has 512 sectors and each sector is 512B in size. So each track size = 512 * 512B = 256KB.

In one rotation one track can be read. So in 1/100 seconds 256KB can be read.

It is given that one word is 4 bytes long. So time taken to read one word from the disk(4 bytes) = (4/256K) * (1/100) seconds ~= 160 ns

Here 160ns is the data preparation time. And time taken by the DMA to transfer the 4 bytes data is one cycle = 80ns.

In cycle stealing mode, the CPU gets blocked for one clock cycle after the data is made ready by the I/O device in this case the disk.

So, % time the cpu gets blocked during DMA operation = 80ns / 160ns = 50%

Solution

Consider the following table:

Here there is no RAW dependency between I0 and I1 so the EX stage of I1 starts at T5 when the previous instruction I0 is no longer in EX stage.

Between I1 and I2 there is dependency, as there is operand forwarding EX phase of I2 starts at T8 after I1’s EX stage completed at T7. To complete all the 3 instructions we need a total of 9 clock cycles as shown in the timing diagram.

Solution

Memory System 1:

Access time for the level-1 cache (T1) = 10 ns

Access time for the level2 cache (T2) = 120 ns

Memory System 2:

Access time for the level-3 cache is (T3) = 20 ns

Access time for the level-4 cache is (T4) = 100 ns

Hit ratio (h2)=0.9

Given that AMAT1 = 1⁄2(AMAT2)

Average access time2 = h2(T3)+(1-h2)(T3+ T4)

= h2(T3)+(1-h2)(T3)+(1-h2)( T4)

= (h2+1-h2)(T3) + (1-h2)( T4)

= (T3)+(1-h2)( T4)

= 20+(1-0.9)(100)

= 30

Since the average memory access time of 1st system is half of average access time of second system,

Average access time1 = 30/2 = h1(T1)+(1-h1)( T1+T2)

This can also be simplified as, 15 = (T1)+(1-h1)( T2)

15 = 10+(1-h1)(120)

15 = 10 + 120 - 120h1

15 = 130 - 120h1

120h1 = 130 - 15

120h1 = 115

h1 = 115/120 = 0.958

Solution

Bottleneck here is U_X as it takes 8ns while U_Y takes 5ns only. We have to do 10 such calculations and we have 2 instances of U_X and U_Y respectively. Since there are two functional units, each unit gets 5 number of units to compute on. Suppose

computation starts at time 0, which means Y starts at 0 and X starts at 5th second since X is dependent on Y and Y finishes computing first element at 5th second.

So, U_X can be done in 8*10/2 = 40ns. For the start U_X needs to wait for U_Y output for 5ns and rest all are pipelined and hence no more wait. So, answer is 5+40=45ns

Solution

Number of Cache entries in the cache of size 256 KB having each block size 128B

=(2^18)/2^7=2^11

Given tag size bits=16

As processor is of 32 bits and cache is using set associative,

number of tag bits +number of bits to represent sets +number of bit to represent block size=32

16+x+7=32

⇒x=9

So, number of sets=2^9

To find k from k-way set associative

⇒2^9 = 2^11 / k

k=2^2=4

Solution

If nothing is mentioned whether it is a simultaneous memory access or hierarchical memory access, we need to consider it as hierarchical memory access only. Here in this question nothing is given about read operation so we need to take it as hierarchical memory access for read operation. But for write it is given as write through policy, which will result in simultaneous memory access. Since write operations in write-through cache always goes to the main memory, in main memory its hit rate is 100%. Hence Hit rate for write= 1.

Since there are 80% read operations and 20% write operations,

Average memory access time = 0.80 * Time spent for read + 0.20 * Time spent for write

Time spent for reading = Hit-rate-for-read * cache access time + Miss-rate-for-read(cache access time + main memory access time)

= ( 0.9 ⨯ 10 + 0.1 ⨯ (100+10) )

= 9+11 = 20ns

Time spend for write = 100ns (simultaneous write mentioned in question)

Average memory access time = 0.8 * 20 + 0.2 * 100 = 16 + 20 = 36 ns

Solution

Cache block size = 256 Bytes, so no. of bits needed for the block offset = 8

Cache size = 16KB, total no. of blocks/lines in the cache = 16KB / 256B = 64.

Since there are 64 blocks in the cache, no. of bits needed for the index = 6

Out of 32 bits of the address, 8 bits are needed for block offset and 6 bits are needed for index. So, no. of tag bits = 32-8-6 = 18 bits

It is given that tag information of 1 valid bit and 1 modified bit are maintained for each cache block. These two bits are in addition to the 18 tag bits from the address.

Total no. of bits required to store the metadata of one cache block = 1+1+18 = 20 bits

Total memory required to store metadata = 20* no. of cache blocks = 20* 64 = 1280 bits

Solution

For I-cache:

No. of blocks in I-cache = 2K words / 4 words per block = 512 = 29

Bits to represent blocks = 9

No. of words within a block = 4 = 22

Bits to represent a word = 2

Tag bits = (length of the physical address of a word) – (Bits to represent blocks ) – (Bits to represent a word)

Tag bits = 30 - 9 - 2 = 19

Each block will have it’s own tag bits. So total tag bits = number of blocks x tag bits.

The capacity of the tag memory in I-cache = 512 X 19 - bit

For D-cache:

No. of blocks in D-cache = 2K words / 4 words per block = 512

Since it is a 2-way set associative mapping, no. of sets = 512 / 2 = 256 = 28

Bits to represent sets = 8

No. of words within a block = 4 = 22

Bits to represent a word = 2

Tag bits = (length of the physical address of a word) – (Bits to represent sets ) – (Bits to represent a word)

Tag bits = 30 - 8 - 2 = 20 bits

Each block will have it’s own tag bits. So total tag bits = number of blocks x tag bits.

The capacity of the tag memory in D-cache = 512 X 20 - bit

For L2-cache:

No. of blocks in L2-cache = 32K words / 16 words per block = 2K

Since it is a 4-way set associative mapping, no. of sets = 2K / 4 = 512 = 29

Bits to represent sets = 9

No. of words within a block = 16 = 24

Bits to represent a word = 4

Tag bits = (length of the physical address of a word) – (Bits to represent sets ) – (Bits to represent a word)

Tag bits = 30 - 9 - 4 = 17 bits

Each block will have it’s own tag bits. So total tag bits = number of blocks x tag bits.

The capacity of the tag memory in D-cache = 2K X 17 - bit

Solution

It is given that seek time = 5ms

It has a rotational speed of 6000 rotations per minute.

So, time taken for 1 rotation will be = 60/6000 = 10ms

Rotation latency= 1/2 * 10 ms = 5 ms

Total time to access a file includes = seek time + rotational latency + data transfer time

To calculate data transfer time, we need to find data transfer rate.

Since the time taken for 1 rotation = 10ms, we can transfer one entire track in one rotation.

The size one track = 500*512 bytes = 250*2*512 bytes = 250*1024 bytes = 250 KB

In 10 ms we can transfer 250 KB of data.

Data transfer rate = In one millisecond the amount of data that can be transferred = 250 KB/10ms = 25 KBytes/ms

Since we are asked to find the time taken to tranfer a file containing 1000 sectors, total size of the file = 1000 * 512 bytes = 500*2*512 bytes = 500*1024 bytes = 500KB

Data transfer time = total bytes to be transferred / transfer rate

= 500KB / 25 KBytes/ms = 20 ms

It is given that each sector requires seek time + rotational latency

= 5ms+ 5ms = 10ms

Total seek time and rotational delay for the 1000 sectors = 1000*10 ms = 10000 ms

To read entire file ,total time = 10000 + 20

= 10020 ms