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.comalgogeeks%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.
