PaperlayerView exact revision on arXiv

Source-linked AI summary

Stateful Dataflow Multigraphs: A Data-Centric Model for Performance Portability on Heterogeneous Architectures

Tal Ben-Nun, Johannes de Fine Licht, Alexandros Nikolaos Ziogas, Timo Schneider, Torsten Hoefler

arXiv:1902.10345v3cs.PLcs.DCcs.PF

TL;DR

Heterogeneous computing has made it difficult for domain scientists to maintain portable, performant code. The paper introduces SDFGs to separate program definition from optimization, and reports state-of-the-art-comparable performance across three different platforms without changing input code.

  • Problem

    Heterogeneous programming complexity and architecture-specific optimization make it difficult for domain scientists to maintain code that is both portable and performant.

    Source: §1 · p. 1

  • Method

    SDFGs represent code semantics and data movement in an intermediate graph that performance engineers can transform without changing the original program.

    Source: §2 · p. 2, §3 · p. 4

  • Results

    Transformations on SDFGs alone achieve performance comparable to the state of the art on three fundamentally different platforms.

    Source: §8 · p. 11

  • Takeaways & Limitations

    The same program source can deliver competitive or faster-than-expert-library results across kernels, graph algorithms, and a quantum transport simulator.

    Source: §1 · p. 2

    The untransformed benchmark test excludes data-centric transformations, which are necessary to optimize the computations in both cases.

    Source: §5 · p. 8

Abstract

from arXiv · show

The ubiquity of accelerators in high-performance computing has driven programming complexity beyond the skill-set of the average domain scientist. To maintain performance portability in the future, it is imperative to decouple architecture-specific programming paradigms from the underlying scientific computations. We present the Stateful DataFlow multiGraph (SDFG), a data-centric intermediate representation that enables separating program definition from its optimization. By combining fine-grained data dependencies with high-level control-flow, SDFGs are both expressive and amenable to program transformations, such as tiling and double-buffering. These transformations are applied to the SDFG in an interactive process, using extensible pattern matching, graph rewriting, and a graphical user interface. We demonstrate SDFGs on CPUs, GPUs, and FPGAs over various motifs --- from fundamental computational kernels to graph analytics. We show that SDFGs deliver competitive performance, allowing domain scientists to develop applications naturally and port them to approach peak hardware performance without modifying the original scientific code.

1 MOTIVATION

Heterogeneous hardware has made performant, portable programming increasingly difficult for domain scientists, while architecture-specific optimization often separates them from their code. The paper proposes SDFGs as an intermediate representation that separates scientific code definition from performance optimization.

1 MOTIVATION

  • Heterogeneous programming complexity makes it difficult for domain scientists to write code that is both portable and performant.The section notes that OpenMP grew from 63 pages in version 1.0 to 666 pages in version 5.0.Source: §1 · p. 1
  • Moving functionality to libraries or manually translating code into optimized languages reduces maintainability and makes later changes difficult for domain scientists.Source: §1 · p. 1
  • Annotations can require programmers to restate code semantics, and complex annotations can introduce hard-to-find bugs when the underlying code changes.For heterogeneous devices, annotation complexity can exceed that of the code being annotated.Source: §1 · p. 1
  • DAPP represents code semantics and transformations in SDFGs, letting domain scientists use familiar languages while performance engineers optimize the graph for target architectures.The implementation supports Python, MATLAB, TensorFlow, selected DSLs, and an extensible SDFG builder interface.Source: §1 · p. 2
  • SDFGs support performance portability across fundamental kernels, graph algorithms, and a quantum transport simulator, with results competitive with or faster than expert-tuned libraries and up to five orders of magnitude faster than naïve FPGA code.The reported results approach peak hardware performance using the same program source code.Source: §1 · p. 2

2 DATA-CENTRIC PROGRAMMING

Data-centric programming separates computation from data movement so that program semantics can remain distinct from architecture-specific optimization. SDFGs represent this separation hierarchically, while the domain-scientist interface supports familiar languages and explicit dataflow.

