Introduction
Modern computing systems face a significant performance bottleneck due to the I/O gap between high-speed processors and slower storage devices. Data prefetching is a critical technique used to mitigate this latency by predicting and loading future data blocks into cache before they are explicitly requested. While traditional prefetchers rely on simple sequential patterns, modern multi-threaded workloads exhibit complex, non-linear access patterns. Recent deep learning approaches, such as LSTMs, treat data access as a chronological sequence of Logical Block Address (LBA) deltas. However, these models often fail to capture the underlying spatial and temporal dependencies disrupted by high concurrency.
Methodology: The Stream-Graph Approach
SGDP (Stream-Graph Data Prefetcher) addresses these limitations by modeling data access patterns as weighted directed graphs rather than linear sequences. This shift allows the model to capture complex relationships that are often obscured in raw chronological traces.
The SGDP framework operates in four primary stages:
- Stream Construction: Access histories are partitioned into discrete "streams" based on temporal proximity. A new stream is initiated if the time interval between successive requests exceeds a predefined threshold.
- Hybrid Graph Modeling: For each stream, a weighted directed graph is constructed using two edge types: sequential edges for immediate succession and full-connect edges to capture global temporal locality and context within the stream.
- Gated Graph Neural Networks (GNNs): A Gated GNN processes these graphs to learn high-dimensional embeddings of LBA deltas, effectively capturing spatial interdependencies.
- Attention Mechanism: An attention layer integrates local preferences with global stream interactions to output the most probable next LBA delta.
Experimental Evaluation
The researchers evaluated SGDP across eight diverse real-world datasets, including five traces from Microsoft Research Cambridge (MSRC) and three proprietary traces from Huawei (HW) commercial storage systems. These datasets represent a wide array of workloads, from media servers to high-traffic production environments.
Results and Discussion
SGDP demonstrates superior performance compared to both traditional stride prefetchers and state-of-the-art (SOTA) deep learning models like DeepPrefetcher and Delta-LSTM.
Key performance metrics include:
- Hit Ratio (HR): SGDP achieved a 6.21% average improvement over SOTA models.
- Effective Prefetching Ratio (EPR): Accuracy improved by 7.00%, indicating a significant reduction in wasted bandwidth from incorrect predictions.
- Inference Speed: SGDP achieved a 3.13x speedup in inference time compared to DeepPrefetcher, a crucial requirement for real-time storage system deployment.
The core innovation of this research is the realization that logical relationships between data blocks are often preserved in graph structures even when chronological sequences are jumbled by concurrency. By predicting address deltas instead of absolute addresses, SGDP also significantly reduces the model's search space, enhancing efficiency.
Conclusion
SGDP represents a significant advancement in data prefetching by leveraging the structural advantages of GNNs. Its ability to handle complex, concurrent workloads with high accuracy and low latency makes it a viable candidate for next-generation storage systems. Future work will focus on addressing data sparsity and further optimizing stream construction parameters for varied workloads.
Summary updated