CPSC 121 Winter 2, 2019 3. (12 marks] Memory, caching and bitwise operations You do not need to memorize the information in the following paragraphs in order to answer this question, nor will we ask about it on examinations, but it provides interesting information on the way in which computers work, and motivates the question. Once upon a time (up to 1985 or so), computers consisted (mostly) of a cen- tral processing unit (CPU) that executed instructions, and main memory where instructions and data were stored. Instructions and data stored in main mem- ory are accessed using their address (think of it like an apartment number in a large building, or a room number in a hotel). However CPUs kept getting faster and faster, while memory was getting faster at a much slower rate. Thus a gap appeared, and started growing, with the result that CPUs spent less and less time doing useful work, and more and more time waiting for instructions and data to arrive from memory. Computer designers then decided that something clearly needed to be done about this, to feed the CPUs appetite for instructions and data and prevent it from spending most of its time twiddling its electronic thumbs. And thus was born the cache: a small, fast memory that sits between the CPU and main memory. Instructions and data that have been used recently end up in the cache, with the expectation that they will be used again in the near future (at which point the CPU will be able to retrieve them much faster). This of course leads to the question of deciding where to store in the cache the instruction or data stored at a given location in memory. The cache location is usually determined based on the bits of the address where the instruction or data is stored in main memory. Before building a CPU, the designers run simulation to see how well the cache will perform, how big they should make it (in general, smaller caches are faster, but will force the CPU to get data all the way from main memory more often, which slows it down), etc. Thus they need to manipulate the address by ex- tracting some of its bits, or by setting some bits while leaving the other bits unchanged. Most programming languages provide ways to manipulate the bits of integers (signed or unsigned). In this question, we will assume integers are 16 bits and unsigned. Let if r and y be two such integers. & is the bitwise AND operator. r & y denotes the integer whose ith bit is the ith bit of r and the ith bit of y. For instance, assuming that we have unsigned integers r = 0101101011010111 and y = 0011000101001010, then r&y=001000001000010. . | is the bitwise OR operator. x y denotes the integer whose ith bit is the ith bit of r or the ith bit of y. For instance, using the same values for x and y as in the previous bullet point, ry= 0111101111011111. >> is the bitwise right shift operator. I >> i denotes the integer obtained by "deleting" the right most i bits of , and adding i 0 bits to the left of the remaining bits. For instance, 0101101011010111 >> 5 = 0000001011010110 (the bits 10111 were removed). CPSC 121 Winter 2, 2019 Consider a 16 bits integer a representing an address in memory (most CPUs now use 64 bit addresses, but the examples would get incredibly tedious to write and read if we used 64 bits). In order to determine where in the cache the data stored at address a will be stored, the integer a is divided into three different fields, each of which is represented by some of the bits of a. More specifically, if a=b15b14b13b12bubiobgbgb7b6b5b4b3b2bibo then we will call bisb14b13b12biibiobgbg the tag, b7b6b5b4b3 the cache inder, and babibo the cache block offset. a. [2 marks] Given an address a, write an expression that will return the cache block off- set for a. For instance, if a = 0101101011010111 then your expression would return 111 (that is, the integer 7). Your answer might look something like a &01010101010101011 1010111010111010 no, this is not the correct answer!) b. [2 marks] Given an address a, write an expression that will return the cache index for a. For instance, if a = 0101101011010111 then your expression would return 11010 (that is, the integer 26). c. [2 marks] Given an address a, write an expression that will return the tag for a. For instance, if a = 0101101011010111 then your expression would return 01011010 (that is, the integer 181). d. [2 marks] Given an address a, write an expression that will return an identical address except that the cache block offset has been set to 000. For instance, if a = 0101101011010111 then your expression would return 01011010110101000. e. [2 marks] Given an address a, write an expression that will return an identical address except that the cache block offset has been set to 101. For instance, if a = 0101101011010111 then your expression would return 01011010110101101. Hint: use your answer from part (d) as a subexpression. f. [2 marks] Given an address a, write an expression that will return an identical address except that the cache index has been set to 01100. For instance, if a = 0101101011010111 then your expression would return 0101101001100111