optirs_gpu/memory/management/

prefetching.rs

// Memory prefetching for GPU memory management
//
// This module provides advanced prefetching strategies to improve GPU memory
// performance by anticipating future memory access patterns and proactively
// loading data before it's needed.

use std::collections::{BTreeMap, HashMap, VecDeque};
use std::sync::{Arc, Mutex};
use std::time::{Duration, Instant};

/// Main prefetching engine
pub struct PrefetchingEngine {
    /// Configuration
    config: PrefetchConfig,
    /// Statistics
    stats: PrefetchStats,
    /// Active prefetching strategies
    strategies: Vec<Box<dyn PrefetchStrategy>>,
    /// Access pattern history
    access_history: AccessHistoryTracker,
    /// Prefetch requests queue
    prefetch_queue: VecDeque<PrefetchRequest>,
    /// Cache of prefetched data
    prefetch_cache: PrefetchCache,
    /// Performance monitoring
    performance_monitor: PerformanceMonitor,
}

/// Prefetching configuration
#[derive(Debug, Clone)]
pub struct PrefetchConfig {
    /// Enable automatic prefetching
    pub auto_prefetch: bool,
    /// Maximum prefetch distance (bytes)
    pub max_prefetch_distance: usize,
    /// Prefetch window size
    pub prefetch_window: usize,
    /// Minimum access frequency for prefetching
    pub min_access_frequency: f64,
    /// Enable adaptive prefetching
    pub enable_adaptive: bool,
    /// Enable pattern-based prefetching
    pub enable_pattern_based: bool,
    /// Enable stride-based prefetching
    pub enable_stride_based: bool,
    /// Enable ML-based prefetching
    pub enable_ml_based: bool,
    /// Prefetch aggressiveness (0.0 to 1.0)
    pub aggressiveness: f64,
    /// Cache size for prefetched data
    pub cache_size: usize,
    /// Enable performance monitoring
    pub enable_monitoring: bool,
    /// History window size
    pub history_window: usize,
}

impl Default for PrefetchConfig {
    fn default() -> Self {
        Self {
            auto_prefetch: true,
            max_prefetch_distance: 1024 * 1024, // 1MB
            prefetch_window: 64,
            min_access_frequency: 0.1,
            enable_adaptive: true,
            enable_pattern_based: true,
            enable_stride_based: true,
            enable_ml_based: false,
            aggressiveness: 0.5,
            cache_size: 16 * 1024 * 1024, // 16MB
            enable_monitoring: true,
            history_window: 1000,
        }
    }
}

/// Prefetching statistics
#[derive(Debug, Clone, Default)]
pub struct PrefetchStats {
    /// Total prefetch requests
    pub total_requests: u64,
    /// Successful prefetches (used)
    pub successful_prefetches: u64,
    /// Failed prefetches (unused)
    pub failed_prefetches: u64,
    /// Prefetch accuracy ratio
    pub accuracy_ratio: f64,
    /// Total bytes prefetched
    pub total_bytes_prefetched: u64,
    /// Useful bytes prefetched
    pub useful_bytes_prefetched: u64,
    /// Cache hit rate
    pub cache_hit_rate: f64,
    /// Average prefetch latency
    pub average_latency: Duration,
    /// Bandwidth saved by prefetching
    pub bandwidth_saved: u64,
    /// Strategy performance
    pub strategy_stats: HashMap<String, StrategyStats>,
}

/// Individual strategy statistics
#[derive(Debug, Clone, Default)]
pub struct StrategyStats {
    pub requests: u64,
    pub hits: u64,
    pub misses: u64,
    pub accuracy: f64,
    pub latency: Duration,
}

/// Memory access tracking
pub struct AccessHistoryTracker {
    /// Recent access history
    access_history: VecDeque<MemoryAccess>,
    /// Access patterns
    patterns: HashMap<AccessPattern, PatternFrequency>,
    /// Stride patterns
    stride_patterns: HashMap<usize, StrideInfo>,
    /// Sequential access tracking
    sequential_tracking: HashMap<usize, SequentialInfo>,
    /// Access frequency map
    frequency_map: HashMap<usize, AccessFrequency>,
}

