DOC

byte-addressable

By Yvonne Baker,2014-08-03 19:03
7 views 0
byte-addressable

COMP212 Computer Organization and Systems

    Tutorial/Lab #4

Problems about Cache Memory

4.2 A two-way set associative cache has lines of 16 bytes and a total size of 8 bytes. The

    64-Mbyte main memory is byte-addressable. Show the format of main memory address.

Ans.

A two-way set => 2 lines / set in the cache;

The cache has lines of 16 bytes and a total size of 8K bytes 3104 => There are a total of 8K bytes/16 bytes = 512 lines (2*2/2) in the cache;

2 lines / set in the cache’ AND ‘There are a total of 512 lines in the cache

    => The cache consists of 512 lines/2 lines/set = 256 sets 8=> 8 bits (256=2) are needed to identify the set number.

64-Mbyte main memory is byte-addressable

    => There are 64M units to be addressed 620=> A 26-bit (2*2) address is needed;

‘The cache has lines of 16 bytes’ AND ‘64-Mbyte main memory’ 22=> Main memory consists of 64-Mbyte/16 bytes = 2 blocks

    => The length of Tag + Set = 22

    => The length of Tag = 22-8 = 14;

The word field length is 26 22 = 4 bits

(Another way to calculate word field length:

    The cache has lines of 16 bytes => The main memory block size is 16 bytes; The main memory is byte-addressable => The word length (size) is 1 byte; => There are 16/1=16 words in one block; 4=> 4 bits (16=2) are needed to identify the word number.)

Therefore, the format of main memory is

    Tag Set Word

    14 8 4

    4.3 For the hexadecimal main memory address 111111, 666666, BBBBBB, show the

    following information, in hexadecimal format:

     a) Tag, Line, and Word values for a direct-mapped cache, using the format of Figure

    4.8 (slide 27).

     1

Ans.

    Address

    (in hexadecimal 111111 666666 BBBBBB

    format)

    Address

    0001 0001 0001 0001 0001 0001 0110 0110 0110 0110 0110 0110 1011 1011 1011 1011 1011 1011 (in binary

    format)

    0001 0001 (11) 0110 0110 (66) 1011 1011 (BB) Tag hhh

    0001 0001 0001 00 (444) 0110 0110 0110 01 (1999) 1011 1011 1011 10 (2EEE) Line h hh

    01 (1) 10 (2) 11 (3) Word hhh

    4.4 List the following values:

     a) For the direct cache example of Fig.4.8: address length, number of addressable units,

    block size, number of blocks in main memory, number of lines in cache, size of tag.

Ans.

    Address length: 24 bits

    24Number of addressable unit: 2, i.e. 16M unit

    2Block size: 2, i.e. 4 words 24222 Number of blocks in main memory: 2/2, i.e. 2

    14Number of lines in cache: 2, i.e. 16K lines

    Size of tag: 8 bits

     2

    b) For the associative cache example of Fig.4.10: address length, number of

    addressable units, block size, number of blocks in main memory, number of lines in

    cache, size of tag.

Ans.

    Address length: 24 bits

    24, i.e. 16M unit Number of addressable unit: 22Block size: 2, i.e. 4 words

    24222 Number of blocks in main memory: 2/2, i.e. 2

    14Number of lines in cache: 2, i.e. 16K lines

    Size of tag: 22 bits

    c) For the associative cache example of Fig.4.12: address length, number of

    addressable units, block size, number of blocks in main memory, number of lines in

    set, number of set, number of lines in cache, size of tag.

     3

Ans.

    Address length: 24 bits 24, i.e. 16M unit Number of addressable unit: 2

    2Block size: 2, i.e. 4 words

    24222 Number of blocks in main memory: 2/2, i.e. 2

    Number of lines in set: 2 13Number of set: 2

    14Number of lines in cache: 2, i.e. 16K lines

    Size of tag: 9 bits

    4.5 Consider a 32-bit microprocessor that has an on-chip 16-KByte four-way set-

    associative cache. Assume that the cache has a line size of four 32-bit words. Draw a

    block diagram of this cache showing its organization and how the different address

    fields are used to determine a cache hit/miss. Where in the cache is the word from

    memory location ABCDE8F8 mapped?

Ans.

A four-way set => 4 lines/set in the cache;

‘16-KByte cache’ AND ‘the cache has a line size of four 32-bit words’ 1432510 => There are 16K*8/4*32 = 2*2/2*2 = 2= 1024 lines in the cache

     4

     lines/set’ AND ‘1024lines in the cache 48 => There are 1024/4 = 256 = 2sets in the cache

    => Set length is 8

    Line size is 4*32 bits = 16 bytes => 4 bits are needed to identify a byte;

    ABCDE8F8 => memory address is 32 bits

So the tag length is 32-8-4=20

     Word select Byte select

     5

    4.6 Given the following specifications for an external cache memory: four-way set-

    associative, line size of two 16-bit words; able to accommodate a total of 4K 32-bit

    words; used with 24-bit addresses. Design the cache structure.

Ans.

    A four-way set => 4 lines/set in the cache;

Line size is 2*16bits = 4 byte

    => 2 bits are needed to identify a byte

     210214 *2*2 = 2bytes A total of 4K 32-bit words => cache size is 2

     1412 1210 So there are 2/4 = 2lines totally, which is equal to 2/4 = 2sets

    => 10 bits are needed to identify a set

