# Adaptive Regression Prefetching Algorithm by Using Big Data Application Characteristics
## 3 Main Architecture
### Prefetch Engine
#### 3.5.3 Optimized LWR Prefetch Engine  
When the prefetch table cannot be used for regular pattern recognition, the arbiter uses an irregular prefetch engine for prefetching. The irregular prefetch engine searches for frequently accessed data in the prefetch table, specifically targeting the entry with the highest number of offsets to retrieve the most commonly used data. Using linear regression to obtain an optimal regression coefficient vector \(w\) enables the prediction of the value of \(y\) through the corresponding expression as follows:  
\[y=ax \tag{2}\]  
Consequently, we obtain value \(a\) through the least square method and Gaussian erasure, followed by the prediction of the next value \(y\). First, we look for the one with the most offsets in the entry table, and then arrange them in order, where \(x\) is the sequential address, and the \(y\)-axis is the offset value; thus, the sequences of \(x\) and \(y\) can be trained as a set (\(x\), \(y\)); then, the regression algorithm is used to obtain the regression coefficient F, and the next step is to prefetch the next F(n + 1). The above is a simple linear regression algorithm, but in fact, most data may not be described by a linear model, and it is possible that not only can they not fit all data points well, but that the error is also very large. To solve the problem of a non-linear model building a linear model, when the value of a point is predicted, the point close to this point was chosen instead of all points. Based on this idea, a locally weighted regression algorithm was developed, where the closer the others are to a point, the greater the weight, and the greater the contribution to the regression coefficient.  
For the above algorithm, optimization operations were performed for special scenarios. When the predicted value of a certain \(y\) is obtained, the regression coefficient \(w\) is needed, but for the data in the sample, the closer the distance \(x\) is, the larger the value is. If the distance is farther, it gives a small weight, which makes the predicted value \(y^{\prime}\) for \(x\) more suitable for the sample data.  
To choose the right weight, a higher weight of the sample point from a given \(x\) is needed. LWR uses the kernel to give higher weight to the nearby points, with the most commonly used method being the Gaussian kernel function, which corresponds to the following expression:  
\[\omega(x,\ i)=e^{-\frac{(x-x)^{2}}{2\delta^{2}}} \tag{3}\]  
It can be seen from the formula that if the distance between \(x\) and \(x_{i}\) is smaller, \(\omega\) will be larger. However, because the x-axis is arranged in the order of visits, it has no reference value; therefore, for application, \(x\) is changed to \(y\); that is, the new expression is the deformed Gaussian kernel function that can be expressed as:  
\[\omega(y,\ i)=e^{-\frac{(y-y)^{2}}{2\delta^{2}}} \tag{4}\]  
After weighting each point, the regression algorithm is executed to obtain F(n), and F(n + 1) is then prefetched. The prefetch operation method is described in Algorithm 3.  
```
//Step 1: foraddressin Entry table ifoffsetTable[i].dataSize >offsetSize offsetEntries \(\leftarrow\) offsetTable[i] //Step 2:  x \(\leftarrow\) i+1 y \(\leftarrow\) offset[i]Value cc \(\leftarrow\) calCC(offsetEntries)  Aoffset = offsetTable.max - offsetTable.min k \(\leftarrow\) calK(cc, \(\alpha\)offset, pageSize) //function 5 weight[i] \(\leftarrow\) calWeight(y[i], y[maxNum], k) //function 4 //Step 3: //find regression coefficient sortAscendingOrder(sortArray, offsetTable[i]) y[i] \(\leftarrow\) weight[i] * y[i]  coefficient \(\leftarrow\) calRegressionCoefficient(sortArray) //predict offset predictOffsetValue(coefficient, offsetSize + 1) _PrefetchAdd \(\leftarrow\)_ entryTable[i] + predictedoffset returnPrefetchAdd
```  
**Algorithm 3** Optimized Linear Regression Engine.