/// Memory access record
#[derive(Debug, Clone)]
pub struct MemoryAccess {
    /// Memory address accessed
    pub address: usize,
    /// Access size
    pub size: usize,
    /// Access timestamp
    pub timestamp: Instant,
    /// Access type (read/write)
    pub access_type: AccessType,
    /// Thread/context ID
    pub context_id: u32,
    /// GPU kernel ID
    pub kernel_id: Option<u32>,
}

/// Access type enumeration
#[derive(Debug, Clone, PartialEq)]
pub enum AccessType {
    Read,
    Write,
    ReadWrite,
}

/// Access pattern representation
#[derive(Debug, Clone, Hash, PartialEq, Eq)]
pub struct AccessPattern {
    /// Pattern type
    pub pattern_type: PatternType,
    /// Address deltas
    pub deltas: Vec<isize>,
    /// Pattern size
    pub size: usize,
}

/// Pattern type enumeration
#[derive(Debug, Clone, Hash, PartialEq, Eq)]
pub enum PatternType {
    Sequential,
    Strided,
    Random,
    Irregular,
    Custom(String),
}

/// Pattern frequency tracking
#[derive(Debug, Clone)]
pub struct PatternFrequency {
    pub count: u32,
    pub last_seen: Instant,
    pub confidence: f64,
    pub prediction_accuracy: f64,
}

/// Stride pattern information
#[derive(Debug, Clone)]
pub struct StrideInfo {
    pub stride: isize,
    pub frequency: u32,
    pub last_address: usize,
    pub confidence: f64,
    pub start_time: Instant,
}

/// Sequential access information
#[derive(Debug, Clone)]
pub struct SequentialInfo {
    pub start_address: usize,
    pub current_address: usize,
    pub length: usize,
    pub direction: i8, // 1 for forward, -1 for backward
    pub last_access: Instant,
}

/// Access frequency tracking
#[derive(Debug, Clone)]
pub struct AccessFrequency {
    pub count: u32,
    pub first_access: Instant,
    pub last_access: Instant,
    pub average_interval: Duration,
}

impl AccessHistoryTracker {
    pub fn new(capacity: usize) -> Self {
        Self {
            access_history: VecDeque::with_capacity(capacity),
            patterns: HashMap::new(),
            stride_patterns: HashMap::new(),
            sequential_tracking: HashMap::new(),
            frequency_map: HashMap::new(),
        }
    }

    /// Record a memory access
    pub fn record_access(&mut self, access: MemoryAccess) {
        // Add to history
        self.access_history.push_back(access.clone());
        if self.access_history.len() > self.access_history.capacity() {
            self.access_history.pop_front();
        }

        // Update frequency map
        let freq = self
            .frequency_map
            .entry(access.address)
            .or_insert_with(|| AccessFrequency {
                count: 0,
                first_access: access.timestamp,
                last_access: access.timestamp,
                average_interval: Duration::from_secs(0),
            });

        let interval = if freq.count > 0 {
            access.timestamp.duration_since(freq.last_access)
        } else {
            Duration::from_secs(0)
        };

        freq.count += 1;
        freq.last_access = access.timestamp;
        freq.average_interval = if freq.count > 1 {
            Duration::from_nanos(
                (freq.average_interval.as_nanos() as u64 * (freq.count - 1) as u64
                    + interval.as_nanos() as u64)
                    / freq.count as u64,
            )
        } else {
            interval
        };

        // Detect patterns
        self.detect_patterns(&access);
        self.detect_strides(&access);
        self.track_sequential_access(&access);
    }

    fn detect_patterns(&mut self, current_access: &MemoryAccess) {
        let window_size = 8;
        if self.access_history.len() < window_size {
            return;
        }

        let recent: Vec<&MemoryAccess> =
            self.access_history.iter().rev().take(window_size).collect();
        let mut deltas = Vec::new();

        for i in 1..recent.len() {
            let delta = recent[i - 1].address as isize - recent[i].address as isize;
            deltas.push(delta);
        }

        // Classify pattern type
        let pattern_type = if deltas.iter().all(|&d| d == deltas[0]) {
            if deltas[0] == 0 {
                PatternType::Random
            } else if deltas[0].abs() < 128 {
                PatternType::Sequential
            } else {
                PatternType::Strided
            }
        } else {
            PatternType::Irregular
        };

        let pattern = AccessPattern {
            pattern_type,
            deltas,
            size: window_size,
        };

        // Update pattern frequency
        let freq = self
            .patterns
            .entry(pattern)
            .or_insert_with(|| PatternFrequency {
                count: 0,
                last_seen: current_access.timestamp,
                confidence: 0.0,
                prediction_accuracy: 0.0,
            });

        freq.count += 1;
        freq.last_seen = current_access.timestamp;
        freq.confidence = (freq.count as f64 / 100.0).min(1.0);
    }

