My Assignment details:
In Computer Architecture, a cache is a collection of data duplicating some original values in the computer memory, where the original data is expensive to fetch (owing to longer access time) compared to the cost of reading the cache. In other words, a cache is a temporary storage area where frequently accessed data can be stored for rapid access.
An analogy of a cache would be a librarian. When requested for some books, a librarian would have to walk to the shelves to pick up the books. However, for frequently requested books, the librarian may put them into a bag she carries so that she can quickly produce them on request.
A computer typically has multiple levels of memory caches. However, to keep things simple (as we always do), we will only consider a computer with 1 level of cache to supplement the main memory. The main memory is equivalent to the library shelves, while the cache is like the librarian's bag.
When we look up the cache for some data and find it there, it is called a cache hit. Otherwise, it is called a cache miss. A cache hit requires only 20 nanoseconds. However in the event of a cache miss, since we have to copy the data from the main memory into the cache before we can read it from the cache, it would require 100 nanoseconds.
We assume the cache is initially empty. When the cache is full and we need to bring in some data from the main memory into the cache, we have to decide which existing item in the cache is to be replaced by the incoming item. We shall replace the least recently used item in the cache in this case.
We shall use an example below to illustrate the states of a cache. We assume that the cache can hold 8 items.
Initial state of the cache
Cache: [1][5][9][8][2][7][12][13]
Timestamp: [0][7][4][1][5][6][ 3][ 2]
Current time : 8
The cache array contains the items in each slot of the cache. The timestamp array denotes the last time a particular item was used. For example, item "1" (at index 0) was used at the 0th unit of time, and item "5" was used at the 7th unit of time, and so on. The current time is 8 now. If now the operating system (OS) requests for item "1", we see that there is a cache hit, and consequently, item 1 can be retrieved from the cache in 20 nanoseconds. We also update the timestamp of item "1" to 8 and increase the current time by 1 unit. See the new state of the cache below.
Cache after retrieving item 1.
Cache: [1][5][9][8][2][7][12][13]
Timestamp: [8][7][4][1][5][6][ 3][ 2]
Current time : 9
Now (at time 9), if the OS requests for item "14", we see that there is a cache miss. In this case, the OS has to fetch the data from the memory and put it into the cache which takes 100ns. Since the cache is already full, we replace the LEAST RECENTLY USED item with the newly retrieved item from the memory. In this case the least recently used item is item 8 with a timestamp of 1. See the new state of cache below.
Cache after retrieving item 14.
Cache: [1][5][9][14][2][7][12][13]
Timestamp: [8][7][4][ 9][5][6][ 3][ 2]
Current time : 10
In this exercise, we want to simulate memory access on a cache with 8 slots, and a main memory of arbitrary large size. You may assume that all requested items are in the main memory and the initial state of the cache is all empty. The input is a series of LOAD commands (e.g. LOAD 12), with the last input being a STOP command. All commands are in upper case. Your output should be a statement denoting the total time required for all operations. Recall that a cache hit takes 20ns, and a cache miss takes 100ns.
The following is always true about this exercise:
All LOAD commands are in the upper case.
The STOP command is always the last line of the input.
There is always a single space between the command and the item number.
The loaded item is specified by an integer between 1 to 9999 (inclusive).
The item number may not be loaded in sequence (for example, item 1 is not always loaded before item 2) - this is demonstrated in the sample runs below.
The println() statement given in the skeleton file prints out the totalTime in the correct output format required in this exercise. You are thus advised not to change it.
And my code:
|
Code:
|
import java.util.*;
public class Cache
{
static int CACHE_SIZE = 8;
static int[] cache = new int[CACHE_SIZE];
static int[] timeStamp = new int[CACHE_SIZE];
static int currTime = 1;
public static void main(String[] args)
{
Scanner stdIn = new Scanner(System.in);
String instr = "";
int totalTime = 0;
while(true){
String command = stdIn.next();
if(command.equals("STOP")) break;
if(command.equals("LOAD")){
int item = stdIn.nextInt();
int found = searchCache(item);
currTime++;
if(found==-1){
System.out.println("cache miss");
totalTime = totalTime +100;
int x = LRU(currTime);
cache[x]=item;
timeStamp[x]=currTime;
}
else{
System.out.println("cache hit");
totalTime = totalTime +20;
timeStamp[found]=currTime;
}
}
print();
}//end while
/*
* Type in your code here.
*/
System.out.println("Total time: " + totalTime + "ns.");
}
public static int searchCache(int x){
for(int i=0;i<8;i++){
if(cache[i]==x) return i;
}
return -1;
}
public static int LRU(int ct){
int least = ct,index=-1;
for(int i=0;i<8;i++){
if(timeStamp[i]<least){
least=timeStamp[i];
index=i;
}
}
return index;
}
public static void print(){
System.out.println("Current time: "+currTime);
for(int i=0;i<8;i++){
System.out.print(cache[i]+", ");
}
System.out.println();
for(int i=0;i<8;i++){
System.out.print(timeStamp[i]+", ");
}
System.out.println();
}
} |
Please help me to see what is wrong... I still failed the dynamic cases when I submitted.
Arrays, Iteration and selection (Cache)
Linear Mode
