# Decision Tree-Based Adaptive Reconfigurable Cache Scheme
## 1 Introduction  
The speed of logical processors has been improved rapidly over the last 50 years following Moore's law, while main memory access latency has been improved slowly, resulting in a growing gap between processor speed and main memory access latency [1]. The cache was introduced as a high-speed, small-capacity memory to mitigate the speed difference between the processor and the main memory. Most commercial processors implement a cache with fixed parameters. However, studies have shown that a wide variety of applications have different preferences for cache parameters; even the same application can have different preferences for caches at different running phases [2]. The cache with fixed parameters cannot match all applications, resulting in performance loss [3]. For example, applications prefer lower associativity in the jump phase. Higher associativity is preferred in the loop-operating phase, because the temporal and spatial locality of the data is better.  
Multicore processors are widely used in modern computer systems to improve performance. Applications such as integrated circuit synthesis, weather forecasting, and fluid simulation are designed to be executed in parallel to take advantage of the multicore processors [4]. They usually run on desktop computing platforms or high-performance servers that are not sensitive to energy consumption. In this application scenario, the system performance can be further improved by dynamically tuning the cache associativity according to the requirements of applications runtime. The implementation of an adaptive reconfigurable cache requires two major elements: First, an adaptive decision-making algorithm is required to determine the current optimal cache associativity based on the monitored information of the system and to control the cache to tune to the optimal associativity; second, a cache memory that can change associativity in real-time is required. Static reconfiguration requires running the application with different cache associativity in advance to find the optimal associativity and then running the application with the best associativity. It is impractical to find the optimal associativity for all applications. The behavior of the application is too complex to build a model that reflects the relationship between cache associativity and runtime statistical information in real-time. Machine learning algorithms are suitable for solving such optimization problems.  
To solve these problems, this paper proposes an adaptive reconfigurable cache scheme based on decision tree algorithm: (1) an optimal associativity search scheme is designed and used as the data set to train the optimal associativity decision tree model; (2) an adaptive decision-making algorithm based on the decision tree is used to periodically tune the associativity to reduce the average memory access time of the L2 cache; (3) the dirty block writeback and cache flush operation are introduced after associativity tuning, which avoids the modification of the cache coherent protocol. Compared with other adaptive schemes, the adaptive reconfigurable cache scheme based on the decision tree proposed in this paper significantly reduces the average memory access time.