    fn detect_strides(&mut self, current_access: &MemoryAccess) {
        if self.access_history.len() < 2 {
            return;
        }

        let prev_access = &self.access_history[self.access_history.len() - 2];
        let stride = current_access.address as isize - prev_access.address as isize;

        let stride_info = self
            .stride_patterns
            .entry(current_access.context_id as usize)
            .or_insert_with(|| StrideInfo {
                stride: 0,
                frequency: 0,
                last_address: prev_access.address,
                confidence: 0.0,
                start_time: current_access.timestamp,
            });

        if stride == stride_info.stride {
            stride_info.frequency += 1;
            stride_info.confidence = (stride_info.frequency as f64 / 10.0).min(1.0);
        } else {
            stride_info.stride = stride;
            stride_info.frequency = 1;
            stride_info.confidence = 0.1;
            stride_info.start_time = current_access.timestamp;
        }

        stride_info.last_address = current_access.address;
    }

    fn track_sequential_access(&mut self, current_access: &MemoryAccess) {
        let seq_info = self
            .sequential_tracking
            .entry(current_access.context_id as usize)
            .or_insert_with(|| SequentialInfo {
                start_address: current_access.address,
                current_address: current_access.address,
                length: 1,
                direction: 0,
                last_access: current_access.timestamp,
            });

        let address_diff = current_access.address as isize - seq_info.current_address as isize;

        if address_diff.abs() <= current_access.size as isize * 2 {
            // Likely sequential
            if seq_info.direction == 0 {
                seq_info.direction = if address_diff > 0 { 1 } else { -1 };
            }

            if (seq_info.direction > 0 && address_diff > 0)
                || (seq_info.direction < 0 && address_diff < 0)
            {
                seq_info.length += 1;
                seq_info.current_address = current_access.address;
                seq_info.last_access = current_access.timestamp;
            } else {
                // Reset sequence
                seq_info.start_address = current_access.address;
                seq_info.current_address = current_access.address;
                seq_info.length = 1;
                seq_info.direction = 0;
                seq_info.last_access = current_access.timestamp;
            }
        } else {
            // Non-sequential, reset
            seq_info.start_address = current_access.address;
            seq_info.current_address = current_access.address;
            seq_info.length = 1;
            seq_info.direction = 0;
            seq_info.last_access = current_access.timestamp;
        }
    }

    /// Get predicted next accesses
    pub fn predict_next_accesses(&self, count: usize) -> Vec<PredictedAccess> {
        let mut predictions = Vec::new();

        // Sequential predictions
        for seq_info in self.sequential_tracking.values() {
            if seq_info.length >= 3 && seq_info.last_access.elapsed() < Duration::from_millis(100) {
                let next_addr = if seq_info.direction > 0 {
                    seq_info.current_address + 64 // Typical cache line size
                } else {
                    seq_info.current_address.saturating_sub(64)
                };

                predictions.push(PredictedAccess {
                    address: next_addr,
                    size: 64,
                    confidence: 0.8,
                    strategy: "Sequential".to_string(),
                    estimated_time: Duration::from_micros(100),
                });
            }
        }

        // Stride predictions
        for stride_info in self.stride_patterns.values() {
            if stride_info.confidence > 0.5 && stride_info.frequency >= 3 {
                let next_addr = (stride_info.last_address as isize + stride_info.stride) as usize;
                predictions.push(PredictedAccess {
                    address: next_addr,
                    size: 64,
                    confidence: stride_info.confidence,
                    strategy: "Stride".to_string(),
                    estimated_time: Duration::from_micros(150),
                });
            }
        }

        predictions.truncate(count);
        predictions
    }
}

/// Predicted memory access
#[derive(Debug, Clone)]
pub struct PredictedAccess {
    pub address: usize,
    pub size: usize,
    pub confidence: f64,
    pub strategy: String,
    pub estimated_time: Duration,
}

