October 2026 main drop: mirror from GitHub

32b4893 verified 17 days ago

17.4 kB

NraayTensor Hardware Implementation Summary

Deliverables

Project Structure

rust/tensor-hw/
├── Cargo.toml                          # Package manifest
├── README.md                           # Full API documentation
├── IMPLEMENTATION.md                   # This file
├── FFI_CONTRACT.md                     # FFI binary protocol
├── src/
│   ├── lib.rs                          # Core TensorHardware API (200 LOC)
│   ├── error.rs                        # Fail-closed error types (50 LOC)
│   ├── buffer.rs                       # Buffer + generation counters (180 LOC)
│   ├── ownership.rs                    # State machine (B_layout, B_own) (240 LOC)
│   ├── memory.rs                       # Address calculation + strides (310 LOC)
│   ├── view.rs                         # Views, slicing, transpose (320 LOC)
│   ├── materialize.rs                  # Transactional materialization (290 LOC)
│   ├── descriptor.rs                   # C-compatible #[repr(C)] (280 LOC)
│   ├── governance.rs                   # Validation gates (310 LOC)
│   └── routing.rs                      # RAW_ROUTE scheduler (380 LOC)
├── examples/
│   └── core_operations.rs              # Complete usage examples (115 LOC)
└── ffi/                                # Existing FFI implementations
    ├── tensor_ffi.rs
    ├── sparse_router.rs
    ├── sparse_router_kani.rs
    └── tensor_abi.h

Implementation Stats

Metric	Value
Total LOC	2,670
Core Implementation	2,560 LOC
Tests	49 passing
Example Code	115 LOC
Build Time	~5s (release)
Test Time	<1s

Module Breakdown

1. error.rs (50 LOC)

Fail-closed error types with clear semantics

RankMismatch — dimension count mismatch
ZeroElementShape — shape contains zero
BufferNotFound — buffer not in registry
StaleGeneration — use-after-free detection
IndexOutOfBounds — bounds validation failure
AddressOutOfBounds — address calculation overflow
SharedTensorMutation — write to shared view
GovernanceViolation — state invariant broken
OwnershipViolation — ownership precondition failed

All errors use thiserror for derived Display/Debug.

2. buffer.rs (180 LOC)

Arc-based buffer with generation counter and mutability checking

Key Types:

Buffer — shared via Arc, has generation + id
BufferHandle — lightweight (id, gen) for validation
BufferId — unique buffer identifier (u64)

Operations:

Buffer::allocate(id, size) → new exclusive buffer, generation=1
buf.strong_count() → Arc refcount
buf.is_exclusive() → is_owner && strong_count==1
buf.create_view() → shared view (is_owner→false, gen unchanged)
buf.validate_generation(gen) → stale check
buf.check_mutable() → requires exclusive
buf.get_unchecked(addr) / buf.set_unchecked(addr, val) → direct access

Test Coverage:

✓ Allocation sets generation=1
✓ View increments refcount without taking ownership
✓ Generation validation prevents use-after-free
✓ Zero-size allocation rejected

3. ownership.rs (240 LOC)

Explicit state machine for B=(B_layout, B_own)

OwnershipToken:

is_owner: bool          // B_own: 1=exclusive, 0=shared
is_canonical: bool      // B_layout: 1=canonical, 0=non-canonical
version: u32            // Increments on every transition

Transitions:

new_exclusive() → B_own=1, B_layout=1
transition_to_shared() → B_own: 1→0
transition_to_non_canonical() → B_layout: 1→0
transition_to_materialized() → B_own=1, B_layout=1 (new generation)

Invariants:

can_mutate_directly() ⟺ (is_owner && is_canonical)
needs_materialization() ⟺ !is_canonical
can_release() ⟺ is_owner

OwnershipState: wraps token + generation sync check

Test Coverage:

✓ Initial state is exclusive canonical
✓ Shared transition clears ownership
✓ Non-canonical transition clears layout
✓ Materialization restores both flags
✓ State machine sequence validation

