Parallel Algorithms for Operations on Multi-Valued Decision Diagrams

Guillaume Perez, Jean-Charles RéginAAAI 2018 · DOI

Abstract

Multi-Valued Decision Diagrams (MDDs) are essential for representing and compressing large-scale data in artificial intelligence and constraint programming. However, as MDDs grow to sizes exceeding 50GB, sequential processing becomes a significant bottleneck. This paper presents the first efficient parallel algorithms for core MDD operations—reduction and apply—designed to scale linearly with CPU cores by minimizing memory contention and avoiding software locks.

Introduction

In fields like constraint programming and music generation, MDDs are used to represent massive sets of valid configurations. While memory-efficient, the computational cost of operations like intersection (apply) or compression (reduction) scales with the size of the diagram. Modern MDDs can reach tens of gigabytes, making sequential processing take hours.

Traditional parallelization techniques, such as work-stealing, often require duplicating data, which is unfeasible when the data structure already consumes most available RAM. The challenge lies in parallelizing graph-based operations on a massive, shared data structure without hitting hardware-level bottlenecks like memory locks or cache conflicts.

Methodology: Parallel Reduction and Apply

The researchers focused on parallelizing the two most fundamental MDD operations:

  1. Parallel Reduction: This process merges equivalent nodes to ensure the MDD is in its most compressed, canonical form. The algorithm utilizes a parallel radix sort (specifically a counting sort) to identify nodes with identical "signatures"—defined by their outgoing edges.
  2. Parallel Apply: This generic operator computes the union, intersection, or difference of two MDDs by building the resulting diagram layer-by-layer in parallel.
The PARAREDUCE algorithm for parallel MDD reduction.

Key Technical Innovations

To achieve high performance, the authors implemented several low-level optimizations:

  • Lock-Free Design: Instead of using slow software locks, the algorithms partition MDD nodes among "workers" (CPU cores). Each worker operates on its segment, and results are merged via a coordinated cumulative step.
  • Junction Management: To handle dependencies where a group of related nodes is split across worker boundaries, the authors employed a Union-Find data structure. This manages "junctions" and ensures global consistency without global locks.
  • False Sharing Mitigation: The implementation specifically avoids hardware-level conflicts where multiple cores attempt to update different variables residing on the same cache line.
Comparison of an MDD before (left) and after (right) reduction.

Evaluation and Results

The algorithms were tested on real-world instances, such as the "Max-Order" problem from music generation (involving MDDs with over 1 million nodes and 200 million arcs), and various random instances.

Performance Gains

  • Linear Scaling: Speedup was found to be perfectly linear up to 16 cores, matching the number of available memory channels on the test hardware. On a 40-core machine, performance continued to improve, though at a sub-linear rate due to the "memory wall."
  • Massive Data Handling: The "Max-Order" problem, which previously required 52GB of memory and significant time, was solved in seconds.
  • Low Overhead: The parallel version running on a single core was less than 10% slower than a highly optimized sequential version, demonstrating minimal architectural overhead.

Conclusion and Future Work

The primary limitation of this approach is hardware-bound: once MDDs saturate the CPU's memory channels (approximately 70GB in tests), the speedup coefficient drops. Additionally, for very small diagrams, the overhead of parallel setup may exceed the execution time of a sequential approach.

Future research may extend these parallel patterns to other decision diagram variants, such as Weighted MDDs, or integrate them into real-time constraint solvers to further enhance performance in dynamic environments.

Summary updated

BibTeX
@inproceedings{perez2018parallel,
  author = {Guillaume Perez and Jean-Charles Régin},
  title = {{Parallel Algorithms for Operations on Multi-Valued Decision Diagrams}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.12210},
}
Figure