2 DATA-CENTRIC PROGRAMMING

  • SDFGs separate high-level program formulation from optimization and expose hierarchical, parametric data movement for reusable tiling and cross-level transformations.The original code can be updated without losing SDFG transformations as long as its dataflow aspects do not change.Source: §2 · p. 2
  • Performance engineers make informed SDFG modifications using program structure, hardware information, and intermediate performance results, while domain scientists can update calculations without undoing those optimizations.Source: §2 · p. 2
  • Stateful dataflow combines execution order based on data dependencies with global state, supporting concurrency as well as compact loops and data-dependent execution.Source: §2 · pp. 2–3
  • The model separates data-holding containers from stateless computations, represents data movement as flow, uses states to express execution order, and supports hierarchical coarsening of parallel patterns.Source: §2 · p. 3

2.1 Domain Scientist Interface

  • DaCe generates SDFGs from restricted Python and also supports MATLAB, TensorFlow, and a builder API for mapping other DSLs.Its Python interface supports NumPy operations, explicit dataflow, arrays, and decorated functions that interact with existing code through array-based interfaces.Source: §2.1 · p. 3
  • Explicit memlets specify movement direction, data container, optional range, and access metadata, including element counts for performance modeling and a conflict-handling function.Source: §2.1 · p. 3
  • DaCe supports external code such as BLAS calls by defining memlet semantics separately, allowing tasklet code to access memory directly while retaining concurrent scheduling.The interface also supports symbolic sizes and complex memlet subset expressions analyzed during compilation.Source: §2.1 · pp. 3–4

3 STATEFUL DATAFLOW MULTIGRAPHS

SDFGs combine dataflow multigraphs within state-machine control flow to represent computation, data movement, and parallelism. Their containers and scopes expose architecture-relevant structure while keeping computation distinct from movement.

3 STATEFUL DATAFLOW MULTIGRAPHS

  • SDFGs place directed acyclic dataflow multigraphs in state nodes, with memlets for data movement and state transitions for conditions and assignments.The top-level graph forms a state machine, allowing cyclic dependencies and control flow.Source: §3 · p. 4

3.1 Containers

  • Data nodes model multidimensional memory arrays, while Stream nodes model concurrent queues accessed with push and pop semantics.Containers are associated with storage locations, including GPUs and files.Source: §3.1 · p. 4

3.2 Computation

  • Tasklets are stateless computations whose code remains immutable during data-centric transformations and compilation.Tasklets are designed to be fine-grained, with memory access mediated by memlets.Source: §3.2 · p. 4

3.3 Concurrency

  • Map and Consume scopes expose parallel subgraphs, with scope boundaries making their overall data requirements analyzable.Maps can be nested; together with streams, they represent concurrency across CPUs, GPUs, and FPGAs.Source: §3.3 · pp. 4–5
  • Connected components execute concurrently and map to parallel sections, CUDA streams, or FPGA command queues, with synchronization aspects configurable by performance engineers.Write-conflict memlets can use atomics, critical sections, or accumulator modules, while Reduce nodes provide target-optimized reductions.Source: §3.3 · p. 5

3.4 State

  • State transitions support conditions and assignments, including data-dependent execution; nested SDFGs can manage control flow such as a convergence loop inside a map.Recursive calls to the same SDFG are disallowed.Source: §3.4 · p. 5

4 PERFORMANCE ENGINEER WORKFLOW

The performance-engineer workflow identifies data-movement motifs in SDFGs and applies transformations before compiling them into executable libraries. Transformations can be authored and applied interactively or programmatically, with DIODE supporting guided editing and tuning.

4 PERFORMANCE ENGINEER WORKFLOW

  • The workflow optimizes SDFGs by finding and leveraging application data-movement motifs, then compiles the resulting graph into an executable library.Transformations are made by performance engineers using program structure, hardware information, and intermediate performance results.Source: §4 · p. 6

4.1 Graph Transformations

  • Graph transformations match a pattern subgraph and replace it when matching requirements are met, enabling optimization strategies such as tiling.VF2 finds isomorphic subgraphs; transformations can be applied interactively or through a Python API and reused across applications.Source: §4.1 · p. 6