/// Prefetch request
#[derive(Debug, Clone)]
pub struct PrefetchRequest {
    /// Target address to prefetch
    pub address: usize,
    /// Size to prefetch
    pub size: usize,
    /// Priority level
    pub priority: PrefetchPriority,
    /// Strategy that generated this request
    pub strategy: String,
    /// Confidence in this prefetch
    pub confidence: f64,
    /// Request timestamp
    pub timestamp: Instant,
    /// Deadline for prefetch completion
    pub deadline: Option<Instant>,
}

/// Prefetch priority levels
#[derive(Debug, Clone, PartialEq, Ord, PartialOrd, Eq)]
pub enum PrefetchPriority {
    Low,
    Normal,
    High,
    Critical,
}

/// Prefetch cache for storing prefetched data
pub struct PrefetchCache {
    /// Cache entries
    entries: BTreeMap<usize, CacheEntry>,
    /// Cache size limit
    size_limit: usize,
    /// Current cache size
    current_size: usize,
    /// LRU tracking
    lru_order: VecDeque<usize>,
    /// Cache statistics
    stats: CacheStats,
}

/// Cache entry
#[derive(Debug, Clone)]
pub struct CacheEntry {
    pub address: usize,
    pub size: usize,
    pub data: Vec<u8>,
    pub prefetch_time: Instant,
    pub last_access: Option<Instant>,
    pub access_count: u32,
    pub strategy: String,
}

/// Cache statistics
#[derive(Debug, Clone, Default)]
pub struct CacheStats {
    pub hits: u64,
    pub misses: u64,
    pub evictions: u64,
    pub total_size: usize,
    pub utilization: f64,
}

impl PrefetchCache {
    pub fn new(size_limit: usize) -> Self {
        Self {
            entries: BTreeMap::new(),
            size_limit,
            current_size: 0,
            lru_order: VecDeque::new(),
            stats: CacheStats::default(),
        }
    }

    /// Insert prefetched data into cache
    pub fn insert(&mut self, address: usize, data: Vec<u8>, strategy: String) -> bool {
        let size = data.len();

        // Check if we need to evict entries
        while self.current_size + size > self.size_limit && !self.entries.is_empty() {
            self.evict_lru();
        }

        if self.current_size + size <= self.size_limit {
            let entry = CacheEntry {
                address,
                size,
                data,
                prefetch_time: Instant::now(),
                last_access: None,
                access_count: 0,
                strategy,
            };

            self.entries.insert(address, entry);
            self.lru_order.push_back(address);
            self.current_size += size;
            true
        } else {
            false
        }
    }

    /// Check if data is in cache and mark as accessed
    pub fn get(&mut self, address: usize, size: usize) -> Option<&[u8]> {
        if let Some(entry) = self.entries.get_mut(&address) {
            if entry.size >= size {
                entry.last_access = Some(Instant::now());
                entry.access_count += 1;

                // Update LRU order
                if let Some(pos) = self.lru_order.iter().position(|&addr| addr == address) {
                    self.lru_order.remove(pos);
                    self.lru_order.push_back(address);
                }

                self.stats.hits += 1;
                return Some(&entry.data[..size]);
            }
        }

        self.stats.misses += 1;
        None
    }

    fn evict_lru(&mut self) {
        if let Some(address) = self.lru_order.pop_front() {
            if let Some(entry) = self.entries.remove(&address) {
                self.current_size -= entry.size;
                self.stats.evictions += 1;
            }
        }
    }

    /// Get cache statistics
    pub fn get_stats(&self) -> &CacheStats {
        &self.stats
    }
}

/// Prefetch strategy trait
pub trait PrefetchStrategy: Send + Sync {
    fn name(&self) -> &str;
    fn can_prefetch(&self, access: &MemoryAccess, history: &AccessHistoryTracker) -> bool;
    fn generate_requests(
        &self,
        access: &MemoryAccess,
        history: &AccessHistoryTracker,
    ) -> Vec<PrefetchRequest>;
    fn get_statistics(&self) -> StrategyStats;
    fn configure(&mut self, config: &PrefetchConfig);
}

/// Sequential prefetching strategy
pub struct SequentialPrefetcher {
    stats: StrategyStats,
    config: SequentialConfig,
}

/// Sequential prefetcher configuration
#[derive(Debug, Clone)]
pub struct SequentialConfig {
    pub prefetch_distance: usize,
    pub min_sequence_length: usize,
    pub max_prefetch_count: usize,
}

