use crate::device::capabilities::WORKGROUP_SIZE_1D;
use crate::device::{SubstrateType, WgpuDevice};
use std::time::Instant;
use wgpu::util::DeviceExt;
const DISCRETE_GPU_CACHE_ESTIMATE: u64 = 32 * 1024 * 1024;
const DISCRETE_GPU_BW_GBS: f64 = 500.0;
const DISCRETE_GPU_VRAM_ESTIMATE: u64 = 16 * 1024 * 1024 * 1024;
const INTEGRATED_GPU_CACHE_ESTIMATE: u64 = 16 * 1024 * 1024;
const INTEGRATED_GPU_BW_GBS: f64 = 100.0;
const INTEGRATED_GPU_VRAM_ESTIMATE: u64 = 8 * 1024 * 1024 * 1024;
const CPU_CACHE_ESTIMATE: u64 = 32 * 1024 * 1024;
const CPU_BW_GBS: f64 = 50.0;
const CPU_VRAM_ESTIMATE: u64 = 64 * 1024 * 1024 * 1024;
const FALLBACK_CACHE_ESTIMATE: u64 = 8 * 1024 * 1024;
const FALLBACK_BW_GBS: f64 = 100.0;
const FALLBACK_VRAM_ESTIMATE: u64 = 8 * 1024 * 1024 * 1024;
#[derive(Debug, Clone)]
struct BandwidthSample {
size_bytes: u64,
bandwidth_gbs: f64,
}
#[derive(Debug, Clone)]
pub struct CacheLevel {
pub name: &'static str,
pub size_bytes: u64,
pub bandwidth_gbs: f64,
pub shared: bool,
}
#[derive(Debug, Clone)]
pub struct MainMemory {
pub size_bytes: u64,
pub bandwidth_gbs: f64,
}
#[derive(Debug, Clone)]
pub struct SubstrateMemoryHierarchy {
pub substrate_name: String,
pub substrate_type: SubstrateType,
pub cache_levels: Vec<CacheLevel>,
pub main_memory: MainMemory,
pub optimal_tile_bytes: u64,
pub probed: bool,
}
impl SubstrateMemoryHierarchy {
#[must_use]
pub fn estimate(device: &WgpuDevice) -> Self {
let info = device.adapter_info();
let substrate_type = Self::classify_substrate(info);
let (cache_size, main_bw, vram_size) = match info.device_type {
wgpu::DeviceType::DiscreteGpu => {
(
DISCRETE_GPU_CACHE_ESTIMATE,
DISCRETE_GPU_BW_GBS,
DISCRETE_GPU_VRAM_ESTIMATE,
)
}
wgpu::DeviceType::IntegratedGpu => {
(
INTEGRATED_GPU_CACHE_ESTIMATE,
INTEGRATED_GPU_BW_GBS,
INTEGRATED_GPU_VRAM_ESTIMATE,
)
}
wgpu::DeviceType::Cpu => {
(CPU_CACHE_ESTIMATE, CPU_BW_GBS, CPU_VRAM_ESTIMATE)
}
_ => {
(
FALLBACK_CACHE_ESTIMATE,
FALLBACK_BW_GBS,
FALLBACK_VRAM_ESTIMATE,
)
}
};
Self {
substrate_name: info.name.clone(),
substrate_type,
cache_levels: vec![CacheLevel {
name: "Cache",
size_bytes: cache_size,
bandwidth_gbs: main_bw * 2.0, shared: true,
}],
main_memory: MainMemory {
size_bytes: vram_size,
bandwidth_gbs: main_bw,
},
optimal_tile_bytes: cache_size / 2, probed: false,
}
}
pub async fn probe(device: &WgpuDevice) -> Self {
let info = device.adapter_info();
let substrate_type = Self::classify_substrate(info);
let probe_sizes: Vec<u64> = vec![
4 * 1024, 16 * 1024, 64 * 1024, 256 * 1024, 1024 * 1024, 4 * 1024 * 1024, 16 * 1024 * 1024, 64 * 1024 * 1024, 256 * 1024 * 1024, 512 * 1024 * 1024, ];
let mut samples: Vec<BandwidthSample> = Vec::new();
for &size in &probe_sizes {
if let Some(bw) = Self::probe_bandwidth(device, size).await {
samples.push(BandwidthSample {
size_bytes: size,
bandwidth_gbs: bw,
});
}
}
if samples.len() < 3 {
return Self::estimate(device);
}
let mut cache_levels = Vec::new();
let mut last_cache_bw = samples[0].bandwidth_gbs;
for pair in samples.windows(2) {
let (prev, cur) = (&pair[0], &pair[1]);
let drop_ratio = cur.bandwidth_gbs / last_cache_bw;
if drop_ratio < 0.8 {
let level_name = match cache_levels.len() {
0 => "L2",
1 => "L3",
_ => "Cache",
};
cache_levels.push(CacheLevel {
name: level_name,
size_bytes: prev.size_bytes,
bandwidth_gbs: last_cache_bw,
shared: cache_levels.is_empty(),
});
last_cache_bw = cur.bandwidth_gbs;
}
}
if cache_levels.is_empty() {
let max_sample = samples.iter().max_by(|a, b| {
a.bandwidth_gbs
.partial_cmp(&b.bandwidth_gbs)
.unwrap_or(std::cmp::Ordering::Equal)
});
if let Some(sample) = max_sample {
cache_levels.push(CacheLevel {
name: "Cache",
size_bytes: sample.size_bytes,
bandwidth_gbs: sample.bandwidth_gbs,
shared: true,
});
}
}
let main_bw = samples.last().map_or(100.0, |s| s.bandwidth_gbs);
let main_memory = MainMemory {
size_bytes: device.device().limits().max_buffer_size,
bandwidth_gbs: main_bw,
};
let optimal_tile = cache_levels
.last()
.map_or(16 * 1024 * 1024, |c| (c.size_bytes as f64 * 0.7) as u64);
Self {
substrate_name: info.name.clone(),
substrate_type,
cache_levels,
main_memory,
optimal_tile_bytes: optimal_tile,
probed: true,
}
}
async fn probe_bandwidth(device: &WgpuDevice, size_bytes: u64) -> Option<f64> {
let elements = (size_bytes / 4) as usize;
if size_bytes > device.device().limits().max_buffer_size / 3 {
return None;
}
let shader_src = r"
@group(0) @binding(0) var<storage, read> a: array<f32>;
@group(0) @binding(1) var<storage, read> b: array<f32>;
@group(0) @binding(2) var<storage, read_write> output: array<f32>;
@compute @workgroup_size(256)
fn main(@builtin(global_invocation_id) global_id: vec3<u32>) {
let idx = global_id.x;
if (idx >= arrayLength(&output)) {
return;
}
output[idx] = a[idx] + b[idx];
}
";
let wgpu_device = device.device();
let data: Vec<f32> = (0..elements).map(|i| i as f32 * 0.001).collect();
let buf_a = wgpu_device.create_buffer_init(&wgpu::util::BufferInitDescriptor {
label: Some("probe_a"),
contents: bytemuck::cast_slice(&data),
usage: wgpu::BufferUsages::STORAGE,
});
let buf_b = wgpu_device.create_buffer_init(&wgpu::util::BufferInitDescriptor {
label: Some("probe_b"),
contents: bytemuck::cast_slice(&data),
usage: wgpu::BufferUsages::STORAGE,
});
let buf_out = wgpu_device.create_buffer(&wgpu::BufferDescriptor {
label: Some("probe_out"),
size: size_bytes,
usage: wgpu::BufferUsages::STORAGE,
mapped_at_creation: false,
});
let shader = wgpu_device.create_shader_module(wgpu::ShaderModuleDescriptor {
label: Some("probe_shader"),
source: wgpu::ShaderSource::Wgsl(shader_src.into()),
});
let bgl_entry = |binding: u32, read_only: bool| wgpu::BindGroupLayoutEntry {
binding,
visibility: wgpu::ShaderStages::COMPUTE,
ty: wgpu::BindingType::Buffer {
ty: wgpu::BufferBindingType::Storage { read_only },
has_dynamic_offset: false,
min_binding_size: None,
},
count: None,
};
let bgl = wgpu_device.create_bind_group_layout(&wgpu::BindGroupLayoutDescriptor {
label: None,
entries: &[bgl_entry(0, true), bgl_entry(1, true), bgl_entry(2, false)],
});
let bufs = [&buf_a, &buf_b, &buf_out];
let bind_group = wgpu_device.create_bind_group(&wgpu::BindGroupDescriptor {
label: None,
layout: &bgl,
entries: &bufs
.iter()
.enumerate()
.map(|(i, b)| wgpu::BindGroupEntry {
binding: i as u32,
resource: b.as_entire_binding(),
})
.collect::<Vec<_>>(),
});
let pl = wgpu_device.create_pipeline_layout(&wgpu::PipelineLayoutDescriptor {
label: None,
bind_group_layouts: &[&bgl],
immediate_size: 0,
});
let pipeline = wgpu_device.create_compute_pipeline(&wgpu::ComputePipelineDescriptor {
label: None,
layout: Some(&pl),
module: &shader,
entry_point: Some("main"),
cache: None,
compilation_options: Default::default(),
});
let workgroups = (elements as u32).div_ceil(WORKGROUP_SIZE_1D).min(65_535);
let run_pass = || {
let mut enc =
wgpu_device.create_command_encoder(&wgpu::CommandEncoderDescriptor::default());
{
let mut p = enc.begin_compute_pass(&wgpu::ComputePassDescriptor::default());
p.set_pipeline(&pipeline);
p.set_bind_group(0, Some(&bind_group), &[]);
p.dispatch_workgroups(workgroups, 1, 1);
}
device.submit_and_poll_inner(Some(enc.finish()));
};
let mut warmup_buffers = Vec::with_capacity(3);
for _ in 0..3 {
let mut enc =
wgpu_device.create_command_encoder(&wgpu::CommandEncoderDescriptor::default());
{
let mut p = enc.begin_compute_pass(&wgpu::ComputePassDescriptor::default());
p.set_pipeline(&pipeline);
p.set_bind_group(0, Some(&bind_group), &[]);
p.dispatch_workgroups(workgroups, 1, 1);
}
warmup_buffers.push(enc.finish());
}
device.submit_and_poll_inner(warmup_buffers);
let iterations = 10;
let start = Instant::now();
for _ in 0..iterations {
run_pass();
}
let elapsed = start.elapsed();
let time_per_op = elapsed.as_secs_f64() / iterations as f64;
let bytes = size_bytes * 3;
let bandwidth_gbs = bytes as f64 / time_per_op / 1e9;
Some(bandwidth_gbs)
}
#[must_use]
pub fn discover(device: &WgpuDevice) -> Self {
Self::estimate(device)
}
fn classify_substrate(info: &wgpu::AdapterInfo) -> SubstrateType {
match info.device_type {
wgpu::DeviceType::DiscreteGpu => SubstrateType::DiscreteGpu,
wgpu::DeviceType::IntegratedGpu => SubstrateType::IntegratedGpu,
wgpu::DeviceType::Cpu => SubstrateType::Cpu,
_ => SubstrateType::Other,
}
}
#[must_use]
pub fn largest_cache(&self) -> Option<&CacheLevel> {
self.cache_levels.iter().max_by_key(|c| c.size_bytes)
}
#[must_use]
pub fn total_cache_bytes(&self) -> u64 {
self.cache_levels.iter().map(|c| c.size_bytes).sum()
}
}
#[derive(Debug, Clone)]
pub enum CacheResidency {
Resident {
cache_level: &'static str,
utilization: f64,
},
DramBound {
overflow_bytes: u64,
},
}
#[derive(Debug, Clone)]
pub struct TileConfig {
pub tile_elements: usize,
pub tile_bytes: u64,
pub num_tiles: usize,
pub target_cache: &'static str,
pub expected_bandwidth_gbs: f64,
}
pub struct CacheAwareTiler {
hierarchy: SubstrateMemoryHierarchy,
}
impl CacheAwareTiler {
#[must_use]
pub fn new(hierarchy: SubstrateMemoryHierarchy) -> Self {
Self { hierarchy }
}
#[must_use]
pub fn optimal_tile_size(
&self,
total_bytes: u64,
element_size: usize,
read_write_ratio: f64,
) -> TileConfig {
let working_set_per_element = (element_size as f64 * read_write_ratio) as u64;
for cache in self.hierarchy.cache_levels.iter().rev() {
let usable_cache = (cache.size_bytes as f64 * 0.7) as u64;
let elements_per_tile = usable_cache / working_set_per_element.max(1);
if elements_per_tile >= 1024 {
let tile_bytes = elements_per_tile * element_size as u64;
let num_tiles = total_bytes.div_ceil(tile_bytes) as usize;
return TileConfig {
tile_elements: elements_per_tile as usize,
tile_bytes,
num_tiles,
target_cache: cache.name,
expected_bandwidth_gbs: cache.bandwidth_gbs,
};
}
}
let total_elements = (total_bytes / element_size as u64) as usize;
TileConfig {
tile_elements: total_elements,
tile_bytes: total_bytes,
num_tiles: 1,
target_cache: "DRAM",
expected_bandwidth_gbs: self.hierarchy.main_memory.bandwidth_gbs,
}
}
#[must_use]
pub fn is_cache_resident(&self, data_bytes: u64) -> CacheResidency {
for cache in &self.hierarchy.cache_levels {
if data_bytes <= cache.size_bytes {
return CacheResidency::Resident {
cache_level: cache.name,
utilization: data_bytes as f64 / cache.size_bytes as f64,
};
}
}
let largest = self
.hierarchy
.cache_levels
.last()
.map_or(0, |c| c.size_bytes);
CacheResidency::DramBound {
overflow_bytes: data_bytes.saturating_sub(largest),
}
}
#[must_use]
pub fn predict_bandwidth(&self, data_bytes: u64) -> f64 {
match self.is_cache_resident(data_bytes) {
CacheResidency::Resident { cache_level, .. } => self
.hierarchy
.cache_levels
.iter()
.find(|c| c.name == cache_level)
.map_or(self.hierarchy.main_memory.bandwidth_gbs, |c| {
c.bandwidth_gbs
}),
CacheResidency::DramBound { .. } => {
self.hierarchy.main_memory.bandwidth_gbs * 0.8
}
}
}
}
impl std::fmt::Display for SubstrateMemoryHierarchy {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
writeln!(
f,
"Memory Hierarchy: {} ({})",
self.substrate_name,
if self.probed { "probed" } else { "estimated" }
)?;
writeln!(f, " Type: {:?}", self.substrate_type)?;
for cache in &self.cache_levels {
writeln!(
f,
" {}: {} MB @ {:.0} GB/s",
cache.name,
cache.size_bytes / 1024 / 1024,
cache.bandwidth_gbs
)?;
}
writeln!(
f,
" DRAM: {:.0} GB/s (theoretical)",
self.main_memory.bandwidth_gbs
)?;
writeln!(
f,
" Optimal tile: {} MB",
self.optimal_tile_bytes / 1024 / 1024
)
}
}
#[cfg(test)]
#[path = "cache_hierarchy_tests.rs"]
mod tests;