4.2 DIODE

  • DIODE lets performance engineers edit SDFGs, tune transformations, inspect links between domain code, graph, and generated code, and compare performance history.Transformation chains can be saved and branched for tuning different architectures; matrix multiplication reached nearly MKL performance in minutes.Source: §4.2 · p. 6

4.3 Compilation Pipeline

  • Compilation resolves data dependencies, generates code hierarchically using platform-specific dispatchers, and invokes the compilers required by those dispatchers.Dependency inference validates graph structure and storage or schedule feasibility, then propagates memlet ranges for memory-copy generation.Source: §4.3 · pp. 6–7

5 ASSESSING PERFORMANCE WITHOUT TRANSFORMATIONS

Without optimizing transformations, SDFGs expose enough parallelism to compete with polyhedral compilers, outperform them on GPUs, and provide placed-and-routed Polybench kernels on FPGAs. Results vary by architecture and kernel, and some CPU cases require transformations for optimization.

5 ASSESSING PERFORMANCE WITHOUT TRANSFORMATIONS

  • The evaluation applies FPGATransform and GPUTransform to Polybench applications, including kernels whose accelerator execution may be unprofitable.FPGA correctness is verified with simulation, followed by full placement and routing.Source: §5 · p. 7
  • On CPU, unoptimized SDFGs are closer to polyhedral compilers than general-purpose compilers for most kernels.For solvers such as cholesky and lu, and simple linear algebra such as gemm, SDFGs are on the order of standard compilers; data-centric transformations are necessary to optimize these computations.Source: §5 · pp. 7–8
  • 11.8× faster than PPCG on bicg GPU; untransformed SDFGs outperform PPCG in most GPU cases.The authors attribute these speedups to avoiding unnecessary array copies through explicit data dependencies and to the representation’s inherent parallel construction.Source: §5 · p. 8

6 PERFORMANCE EVALUATION

Across fundamental kernels and three case studies, SDFG transformations produce competitive performance on CPUs, GPUs, and FPGAs. The evaluation also shows how successive transformations and data-layout changes address specific optimization challenges.

6.1 Fundamental Computational Kernels

  • For matrix multiplication, SDFGs reach ∼98.6% of MKL, ∼70% of CUBLAS, and ∼90% of CUTLASS; on FPGA they are 4,992× faster than naïve HLS over SDAccel.For 1,024 × 1,024 matrices, the reported FPGA runtime is 45 ms versus 878 ms for Spatial, a 19.5× speedup.Source: (b) GPU · p. 8

(b) GPU

  • SDFGs match MKL at 99.9% performance on CPU for SpMV and vectorize it on GPUs; histogram vectorization reaches 8× gcc performance.The histogram passage says other compilers fail because of data-dependent accesses.Source: (b) GPU · p. 8
  • For Query, streaming access automatically parallelizes filtering, while an FPGA pipeline packs sparse filtered vectors into dense vectors for a 10× speedup.The CPU/GPU results are reported as significantly better than HPX and STL.Source: (b) GPU · p. 8
  • Hard-coded Halide timesteps compile in ∼68 minutes but yield a result 20% faster than SDFGs; FPGA Jacobi scales to 139 GOp/s.The passage also reports that SDFGs marginally outperform Pluto for the transformed GEMM comparison.Source: Figure 15 · p. 9

6.2 Case Study I: Matrix Multiplication

  • After seven transformation steps, matrix multiplication reaches ∼536× speedup and 75% of MKL performance, then 98.6% of MKL after size-specific tuning.The sequence includes fusion, cache and vector-register tiling, packing, vectorization, and reduction peeling.Source: §6.2 · p. 9

6.3 Case Study II: Graph Algorithms

  • SDFGs match graph frameworks on all tested graphs; they are up to 2× faster than Galois on road maps, while Galois is marginally faster on social networks and the Kronecker graph.The authors suggest fine-grained scheduling from map scopes could explain the road-map result.Source: Figure 17 · p. 9

