I understand the algorithm, but what is the question? On Wed, Jan 26, 2011 at 10:10 AM, bittu <shashank7andr...@gmail.com> wrote:
> 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
