Question

Assume a byte-addressable memory has 64K bytes. Blocks are 8 bytes in length and the cache...

  1. Assume a byte-addressable memory has 64K bytes. Blocks are 8 bytes in length and the cache consists of 4K bytes. Show the format for a main memory address assuming a 4-way set associative cache mapping scheme. Include the field names as well as their sizes.
  2. A direct-mapped cache consists of 8 blocks. Byte-addressable main memory contains 4K blocks of 8 bytes each. Access time for the cache is 22ns, and the time required to fill a cache slot from main memory is 300ns. (This time allows us to determine the block is missing and bring it into cache.) Assume a request is always started in parallel to both cache and to main memory(so if it is not found in cache, we do not have to add this cache search time to the memory access). If a block is missing from cache, the entire block is brought into the cache and the access is restarted. Initially, the cache is empty.  You MUST show your work for all parts of this problem to receive full credit!
    1. Show the main memory address format that allows us to map addresses from main memory to cache. Be sure to include the fields as well as their sizes.
    2. Compute the hit rate for a program that loops 4 times from locations 0x0 to 0x43 (address 0 hex to address 43 hex).
    3. Compute the effective access time for this program.

Homework Answers

Answer #1

Answer 1

Main Memory Size = 64 K bytes = 216 Bytes so main memory address = 16 bits

Block Size = 8 Bytes = 23

Cache Size = 4 K bytes = 212 Bytes

4-way set associative cache which means Number of sets = 4

Main Memory Address = Tag bits Set Offset Byte Offset

Number of sets = Number of blocks / associativity

= (Cache Size/block size) / associativity

= (212 / 23) / 4

= 27 = 128 sets   

So, Main Memory Address = Tag(6 bits) Set Offset (7 bits) Byte Offset(3 bits)

Answer 2

Direct-mapped cache

Number of blocks in cache = 8 = 23.

Number of blocks in Main memory = 4K = 212

Block size = 8 bytes = 23.

Cache access time =  22 ns

Page fault time = 300 ns.

a)

Main memory size = 212 * 23 = 215 so address = 15 bits

Byte offset = 3 bits (required to access each byte in the block)

Block offset = 3 bits (required to access each block in cache)

Tag = 15-3-3= 9 bits

Main Memory Address = Tag(9 bits) Block Offset (3 bits) Byte Offset(3 bits)

b)

Loop runs from 0x0 to 0x43 (67 in decimal)

Each block of memory contains 8 bytes. So first time miss will happen for starting address of block but subsequent 7 addresses will be hit. Please note that number of cache blocks are 8.

Pass 1 of Loop

Main Memory Block

Addresses Cache Block Number of Misses Number of Hits
0 0x0 - 0x7 0 1 7
1 0x8 - 0xF 1 1 7
2 0x10 - 0x17 2 1 7
3 0x18 - 0x1F 3 1 7
4 0x20 - 0x27 4 1 7
5 0x28 - 0x2F 5 1 7
6 0x30 - 0x37 6 1 7
7 0x38 - 0x3F 7 1 7
8 0x40 - 0x43 0 1 3

Pass 2 of Loop

Main Memory Block

Addresses Cache Block Number of Misses Number of Hits
0 0x0 - 0x7 0 1 7
1 0x8 - 0xF 1 0 8
2 0x10 - 0x17 2 0 8
3 0x18 - 0x1F 3 0 8
4 0x20 - 0x27 4 0 8
5 0x28 - 0x2F 5 0 8
6 0x30 - 0x37 6 0 8
7 0x38 - 0x3F 7 0 8
8 0x40 - 0x43 0 1 3

Pass 3 and pass 4 of Loop will also be similar to pass 2.

So Hit ratio = Number of hits / total access (hit+miss)

= 257/272

= 0.94485 = 94.48%

c)

Effective access time = Hit rate * cache access time + miss rate * page fault time

= (257/272) * 22 + (15/272)*300