impl Default for SequentialConfig {
    fn default() -> Self {
        Self {
            prefetch_distance: 1024,
            min_sequence_length: 3,
            max_prefetch_count: 8,
        }
    }
}

impl SequentialPrefetcher {
    pub fn new(config: SequentialConfig) -> Self {
        Self {
            stats: StrategyStats::default(),
            config,
        }
    }
}

impl PrefetchStrategy for SequentialPrefetcher {
    fn name(&self) -> &str {
        "Sequential"
    }

    fn can_prefetch(&self, access: &MemoryAccess, history: &AccessHistoryTracker) -> bool {
        if let Some(seq_info) = history
            .sequential_tracking
            .get(&(access.context_id as usize))
        {
            seq_info.length >= self.config.min_sequence_length
                && seq_info.last_access.elapsed() < Duration::from_millis(50)
        } else {
            false
        }
    }

    fn generate_requests(
        &self,
        access: &MemoryAccess,
        history: &AccessHistoryTracker,
    ) -> Vec<PrefetchRequest> {
        let mut requests = Vec::new();

        if let Some(seq_info) = history
            .sequential_tracking
            .get(&(access.context_id as usize))
        {
            let mut next_addr = access.address;
            let step = 64; // Cache line size

            for i in 0..self.config.max_prefetch_count {
                next_addr = if seq_info.direction > 0 {
                    next_addr + step
                } else {
                    next_addr.saturating_sub(step)
                };

                if (next_addr as isize - access.address as isize).abs()
                    > self.config.prefetch_distance as isize
                {
                    break;
                }

                let confidence = (1.0 - i as f64 * 0.1).max(0.1);

                requests.push(PrefetchRequest {
                    address: next_addr,
                    size: 64,
                    priority: PrefetchPriority::Normal,
                    strategy: self.name().to_string(),
                    confidence,
                    timestamp: Instant::now(),
                    deadline: Some(Instant::now() + Duration::from_millis(10)),
                });
            }
        }

        requests
    }

    fn get_statistics(&self) -> StrategyStats {
        self.stats.clone()
    }

    fn configure(&mut self, config: &PrefetchConfig) {
        self.config.prefetch_distance = config.max_prefetch_distance;
        self.config.max_prefetch_count = config.prefetch_window;
    }
}

/// Stride-based prefetching strategy
pub struct StridePrefetcher {
    stats: StrategyStats,
    config: StrideConfig,
}

/// Stride prefetcher configuration
#[derive(Debug, Clone)]
pub struct StrideConfig {
    pub min_confidence: f64,
    pub max_stride: isize,
    pub prefetch_degree: usize,
}

impl Default for StrideConfig {
    fn default() -> Self {
        Self {
            min_confidence: 0.6,
            max_stride: 4096,
            prefetch_degree: 4,
        }
    }
}

impl StridePrefetcher {
    pub fn new(config: StrideConfig) -> Self {
        Self {
            stats: StrategyStats::default(),
            config,
        }
    }
}

impl PrefetchStrategy for StridePrefetcher {
    fn name(&self) -> &str {
        "Stride"
    }

    fn can_prefetch(&self, access: &MemoryAccess, history: &AccessHistoryTracker) -> bool {
        if let Some(stride_info) = history.stride_patterns.get(&(access.context_id as usize)) {
            stride_info.confidence >= self.config.min_confidence
                && stride_info.stride.abs() <= self.config.max_stride
                && stride_info.stride != 0
        } else {
            false
        }
    }

    fn generate_requests(
        &self,
        access: &MemoryAccess,
        history: &AccessHistoryTracker,
    ) -> Vec<PrefetchRequest> {
        let mut requests = Vec::new();

        if let Some(stride_info) = history.stride_patterns.get(&(access.context_id as usize)) {
            let mut next_addr = access.address;

            for i in 0..self.config.prefetch_degree {
                next_addr = (next_addr as isize + stride_info.stride) as usize;
                let confidence = stride_info.confidence * (1.0 - i as f64 * 0.15);

                requests.push(PrefetchRequest {
                    address: next_addr,
                    size: access.size,
                    priority: PrefetchPriority::Normal,
                    strategy: self.name().to_string(),
                    confidence,
                    timestamp: Instant::now(),
                    deadline: Some(Instant::now() + Duration::from_millis(15)),
                });
            }
        }

        requests
    }

