# Decision Tree-Based Adaptive Reconfigurable Cache Scheme
## 3 Proposed Adaptive Reconfigurable Cache Scheme Based on Decision Tree
### Adaptive Decision-Making Algorithm Based on Decision Tree
**Step 1**: Determine whether the reconfiguration period has been reached according to the current number of clock cycles, and do not perform any operation before the reconfiguration period is reached;  
**Step 2**: After reaching the reconstruction period, the performance monitor starts to collect the information of the application runtime, including the cache miss rate, the total number of memory accesses, and the instructions per cycle (IPC), which are used for the optimal associativity decision;  
**Step 3**: Preserve the statistics of runtime information until the decision-making period is reached;  
**Step 4**: The adaptive controller determines the optimal associativity in the current reconfigurable period according to the trained decision tree model after reaching the decision-making period;  
**Step 5**: If the optimally determined associativity is consistent with the current associativity, the system will continue to operate with the current associativity--jump to step 7;  
**Step 6**: The controller sends an interruption to the CPU, writes back dirty blocks, flushes the cache, and tunes the associativity to the optimal associativity when inconsistent;  
**Step 7**: Determine whether the application has finished running. When it ends, the adaptive control algorithm runs to completion after the application is finished; otherwise, it continues to run to Step 1. Based on the decision tree model of the optimal associativity, the adaptive control algorithm's workflow is shown in Figure 5. The adaptive control algorithm is executed as follows:  
Errors may be caused when the two adjacent reconfiguration periods have different associativities because the mapping relationship between the cache and main memory is changed. Taking the false hit caused by associativity decrease as an example, the cache is two-way set-associative in the first reconfiguration period. The data stored in the main  
Figure 4: Decision tree model. Figure 5: Adaptive control workflow. memory address 1000001 is A. Suppose A is stored in the second way of the 001 cache set. At the same time, the tag stored in the tag array is the upper four bits of the address 1000. The first cache way in the same cache set holds data B from memory address 1001001 with tag 1001 in the tag array. In the next reconfiguration period, the cache is tuned to be direct-mapped (1-way set-associative). At this moment, there is only one cache block in the cache set 0001. Same as the last reconfiguration period, the block holds data B from address 1001001, and the tag in the corresponding tag array is still 1001. If the CPU issues a memory access request to address 1000001, the cache set 0001 will be selected; the upper three bits of the tag 1001 stored in the tag array are compared with the upper three bits of the address 1000001 requested by the CPU. The comparison result is true, and the cache returns a hit signal. The CPU reads B from address 1000001, while the address 1000001 holds data A. This will cause system errors. Figure 6 shows the false hit caused by an associativity decrease. To solve the false hit problem without modifying the complex cache coherent protocol, all dirty blocks are written back to the main memory and the cache is flushed before the reconfiguration. These operations will stall the CPU; all cache accesses after the cache flush will experience a compulsory miss, which will also compromise the system performance. Therefore, it is necessary to evaluate the impact of different reconfiguration periods on performance. This is discussed in Section 5.