6.4 Case Study III: Quantum Transport

  • 32.26× over manually tuned implementations and 1,021× over Python: SDFG transformations mitigate underutilization in OMEN’s scattering self-energy computation.The runtime comparison covers a 4,864-atom nanostructure.Source: Table 2 · p. 10, §6.4 · p. 10

7 RELATED WORK

The related-work discussion positions SDFGs among performance-portability models, separation-of-concerns approaches, and dataflow representations. It distinguishes SDFGs by their explicit data movement, fine-grained dependencies, and extensible transformations.

Performance Portability

  • Unlike models designed for load/store architectures, SDFGs are presented as natively supporting both load/store architectures and reconfigurable hardware.The comparison discusses Kokkos, RAJA, Legion, Legate, OpenCL, OpenACC, OpenMP, and SYCL.Source: §7 · p. 10

Dataflow Representations

  • SDFGs represent explicit state machines of dataflow execution with fine-grained dependencies, while PDGs use control-centric statement nodes and lose parametric concurrency when converted from SDFGs.The paper contrasts memlets’ data-movement information with data-dependent accesses in PDGs.Source: §7 · p. 11

Decoupling Data Access and Computation

  • SDFG transformations can be customized or extended for fine-tuning, whereas related approaches may rely on middleware tuned for existing memory hierarchies and require algorithm reimplementation for other targets.The discussion covers polyhedral frameworks and models for graph analytics, stream processing, and machine learning.Source: §7 · p. 11

Summary

  • SDFGs combine general-purpose expressiveness with performance portability without changing original code, and their extensible data-centric transformations generalize existing optimization approaches.The paper says the model is not limited to particular application classes or hardware.Source: §7 · p. 11

8 CONCLUSION

The paper presents a data-centric model that uses SDFG transformations to optimize scientific code without modifying its input. It concludes that this approach achieves performance comparable to the state of the art on three different platforms.

8 CONCLUSION

  • Transformations on an SDFG alone, without modifying input code, achieve performance comparable to the state of the art on three fundamentally different platforms.The model uses dataflow tracking and graph rewriting, with performance engineers applying the transformations.Source: §8 · p. 11
  • Future directions include systematic application of transformations to reduce human intervention, richer cost models using tasklet information, and applying SDFGs to distributed systems.The distributed-systems direction is framed around minimizing data movement through communication-avoiding formulations.Source: §8 · pp. 11–12

A SDFG OPERATIONAL SEMANTICS

  • The operational-semantics appendix defines SDFG elements, function invocation, and rules for evaluating an SDFG.Each operational rule is preceded by a less formal description of its intent.Source: A SDFG OPERATIONAL SEMANTICS · p. 14

A.1 Elements of an SDFG

An SDFG organizes execution as states connected by transitions, with each state encoding data dependencies through typed nodes and memlets. Its elements cover memory, computation, parallel scopes, and the values and symbols initialized at invocation.

A.1 Elements of an SDFG

  • An SDFG is a directed multigraph of states and transitions with one start state; each state is a directed acyclic multigraph whose edges encode dependencies and dataflow through memlets.State transitions carry conditions and assignments, while a global symbol namespace supports symbolic expressions.Source: §A.1 · pp. 14–15
  • Data nodes describe typed memory locations, while tasklets describe computation whose external reads and writes are restricted to named connectors.Data may be externally allocated or transient; tasklet code may use Python or target-supported languages such as C++.Source: §A.1 · p. 14
  • Streams use queue semantics, and reduce nodes represent target-optimized reductions using axes and a write-conflict-resolution function.The reduction is semantically equivalent to a map containing an identity tasklet and an output memlet annotated with the reduction function.Source: §A.1 · p. 14
  • Memlets specify connector-to-connector dataflow through a subset and reindex mapping, with optional write-conflict resolution for concurrent writes.Subset/reindex ranges can use exclusive ranges with start:end:stride:tilesize notation; tilesize can represent multiple elements such as vector types.Source: §A.1 · p. 14
  • Map scopes expand a subgraph concurrently over a symbolic range, while consume scopes support producer-consumer processing of streams until a quiescence condition is met.Map connectors can carry data between the scope and its surroundings or provide symbols for data-dependent ranges.Source: §A.1 · p. 14

