OrthoRoute/docs/optimization/baseline_template.md

OrthoRoute Optimization Baseline — [DATE]

Status: [✅ IMPROVEMENT | ⚠️ REGRESSION | 📊 BASELINE]

Summary

[One-paragraph summary of the optimization and its impact]

Example:

This optimization vectorized bitmap construction in _build_owner_bitmap_for_fullgraph, reducing per-net overhead from 920ms to 116ms (8× speedup). Total routing time improved from 1106.6s to 950.2s (14% faster). All 512 nets routed successfully with zero overuse.

---

Change Description

Files modified:

• orthoroute/algorithms/manhattan/unified_pathfinder.py — [brief description]
• orthoroute/algorithms/manhattan/pathfinder/cuda_dijkstra.py — [brief description]

Optimization type:

• Algorithm improvement (logic change)
• Vectorization (loop → GPU kernel)
• Memory optimization (reduced allocations/copies)
• Caching (precompute vs. recompute)
• Other: _____________

Root cause of previous slowdown: [Explain what was slow and why]

Example:

The _build_owner_bitmap_for_fullgraph function iterated over seed nodes in a Python loop, calling int(seed) for each (100+ calls per net). Each int() triggered a GPU→CPU sync (~1ms each), accumulating to ~920ms per call × 73 iterations = 67.2s total (6% of routing time).

Solution implemented: [Explain the fix and why it works]

Example:

Replaced the loop with vectorized CuPy operations: seed_words = seed_nodes // 32, masks = cp.uint32(1) << seed_bits, then used cupyx.scatter_add() to build the bitmap in a single GPU kernel call. This eliminates all GPU→CPU round-trips, reducing overhead from ~920ms to ~116ms.

---

Performance Metrics

Before vs After

Metric	Before	After	Change	Status
Total time	1106.6s	950.2s	-156.4s (-14%)	✅
Avg iteration	15.2s	13.6s	-1.6s (-11%)	✅
Iterations	73	70	-3 (-4%)	✅
Nets routed	512/512	512/512	—	✅
Converged	True	True	—	✅
Overuse	0	0	—	✅
Barrel conflicts	367	340	-27 (-7%)	✅

Interpretation: [Explain if the results match expectations, any surprises, trade-offs]

Example:

The optimization met expectations with a ~14% total speedup. Iteration count decreased slightly (73→70) as a side effect of faster convergence. Barrel conflicts also decreased, likely due to better net ordering from faster early iterations.

Profiling Data Comparison

Target function (what was optimized):

Function	Before	After	Improvement
_build_owner_bitmap_for_fullgraph	67.2s (73 calls, 920ms avg)	8.5s (73 calls, 116ms avg)	87% reduction

Top 5 functions (current bottlenecks):

Function	Total Time	Call Count	Avg Time	Notes
commit_path	8.5s	512	16.6ms	Next optimization target
_path_to_edges	4.2s	512	8.2ms	Acceptable
find_path_fullgraph_gpu_seeds	3.8s	512	7.4ms	GPU kernel overhead
...	...	...	...	...

Next optimization candidates:

1. commit_path — 8.5s total, called per-net (512×)
2. [other candidates...]

---

Test Configuration

Parameter	Value
Date	[YYYY-MM-DD @ HH:MM:SS]
Board	[TestBackplane.kicad_pcb]
Mode	[KiCad Plugin / Headless / CLI]
Hardware	[NVIDIA GPU model / CPU-only]
Repository	[Commit hash or branch]
KiCad Version	[e.g., 9.0.0]

---

Validation Results

Smoke Test (100 nets, fast validation)

.\scripts\optimize_and_validate.ps1 -Compare tests/regression/smoke_metrics.json

Result: [✅ PASS | ⚠️ WARN | ❌ FAIL]

Metric	Actual	Threshold	Status
Nets routed	100/100	100	✅
Converged	True	True	✅
Iterations	18	≤30	✅
Total time	25.3s	≤90s	✅

Backplane Test (512 nets, full validation)

