Results 1 to 18 of 18
  1. #1
    dietgal is offline Member
    Join Date
    Oct 2008
    Posts
    19
    Rep Power
    0

    Default Arrays, Iteration and selection (Cache)

    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:

    Java 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.

  2. #2
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

  3. #3
    dietgal is offline Member
    Join Date
    Oct 2008
    Posts
    19
    Rep Power
    0

    Default

    Basically, supposed to produce this output:

    Java Code:
    $ javac Cache.java
    $ java Cache
    LOAD 19
    LOAD 21
    LOAD 3
    LOAD 10
    LOAD 7
    STOP
    Total time: 500ns.
    But even though i've made the program compliable, it just doesn't work and i dont know where else to add things on.

  4. #4
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

    Default

    Ok, you run the code as java Cache. Then what are the inputs? You have to deal with user inputs according to your code.

    In main method you entered into a while loop. What you have done in the first line of the while loop, assign a value to command variable. Did you do that?

  5. #5
    dietgal is offline Member
    Join Date
    Oct 2008
    Posts
    19
    Rep Power
    0

    Default

    Does that mean that instead of

    Java Code:
    String command = stdIn.next();
    I should change it to

    Java Code:
    String command = 0
    command = stdIn.next();
    ?

    I've tried my program, but after I enter my input as:

    Java Code:
    LOAD 19
    ,

    it just ended and printed out

    Java Code:
    cache miss
    Current time: 2
    19, 0, 0, 0, 0, 0, 0, 0, 
    2, 0, 0, 0, 0, 0, 0, 0,

  6. #6
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

    Default

    That's what I'm saying. For your input LOAD 19 I got the same result as you said here. So you should know what's the input is and what are outputs according to your requirements.

    No need to do any changes you mentioned. Because both are same, isn't it?

  7. #7
    dietgal is offline Member
    Join Date
    Oct 2008
    Posts
    19
    Rep Power
    0

    Default

    That's what I'm saying. For your input LOAD 19 I got the same result as you said here. So you should know what's the input is and what are outputs according to your requirements.
    Sorry, don't really know how to rectify. To prevent the program from ending, I should use another loop? Really at wits' end.

    No need to do any changes you mentioned. Because both are same, isn't it?
    Opps, sorry again, basic concepts not very good.

  8. #8
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

    Default

    Quote Originally Posted by dietgal View Post
    Sorry, don't really know how to rectify. To prevent the program from ending, I should use another loop? Really at wits' end.
    Seems to me that's a different thing. To loop the entire process, you need another loop. First of all, you have to clarify how to handle user inputs. You should know that, because this is your design.

  9. #9
    dietgal is offline Member
    Join Date
    Oct 2008
    Posts
    19
    Rep Power
    0

    Default

    Seems to me that's a different thing. To loop the entire process, you need another loop. First of all, you have to clarify how to handle user inputs. You should know that, because this is your design.
    Had been trying at it for hours, but still can't figure how how to rectify. Would appreciate any kind help!

  10. #10
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

    Default

    How can I help you, because I don't know what's your design.

    Anyway, initially you get a user input,

    Java Code:
    String command = stdIn.next();
    Can you tell me what it is? What you going to do with that user input? Lets start from that place.

  11. #11
    dietgal is offline Member
    Join Date
    Oct 2008
    Posts
    19
    Rep Power
    0

    Default

    Yes, that input in whereby the user key in either "LOAD" or "STOP".

    User is supposed to key in "LOAD XX" then he/she can choose to continue or to "STOP". If user key in "STOP", the program will present the output as in the sample run.

    For my program, I cannot even key in the second "LOAD XX" as it will instantly print out irelevant materials?

  12. #12
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

    Default

    Your code does not handle that much. See the code line below,

    Java Code:
    if(command.equals("STOP"))
    If your command is STOP this code segment is executed. What happen if your command is STOP 23, or LOAD 34. Is there any code to execute?

    Got it what I say?

  13. #13
    dietgal is offline Member
    Join Date
    Oct 2008
    Posts
    19
    Rep Power
    0

    Default

    Java Code:
    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;
        }
    How come the above segment do not handle "LOAD"?

  14. #14
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

    Default

    No that above code segment handle LOAD, but not LOAD XX. That's what I'm saying in last post. You want to handle a command like LOAD XX, right?

  15. #15
    dietgal is offline Member
    Join Date
    Oct 2008
    Posts
    19
    Rep Power
    0

    Default

    No that above code segment handle LOAD, but not LOAD XX. That's what I'm saying in last post. You want to handle a command like LOAD XX, right?
    Got it!

    But in "LOAD XX", the LOAD and XX are separate, how do I code it?

  16. #16
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

    Default

    You have a string of two words, basically. You have two options.

    Make sub strings depends on the space and the XX. But it's not a best practice.

    Use a regular expression and separate two words. Strongly advice to do it in this way.

  17. #17
    dietgal is offline Member
    Join Date
    Oct 2008
    Posts
    19
    Rep Power
    0

    Default

    Thanks.

    Am done with all the test cases.

  18. #18
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

Similar Threads

  1. clear cache
    By Jadellll in forum New To Java
    Replies: 0
    Last Post: 03-20-2008, 09:27 AM
  2. JSP - using connection cache
    By Java Tip in forum Java Tip
    Replies: 0
    Last Post: 01-30-2008, 09:54 AM
  3. cache problem in jsp
    By lpwing in forum JavaServer Pages (JSP) and JSTL
    Replies: 4
    Last Post: 01-15-2008, 07:43 AM
  4. Enum Iteration
    By A.Russell in forum New To Java
    Replies: 1
    Last Post: 08-15-2007, 12:17 PM
  5. iteration on huge amount of files in a folder
    By tshaked in forum Advanced Java
    Replies: 1
    Last Post: 08-07-2007, 07:08 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •