Numerical Examples of DRAM and Cache | Advanced Computer Architecture | CS501_Lecture41

Asalamaikkum. Welcome to the series of lectures on advanced computer architecture. So far we have been talking about the memory subsystems. We talked about the technologies prevalent for the memory chips. For the case of static RAM, we said that it is one of the fastest memories available. However, it is still expensive and requires more number of transistors per cell. The dynamic RAM is relatively cheaper and that makes the bulk of the memory that is presently utilized. However, the dynamic RAM requires refreshing because basically the data is stored in the form of ones and zeros as a charge on the capacitor and this capacitor cannot hold the charge indefinitely. So a refresh cycle is required. So primarily we discussed how to build up the memories based on the cells corresponding to the static RAM and the dynamic RAM. Now then we said that in order to have an efficient use of the memories we need to have a hierarchy. We talked about the memory hierarchy. We said that closest to the CPU we provide a cache and the cache would be one of the expensive types of memories. Then we will have main memory which would be primarily a DAM and then the bulk memory which could consist of the hard disks. So we make the hierarchy in the form so that to the user the infinite resources are available or it appears to be infinite resources. So we take the locality principle and we said that we keep the data which would usually be required by CPU one after the other into the cache and if it is not available in the cache then it has to be fetched from the f main memory to cache and we have a possibility of what we talked about the hit or miss. Today we are going to have some numerical worked examples for these ideas regarding the memory subsystems. We'll start with some examples regarding the technologies uh covered for the memories. Then we'll talk about some management issues for the cache. Then we'll see the performance of the cache based on hit and miss. and then we will see that what are the uh writing options which we have already discussed. We'll illustrate these ideas with the help of worked examples so that you still have a better understanding of the working principles of the memory subsystems and the concepts of memory hierarchy and different aspects related with it. We start with a very simple example and we have a dynamic RAM which has 512 rows and its refresh time is given by the manufacturer as 9 milliseconds. So we want to find out what should be the frequency of a row refresh operation on the average. It's very simple. The refresh time is given as 9 milliseconds and the number of rows as 512. Therefore, we have to do 512 row refresh within a time period of 9 milliseconds. In other words, one row refresh operation would require a time 9 millisecond divided by 512 which is 1.76 into 10 ^ - 5 seconds. Consider another example for the same similar DM. However, now the rows are double. It is 1 K that is 1024 rows and a refresh time is given as 10 millisecond. Find out the frequency of row refresh operation and what fraction of the DAM's time is spent on refreshing if each refresh actually takes place after every 100 nanoseconds. Now in this case we have a total number of rows as 1024. The refresh period is given as 10 milliseconds. So therefore one row refresh takes place after every 10 millisecond divided by 1024 which is 9.7 microsconds. Therefore, each row refresh takes actually 100 nanconds, which makes a fraction corresponding to 100 nancond divided by 9.7 microcond which is 1.03%. In our previous two examples, we have seen that DAM needs to be refreshed. that is the charge stored on the capacitor needs to be refreshed. So unless we refresh DM it would lose data. This is not the case in static RAM. Now the process of refreshing should not be confused with the property which we call the volatile memory. Both static as well as dynamic RAM are examples of volatile memory. That means when the power supply is not present then both of these would lose data. Static RAM doesn't need a refreshing process because it would keep data in the form of ones and zeros. The basic cell is in the form of a flip-flop. Right? And in dynamic RAM we primarily utilize the charging and discharging of the capacitor. Now let us look in the next few examples the comparison regarding the price per bite or per unit of the memory for static RAM and dynamic RAM. Naturally you will expect that the dynamic RAM is cheaper. The static RAM is more expensive. Overall memory when you combine along with the disk then the disk would be cheapest. Then we'll have dynamic RAM and then static RAM. And we can combine in the order that nearest to the CPU we will have the most expensive memory. And as we go away from the CPU, the cost would decrease. So combined all together, we just have two worked examples to look into some aspect of price per bite. Consider a memory system having the following specifications as shown in the slide. Find its total cost and cost per bite of memory. We have the static RAM with total of 256 kilobyte. The cost per megabyte of S RAM is $30. D RAM is 128 mgabyte and cost is $1 per megabyte. The hard disk we have 1 GBTE just to illustrate a simple example and the cost is $10 per gabyte. So total cost of the system would be 256 kilobyte of SRAM which is one quarter of mgabyte. So it would be $30 into 1 by4 which comes to $7.5. 128 mgabyte of DAM costs $1 per megabyte. So 1 into 128 is $128. 1 GBTE of disk space costs $10. So altogether this turns out to be 145. The total storage capacity is 256 kilobyte + 128 mgabyte plus 1 gabyte which is 117904 mgabyte. The total cost is 145.5. Therefore the cost per bite is total cost divided by the total number of bytes and it turns out to be 1.2 into 10 raised^ -7 per bte. Now we are going to consider some aspects of memory hierarchy. Now as we said that closest to the CPU we have cache. Physically this cache would consist of the static RAM. Then we have the main memory which would consist of the DAM and then we'll have the virtual memory which would physically be implemented by using hard disks or a number of hard disks if you like. So now we want to look into two aspects that what would be the total or average excess time for a given hierarchy and secondly then what would be the overall cost aspect and then we'll look into the cost benefit ratio. A number of options could be considered. We could have a larger cache which would definitely give us a benefit but the cost would increase. At the same time we could have a large main memory then it would also affect the cost. Two aspects are quite obvious. Firstly at any position in the hierarchy when we increase the memory we'll get a benefit. However the cost would also be involved. So we have to see what is the cost benefit involved in that situation. The second option is that given a total amount of memory we could have different subdivisions. We could have more cache or lesser main memory or less cache and more memory. In that case the performance would be affected in terms of access time. Now if we find the data in cache then excess time would be lower and that would be an example when we have a hit when the data is not there it would be an example of a miss and we need to fetch data from the main memory. So through a couple of other examples we see the performance for different options or different combinations of the cache main memory and the backup memory. Let us look at these examples in the next slides. Find the average access time of a level of memory hierarchy if the hit rate is 80%. The memory access time is 12 nanconds on a hit and 100 nconds on a miss. So in this simple example the hit rate is 80% that is8. Therefore the miss rate is 20% or2. So the time for hit we designate it as TH is 12 nconds and TM which corresponds to miss time the penalty is higher it is 100 nonds. So the average excess time would be hit rate into the time for hit and plus miss rate into the time required for excess for a miss. So it works out as8 into 12 +2 into 100 and this is 29.6 nanconds. In the next example, we consider a memory system with a cache, a main memory and a virtual memory. The access times and hit rates are shown in the slide. We are required to find the average access time for this given hierarchy. Now for the main memory, the hit rate is 99%. For cache it is 80% and virtual memory 100%. Because we are bound to find data in the virtual memory. The excess times are respectively 100 nconds for main memory, 5 nconds for cache and 8 milliseconds for the virtual memory. So the average access time for requests that reach the main memory. So we'll start from the bottom the farthest point that is the virtual memory and then comes the main memory and then we have cache. So therefore 100 nconds into.99 plus 8 millisecond into 01 that gives 80,99 nanconds. average access time for requests that reach the cache that is the next uh hierarchy after the main memory. So we have 5 nconds into8 which is when we hit and get data in the cache plus the uh value which we have calculated 80,999 nconds into the miss rate which is2 that turns out to be 16,23.8 8 nconds or six approximately 16 microsconds. Let us consider another example. The memory hierarchy is shown in this slide. We need to find out the average memory access time for the complete system. The static RAM is given as 5 nconds. As far as access time is concerned, the hit rate is 80%. The next is dynamic RAM with excess time of 60 nconds and a hit rate of again 80%. At the bottom of the hierarchy is the disk which has average excess time of 10 milliseconds and hit rate naturally would be just 100%. Now look at the solution for each level. Average excess time is calculated as hit rate at that level into excess time for that level plus 1 minus the hit rate which corresponds to the miss rate into average excess time for the next level. You could repeat it two times for two different interfaces. Let us look at the average excess time for the complete system. We'll use this formula twice and you just see.8 into 5 nconds plus.2 and within brackets now the second level gives us.8 into 60 nconds plus2 into 10 milliseconds. So 10 milliseconds correspond to disk and we reach the disk at 2 as the rate because8 is the rate for DAM. So if the data is not available in DAM we need to fetch it from the disk. So altogether this turns out to be pretty high and that is 400 013.6 six nanconds which is approximately 400 microsconds. We have looked into the examples of parallelism at instruction level and also with reference to memory we said that pre-charging might be required and that would delay the overall uh access time when we have a read or write or load or store instruction from the memory. Now let us look at one example where we incorporate the pre-charging. Sometimes we need to have stalls also. There would be memory stalls and it would delay an overall process. Parallelism would improve the throughput. It would increase the effective bandwidth. On the other hand, the stalls would deteriorate the performance and it the throughput would decrease. Let us look at a very simple example on this aspect of the memory management. It's a simple example. We are supposed to find the bandwidth or the throughput of a memory system that has a latency of 25 nanconds and a pre-charged time of 5 nconds and it transfers two bytes of data per access. Now we assume no other overhead other than the pre-charge. So therefore the time between two memory references would be equal to the sum of latency and the pre-charge time which is 30 nanconds. Therefore the throughput would be just reciprocal of that 1 / 30 nconds which corresponds to 3.33 into 10 raised to power 7 operations per second and in every operation we transfer two bytes of data. So multiply with 2 and that would give us the bandwidth which is 66.6. six megabytes per second. Now next we are going to look into the examples for the cache management. Now we said that the cache basically is the memory where we use the principle of locality and ahead of time we keep the data bring it from the main memory into the cache so that in the program which is being executed we have the data available in the cache. Now the cache could be organized in different ways and there are three basic ways that we discussed in one of the previous lectures. We said that we could organize the cache in a fully associative manner or we could have set associated or we could have a directly mapped cache. We'll consider these examples in the next slides to illustrate what is the main difference. However, one thing should be clear and that should be kept in mind. The best organization for the cash would be fully associative organization. However, the overhead in this case would be large. we need to compare and the logic would be more exhaustive and we need to find out whether the data is available by more than one comparison. So the address part which we called the tag that needs to be compared with a number of rows available and then the decision would be whether we have a hit or a miss and if there is a hit then corresponding line of data could be transferred. Now in order to reduce the over overhead we could go to the next organization which is set associative. In in this particular case the number of comparisons would reduce and per line we might have uh let us say two entries and this would be called then two set associative organization. In the case of direct mapped cache, we only have one entry per line out of the blocks from the main memory. This is the simplest organization of the C cache and would require the minimum overhead. So in the case of the logic overhead we just say that it would increase from directly mapped cache to set associative and finally to fully associative. Set associative is in between fully associative and the direct mapping of the cache. Let us look at some figures in the following slides. Consider an example where we have a cache with 128 byte cache line or cache block size. How many cycles does it take to fetch a block from main memory if it takes 20 cycles to transfer two bytes of data? Now look at the number of cycles required for the complete transfer of the block which is 20 into 128 divided by 2. There are 20 cycles required per block and we can transfer two bytes of data. Therefore, 128 divided by 2 will have 1,280 cycles to transfer one block from the main memory into the cache. Now, using large cache lines decreases the miss rate, but it increases the amount of time a program takes to execute. as is obvious from the number of clock cycles required to transfer one block of data into the cache. Let us look at another example. Find out the number of cycles required to transfer the same 128 byt cache line as we considered in the last example. If page mode DAM with a cache data delay of eight cycles is used for main memory, assume that the cache lines always lie within a single row of the dynamic RAM and each line lies in a different row than the last line which has been fetched. Now solution goes as follows. The memory request to fetch each cache line would be 128 divided by 2 which is 64. That is two bytes are fetched in each request. Therefore there would be 64 requests per line corresponding to 128 bytes. Only the first fetch requires the complete 20 cycles and the other 63 fetch operations would take only eight clock cycles per fetch. Hence the number of cycles required to fetch a cache line would be 20 + 8 into 63 which is 524 cycles. Let us now look at a very simple and interesting example of directmapped cache. We have 64 kilob of directmapped cache with a line length of 32 bytes. Determine the number of bits in the address that refer to the bite within a cache line. And part B says determine the number of bits in the address required to select the cache line. The total address would have different parts. One part we just call n bits to find the bytes within the line and then m corresponds to the bits to find line within the cache. So in this example we have n is equal to log of 32 because we have 32 bytes in each entry and the number would be just five. So we need to have five bits to indicate the corresponding bite within a line. So the total number of lines would be 64k divided by 32 which is 248. So there are 2k lines in the given cache. So the number of bits required would be log of 248 which is 11 bits. Therefore n is equal to 5 and m is equal to 11 for this particular example. Out of the total address given for the main memory, the remaining bits would be utilized for attack and one bit in addition to that would be used for validity and we just call it the valid bit. I hope you remember it from the previous lecture. Let's have now an example for set associative cache. Consider a two-way set associative cache with the same number as in the last example. That is the total capacity is 64 kilobyt. And now we have 16 bytes line. Find out how many sets are there in the cache. How many bits of address are required to select a set in the cache. Repeat the above two calculations if we have a four-way set associative cache instead of a two-way. Part A is simple. A 64 kilobyte cache with 16 byte lines would contain 64 divided by 16 which is 4k to be exact 4,96 lines of data. In a two-way set associative cache, each set contains two lines. So there are 24,48 sets in the cache. Now the number of bits required would be log of 248 which now corresponds to 11 bits. Therefore 11 bits of address are required to select a set. If we had four-way set associative cache, there would be 1,024 sets and therefore instead of 11 bits, we would require 10 bits to specify the set in the cache. Now just for these two examples just see that the total address is divided into a tag address, a group and bytes. So total number of bits would be in the previous example we had 11 for the group five for the bite and if there were total 16 bits for the main memory then four bits would be used for tag and comparison with the tag would indicate the corresponding entry and let us know if the cache has that particular data available or not. Now we have noticed that for the case of cache the actual capacity of the cache would be lesser than what we have for the main memory and therefore the total address would be uh split up into different parts indicated by given number of bits. So we'll have the number of bytes per line in the cache. Then we'll have total number of lines in the cache and as compared to the number of bits for the total uh addressability of the main memory the remaining bits would indicate the tag and on top of that we will have a valid bit to indicate if the data is available in the cache. It would be just a one bit to indicate the validity. Now whichever out of these three arrangements are used for cache we will have still hit and miss. So under hit and miss the performance of the cache would be further affected by the fact that how many instructions correspond to load and store and we might also have memory stalls right and that would also affect the overall performance of the cache. We are going to look into these aspects in the next example considering the performance of cache under hit and miss. Consider a computer whose number of clocks per instruction we call CPI is one just for illustration. When all memory accesses hit in the cache, the only data accesses are load and store and these total 60% of the instructions. If the miss penalty is 30 clock cycles and the miss rate is 1.5%, how much faster would be the computer if all instructions were cash hits? and we had no miss. Now the solution is very simple. without any miss. The computer performance is given in terms of CPU execution time which is equal to CPU clock cycles plus memory stall cycles multiplied with the clock cycle time which is in the form of symbols. IC stands for instruction count multiplied with CPI the count per instruction which is one in our example. We don't consider memory stall just for simplicity and therefore this is IC multiplied with CPI plus 0 within bracket and multiplied with the clock cycle time. So it is IC into 1 multiplied with T which is the clock cycle time. Now for the computer with the real cache, first we compute the number of memory stalls. The memory stalls would be given as the instruction count multiplied with memory excesses per instruction. then into miss rate and multiplied with penalty corresponding to miss. So for this example we have instruction count multiplied by within brackets 1 + 6. Note that this 1 + 6 represents one instruction access and 6 corresponds to data accesses per instruction that is given that we have 60% as the load instructions or store. So in case of load and store the data is to be fetched and that would cost an extra 60% total would be 1 + 6 multiplied with the miss rate which is 015 into the penalty is 30 cycles. So altogether this would become instruction count multiplied with 72. So therefore the execution time for CPU for this particular cache would be 1.72 into the instruction count multiplied by the clock cycle time. The performance ratio is just the inverse of execution time that is larger the execution time lesser would be the performance. So when we compare it the CPU execution time with cache divided by CPU execution time without using this cache we have this ratio as 1.72. So if we did not encounter any miss that means all the data was available in the cache the computer would be 1.72 times faster. Consider the previous example but this time assume a miss rate of 20 per thousand instructions. What is the memory stall time in terms of instruction count? Now recomputee the memory stall cycles which is simply number of misses into the miss penalty. And we can write it as the instruction count multiplied with number of misses per instruction into the miss penalty. Putting in the data for this example, we get it as instruction count into 6. Let us now look at another aspect of cache and that is the writing policy. In one of the earlier lecture we have talked about this and we say that if we write and update the data in cache then it has to be done at some stage in the main memory also when same data is to be stored. How do we do that? If we don't write and we have uh different data there would be inconsistency of data. So theoretically speaking we should have the same copy of data in the main memory for the same particular block as we have in the cache. There could be two possibilities. One is called write through. In the case of write through when we write data to cache at the same time we also write it in the main memory. However this would cost extra time. Maybe that through parallelism we don't wait for the completion of writing to the main memory but still we need to write into the main memory. This would be called write through. Now the second option is the write back. In the case of write back, we only update the data in the cache and then when that data needs to be changed then that is written also into the main memory. So till such time there is no change in that data that stays in the cache and it is not placed it is not written into the main memory. Now we could also have a miss for the case of right as we had a miss for the case of read. How would it be affected and how would it be tackled? That is illustrated in one of the following examples in the next slide. What happens on a right miss? There are two options to handle a right miss. We could have write allocate. In this case, the block is allocated on a right miss followed by the right hit actions. This is just like read miss. Second option is no right allocate. In this case, when we encounter a right miss, it doesn't affect the cache. The block is modified only in the lower level memory. Let us look at the example as shown in this slide. Assume a fully associative writeback cache with many cache entries that start with empty situation. With the program shown in the slide, we have five memory operations. The address is indicated in the square brackets. Find out what are the number of hits and misses when we use no right allocate or write allocate. That means under the two options what would be the difference in the number of hits and misses for no write allocate the address 300 in the first instruction is not available in the cache and there is no allocation on write. So the first two writes will result in misses. The next address 400 in instruction number three that is read memory 400. It is subsequent write to address 4. It is a hit. The last write to 300 is still a miss. So the result for no right allocate is four misses and only one hit. For the option when we have write allocate the first access to 300 and then to 400 are misses and the rest are hits since 300 and 400 are both found in the cache after the two instructions. Thus the result for right allocate is two misses and three hits. Up till now we have assumed that the same cache contains the program as well as the data which is required by that program. So this situation is called a unified cache. That is the same physical cache has got both program as as well as data. Now we could also have a situation where we could split this cache. So we have two caches. One is for the program, the other one is for the data. So is it always so that the split cache would be better or a unified cache would be better. There could be occasions where split cache could be better and that could be normally the case. However, there could be some acute examples where unified cache could still be better option than a split cache. We look at this principle and see the performance of split versus unified cache. In the next slide, we will consider that we have one option of 64 kilobyte of cache and that would be unified having both program as well as data. The second would be we make it half for data and half for the program. So we'll have two parts or two separate caches each one of 32 kilobytes. Let us see this example in the next slide and compare the performance of the two. As we said in this example we have two options. First one a 32 kilobyte instruction cache with a 32 kilobyte data cache. Or the second option is just to have a 64 kilobyte unified cache. For illustration, we will use the miss rate as given in the table. For 32 kilobyte size, we have for instruction cache as 1.5% or 1.5 instructions per 1,000 instruction as the mis rate. For data cache, it is 40 and for unified it is 42.2. For 64 kilobyte the figures are 7, 38.5, 41.2. The percentage of instruction referenced is about 75%. Assume 40% of the instructions are data transfer instructions. Further assume a hit takes one clock cycle and the miss penalty is 100 clock cycles. A load or store hit takes one extra clock on a unified cache if there is only one cache port to satisfy two simultaneous requests. Also, the unified cache might lead to a structural hazard. What is the average memory access time in each case? Assume write through caches with a right buffer and ignore stalls due to the right buffer. First of all, let us convert the misses per thousand instructions into a miss rate which is very simple. You can just say miss rate is the misses per thousand instruction divided by the memory excesses per instruction and we will get for 32 kilobyte cache as an example this would be 1.5 over,000 and number of memory accesses per instruction are assumed as one it is 015 is the rate. Similarly, 40% would be reflected as 40 divided by 1,000 now divided by 04 because for data we assume that only 40% of the instructions are the data instructions. So this would figure out to be 0.1 the unified miss rate needs to account for instruction and data accesses and therefore the miss rate for 64 kilobyte unified cache would be 42.2 2 /,000 divided by 1 +4 which is 031. As stated above about 70% of the memory accesses are instruction references. Thus the overall miss rate for split cash would be 75% into 0.15 plus the remaining 25% into.1 that turns out to be 026125. Thus a 64 kilobyte unified cache has a slightly miss rate than the two 32 kilobyte caches. The average memory access time can be divided into two parts for instruction and for data accesses. So the average memory access time would be percentage instructions into hit time plus instruction miss time into miss penalty plus the percentage of data into hit time plus miss time into miss penalty within brackets. Therefore, putting down the figures, we see that the average memory access time for unified memory turns out to be 4.41 and for the split one, it turns out to be 3.72. Therefore, the split cache has a better access time despite having a comparable miss rate. Today we have gone through the worked examples to illustrate the principles which we have learned in the earlier lectures. Now with these examples we are going to close the chapters on memory subsystems. We have discussed different technologies which are available for making up the memory modules. We said that normally cash would be utilizing the static RAM and therefore would have the best access time. It would have less excess time. However, one has to pay more cost. The dynamic RAM constitutes the bulk memory, the main memory and then the virtual memory is physically constructed using disks or arrays of disks. Now based on an appropriate partitioning of the different tiers in the hierarchy we could get a good access time at a reasonable cost. So how much should be the cache then how much should be the main memory and how much should be the disk capacity. So everybody would like to have as much as it is possible and we said that larger the memory better would be the overall performance of the system. Nevertheless, the overall performance of the memory still lags behind the performance that we get from the central processing unit. So in order to give a feeling to the programmer that he has got infinite resources we have a hierarchy. We make a structure right from some registers within the CPU then cache then main memory and then virtual memory. Based on this we try to optimize and try to place the data mostly in the cache. We have discussed the performance of the cache for a given miss and hit rates. Then we also looked into the example where we said that if there is additional memory stall based on that some penalty would be there and the overall performance may reduce. So for any particular situation for a given memory subsystem the performance could be evaluated. So to an architect this would be a handy tool and he must understand clearly the memory subsystem so that the overall performance is better and it is coupled with the performance of the CPU. With that we close the aspects of memory subsystems. That's all for today. Till next time Allah hop.