= 37.33 ns

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Suppose a computer using direct mapped cache has 224 bytes of byte-addressable main memory, and a...
Suppose a computer using direct mapped cache has 224 bytes of byte-addressable main memory, and a cache of 128 blocks, where each cache block contains 8 bytes. For four-way set associative cache, to which block of cache the address 0x1895BA maps? Group of answer choices Block 70 Block 16 Block 23 Not enough information
Assume a byte-addressable memory consisting of 1G (230) bytes. A Direct Mapped Cache contains 256 (28)...
Assume a byte-addressable memory consisting of 1G (230) bytes. A Direct Mapped Cache contains 256 (28) blocks of 2048 (211) bytes each. Therefore the 30 bits address is partitioned into three areas of the following sizes (in bits): offset bits block bits tag bits
In a hypothetical system with 1024 bytes of main memory, 128 bytes of cache, blocks of...
In a hypothetical system with 1024 bytes of main memory, 128 bytes of cache, blocks of 32-byte size, with direct-map (S = 1) placement policy and LRU replacement policy, answer each of the following questions: Determine the address fields for index, tag and block offset in the memory address. How many sets are there in the cache? How many blocks in the main memory are mapped to the same set of blocks in cache? If associative (parallel) comparison is to...
In a hypothetical system with 1024 bytes of main memory, 128 bytes of cache, blocks of...
In a hypothetical system with 1024 bytes of main memory, 128 bytes of cache, blocks of 32-byte size, with direct-map (S = 2) placement policy and LRU replacement policy, answer each of the following questions: Determine the address fields for index, tag and block offset in the memory address. How many sets are there in the cache? How many blocks in the main memory are mapped to the same set of blocks in cache? If associative (parallel) comparison is to...
Suppose a 1024-byte cache has an access time of 0.1 microseconds and the main memory stores...
Suppose a 1024-byte cache has an access time of 0.1 microseconds and the main memory stores 1 Mbytes with an access time of 1 microsecond. A referenced memory block that is not in the cache must be loaded into the cache and the reference started again. Answer the following questions: i. What is the number of bits needed to address the main memory? ii. If the cache hit ratio is 95%, what is the average access time for a memory...
A 16 GB main memory has a 8 MB cache organized as a 8-way set associative...
A 16 GB main memory has a 8 MB cache organized as a 8-way set associative cache with 128 Byte cache blocks (line). How many cache blocks are there in the cache? How many sets are there in the cache? (Show your computation.) Show how the 36-bit address generated by the CPU would be divided to map into the cache. (Indicate the sizes of the tag, line, etc.)
1. Suppose we have a 32KB direct-mapped data cache with 32-byte blocks. a) Show how a...
1. Suppose we have a 32KB direct-mapped data cache with 32-byte blocks. a) Show how a 32-bit memory address is divided into tag, index and offset. Show clearly how many bits are in each field. b) How many total bits are there in this cache? 2. Suppose we have a 8KB direct-mapped data cache with 64-byte blocks. a) Show how a 32-bit memory address is divided into tag, index and offset. Show clearly how many bits are in each field....
Consider a cache of 4 lines of 16 bytes each. Main memory is divided into blocks...
Consider a cache of 4 lines of 16 bytes each. Main memory is divided into blocks of 16 bytes each. That is, block 0 has bytes with addresses 0 through 15, and so on. Now consider a program that accesses memory in the following sequence of addresses: Once: 63 through 70. Loop two times: 15 through 32; 80 through 95. Suppose the cache is organized as two-​way set associative, with two sets of two lines each. Even-​numbered blocks are assigned...
1.) Perform the following multiplication using Booth’s algorithm: (You will receive full credit only if you...
1.) Perform the following multiplication using Booth’s algorithm: (You will receive full credit only if you show all your work)      13 x -13 (a) 27/4 Using paper pencil approach and (b) simulate how a machine does this job 2.)Perform the following division as directed: (a) 27/4 using non-restoring division algorithm // we need 4 quotient bits. (b) Using Newton-Raphson algorithm find 1/d when d=0.84 // show the results of the first 3 iterations 3.) A real-time computer system has...
1. The memory units that follow are specified by the number of words times the number...
1. The memory units that follow are specified by the number of words times the number of bits per word. How many address lines and input/output data lines are needed in each case? (a) 8K X 16 (b) 2G X 8 (c) 16M X 32 (d) 256K X 64 2. Give the number of bytes stored in each memory unit in question 1. 3. Word number 563 decimal in the memory shown in Fig. 7.3 (see Mano-Ch7.pdf) contains the binary...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT