Albert-Jan N. Yzelman

What's new

• ...and in more BSP-related news, our recent publication at SPAA '26 takes the concept of streams as a building block for parallel models of computation. A stream is an operation on a contiguous block of memory, which can be something like a reduction, a (partial) copy of the data into faster memory than where its from, or a write-back to slower memory. Modern GPUs and AI accelerators tend to be great at such operations. All architectures I have had the pleasure of working with (including CPUs) furthermore can process multiple streams simultaneously— and, in fact, programs are encouraged to do so, in order to extract the best performance from the system.
  Our PaHiS model keeps the structure of BSP: supersteps consisting of data movement and computations. However, the data movement should be expressed as streams and are costed based on streams: opening a stream costs latency, and processing the stream has an additional per-word throughput cost, thus depending also on the payload size. We add to this a hierarchical model that reflects that of Multi-BSP, in order to capture modern, highly-NUMA architectures. Paradoxically, PaHiS naturally captures irregular accesses through needing many streams: one for every jump in memory. As a result, PaHiS encourages algorithm designers to do all the right things: minimise the number of supersteps (minimise coarse-grained latencies), minimise the number of jumps in memory (minimise fine-grained memory latencies), minimise data movement, maximise locality (concentrate data movement and latencies as much as possible down the memory hierarchy)—and, of course, minimise work, which I emphatically and unapologetically mention in last place.
  When costing complete sparse irregular solvers, PaHiS achieves a Spearman correlation between cost and actual run-time of almost one— almost perfect correlation. It is significantly better than hierarchical roofline in the same metric, and improves on Multi-BSP as well. It integrates with Algebraic Programming (its GraphBLAS front-end) to enable enhanced auto-tuning on the short term. Further down the road, PaHiS will enable better-informed hardware-software co-design: indeed, well-designed cost models work in both directions, which is why they are also often called bridging models.
  Read all about it over at the SPAA proceedings, with many thanks to co-authors Petros Anastasiadis and Denis Jelovina for bringing this one home. It is especially symbolic that stream-based parallel computation modelling was one of my first ideations while helping establish the Computing Systems Lab in Zürich, back in 2020 already. Petros took over and finished adding his magic just before I left, with the resulting paper getting accepted right after having left. Full circle, in several ways!
• Stale synchronicity, originally posited and popularised in machine learning by Xing's Petuum framework, relaxes the strict superstep structure in Bulk Synchronous Parallel (BSP) processing in a structured, bounded fashion. BSP can be relaxed even further to fit, for example, inference-only deep learning workloads: by exploiting sparse neural network connectivity while relaxing barrier implementations, or by relaxing collective semantics. These relaxations retain the advantages of structured general-purpose parallel programming whilst achieving performance that exceeds the state of the art. With thanks to co-authors Raphael Steiner, Christos Matzarakos, András Papp, and Toni Böhnlein, you can now also enjoy the benefits of stale synchronicity for sparse triangular solves: on 32 realistic matrices for SpTRSV workloads and using a full 48-core AMD EPYC, we achieve a geometric mean speedup of 26% versus SpMP.
• In partitioning matrices, replicating separators instead of incurring communication on separators can trade memory for data movement. This classic trade-off has become known as 2.5D methods-- however, goes back as far as 1999 in classic computations and (at least) to 2011 as a general concept in sparse matrix partitioning. We now release a pre-print that studies replication applied to scheduling general computations.
• After more than eleven years, I have moved on from Huawei. Follow me on LinkedIn for more details and for what's next!
• A summary of our recent papers on scheduling and applications was presented at the 19th workshop on Scheduling for Large-Scale Systems. The slides are available.

Contact info

Overview

• Publications
• Presentations
• ALP/Pregel & ALP/GraphBLAS (gitee), MulticoreBSP, and other software
• A short biography, and an even shorter one