In order to make their newest microcontroller as cheap as possible, the ACME Widget Company designed it with a very simple cache. The processor is connected to a slow memory system that contains n bytes, numbered 0 to n - 1. The cache holds a copy of k of these bytes at a time, for fast access. It has a base address (referred to as base below), and it holds a copy of the bytes numbered base, base+1, ..., base+k-1. When a program reads a byte, the cache controller executes the following algorithm:
1. Find a new range of k bytes which contains the requested byte, such that the difference between the old and new base addresses is minimized. Note that if the requested byte was already in the cache, then the base address will not change. 2. Update the cache to the new range by reading from the memory system any bytes that are in the new range but not the old range, and discarding any bytes that were in the old range but not the new range. 3. Return the requested byte to the program. To analyze the performance of a program, you wish to know how many bytes are read from the memory system. The numbers of the bytes that the program reads are given in addresses, in the order that they are read. When the program starts, the base address is 0. Thanks & Regards Shashank -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