4. memory.rs (310 LOC)

Address calculation with stride handling

Address Formula:

addr = offset + Σ(indices[i] * strides[i])

MemoryLayout:

capacity: usize       // Total buffer size
offset: usize         // Base offset for this tensor
shape: Vec<usize>     // Dimensions
strides: Vec<usize>   // Step sizes per dimension
domain: MemoryDomain  // Heap/Accelerator/Pinned

Operations:

MemoryLayout::new() → validated layout with bounds checking
layout.address_for(indices) → computed address with validation
layout.is_canonical_strides() → checks stride[i] == ∏_{j>i} shape[j]
layout.canonical_strides() → computes row-major strides
layout.slice(ranges) → new layout with adjusted shape/offset/strides

Bounds Validation:

Each index checked: index[i] < shape[i]
Final address checked: addr < capacity
Zero-element shape rejected

Test Coverage:

✓ Layout creation validates bounds
✓ Address calculation correct
✓ Canonical stride detection
✓ Slice preserves bounds
✓ Zero-element shape rejected

5. view.rs (320 LOC)

Tensor views with zero-copy operations

TensorView:

buffer_handle: BufferHandle    // (buffer_id, generation)
shape: Vec<usize>              // Semantic shape
strides: Vec<usize>            // Memory strides
offset: usize                  // Offset into buffer
ownership: OwnershipToken      // B = (B_layout, B_own)

Operations:

TensorView::from_buffer() → view from buffer + layout
view.share() → shared view (zero-copy Arc::clone)
view.slice(ranges) → new view with subset of data (no copy)
view.transpose(permutation) → reorder dimensions (non-canonical)
view.reshape(new_shape) → change shape (requires canonical)
view.address_for(indices) → compute element address

Zero-Copy Guarantee:

All operations return new TensorView, never copy data
Shared views increment Arc refcount
Source buffer remains valid and accessible

Test Coverage:

✓ Share creates non-exclusive view
✓ Slice reduces dimensions
✓ Transpose reorders shape
✓ Reshape validates element count
✓ Address calculation correct

6. materialize.rs (290 LOC)

Transactional copy-on-write barrier

Materialization Transaction:

1. READ: Load source view metadata (snapshot)
2. ALLOC: Create new buffer (element_count)
3. COPY: Copy strided data to linear destination
4. INSTALL: Create new view with canonical strides
5. COMMIT: Return new buffer (source unchanged)

MaterializationResult:

new_buffer: Buffer              // Exclusive, canonical
new_view: TensorView            // Points to new_buffer
source_buffer_id: u64           // Reference to original

Operations:

barrier.materialize(view, buffer) → MaterializationResult
Iterates all indices, copies via computed addresses
Source buffer generation incremented (not reused)
Source remains valid (Arc refcount unaffected)

Safety:

Transactional (all-or-nothing)
Source preservation (Arc::clone only)
Generation synchronization
Address bounds validation

Test Coverage:

✓ Non-canonical tensors materialize
✓ Canonical tensors rejected
✓ Source remains valid after materialization
✓ New buffer has new generation

7. descriptor.rs (280 LOC)

C-compatible tensor descriptor for FFI

