Problem 1: Memory Modeling

1.1

Briefly explain what is meant by the term Big Endian in the context of this course. Answer: If you don't think of the term ``memory address'' when you see the terms Big-Endian and Little-Endian, then you don't know your definition.

Typically, we refer to memory as byte addressable. This means that aligned accesses occur at byte boundaries, and that byte, half-word, word, and double-word loads and stores must occur at predefined locations, as shown in the table below. Note that all data access instructions are considered to be integer instrcutions because they require the computation of the effective address using the INT ALU unit.

Dest/Src	Memory	MIPS64	Effective
Register	Access	OP Code	Address
GPR (R0-R31)
	load byte	LB	0 mod 1
	store byte	SB	0 mod 1
	load half word	LH	0 mod 2
	store half word	SH	0 mod 2
	load word	LW	0 mod 4
	store word	SW	0 mod 4
	load double word	LD	0 mod 8
	store double word	SD	0 mod 8
FPR (F0-F31)
	load sp word	L.S	0 mod 4
	store sp word	S.S	0 mod 4
	load dp word	L.D	0 mod 8
	store dp word	S.D	0 mod 8

Just like books can be placed on a shelf on their sides, with their spines readable right side up or upside down (alternatly left to right or right left), or even their spines in, multi-byte words can be stored in memory with two specific byte orderings, as indicated by the location of the MSB, the most significant bit (often, the sign bit), and the location of the least significant bit (the LSB).

While the table indicates how big each word or double word is, and the address at which any such entity resides, it doesn't tell you the byte address of the MSB (most significant bit) or the LSB (least significant bit). Typically, the LSB is the bit which is the coefficient of $2^{0}$, and the MSB is the bit which is the coefficient of $2^{31}$ (or $2^{63}$) when the word (or double word) is interpreted as an unsigned binary number. That is the focus of the Little-Endian or Big-Endian organization--how individual bytes of a multi-byte word are stored in memory. The MSB is the big end, and the LSB is the little end. The way to understand this is to remember the source of the name.

Little Endian means, literally, little end, or LSB, in first.
Big Endian means, literally, big end, or MSB,in first.

So, in Little-Endian organization, the LSB is the byte at address 0 mod 4 of a word, and at address 0 mod 8 of a double word. The MSB is at address 3 mod 4 for a word, and at address 0 mod 7 of a double word.

In Big-Endian organization, the MSB is the byte at address 0 mod 4 of a word, and at 0 mod 8 of a double word. For a word, the LSB is at an address which is 3 mod 4, word, and at address 7 mod 8 of a double word.

Note that a big-endian byte-level organization says nothing about the bit-level organization. Some machines are byte-level big-endian, and bit-level big-endian. Others are byte-level big-endian, and bit-level little-endian. Both bit-flavors of little-endian machines exist as well, but, this is the last you will hear of bit-level ordering.

For purposes of this course, we will always write the MSB on the left and the LSB on the right. Since MIPS assumes a Big Endian organization, the book will label the MSB as bit 0, and the LSB as bit 31 in a word, and is bit 63 in a double word.

1.2

A 256K cache is implemented with a block-size of 4K bytes. Diagram the memory address, assuming that the organization of the cache is direct mapped. Be sure to label all parts of the 48-bit wide address correctly.

Answer: This one is the straightforward one. That is, it works just like the formula in the book.

Block offset: 12 bits because $4K = 2^{2} * 2^{10}= 2^{12}$

Index: 6 bits because $2^{6} =256K/(4K * 1)= 2^{18-12}$

Tag: 30 bits because $30= 48 - 18$

Also, order matters: ``Tag Index Offset'', with MSB on the far left.

1.3

Suppose that the 256K cache described above is implemented using a slightly different organization strategy. How is the cache organized if the index is 5-bits long? Explain your answer for full credit.

Hint: Diagram the memory address and analyze how you would identify a given block in the cache.

Answer: First, we know the organization strategy is different. Since the number of index bits is non-zero, we know it can't be fully associative. And, since the problem states that the organization strategy has changed, it can't be direct mapped.

Note: if it were direct mapped, we'd end up with 8K size blocks, because we'd have 32 sets instead of 64. However, no where in the problem is there any hint of a block size change. That is, a block size change is not considered to be an organizational change.

Thus, we can conclude that it is set associative. The question is, how many way set associative is it? Note that the 5 bits in the index mean that there are 32 sets. We have to determine the number of slots per set.

Now, by inspection, perhaps, you can tell that there are 2 slots per set.

However, we can also use the standard formula, assuming that it's x-way set associative, solving

$$2^{5} = 256K/(4K * x)$$

for x, yields $x=2$.

1.4

Given a memory address, explain how to determine whether or not you have a read hit. Be specific regarding your use of the fields in the address and data areas of the memory.

Answer: Here are the basics. I've left out details regarding actual access of tags-such as if they are checked in parallel or sequentially.

1. Check the index bits to determine which set to examine.
2. Check the cache tag field for a match to the tag bits.
3. If a tag match is found, and the entry is valid, then you have a read hit.

1.5

A draft version of an architecture textbook claims that good memory organization can prevent at least 99% of all cache misses from occurring. Do you believe this statement, or do you think that there might be a typographical error on this page? Make sure you justify your answer clearly using the appropriate memory-related terminology.

Answer: The most basic answer is that no one can ever totally eliminate compulsory misses. So, unless this is an embedded system with an extremely restricted set of programs that are started and never re-started, it's not remotely possible to get the advertised improvements.

Sorry, Genghis! It's off to the garage for you.