.\scripts\optimize_and_validate.ps1 -ProfileMode -TestBoard backplane -Compare tests/regression/golden_metrics.json

Result: [✅ PASS | ⚠️ WARN | ❌ FAIL]

Metric	Actual	Threshold	Status
Nets routed	512/512	512	✅
Converged	True	True	✅
Iterations	70	≤88	✅
Total time	950.2s	≤1328s	✅
Barrel conflicts	340	≤450	✅

Log analysis:

python scripts/analyze_log.py --compare tests/regression/golden_metrics.json

[Paste summary output or highlight key findings]

---

Regression Thresholds

Should these metrics become the new golden baseline? [YES / NO / TBD]

If YES, update tests/regression/golden_metrics.json:

{
  "gpu": {
    "iterations_max": 84,        // 70 × 1.20
    "total_time_s_max": 1140,    // 950.2 × 1.20
    "barrel_conflicts_max": 408  // 340 × 1.20
  }
}

Rationale: [Why this should/shouldn't become the new baseline]

Example:

YES — This optimization achieved significant improvement (14% speedup) with no correctness regressions across smoke and backplane tests. Profiling confirms the root cause was addressed. Update golden metrics to reflect the new baseline and prevent future regressions back to the slower implementation.

---

Reproducibility

Commands Used

Baseline measurement (before optimization):

git checkout <before_commit_hash>
.\scripts\optimize_and_validate.ps1 -ProfileMode -TestBoard backplane
python scripts/analyze_log.py > baseline_profile.txt

Optimization measurement (after changes):

git checkout <after_commit_hash>
.\scripts\optimize_and_validate.ps1 -ProfileMode -TestBoard backplane
python scripts/analyze_log.py > optimized_profile.txt

Comparison:

code --diff baseline_profile.txt optimized_profile.txt

Logs Archived

• Baseline log: docs/optimization/logs/baseline_YYYY-MM-DD.log
• Optimized log: docs/optimization/logs/optimized_YYYY-MM-DD.log
• Profiling comparison: docs/optimization/profile_YYYY-MM-DD.txt

---

Commit Information

Branch: [e.g., optimization/vectorize-bitmap-construction]

Commit message:

optimization: [one-line description]

[Detailed explanation of what changed and why]

Before: [key metric]
After:  [key metric]
Speedup: [percentage or absolute improvement]

Validation:
- Smoke test: PASS (100/100 nets, <30s)
- Backplane: PASS (512/512 nets, zero overuse, X iters, Xs total)

Example:

optimization: vectorize bitmap construction (8× faster bitmap builds)

Replaced per-seed GPU→CPU sync loop with single vectorized scatter-add.
Reduces _build_owner_bitmap_for_fullgraph from 920ms to 116ms avg.

Before: 73 iters, 1106.6s total (15.2s avg)
After:  70 iters,  950.2s total (13.6s avg)
Speedup: 14% total routing time reduction

Validation:
- Smoke test: PASS (100/100 nets, 25.3s)
- Backplane: PASS (512/512 nets, zero overuse, 70 iters, 950.2s)

---

Known Issues / Limitations

[Document any trade-offs, limitations, or edge cases introduced by this optimization]

Example:

• None identified — optimization is a pure speedup with no correctness impact
• OR: Increased iteration count by 5% but overall time still 10% faster due to faster per-iteration execution

---

References

• Previous baseline: optimization_baseline_YYYY-MM-DD.md
• Golden result: golden_result_2026-04-10.md
• Optimization workflow guide
• GitHub issue/PR: #XXX (if applicable)

---

Checklist

Before publishing this baseline doc:

• Smoke test validation completed (PASS)
• Backplane test validation completed (PASS or explained)
• Profiling data captured and analyzed
• Before/after metrics documented with evidence
• Logs archived (if significant baseline)
• Golden metrics updated (if this becomes new baseline)
• Code committed with proper commit message
• OPTIMIZATION_QUICK_REF.md updated (for minor changes)
• This baseline doc added to docs/optimization/