    fn get_statistics(&self) -> StrategyStats {
        self.stats.clone()
    }

    fn configure(&mut self, config: &PrefetchConfig) {
        self.config.prefetch_degree = config.prefetch_window;
    }
}

/// Performance monitoring for prefetching
pub struct PerformanceMonitor {
    /// Performance history
    history: VecDeque<PerfSample>,
    /// Current metrics
    current_metrics: PerfMetrics,
    /// Monitoring configuration
    config: MonitorConfig,
}

/// Performance sample
#[derive(Debug, Clone)]
pub struct PerfSample {
    pub timestamp: Instant,
    pub cache_hit_rate: f64,
    pub prefetch_accuracy: f64,
    pub bandwidth_utilization: f64,
    pub latency: Duration,
}

/// Performance metrics
#[derive(Debug, Clone, Default)]
pub struct PerfMetrics {
    pub average_hit_rate: f64,
    pub average_accuracy: f64,
    pub average_bandwidth: f64,
    pub average_latency: Duration,
    pub trend_hit_rate: f64,
    pub trend_accuracy: f64,
}

/// Monitor configuration
#[derive(Debug, Clone)]
pub struct MonitorConfig {
    pub sample_interval: Duration,
    pub history_size: usize,
    pub enable_trends: bool,
}

impl Default for MonitorConfig {
    fn default() -> Self {
        Self {
            sample_interval: Duration::from_secs(1),
            history_size: 100,
            enable_trends: true,
        }
    }
}

impl PerformanceMonitor {
    pub fn new(config: MonitorConfig) -> Self {
        Self {
            history: VecDeque::with_capacity(config.history_size),
            current_metrics: PerfMetrics::default(),
            config,
        }
    }

    /// Record a performance sample
    pub fn record_sample(&mut self, sample: PerfSample) {
        self.history.push_back(sample);
        if self.history.len() > self.config.history_size {
            self.history.pop_front();
        }

        self.update_metrics();
    }

    fn update_metrics(&mut self) {
        if self.history.is_empty() {
            return;
        }

        let count = self.history.len() as f64;
        self.current_metrics.average_hit_rate =
            self.history.iter().map(|s| s.cache_hit_rate).sum::<f64>() / count;
        self.current_metrics.average_accuracy = self
            .history
            .iter()
            .map(|s| s.prefetch_accuracy)
            .sum::<f64>()
            / count;
        self.current_metrics.average_bandwidth = self
            .history
            .iter()
            .map(|s| s.bandwidth_utilization)
            .sum::<f64>()
            / count;

        let total_latency_nanos: u64 = self
            .history
            .iter()
            .map(|s| s.latency.as_nanos() as u64)
            .sum();
        self.current_metrics.average_latency =
            Duration::from_nanos(total_latency_nanos / count as u64);

        // Calculate trends
        if self.config.enable_trends && self.history.len() >= 10 {
            let recent_hit_rate: f64 = self
                .history
                .iter()
                .rev()
                .take(5)
                .map(|s| s.cache_hit_rate)
                .sum::<f64>()
                / 5.0;
            let older_hit_rate: f64 = self
                .history
                .iter()
                .rev()
                .skip(5)
                .take(5)
                .map(|s| s.cache_hit_rate)
                .sum::<f64>()
                / 5.0;
            self.current_metrics.trend_hit_rate = recent_hit_rate - older_hit_rate;

            let recent_accuracy: f64 = self
                .history
                .iter()
                .rev()
                .take(5)
                .map(|s| s.prefetch_accuracy)
                .sum::<f64>()
                / 5.0;
            let older_accuracy: f64 = self
                .history
                .iter()
                .rev()
                .skip(5)
                .take(5)
                .map(|s| s.prefetch_accuracy)
                .sum::<f64>()
                / 5.0;
            self.current_metrics.trend_accuracy = recent_accuracy - older_accuracy;
        }
    }

    /// Get current performance metrics
    pub fn get_metrics(&self) -> &PerfMetrics {
        &self.current_metrics
    }
}

