CS Paper Radar

Parallelizing the Factorial Space: Multi-Core OpenMP Scaling and Scalable SIMD Acceleration of the Steinhaus-Johnson-Trotter Algorithm via Dual-Lane AVX2 Execution

Serge Melnikov

cs.DS ·submitted 2026-09-07 18:21 UTC · v3

Abstract

This paper presents a high-performance SIMD acceleration framework for the Steinhaus-Johnson-Trotter algorithm, targeted at modern x86-64 architectures using the AVX2 instruction set. By exploiting a novel combinatorial space partitioning combined with single-cycle vector byte shuffling ($\texttt{\_mm256\_shuffle\_epi8}$), our dual-lane vectorized implementation processes two independent, concurrent permutation streams within a single 256-bit YMM register under a uniform execution mask. Empirical evaluations demonstrate a $3\times$ throughput increase over an optimized scalar baseline of Knuth's Algorithm P (accelerated by $3\times$ via isolated sweeping branches) and outperform the recent Ring-Cascade algorithm by Yusheng Hu, completely avoiding store-forwarding stalls during hot loops. To scale this engine across multi-core processors, we extend the framework into a highly concurrent environment via OpenMP using a localized mathematical state decoder and macro-period loop scheduling. The parallel performance is shown to scale strictly and linearly with the number of active physical processor cores ($\text{Speedup}(M) \approx M$) due to a lock-free thread-local accumulation pipeline that eliminates false sharing. On a 6-core processor, the multi-threaded engine delivers a $5.25\times$ throughput gain for $n=14$ ($3.25$ billion CPU cycles) and processes the massive $n=15$ space in just $16.0$ seconds, yielding a $5.25\times$ speedup over the sequential vector baseline, while Hyper-Threading virtual cores yield zero additional throughput due to physical SIMD port saturation.

Comment
Added extended framework with multi-core parallel execution via OpenMP, introduced dynamic state mapping and thread scalability benchmarks up to n=16. Cross-platform C source repository link updated

Closest papers

Nearest neighbours by meaning across the whole index.

Investigating ET-SoC-1 Vector and Parallel Performance with sGEMM

cs.DC ·2026-10-31 ·Richard Neale, Nick Brown
publishedbenchmark similarity 0.66
Abstract · Author accepted version of paper published in RISC-V for HPC workshop at SC26

The Ainekko (formerly Esperanto) ET-SoC-1 is a massively parallel RISC-V accelerator. Its compute array comprises 1024 dual-threaded in-order ET-Minion cores (2048 harts) operating at 600 MHz, each core providing an eight-lane 256-bit packed-single (PS) SIMD datapath shared by its two harts, with access to LPDDR4X memory at a nominal 133 GiB/s. This paper presents a performance investigation using single-precision general matrix multiplication (sGEMM) as the benchmark kernel. Two device kernels are implemented and evaluated on the ET-SoC-1, these are a register-blocked PS SIMD baseline with two-step software pipelining, and a TensorFMA32 kernel that drives the same FMA datapath through the per-core tensor micro-operation sequencer, with double-buffered A scratchpad loading. Because both kernels are bounded by the same arithmetic peak, the comparison isolates the effect of operand delivery from that of arithmetic width. Performance is compared against CPU references (SpacemiT K3, Intel i5-11600, AMD Ryzen 9 9950X and the Arm Cortex-X925/A725 CPU of an NVIDIA DGX Spark) and two GPUs (NVIDIA GB10 Blackwell and AMD RDNA4 RX 9060 XT).

0.36

StrataFlux: Memory-Hierarchy-Native Low-Bit LLM Inference

cs.LG cs.DC ·2026-11-05 ·Jake Hyun, Ziyu Zhao, Jae-sun Seo, Mohamed S. Abdelfattah
similarity 0.65
Abstract · 34 pages, 18 figures, 44 tables. Includes appendix

Quantization reduces the memory and bandwidth demands of large language model (LLM) inference but can degrade accuracy; offloading higher-precision data can instead stall generation. We introduce StrataFlux, a framework that challenges this tradeoff by recovering accuracy lost to low-bit weight and key-value (KV) cache quantization while retaining quantization's memory and speed advantages. StrataFlux co-designs refinement representation, selection, and delivery to make host RAM and solid-state drives useful sources of additional precision. Its selective precision streaming reduces transfer volume, overlaps delivery with computation, and reuses fetched precision across decoding steps so generation need not wait for every transfer. We evaluate 2-4-bit weights and 2-3-bit KV-cache on dedicated GPUs and unified-memory platforms. For 2-bit Llama-3.1-8B-Instruct weights, StrataFlux reduces WikiText-2 perplexity from 9.46 to 8.40 while maintaining 95.4% of the quantized base's throughput on RTX 5090. With 2-bit weights and KV, StrataFlux raises Qwen3-8B's AIME 2024/2025 accuracy from 11.0% to 47.1% at unchanged GPU memory use. At 128K context, Llama-3.1-8B-Instruct with 3-bit weights and 2-bit KV achieves comparable perplexity and speed to vLLM's 4-bit AWQ weights and 8-bit KV on RTX 5090, using approximately half the GPU memory. These results show that GPU-resident precision need not set the accuracy ceiling, nor offloading-tier latency dictate decoding speed.