A.2.1 Initialization.

  • At invocation, the execution configuration binds supplied data pointers and symbol values, starts at the SDFG’s start state, and initializes stream queue sizes to zero.The configuration also tracks data-node locations and the data visible at connectors.Source: §A.2.1 · p. 15

A.2.2 Propagating Data in a State.

Within a state, data propagates along edges in an order constrained by explicit dependencies, with nodes processed when their inputs are visible. When the state is empty, execution evaluates transitions to continue or terminate.

A.2.2 Propagating Data in a State.

  • State execution processes available memlets and nodes in an arbitrary order constrained by edge dependencies, continuing until the current state is empty.For a memlet, the visible data is transformed by subset, reindex, and optional write-conflict resolution before becoming visible at the destination connector.Source: §A.2.2 · p. 15
  • Tasklets execute generated input and output setup around their code, while data nodes write visible input data into their referenced memory.Tasklet inputs are initialized from visible connector data and outputs update connector visibility after execution.Source: §A.2.2 · p. 15
  • Map entries expand their enclosed subgraph across the symbolic range, while consume entries are rewritten as a map plus an invoked SDFG that loops under the consume condition.Reduce nodes are expanded into a map entry and exit surrounding an identity tasklet; their output memlet carries the reduction write-conflict-resolution annotation.Source: §A.2.2 · p. 15
  • Stream propagation handles simultaneous push and pop, push-only, or pop-only steps, updating queued data and queue size as appropriate.A pop requires at least one queued item; pushing stores data at the position indexed by the current queue size.Source: §A.2.2 · p. 16

A.2.3 Evaluating State Transitions.

  • Once state processing is complete, a true transition selects the next state and applies its symbol assignments; if no transition condition is true, execution ends.Data propagation then proceeds in the selected next state.Source: §A.2.3 · p. 16

B DATA-CENTRIC GRAPH TRANSFORMATIONS

SDFG transformations are implemented through algebraic graph rewriting: a matched subgraph is rewritten to produce a transformed graph. The paper presents this construction as the single-pushout approach.

B DATA-CENTRIC GRAPH TRANSFORMATIONS

C POLYBENCH FLAGS

The appendix lists compiler flag variants used for Polybench and illustrates a DaCe graph transformation that removes a redundant transient array. That transformation can be registered for reuse, while strict transformations are applied automatically after program processing.

C POLYBENCH FLAGS

  • Polybench compilers used -O3 -march=native -mtune=native as base flags, with reported results taken from the best-performing tested variants.The tested variants included compiler-specific options for gcc, icc, Polly, Pluto, and others, as well as compile-time size specialization.Source: C POLYBENCH FLAGS · p. 17

D TRANSFORMATION EXAMPLE: REDUNDANT ARRAY REMOVAL

  • RedundantArray removes a transient array copied directly to another array when it has no other uses, redirecting incoming dataflow to the retained array.In strict mode, it only matches arrays of the same shape; the illustrated checks also require compatible storage and no other access-node occurrences.Source: D TRANSFORMATION EXAMPLE: REDUNDANT… · p. 17
  • Custom transformations can be registered in a global registry, while strict transformations such as RedundantArray are applied automatically after processing a DaCe program.StateFusion and InlineSDFG are also identified as strict transformations.Source: D TRANSFORMATION EXAMPLE: REDUNDANT… · p. 17

E GRAPH DATASETS

This block identifies the graph-properties table used in the BFS case study and explains how SDFGs represent indirect memory access.

E GRAPH DATASETS

  • The graph-properties table is used to describe datasets in the paper’s BFS case study.The supplied passage identifies the table’s role but does not give its dataset values.Source: E GRAPH DATASETS · p. 18, Table 5 · p. 18

F INDIRECT MEMORY ACCESS

Loading 1902.10345v3…