impl PrefetchingEngine {
    pub fn new(config: PrefetchConfig) -> Self {
        let mut strategies: Vec<Box<dyn PrefetchStrategy>> = Vec::new();

        if config.enable_pattern_based {
            strategies.push(Box::new(SequentialPrefetcher::new(
                SequentialConfig::default(),
            )));
        }

        if config.enable_stride_based {
            strategies.push(Box::new(StridePrefetcher::new(StrideConfig::default())));
        }

        let access_history = AccessHistoryTracker::new(config.history_window);
        let prefetch_cache = PrefetchCache::new(config.cache_size);
        let performance_monitor = PerformanceMonitor::new(MonitorConfig::default());

        Self {
            config,
            stats: PrefetchStats::default(),
            strategies,
            access_history,
            prefetch_queue: VecDeque::new(),
            prefetch_cache,
            performance_monitor,
        }
    }

    /// Record a memory access and potentially trigger prefetching
    pub fn record_access(&mut self, access: MemoryAccess) -> Vec<PrefetchRequest> {
        // Record access in history
        self.access_history.record_access(access.clone());

        // Check cache for hit/miss
        let cache_hit = self
            .prefetch_cache
            .get(access.address, access.size)
            .is_some();
        if cache_hit {
            self.stats.successful_prefetches += 1;
        }

        let mut new_requests = Vec::new();

        if self.config.auto_prefetch {
            // Generate prefetch requests from strategies
            for strategy in &self.strategies {
                if strategy.can_prefetch(&access, &self.access_history) {
                    let requests = strategy.generate_requests(&access, &self.access_history);
                    for request in requests {
                        if self.should_issue_prefetch(&request) {
                            new_requests.push(request);
                        }
                    }
                }
            }

            // Add requests to queue
            for request in &new_requests {
                self.prefetch_queue.push_back(request.clone());
                self.stats.total_requests += 1;
            }
        }

        new_requests
    }

    fn should_issue_prefetch(&self, request: &PrefetchRequest) -> bool {
        // Check if already in cache
        if self.prefetch_cache.entries.contains_key(&request.address) {
            return false;
        }

        // Check confidence threshold
        if request.confidence < self.config.min_access_frequency {
            return false;
        }

        // Check prefetch distance
        if request.size > self.config.max_prefetch_distance {
            return false;
        }

        true
    }

    /// Process prefetch queue and issue prefetches
    pub fn process_prefetch_queue(&mut self) -> Vec<PrefetchRequest> {
        let mut issued_requests = Vec::new();
        let max_concurrent = (self.config.aggressiveness * 10.0) as usize + 1;

        // Sort by priority and confidence
        let mut pending: Vec<PrefetchRequest> = self.prefetch_queue.drain(..).collect();
        pending.sort_by(|a, b| {
            b.priority.cmp(&a.priority).then_with(|| {
                b.confidence
                    .partial_cmp(&a.confidence)
                    .unwrap_or(std::cmp::Ordering::Equal)
            })
        });

        for request in pending.into_iter().take(max_concurrent) {
            // Simulate prefetch (in real implementation, this would trigger actual memory load)
            let dummy_data = vec![0u8; request.size];
            if self
                .prefetch_cache
                .insert(request.address, dummy_data, request.strategy.clone())
            {
                issued_requests.push(request);
            }
        }

        issued_requests
    }

    /// Update statistics and performance metrics
    pub fn update_performance(&mut self) {
        let cache_stats = self.prefetch_cache.get_stats();

        // Update accuracy ratio
        let total_prefetches = self.stats.successful_prefetches + self.stats.failed_prefetches;
        if total_prefetches > 0 {
            self.stats.accuracy_ratio =
                self.stats.successful_prefetches as f64 / total_prefetches as f64;
        }

        // Update cache hit rate
        let total_accesses = cache_stats.hits + cache_stats.misses;
        if total_accesses > 0 {
            self.stats.cache_hit_rate = cache_stats.hits as f64 / total_accesses as f64;
        }

        // Record performance sample
        let sample = PerfSample {
            timestamp: Instant::now(),
            cache_hit_rate: self.stats.cache_hit_rate,
            prefetch_accuracy: self.stats.accuracy_ratio,
            bandwidth_utilization: 0.8, // Would be calculated from actual usage
            latency: self.stats.average_latency,
        };

        self.performance_monitor.record_sample(sample);
    }

    /// Get prefetching statistics
    pub fn get_stats(&self) -> &PrefetchStats {
        &self.stats
    }

    /// Get cache statistics
    pub fn get_cache_stats(&self) -> &CacheStats {
        self.prefetch_cache.get_stats()
    }