0.20

Reorienting the Vector Axis: Restructuring FlashAttention for Long-Vector Processors

cs.AR cs.DCcs.PF ·2026-10-21 ·Emmanuel Irabor, Marc Casas
similarity 0.65
Abstract

A Transformer is built around attention, whose cost grows with the square of the sequence length and dominates the layer on long sequences. FlashAttention made that cost manageable by tiling the attention matrix and updating the softmax as it goes, but almost all work since has targeted GPUs. On long-vector processors one vector register can hold up to 512 single-precision numbers. The savings of a vector instruction are proportional to how much of the register it uses, so the choice of which loop to vectorize is a first-order decision. We port PyTorch's CPU FlashAttention kernel to a RISC-V CPU with 2KB vector registers and find that it reaches 16.2% of peak floating-point throughput. The kernel walks each tile one query row at a time: the product against V is vectorized along the 64-element head dimension, the softmax's per-row maximum and sum are reductions that collapse a full register to a scalar, and the software exponential's polynomial coefficients compete with tile data for vector registers and cause spilling. We propose two techniques. The first transposes the score tile and the running output so that queries lie along the contiguous axis. The algorithm and its values are unchanged. A single parameter, the number of queries in a tile, now sets the vector length of every part of the kernel and can be matched to the machine. Both reductions also disappear. The second moves the polynomial's coefficients into scalar registers, removing the spills and cutting the softmax's vector memory instructions by 78.7%. On silicon the two together cut whole-kernel cycles by 1.84 to 2.08x at a head dimension of 64, raising floating-point utilization from 16.2% to 29.7% of peak. An FPGA of the same design ranks the changes identically and scores them higher, at 2.71x.

0.06

Superscalar Loop Processors

cs.AR cs.DC ·2026-11-01 ·Luca Colagrande, Pascal Etterli, Luca Benini
top venuecode/data similarity 0.64
Abstract · Accepted at MICRO 2026

To sustain the computational demands of modern ML and HPC workloads, programmable accelerators integrate large arrays of processing elements (PEs), typically built around single-issue in-order cores to maximize integration density and energy efficiency. As a result, each PE's instruction throughput is upper-bounded at one instruction per cycle (IPC), often suffering from significant underutilization of its functional units (FUs). Conventional superscalar processors can improve FU utilization by increasing IPC, but they typically incur substantial area and energy overheads. This work proposes the Superscalar Loop Processor (SLP) architecture, a lightweight approach to superscalar execution that targets regular, compute-intensive loop kernels. We present the SLP execution model, which exploits the static structure of these workloads to enable efficient multiple-issue execution without the complexity of dynamic out-of-order scheduling. We demonstrate the SLP architecture through an open-source prototype implementation, Schnizo, developed as an enhancement of a tiny RV32I core with floating-point support. Across several ML and HPC microkernels, Schnizo achieves substantially higher IPC and FPU utilization than the scalar baseline while retaining the efficiency of lightweight in-order designs. These results demonstrate that SLPs can provide an efficient architectural solution for programmable accelerators targeting regular, compute-intensive workloads.

0.51

Annotation-Driven Migration of CUDA Programs to Tenstorrent Blackhole

cs.DC ·2026-10-02 ·Ayumi Ohno, Shinya Takamaeda-Yamazaki
similarity 0.64
Abstract · Accepted at the Thirteenth Workshop on Accelerator Programming and Directives (WACCPD 2026)

Tenstorrent Blackhole combines distributed local memories, explicit inter-core communication, and Tensix cores decoupling data movement from computation. CUDA offers a substantial HPC software base but leaves physical data placement and scheduling largely implicit. Migrating CUDA HPC kernels to Blackhole requires spatial mapping across cores and per-core coordination of compute and data-movement kernels. We present an MLIR-based compiler deriving data placement, inter-core communication, and tile computation from a statically shaped affine CUDA subset. Declarative annotations express choices not fixed by the source, including compute/DM operation placement and streaming granularity. We evaluate it on Gaussian elimination, five-point stencil, and symmetric rank-k update. Relative to our compiler's default realizations, the best measured configurations achieve a 4.2x speedup for BF16 Gaussian and 2.1-2.2x for FP32 Gaussian and Jacobi. A choice's performance impact can reverse with surrounding policies, precision, and loop schedule, motivating comparison of alternative per-core realizations rather than independent policy selection.