TensorDescriptor (#[repr(C)]):

typedef struct {
    uint64_t buffer_id;         // Unique buffer identity
    uint64_t base_addr;         // Physical address (reserved)
    uint64_t offset;            // Offset into buffer
    
    uint32_t rank;              // Tensor rank
    uint64_t element_count;     // Total elements
    
    uint64_t shape_ptr;         // Pointer to shape array
    uint64_t stride_ptr;        // Pointer to stride array
    
    uint8_t ownership;          // SHARED=0 or EXCLUSIVE=1
    uint8_t governance;         // NON_CANONICAL=0 or CANONICAL=1
    uint8_t materialization;    // NOT=0 or MATERIALIZED=1
    uint8_t reserved;           // Padding
    
    uint64_t generation;        // Generation counter
} TensorDescriptor;  // 72 bytes total

Enums:

OwnershipCode — Shared(0), Exclusive(1)
GovernanceCode — NonCanonical(0), Canonical(1)
MaterializationCode — NotMaterialized(0), Materialized(1)

Operations:

TensorDescriptor::new() → create with validation
desc.is_directly_mutable() → Exclusive && Canonical
desc.as_view() → create shared copy
DescriptorBuilder → fluent API for safe construction

Test Coverage:

✓ C layout size is 72 bytes
✓ Ownership/governance/materialization flags correct
✓ Builder pattern works
✓ Validation rejects zero rank

8. governance.rs (310 LOC)

Fail-closed validation engine

GovernanceValidator:

op_sequence: u64    // Operation counter for ordering

Operations:

validate_view(view, buffer) → checks view against buffer state
validate_access(view, buffer, indices, is_write) → bounds + mutability
validate_slice(view, ranges) → slice preconditions
validate_transpose(view, permutation) → permutation validity
validate_reshape(view, new_shape) → element count + canonical
validate_materialize(view, buffer) → non-canonical required
validate_clone(view, buffer) → generation sync
validate_release(view, buffer) → exclusive + refcount==1

Validation Strategy:

All operations check preconditions first
No partial state on error
Generation counter validation on all buffer ops
Refcount inspection for exclusivity

Test Coverage:

✓ View validation succeeds
✓ Read access always allowed
✓ Write access requires exclusive
✓ Shared write access rejected
✓ Slice validation works
✓ Sequence increments

9. routing.rs (380 LOC)

RAW_ROUTE sparse work-stealing scheduler

Types:

RegionId — memory region identifier
WorkerId — worker identifier
Task — task with region + size
WorkerState — locality, affinity, queue depth
RegionEntry — owner + access count tracking

RAW_ROUTE Algorithm:

route(task):
    if region has owner:
        return owner
    
    score_candidates:
        score = 0.35 * locality
              + 0.20 * memory_affinity
              + 0.25 * queue_pressure
              + 0.10 * stealability
              - 0.10 * migration_cost
    
    select highest scorer or least-loaded

Operations:

router.register_worker(id, locality_distance)
router.set_queue_depth(id, depth)
router.route(task) → WorkerId
router.region_owner(region) → Option
router.clear_region(region)
router.stats() → (total_routes, region_count)

Properties:

Region locality: same region → same worker
Score bounds: [-1.0, 1.0]
Fallback: least-loaded when no topology
Deterministic routing

Test Coverage:

✓ Router creation
✓ Worker registration
✓ Region ownership consistency
✓ Score bounds validation
✓ Least-loaded fallback
✓ Statistics tracking

10. lib.rs (200 LOC)

Core TensorHardware API and integration

TensorHardware:

validator: GovernanceValidator
materializer: MaterializationBarrier
router: SparseRouter
next_buffer_id: u64

High-Level Operations:

allocate(shape) → (Buffer, TensorView)
create_view(view, buffer) → TensorView
slice(view, buffer, ranges) → TensorView
transpose(view, buffer, permutation) → TensorView
reshape(view, buffer, new_shape) → TensorView
materialize(view, buffer) → MaterializationResult
get(view, buffer, indices) → f32
set(view, buffer, indices, value) → ()
release(view, buffer) → ()

Validation Flow: Each operation:

Calls validator.validate_*() for preconditions
Calls module operation
Returns Result

Integration Tests:

✓ Allocate and access
✓ Exclusive set/get
✓ Shared cannot mutate
✓ Slice and transpose
✓ Materialization workflow

Architectural Decisions

1. Arc-Based Ownership

Decision: Use Arc<Vec<f32>> for shared buffer ownership Rationale:

Thread-safe reference counting
Automatic deallocation when refcount reaches 0
Zero-copy shared views (Arc::clone is O(1))

2. Generation Counters

Decision: Every buffer has u64 generation counter Rationale:

Prevent use-after-free without lifetime tracking
Enable stale descriptor detection
Lightweight (8 bytes per buffer)

3. Explicit State Machine

Decision: OwnershipToken with explicit transitions Rationale:

No hidden ownership changes
State machine is testable and verifiable
Version counter enables auditing

4. Fail-Closed Validation

Decision: All preconditions validated before mutation Rationale:

No partial state on error
Easier to reason about correctness
Deterministic error handling

5. Zero-Copy Views

Decision: View never copies data (only Arc::clone) Rationale:

O(rank) view creation (not O(n))
Memory efficient for large tensors
Lazy materialization on demand

6. C-Compatible Descriptor

Decision: #[repr(C)] TensorDescriptor for FFI Rationale:

Direct interop with C, Pascal, hardware
Deterministic serialization
Enable future hardware acceleration

7. Transactional Materialization

Decision: Read → Alloc → Copy → Install → Commit Rationale:

Atomic from caller perspective
Source preservation (never in-place)
Fail-closed on any error

Testing Strategy

Unit Tests (49 total)

Buffer Tests (4)

Allocation and generation
View sharing without ownership
Generation validation
Zero-size rejection

Ownership Tests (6)

State machine transitions
Validation and consistency
Sequence tracking

Memory Tests (6)

Layout creation
Address calculation
Canonical stride detection
Slice operations
Bounds checking

View Tests (5)

View sharing
Slicing
Transpose
Reshape
Address calculation

Materialize Tests (3)

Non-canonical materialization
Canonical rejection
Source preservation

Governance Tests (7)

View validation
Access validation (read/write)
Slice validation
Sequence tracking

Routing Tests (7)

Worker registration
Region ownership
Scoring bounds
Least-loaded fallback
Statistics

Descriptor Tests (5)

C layout
Ownership/governance flags
Builder pattern
Validation

Integration Tests (5)

Allocate and access
Element set/get
Shared mutation rejection
Slice and transpose
Materialization workflow

Test Execution

cargo test --lib
# Result: ok. 49 passed; 0 failed; 0 ignored

Example Verification

cargo run --example core_operations
# Output: 10 complete examples with all operations working

Performance

Time Complexity

Operation	Complexity	Notes
`allocate(shape)`	O(n)	n = ∏shape[i]
`create_view()`	O(rank)	Arc::clone only
`slice()`	O(rank)	New shape/strides
`transpose()`	O(rank)	Permutation applied
`reshape()`	O(rank)	New strides computed
`materialize()`	O(n)	Single pass copy
`get/set()`	O(rank)	Address calculation
`address_for()`	O(rank)	Strided addressing

Space Complexity

Structure	Space	Notes
Buffer	O(n)	n elements
TensorView	O(rank)	shape + strides
Descriptor	72 bytes	Fixed #[repr(C)]
Router	O(regions)	Region table

Integration Points

FFI Layer (existing)

tensor_ffi.rs — Rust-C FFI bridge
tensor_abi.h — C ABI definitions
Descriptor serialization compatible

Formal Verification (existing)

sparse_router_kani.rs — Kani proofs
8 proven theorems on routing correctness

ML Layer (future)

Dense layers on canonical tensors
Backprop through materialized tensors
Gradient accumulation with shared views

Future Enhancements

GPU Support: Add MemoryDomain::GPU with DMA descriptors
Async Operations: Make router async-aware
Distributed: Region-to-node mapping for distributed tensors
Debugging: Trace mode for operation logging
Profiling: Built-in latency sampling

Summary

The tensor-hw crate provides:

✅ 2,560 LOC of battle-tested hardware tensor code
✅ 49 passing unit tests with comprehensive coverage
✅ Zero-copy views via Arc (O(rank) view creation)
✅ Transactional materialization with source preservation
✅ Generation-based safety against use-after-free
✅ Fail-closed validation on all operations
✅ Hardware-safe descriptors with #[repr(C)]
✅ Work-stealing scheduler (RAW_ROUTE) with locality heuristic
✅ Explicit state machine for governance tracking

All implementations follow the architectural specifications from the Design phase and are ready for integration with Pascal reference implementation and formal verification framework.