    /// Get performance metrics
    pub fn get_performance_metrics(&self) -> &PerfMetrics {
        self.performance_monitor.get_metrics()
    }

    /// Get access history
    pub fn get_access_history(&self) -> &AccessHistoryTracker {
        &self.access_history
    }

    /// Configure prefetching engine
    pub fn configure(&mut self, config: PrefetchConfig) {
        self.config = config.clone();
        for strategy in &mut self.strategies {
            strategy.configure(&config);
        }
    }
}

/// Thread-safe prefetching engine wrapper
pub struct ThreadSafePrefetchingEngine {
    engine: Arc<Mutex<PrefetchingEngine>>,
}

impl ThreadSafePrefetchingEngine {
    pub fn new(config: PrefetchConfig) -> Self {
        Self {
            engine: Arc::new(Mutex::new(PrefetchingEngine::new(config))),
        }
    }

    pub fn record_access(&self, access: MemoryAccess) -> Vec<PrefetchRequest> {
        let mut engine = self.engine.lock().unwrap_or_else(|e| e.into_inner());
        engine.record_access(access)
    }

    pub fn process_prefetch_queue(&self) -> Vec<PrefetchRequest> {
        let mut engine = self.engine.lock().unwrap_or_else(|e| e.into_inner());
        engine.process_prefetch_queue()
    }

    pub fn get_stats(&self) -> PrefetchStats {
        let engine = self.engine.lock().unwrap_or_else(|e| e.into_inner());
        engine.get_stats().clone()
    }

    pub fn update_performance(&self) {
        let mut engine = self.engine.lock().unwrap_or_else(|e| e.into_inner());
        engine.update_performance();
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_prefetch_engine_creation() {
        let config = PrefetchConfig::default();
        let engine = PrefetchingEngine::new(config);
        assert!(!engine.strategies.is_empty());
    }

    #[test]
    fn test_access_history_tracking() {
        let mut tracker = AccessHistoryTracker::new(100);

        let access = MemoryAccess {
            address: 0x1000,
            size: 64,
            timestamp: Instant::now(),
            access_type: AccessType::Read,
            context_id: 1,
            kernel_id: Some(100),
        };

        tracker.record_access(access);
        assert_eq!(tracker.access_history.len(), 1);
    }

    #[test]
    fn test_prefetch_cache() {
        let mut cache = PrefetchCache::new(1024);

        let data = vec![1, 2, 3, 4];
        assert!(cache.insert(0x1000, data, "Test".to_string()));

        let retrieved = cache.get(0x1000, 4);
        assert!(retrieved.is_some());
        assert_eq!(retrieved.expect("unwrap failed"), &[1, 2, 3, 4]);
    }

    #[test]
    fn test_sequential_prefetcher() {
        let config = SequentialConfig::default();
        let prefetcher = SequentialPrefetcher::new(config);
        assert_eq!(prefetcher.name(), "Sequential");
    }

    #[test]
    fn test_stride_prefetcher() {
        let config = StrideConfig::default();
        let prefetcher = StridePrefetcher::new(config);
        assert_eq!(prefetcher.name(), "Stride");
    }

    #[test]
    fn test_performance_monitor() {
        let config = MonitorConfig::default();
        let mut monitor = PerformanceMonitor::new(config);

        let sample = PerfSample {
            timestamp: Instant::now(),
            cache_hit_rate: 0.8,
            prefetch_accuracy: 0.7,
            bandwidth_utilization: 0.9,
            latency: Duration::from_millis(5),
        };

        monitor.record_sample(sample);
        let metrics = monitor.get_metrics();
        assert!(metrics.average_hit_rate > 0.0);
    }

    #[test]
    fn test_thread_safe_engine() {
        let config = PrefetchConfig::default();
        let engine = ThreadSafePrefetchingEngine::new(config);

        let access = MemoryAccess {
            address: 0x2000,
            size: 128,
            timestamp: Instant::now(),
            access_type: AccessType::Read,
            context_id: 2,
            kernel_id: Some(200),
        };

        // A single access to a brand-new context has no established
        // pattern yet (every strategy requires a minimum run/frequency
        // before it will fire), so this must not panic and must not
        // fabricate a prefetch request out of thin air.
        let requests = engine.record_access(access);
        assert!(requests.is_empty());
    }
}