Hardware-sympathetic algorithms with explicit vectorisation and GPU offload support

[Twon]

Summary

Introduce a structured effort in Morpheus to identify, design, and implement hardware-sympathetic algorithms — i.e. algorithms and data structures explicitly shaped for:

SIMD/vectorised CPU execution
cache-aware memory layouts
GPU offloading (CUDA/SYCL/HIP)
portable heterogeneous execution (CPU + GPU)

This includes both:

algorithm selection/design patterns
and integration with heterogeneous compute frameworks such as SYCL and AdaptiveCpp
Motivation

Modern high-performance systems are increasingly heterogeneous, and peak performance requires more than multithreading:

CPU performance is dominated by vectorisation (SIMD / AVX / SVE)
GPU performance depends on memory coalescing + occupancy
portability layers alone (e.g. STL parallelism) are often insufficient without algorithmic restructuring

Resources such as Algorithmica highlight that algorithm design itself must reflect hardware topology rather than being purely abstract.

Additionally, Morpheus already targets:

GPU abstraction layers (OpenGL / WDDM / vendor affinity)
cross-platform execution
high-performance systems programming

This makes it a strong candidate for a hardware-aware algorithm layer.

Goals

1. Identify hardware-sympathetic algorithm set

Catalogue and prioritise algorithms that benefit from:

SIMD/vectorisation
data-parallel execution
GPU offload
memory coalescing patterns

Examples include:

prefix sums / scans
sorting networks / radix sort variants
graph traversal kernels
stencil computations
reduction-heavy pipelines
streaming transform pipelines

Reference inspiration:

https://en.algorithmica.org/
2. Introduce explicit vectorisation strategy (CPU side)

Ensure critical code paths:

expose SIMD-friendly layouts (SoA over AoS where appropriate)
enable compiler auto-vectorisation (but do not rely on it)
optionally integrate:
std::execution::par_unseq
compiler intrinsics where necessary
PGO-guided layout decisions
3. Enable GPU offload abstraction layer

Evaluate and integrate support for:

SYCL 2020 model
AdaptiveCpp (portable SYCL + stdpar + multi-backend support)

AdaptiveCpp is particularly relevant because it enables:

CPU + NVIDIA + AMD + Intel GPU execution from a single codebase
multiple compilation flows (JIT + static)
interoperability with CUDA/HIP-like kernels

References:

https://github.com/AdaptiveCpp/AdaptiveCpp
https://arxiv.org/abs/2405.01420 (SYCL GPU portability studies)
4. Define “hardware-sympathetic algorithm interface”

Introduce a design abstraction such as:

parallel_for
reduce
scan
transform
device_policy

with backend selection:

CPU SIMD backend
GPU SYCL backend
fallback scalar backend

Goal: allow algorithms to express intent, not execution model.

5. Performance validation framework

Add benchmarking for:

CPU SIMD scaling (AVX2 / AVX-512 / ARM NEON if applicable)
GPU offload scaling
memory bandwidth efficiency
cross-backend portability overhead

Include regression detection for:

vectorisation breakdown
unexpected host/device transfers
cache inefficiencies
Non-goals (for now)
Full rewrite of STL usage in the codebase
Vendor-specific kernel rewriting (CUDA-only optimisations)
Deep compiler development work
Deliverables
Phase 1
Identify candidate algorithm set in Morpheus
Define hardware-sympathetic algorithm guidelines
Add initial SIMD-friendly utilities (layout + transform primitives)
Phase 2
Introduce SYCL / AdaptiveCpp integration prototype
Offload one or two representative kernels (e.g. transform/reduce pipeline)
Phase 3
Benchmark suite + regression tracking
Extend pattern library (scan/sort/stencil abstractions)
Risks / Considerations
Over-abstraction may reduce readability
SYCL/AdaptiveCpp adds build complexity
GPU offload performance depends heavily on memory layout decisions
Some algorithms may require dual CPU/GPU implementations
Expected Benefits
Significant performance gains in compute-heavy paths
Better utilisation of modern CPU vector units
Portable GPU acceleration across vendors
Clear architectural separation between “algorithm intent” and “execution backend”
Foundation for future heterogeneous compute expansion
Resources

• https://en.algorithmica.org/
• https://adaptivecpp.github.io/
• https://arxiv.org/abs/2405.01420
• https://isocpp.org/files/papers/n3571.pdf
• https://github.com/GPUOpen-LibrariesAndSDKs/AGS_SDK