Albert-Jan N. Yzelman

What's new

• Our paper on DAG Scheduling in the BSP Model (mirror) has been accepted at SOFSEM 2025! DAG scheduling here refers to the assignment of a time step and compute resource to each vertex in an arbitrary computational DAG, while minimising the resulting makespan. Said makespan is evaluated using the Bulk Synchronous Parallel (BSP) model, which means the costs of data movement in terms of bandwidth and latency is minimised as part of scheduling. By contrast, previous work with theoretical perspectives on arbitrary DAG scheduling tend to ignore data movement costs, while most work on practical high-performance computations analyse specific DAG structures that correspond to specific algorithms.
  With this paper, we propose a small step in bridging this gap between scheduling theory and practice. Amongst other contributions, we introduce a taxonomy of scheduling models that includes previous works, and show how most generalise as special cases of scheduling in BSP. We analyse relations between model variations, and analyse the complexity of the BSP DAG scheduling problem. We show NP-hardness already for simple specific DAG structures, and prove that there is no polynomial-time algorithm that approximates the optimal schedule for arbitrary DAGs: i.e., BSP scheduling is APX-hard. We hope this work inspires further theoretical studies of scheduling under realistic cost models.
• This website was down for a short period-- apologies for any inconvenience caused as well as a big thank-you to the folks at Netrouting for help with getting things up once more!
• Our new pre-print combines pebbling and scheduling in a single, multi-processor red-blue pebbling game (MPP). The key idea is to represent fast memories with different localities as different shades of red; e.g., if there are k NUMA domains with their own local fast memory, then there are k shades of red. In this two-level model, slow memory remains represented by blue pebbles. The model captures both (parallel) I/O and (parallel) compute costs, and proves, amongst others, that determining the optimal MPP schedule is NP-hard even for simple subclasses of DAGs, and that approximating the optimal parallel overhead for arbitrary DAGs cannot be done in polynomial time.
• My text on Humble Heroes (citation) has left press. Humble here refers to the notion of the humble programmer, a concept first coined by Edsger Dijkstra, who urged us to approach programming while respecting the intrinsic limitations of the human mind. Today, few programming models are humble. Even fewer are both humble and scalable. Almost none are humble, scalable, and high performance.
  The ever-increasing scale and complexity of computing systems – inspired by ever-increasing scales of problems and data – however, requires ever-more programmers, each with ever-deeper expertise, to write programs that require ever-higher scalability and performance.
  In a bid to resolve this juxtaposition, Humble Heroes argues many humble programming models can be built on top of a few foundational ones, while retaining high performance and optimal scalability– and demonstrates this is feasible by introducing and evaluating ALP/Pregel, freely available on GitHub.

Contact info

Overview

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