Hacktoberfest 2026: the issues maintainers tagged for October, open and beginner-friendly. Browse Hacktoberfest issues

Ordering chooser picks AMD on large KKT systems: cost model weighs column-etree depth, not supernodal schedule depth (2× schedule depth vs ND)

Open
  • Is something wrong?
#108 1 comment 0 reactions 0 assignees View on GitHub

Maintainers usually reply within 1 day

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
15/100
Issue type
Bug
Clarity
Mostly clear
Activity status
Active
Tech stack
julia
Domain
performance

Research direction

The chooser is compute_ordering and ordering_cost in src/symbolic/ordering.jl; the benchmarks behind the claim are bench/order_search.jl and bench/solve_nd.jl. Start by reproducing the schedule-depth numbers for the 78k-bus KKT matrix and comparing them with the column-etree nlevels the cost model uses. Done means the chooser picks a choice that gives lower supernodal schedule depth at large n, or the owner settles the design question first.

Written by the indexing model from the issue text.

Description

found-by-agent performance triaged

Found while working on: PR #107 (performance prototypes, experiments 0/5/6; ordering study bench/order_search.jl, bench/solve_nd.jl)

What: the automatic ordering choice (compute_ordering, src/symbolic/ordering.jl, reordering_alg = "default") picks AMD on large KKT systems where ND is 2× better for the GPU. ordering_cost(flops, nlevels, n) = flops × (1 + nlevels/n) weighs depth at ~0.2% for n = 674 562 (the 78k-bus pglib condensed KKT), so the chooser is a flop contest that AMD wins; and nlevels is the column-etree depth, which does not predict the supernodal schedule depth that governs GPU time (cuDSS's permutation: 1279 column levels → 30 schedule levels; METIS: 1216 → 29; AMD: competitive column metrics → 65 schedule levels). Forcing reordering_alg = "algo4" on that matrix: schedule depth 65 → 29, solve 36% faster, factorization 11–17% faster (GV100). A METIS knob sweep (seed, ufactor, nseps) moves schedule depth 28–41 with noise; plain ND is enough.

Why it is out of scope: #107 is a bench-level campaign; the cost model is T05 code and a PLAN §2.3 step 2 decision. Does not block a task; it makes every GPU run on large KKT systems slower by default.

Suggested fix or plan change: score candidate orderings by supernodal schedule depth (cheap: compute the supernode partition and tree_levels(snparent) per candidate, as the T06 Report already suggested), with a weight that matters at n ≈ 1e6; or prefer ND on GPU backends and keep AMD for the CPU backend. Owner note under T25; PLAN §2.3 step 2 updated in the docs PR that cites this issue.

Generated by Claude Code

Dominant language
Julia
Stars
3
Forks
0
Avg merge
4h 1m
Merged PRs (30d)
73

Getting set up

  • No Dockerfile or Docker Compose file
  • Has a pull request template
  • No contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from exanauts/SparseDirectSolver.jl

All issues in exanauts/SparseDirectSolver.jl

Similar issues

More Julia issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.