You are to write (in C, C++ or Java) a program that simulates a simple cache. The parameters associated with the memory system are as follows: Memory Block Size = Cache Line Size = 16 Number of Blocks in Memory =16 Number of Cache Lines = 8 Write Through Cache Policy Each line of the cache has the following components: Valid Bit 0 = The set number Empty 1 = cache Valid belongs Set Tag Data Values Block Number this Memory line Block Copy to Byte 0 of Byte Byte 1 Byte 2 7 Your memory should be initialized to zeros at the start of your program. You have any two choice of which type of block placement strategy to implement for your project from below three: Direct mapped 2-way set associative Fully associative Your submission must include complete instructions for compiling and executing your code. Your program should have the following functions: void print_cache(cache_line_t *my_cache) This function prints all current contents of cache. For example: =================== CACHE ========================== Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Set = 3 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Set = 3 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 void print_mem(int num_cache_lines, int cache_line_size) This function prints all current contents of memory. For example: ================================== MEM ========================== 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 30 31 32 234 34 35 36 37 38 39 40 41 42 43 44 45 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 50 51 52 53 54 55 56 57 58 59 60 61 62 66 64 65 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 void init_cache(cache_line_t my_cache[], int associativity) This function initializes the cache to the following state: ============================== CACHE ============================ Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Set = 3 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Set = 3 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 int map_mem_block_to_cacheline_for_replacement(int block_num, int associativity, cache_line_t my_cache[]) This function receives the memory block number of interest and calculates the cache line number associated with is using the formula for 2-Way Set Associative caches. Please note that internal to this function, you determine the SET NUMBER of the interest. Then within that set you search for the first cache line whose valid bit is 0. This cache line number then will be returned by this function. If no cache lines with valid bit equal to 0 were found, then randomly select one of the cache lines to be replaced. void write_to_cache(int block_num, int offset, int value, cache_line_t my_cache[], int associativity) This function writes a single value to an offset within a given block number 2 void load_from_mem(int block_num, int block_size, cache_line_t my_cache[], int associativity) This function loads a block from memory (identified by the block number into the appropriate cache line (as per the Set associative cache formula). It also sets the valid bit for this cache line to 1, and copies the block number of the memory into the tag field. void write_through_to_mem(int block_num, int block_size, int associativity, cache_line_t my_cache[]) This function writes an entire cache line to the appropriate block in the memory associated with it. int is_cache_hit(int block_num, int associativity, cache_line_t my_cache[]) Gets a mem block number and determines if that block is already in cachememory block number has its tag equal to the block number int calc_number_of_sets(int associativity) This function calculates the number of sets in this cache based on the associativity given. int calc_my_set_number(int cache_line_num, int num_lines, int associativity) this function calculates the set number that any cache line belongs to int map_mem_block_to_set(int block_num, int associativity) ss based on associativity returns the set number in cache mapped to a mem block number void store_to_mem(int block_num, int offset, int value) Stores a single value to the given offset of a given block in memory 3 The main program should have the following flow: init_cache init mem while true { Print the number of hits and misses print_mem print_cache Get from the keyboard the command from the CPU on the bus: If the command is READ, get the block number, and offset. Then if ( is_cache_hit) increment num_read_hits counter else increment num_read_misses counter load_from_mem print the value of the memory location requested If the command is WRITE, get the block number, offset, and value. Then if ( is_cache_hit) increment num_write_hits counter write_to_cache write_thru_to_mem else increment num_write_misses counter load_from_mem print the value of the memory location written if the command is QUIT, exit the loop } 4 A sample run of the program is shown below for your reference and understanding: $ ./cache.exe 2 2-way Set Associative Map Cache Set Associativity of this cache: 2 Number of sets in this cache: 4 =============== cache performance =============== read misses = 0 read hits = 0 write misses = 0 write hits = 0 ================================== MEM ========================== 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 ============================== CACHE ============================ Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0
0 Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 3 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 3 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 5 Enter choice: [0] to read from mem [1] to write to mem [2] to quit > 0 enter block number: 3 enter offset: 2 get_cpu_action(): action = READ, block = 3, offset = 2 cache read miss block [3] offset[2] > [0] =============== cache performance =============== read misses = 1 read hits = 0 write misses = 0 write hits = 0 ================================== MEM ========================== 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 ============================== CACHE ============================ Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 3 v = 1 tag = 3 30 31 32 33 34 35 36 37 38 39 40 41 4 Set = 3 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 6 Enter choice: [0] to read from mem [1] to write to mem [2] to quit > 0 enter block number: 5 enter offset: 1 get_cpu_action(): action = READ, block = 5, offset = 1 cache read miss block [5] offset[1] > [0] =============== cache performance =============== read misses = 2 read hits = 0 write misses = 0 write hits = 0 ================================== MEM ========================== 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 ============================== CACHE============================ Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 1 v = 1 tag = 5 50 51 52 53 54 55 56 57 58 59 60 61 6 Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 3 v = 1 tag = 3 30 31 32 33 34 35 36 37 38 39 40 41 4 Set = 3 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 7 Enter choice: [0] to read from mem [1] to write to mem [2] to quit > 1 enter block number: 4 enter offset: 1 enter value: 444 get_cpu_action(): action = WRITE, block = 4, offset = 1 value = 444 cache write miss block [4] offset[1] > [0] =============== cache performance =============== read misses = 2 read hits = 0 write misses = 1 write hits = 0 ================================== MEM ========================== 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 40 444 42 43 44 45 46 47 48 49 50 51 52 53 54 55 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 ============================== CACHE ============================ Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 1 v = 1 tag = 5 50 51 52 53 54 55 56 57 58 59 60 61 6 Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 3 v = 1 tag = 3 30 31 32 33 34 35 36 37 38 39 40 41 Set = 3 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 8 Enter choice: [0] to read from mem [1] to write to mem [2] to quit > 0 enter block number: 4 enter offset: 1 get_cpu_action(): action = READ, block = 4, offset = 1 cache read miss block [4] offset[1] > [0] =============== cache performance =============== read misses = 3 read hits = 0 write misses = 1 write hits = 0 ================================== MEM ========================== 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 40 444 42 43 44 45 46 47 48 49 50 51 52 53 54 55 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 ============================== CACHE ============================ Set = 0 v = 1 tag = 4 40 444 42 43 44 45 46 47 48 49 50 51 5 Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 1 v = 1 tag = 5 50 51 52 53 54 55 56 57 58 59 60 61 6 Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 Set = 3 v = 1 tag = 3 30 31 32 33 34 35 36 37 38 39 40 41 4 Set = 3 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 9 Enter choice: [0] to read from mem [1] to write to mem [2] to quit > q exiting main loop *******************************************************************************************