0.24

A Thread-Register Decoupled GPU Execution Model for Efficient Tensor Computation

cs.AR ·2026-08-20 ·Zihan Liu, Jingwen Leng, Yangjie Zhou, Yitong Ding, Guanlin Zhu +10 more
similarity 0.63
Abstract

Modern GPUs increasingly integrate Tensor Cores into the execution pipeline. Although aggregate tensor throughput continues to grow, aided by an operand supply that has evolved from register-based in Ampere to redundancy-free, memory-based in Hopper and Blackwell, efficiently orchestrating the complete tensor compute pipeline for the modern AI workloads remains challenging. We identify the fundamental bottlenecks as fixed parallelism and coarse-grained scheduling, both of which are exposed by modern AI workloads that interleave diverse non-GEMM operations with GEMM. To orchestrate tensor computation efficiently, we propose FIBER, a new architecture that extends the GPU SIMT (single instruction, multiple thread) model. Its basic execution instance, the \emph{fiber}, is decoupled from private register ownership, carrying only minimal control state while accessing an SM's registers through a shared view. This enables dynamic parallelism scaling, fine-grained register-level dataflow scheduling, and offers a redundancy-free alternative for matrix operand supply. We extend the ISA, microarchitecture, and compiler to realize shared-register addressing, conflict-free operand delivery, and fiber-based program mapping. Under a typical mixed-precision LLM serving scenario, FIBER achieves a 2.25x end-to-end speedup on Ampere (1.15x for the original FP16 computation), with 1.8x and 2.09x on Hopper and Blackwell respectively, and kernel-level gains up to 2.49x.

0.38

Adaptive Matrix Multiplication for Dynamic Shapes on Ascend NPUs

cs.AR ·2026-08-11 ·Yuhang Zhou, Jiang Peng, Qianyu Jiang, Zhibin Wang, Xinghui Tian +5 more
similarity 0.63
Abstract

Matrix Multiplication (MatMul) faces a "generalization crisis" driven by highly dynamic tensor shapes. This crisis is particularly acute on Ascend NPUs, where explicitly controlled architectures and strict physical constraints render existing GPU-centric optimizations ineffective. To resolve this, we propose AdaptCore, an adaptive framework for universally high-performance MatMul on Ascend NPUs. AdaptCore systematically decouples operator optimization into spatial tiling and instruction orchestration. It first maps dynamic shapes into a hardware-aware 2D tiling taxonomy to balance on-chip capacity limits and multi-core parallelism. Furthermore, it integrates a composable optimization library with a deterministic analytical performance model. By mathematically evaluating hardware state mutations, AdaptCore proactively selects and caches optimal implementations, enabling O(1) overhead runtime dispatching. Evaluations demonstrate that AdaptCore delivers a remarkable 1.85x mean speedup across 80,000 input shapes, and achieves up to a 1.48x acceleration in representative end-to-end models over the highly-tuned native vendor library (ACLNN).

0.04

NDS: Programmer-Free Offload of High-Performance Near Data Strands

cs.AR ·2026-09-29 ·Shreyas Singh, Pratyush Nandi, Lin Jia, Shankar Balachandran, Rajeev Balasubramonian
similarity 0.63
Abstract · 13 pages, 12 figures. Extended version of the two-page PACT '26 poster paper; DOI: 10.1145/3838684.3846876

Near Data Processing (NDP) has the potential to significantly improve system performance and energy by alleviating data movement bottlenecks. However, most NDP proposals pose heavy requirements for the software stack, data layout, and/or the underlying hardware. To broaden NDP adoption, this work focuses on a modular hardware-centric approach that automates the above steps and can target unmodified binaries. This paper presents Near Data Strands (NDS), a framework that orchestrates tasks and data automatically without involving the programmer and the software stack. As a first step towards this ambitious goal, this work focuses on regular loops that meet specific criteria. The framework identifies potential offloadable loops, decomposes them into parallel execution strands, creates a high performance instruction schedule, performs the required data marshaling and orchestration, and initiates near-data execution. We demonstrate that NDS achieves a 3.14x geomean speedup over a single-core host baseline and a 1.82x geomean speedup over 8-core host-parallel variants, all without any modifications to the software stack. These gains grow as repeated loop invocations amortize offload costs, showing that legacy applications can leverage a transparent hardware approach to extract benefits from NDP.

0.19