So the Tag length is 24-2-10=12

    16 4.8 Consider a machine with a byte addressable main memory of 2bytes and block size of

    8 bytes. Assume that a direct mapped cache consisting of 32 lines is used with this

    machine.

     a) How is a 16-bit memory address divided into tag, line number, and byte number?

     b) Into what line would bytes with each of the following addresses be stored?

     0001 0001 0001 1011

     1100 0011 0011 0100

     1101 0000 0001 1101

     1010 1010 1010 1010

     6

     c) Suppose the byte with address 0001 1010 0001 1010 is stored in the cache. What

    are the addresses of the other bytes stored along with it?

     d) How many total bytes of memory can be stored in the cache?

     e) Why is the tag also stored in the cache?

Ans.

    a) Address length: 16 bits

     Word: 3 rightmost bits (as the block size if 8 bytes)

     Line: 5 middle bits (as there are 32 lines)

     Tag: 8 leftmost bits (as 16 3 5=8)

    b)

     0001 0001 0001 1011 ; line 3

     1100 0011 0011 0100 ; line 6

     1101 0000 0001 1101 ; line 3

     1010 1010 1010 1010 ; line 21

    c)

     bytes with addresses 0001 1010 0001 1000

     0001 1010 0001 1001

     0001 1010 0001 1010

    

     0001 1010 0001 1111

     are stored in the cache.

    d)

     32 lines 8 bytes = 256 bytes

    e) It is because 2 items with two different memory addresses can be stored in the same

    place in the cache. The tag is used to distinguish between them.

    4.11 Consider a memory system that uses a 32-bit address to address at the byte level, plus a

    cache that uses a 64-byte line size.

     a) Assume a direct mapped cache with a tag field in the address of 20 bits. Show the

    address format and determine the following parameters: number of addressable

    units, number of block in main memory, number of lines in cache, size of tag.

Ans.

    a) Address format: Tag=20 bits, Word=6 bits (64-byte line size), Line=32-20-6=6 bits

    32, i.e. 4Giga unit Number of addressable units: 232626 Number of block in main memory: 2/2, i.e. 2

    6 Number of lines in cache: 2=64 lines

     Size of tag: 20 bits

    b) Assume an associative cache. Show the address format and determine the following

    parameters: number of addressable units, number of block in main memory,

    number of lines in cache, size of tag.

Ans.

    b) Address format: Word=6 bits (64-byte line size), Tag=32-6=26 bits

    32 Number of addressable units: 2, i.e. 4Giga unit

    32626 Number of block in main memory: 2/2, i.e. 2

     Number of lines in cache: undetermined

     Size of tag: 26 bits

     7

    c) Assume a 4-way set associative cache with a tag field in the address of 9 bits. Show

    the address format and determine the following parameters: number of addressable

    units, number of block in main memory, number of lines in cache, size of tag.

Ans.

    c) Address format: Tag= 9 bits, Word=6 bits (64-byte line size), Set=32-9-6=17 bits 32, i.e. 4Giga unit Number of addressable units: 2

    32626 Number of block in main memory: 2/2, i.e. 2

     Number of lines in set: 4 17 Number of sets in cache: 2 1719 Number of lines in cache: 4*2=2

     Size of tag: 9 bits

    4.12 Consider a computer with the following characteristics: total of 1MByte of main

    memory; the word size is one byte; block size of 16 bytes; and cache size of 64Kbytes.

     a) For the main memory addresses of F0010, 01234, and CABBE, give the

    corresponding tag, cache line address, and word offsets for a direct-mapped cache.

     b) Give any two main memory addresses with different tags that map to the same

    cache slot for a direct-mapped cache.

Ans.

    a) Word=4 bits,

     Number of cache lines=64Kbytes/16bytes=4K lines=4096 lines. To address them, we

    need 12 bits. Thus, the tag will take up 20-12-4=4 bits

     For MM address

     F0010=1111 0000 0000 0001 0000 ? Tag=1111 (F), Line=001, Word Offset=0

     01234=0000 0001 0010 0011 0100 ? Tag=0000 (0), Line=123, Word Offset=4

     CABBE=1100 1010 1011 1011 1110 ? Tag=1100 (C), Line=ABB, Word Offset=E

    b) We need to pick any address where the slot is the same, but the tag (and optionally, the

    word offset) is different. For the line/slot=1111 1111 1111 (altogether 12 bits), we

    have

    Address 1: Word offset=1111; Slot=1111 1111 1111; Tag=0000

     Address=0FFFF

    Address 2: Word offset=0001; Slot=1111 1111 1111; Tag=0011

     Address=3FFF1

     8

    4.19 A computer has a cache, main memory, and a disk. If a referenced word is in the cache,

    20 ns are required to access it. If it is in the main memory but not in the cache, 60 ns are

    required to load it into the cache, and then the reference is started again. If the word is

    not in the main memory, 12 ms are needed to load it from the disk to main memory,

    followed by 60 ns to copy it to the cache, and then the reference is started again. The

    cache hit ratio is 0.9 and the main memory hit ratio is 0.6. What is the average time

    needed to access a referenced word?

Ans.

     There are three cases to consider:

     9

10

Report this document

For any questions or suggestions please email
cust-service@docsford.com