This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Nov 13th, 2012  |  syntax: C  |  size: 3.41 KB  |  views: 130  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <assert.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include "cache.h"
  5.  
  6. // take the log base 2 of a number      
  7. int
  8. log2(int num) {          
  9.   assert((num & (num - 1)) == 0);   // "num" must be a power of 2 !!
  10.   int ret = 0;
  11.  
  12.   // count the number of 1s in "<num> - 1"
  13.   for (int shifter = num - 1; shifter > 0; shifter >>= 1) {
  14.     ret++;
  15.   }
  16.  
  17.   return ret;
  18. }
  19.  
  20. // initialize the cache by allocating space for all of the cache
  21. // blocks and initializing them to be invalid and with 0 last access
  22. // times.
  23. void
  24. init_cache(cache_t *cache, unsigned size,
  25.            unsigned nways, unsigned block_size) {
  26.  
  27.    int num_blocks = size / block_size;
  28.  
  29.   // this call will assert if any of the parameters are not powers of 2
  30.  
  31.   cache->boff_bits = log2(block_size);
  32.  
  33.   // copy over parameters cache->size, cache->num_blocks, cache->nways, cache->block_size
  34.  
  35.   cache->size = size;
  36.         cache->num_blocks = num_blocks;
  37.         cache->nways = nways;
  38.         cache->block_size = block_size;
  39.  
  40.   // initialize counters and statistics
  41.   cache->LRU_counter = 1;  // for LRU
  42.        
  43.   // setup bitmak masks for tag and index
  44.  
  45.         cache->index_bits = log2(num_blocks / nways);
  46.         cache->tag_bits = size - cache->index_bits - cache->boff_bits;
  47.  
  48.         cache->tag_mask = ((1 << cache->tag_bits) - 1) << (cache->size - cache->tag_bits);
  49.         cache->index_mask = ((1 << cache->index_bits) - 1) << cache->boff_bits;
  50.        
  51.   // dynamically allocate space for cache blocks (this is C's new)
  52.   cache->blocks = (cache_block_t *) malloc(num_blocks * sizeof(cache_block_t));
  53.  
  54.   // initialize each cache block to be invalid
  55.   for (int i = 0 ; i < num_blocks ; ++ i) {
  56.     cache->blocks[i].valid = false;
  57.     cache->blocks[i].last_access_time = 0;
  58.   }
  59. }
  60.  
  61. void init_stats(stats_t *stats){
  62.         stats->accesses=0;
  63.         stats->hits=0;
  64. }
  65.  
  66. // This function returns the cache block which is the "way"th
  67. // entry in the "index"th set.
  68. cache_block_t *
  69. get_block(cache_t *cache, unsigned index, unsigned way) {
  70.   assert (way < cache->nways);
  71.   unsigned num_sets = cache->num_blocks / cache->nways;
  72.   assert (index < num_sets);
  73.   unsigned i = (index * cache->nways) + way;
  74.   return &cache->blocks[i];
  75. }
  76.  
  77. // given an address, extract the tag field for cache "cache"
  78. unsigned
  79. extract_tag(cache_t *cache, unsigned address) {
  80.  
  81.   return address & cache->tag_mask;
  82. }
  83.  
  84. // given an address, extract the index field for cache "cache"
  85. unsigned
  86. extract_index(cache_t *cache, unsigned address) {
  87.   return address & cache->index_mask;
  88. }
  89.  
  90. // given an address, look up in cache "cache" to see if that
  91. // address hits.  If it does update the last access time
  92. bool
  93. find_block_and_update_lru(cache_t *cache, unsigned address, stats_t *stats) {
  94.   unsigned tag = extract_tag(cache, address);
  95.   unsigned index = extract_index(cache, address);
  96.         stats->accesses++;
  97.  
  98.   for (unsigned way = 0 ; way < cache->nways ; ++ way) {
  99.     cache_block_t *block = get_block(cache, index, way);
  100.     if ((block->tag == tag) && block->valid) {
  101.       return true;
  102.                         stats->hits++;
  103.     }
  104.   }
  105.  
  106.   return false;
  107. }
  108.  
  109. // This function should find the LRU block and replace it
  110. // with one that contains "address"
  111. void
  112. fill_cache_with_block(cache_t *cache, unsigned address) {
  113.  
  114.        
  115.   // We technically don't need to check the validity of the blocks we
  116.   // look at, because all invalid blocks will have a last_access_time
  117.   // of 0, but I've added code to do the check, just for completeness
  118.  
  119. }
clone this paste RAW Paste Data