Elhadji Sall
All projects

Team project · CPSC 482, UNBC

DSM Optimizer

Reorders a project's task-dependency matrix to cut rework loops, in C++17.

With Simon Kraft and Joshua Payne.

  • C++17
  • graphs
  • sparse matrices
CodeReport (PDF)Slides (PDF)
Two matrix plots of the California benchmark. Before: dots scattered across the whole matrix, with 6,063 feedback marks. After: nearly all dots below the diagonal, with 192 feedback marks.
The California benchmark before and after: 6,063 feedback marks down to 192.

Problem

A Design Structure Matrix lists the tasks in a project, with a mark wherever one task depends on another. Marks above the diagonal are feedback marks: a task that depends on work scheduled after it, which means rework.

Reordering the tasks can remove many of those marks. We measured two things: the number of feedback marks (FBM), and their total distance from the diagonal (TFBD).

What I built

A six-stage pipeline in C++17 that reads a sparse matrix and returns a reordered one. We tested it on 10 benchmark matrices, from 11×11 up to 27,770×27,770.

How

  1. ParseMatrix Market into compressed sparse columns
  2. SCC decompositionTarjan's and Kosaraju-Sharir's algorithms
  3. Condense and sortContract each SCC, then Kahn's topological sort
  4. TearingEades-Lin-Smyth Algorithm GR inside each SCC
  5. BandingReverse Cuthill-McKee, then adjacent-swap hill climbing
  6. PermuteApply P^T A P and verify the result

Tasks in a strongly connected component depend on each other, so no ordering can clear every feedback mark among them. Contracting each component gives a DAG, and a topological sort of that DAG leaves feedback marks only inside the components.

Tearing then approximates a minimum feedback arc set inside each component. The hill climbing step accepts a swap only if TFBD drops and FBM does not rise.

Bar chart of average reduction by stage across 10 matrices. Topological sort alone reaches about 76% for FBM and 95% for TFBD. Tearing raises FBM to about 84%. Banding changes little.
Average reduction after each stage, across all 10 matrices.
Log-log plot of mean runtime against vertices plus edges for each pipeline stage, with an O(V+E) reference line.
Runtime of each stage against V + E, on log-log axes, with an O(V+E) reference line.

Results

  • 84% average FBM reduction and 94.54% average TFBD reduction across the 10 matrices.
  • On California (9,664 tasks), FBM fell from 6,063 to 192 and TFBD from 18,810,564 to 669.
  • Tarjan ran about 1.8× faster than Kosaraju.
  • Most of the gain came from SCC condensation plus topological sort; tearing added about 8 points of FBM reduction, and banding barely moved either metric.
Next projectWharf