# Decision Tree-Based Adaptive Reconfigurable Cache Scheme
## 3 Proposed Adaptive Reconfigurable Cache Scheme Based on Decision Tree
### Optimal Associativity Search Scheme  
This subsection discusses how the optimal cache associativity configuration can be obtained. The decision tree model of optimal associativity in Section 3.3 can be trained by using the obtained configuration as a sample of the dataset.  
The traditional method generates the optimal associativity scheme by traversing all candidate associativity for each reconfiguration period. The running time of an application is divided into N reconfiguration periods with the same length as shown in Figure 2, and 5 candidate associativities can be adopted in each reconfiguration period. In this case, there are 5N possible cache associativity combination schemes for the running of a certain application. It takes a long time to traverse all the configurations, which makes it difficult to obtain the optimal configuration.  
This paper designs an optimal associativity configuration search scheme, which can generate the optimal configuration only by running the workload once. As shown in Figure 3, the decision-making period of each reconfiguration period is further divided into five equal sub-periods. The optimal associativity search scheme is as follows:  
**Step 1**: Run applications using five candidate associativities sequentially in the corresponding five sub-periods of the decision-making period;  
**Step 2**: Select the associativity that provides the highest performance as the optimal configuration and use this associativity during the stable-running period;  
**Step 3**: The optimal associativity of each reconfiguration period and its corresponding IPC, total number of memory access, and L2 cache miss rate are recorded as a sample of the dataset.  
The decision-making period uses the associativity of the last reconfiguration period. Therefore, the current optimal associativity is also related to the optimal associativity of the last reconfiguration period in addition to the IPC, the total number of memory accesses, and miss rate. With these elements being combined, an optimal cache configuration can be expressed as Equation (2):  
\[\{associativity_{i-1},total\ memory\ access_{i},miss\ rate_{i}, IPC_{i}\}\to associativity_{i} \tag{2}\]  
The parameters to be monitored are in curly brackets. The subscript \(i\) indicates the current reconfiguration period, and the subscript \(i-1\) indicates the last reconfiguration period. These parameters are collected during the decision-making period. The associativity on the right side is the decision of the current optimal associativity.  
The performance of the adaptive reconfigurable cache is related to the length of the reconfiguration period. The shorter the reconfiguration period, the more accurate the observed application behavior. The application behavior may change during the long reconfiguration period, while the statistical information cannot reflect this change. However, reducing the reconfiguration period will increase the reconfiguration number, resulting in a large reconfiguration overhead. System performance will be compromised when  
Figure 3: Optimal associativity search scheme.  
reconfiguration overhead is greater than performance gain benefit from reconfiguration. In Section 5, the optimal reconfiguration overhead is discussed.