use crate::fuse::compute_costs;
use crate::inline::{InlineVec, OperandVec};
use crate::{BLOCK_MEMORY_SIZE, CACHE_LINE_SIZE};
use strided_view::auxiliary::index_order;
pub(crate) fn compute_block_sizes(
dims: &[usize],
strides_list: &[&[isize]],
elem_size: usize,
) -> InlineVec<usize> {
if dims.is_empty() || elem_size == 0 {
return dims.iter().copied().collect();
}
let elem_size = elem_size as u128;
let byte_strides: OperandVec<InlineVec<u128>> = strides_list
.iter()
.map(|strides| {
strides
.iter()
.map(|&s| s.unsigned_abs() as u128 * elem_size)
.collect()
})
.collect();
let byte_stride_refs: OperandVec<&[u128]> = byte_strides.iter().map(|s| s.as_slice()).collect();
if total_memory_region_at(dims, &byte_stride_refs, 0) <= BLOCK_MEMORY_SIZE as u128
|| strides_list.iter().all(|s| strictly_increasing(s))
{
return dims.iter().copied().collect();
}
let stride_orders: OperandVec<InlineVec<usize>> =
strides_list.iter().map(|s| index_order(s)).collect();
let stride_order_refs: OperandVec<&[usize]> =
stride_orders.iter().map(|s| s.as_slice()).collect();
let costs = compute_costs(strides_list);
compute_blocks(
dims,
&costs,
&byte_stride_refs,
&stride_order_refs,
BLOCK_MEMORY_SIZE,
)
}
fn strictly_increasing(strides: &[isize]) -> bool {
strides.first().is_some_and(|&s| s != 0)
&& strides
.windows(2)
.all(|w| w[0].unsigned_abs() < w[1].unsigned_abs())
}
fn compute_blocks(
dims: &[usize],
costs: &[isize],
byte_strides: &[&[u128]],
stride_orders: &[&[usize]],
block_size: usize,
) -> InlineVec<usize> {
compute_blocks_at(dims, 0, costs, byte_strides, stride_orders, block_size)
}
fn compute_blocks_at(
dims: &[usize],
offset: usize,
costs: &[isize],
byte_strides: &[&[u128]],
stride_orders: &[&[usize]],
block_size: usize,
) -> InlineVec<usize> {
let n = dims.len();
if n == 0 {
return InlineVec::new();
}
let block_size_bytes = block_size as u128;
if total_memory_region_at(dims, byte_strides, offset) <= block_size_bytes {
return dims.iter().copied().collect();
}
let min_order = stride_orders
.iter()
.filter_map(|orders| orders[offset..].iter().min().copied())
.min()
.unwrap_or(1);
if stride_orders
.iter()
.all(|orders| !orders[offset..].is_empty() && orders[offset] == min_order)
{
let tail_blocks = compute_blocks_at(
&dims[1..],
offset + 1,
&costs[1..],
byte_strides,
stride_orders,
block_size,
);
let mut result: InlineVec<usize> = InlineVec::new();
result.push(dims[0]);
result.extend(tail_blocks);
return result;
}
let min_stride = byte_strides
.iter()
.filter_map(|s| s[offset..].iter().min().copied())
.min()
.unwrap_or(0);
if min_stride > block_size_bytes {
return (0..n).map(|_| 1).collect();
}
let mut blocks: InlineVec<usize> = dims.iter().copied().collect();
while total_memory_region_at(&blocks, byte_strides, offset) >= 2 * block_size_bytes {
let i = last_argmax_weighted(&blocks, costs);
if i.is_none() || blocks[i.unwrap()] <= 1 {
break;
}
let i = i.unwrap();
blocks[i] = blocks[i].div_ceil(2);
}
while total_memory_region_at(&blocks, byte_strides, offset) > block_size_bytes {
let i = last_argmax_weighted(&blocks, costs);
if i.is_none() || blocks[i.unwrap()] <= 1 {
break;
}
let i = i.unwrap();
blocks[i] -= 1;
}
blocks
}
#[cfg(test)]
fn total_memory_region(dims: &[usize], byte_strides: &[&[u128]]) -> u128 {
total_memory_region_at(dims, byte_strides, 0)
}
fn total_memory_region_at(dims: &[usize], byte_strides: &[&[u128]], offset: usize) -> u128 {
let cache_line = CACHE_LINE_SIZE as u128;
let mut memory_region = 0u128;
for strides in byte_strides {
let strides = &strides[offset..];
let mut num_contiguous_bytes = 0u128;
let mut num_cache_line_blocks = 1u128;
for (&d, &s) in dims.iter().zip(strides.iter()) {
if s < cache_line {
num_contiguous_bytes =
num_contiguous_bytes.saturating_add(d.saturating_sub(1) as u128 * s);
} else {
num_cache_line_blocks = num_cache_line_blocks.saturating_mul(d as u128);
}
}
let contiguous_lines = num_contiguous_bytes / cache_line + 1;
memory_region = memory_region.saturating_add(
cache_line
.saturating_mul(contiguous_lines)
.saturating_mul(num_cache_line_blocks),
);
}
memory_region
}
fn last_argmax_weighted(blocks: &[usize], costs: &[isize]) -> Option<usize> {
if blocks.is_empty() {
return None;
}
let mut max_score = 0u128;
let mut max_idx = None;
for (i, (&b, &c)) in blocks.iter().zip(costs.iter()).enumerate() {
if b <= 1 {
continue;
}
let score = (b - 1) as u128 * c as u128;
if score >= max_score {
max_score = score;
max_idx = Some(i);
}
}
max_idx
}
#[cfg(test)]
#[path = "block/tests/tests.rs"]
mod tests;