mgrettondann/partridge-cpp
1
0
Fork 0
Code Issues 4 Pull Requests Activity

solver: parallelize a shallow search frontier #11

New Issue
Open
opened 2026-07-30 16:23:34 +01:00 by mcp · 0 comments
mcp commented 2026-07-30 16:23:34 +01:00
Collaborator
Copy Link
Copy Source

Background

Search branches are independent once a partial state is copied. Since only one solution is needed, workers can stop as soon as any branch succeeds. Static root partitioning is likely to be severely imbalanced.

Proposed work

  • Expand the search to an over-decomposed shallow frontier.
  • Schedule frontier states dynamically with work stealing or an atomic task queue.
  • Publish the first validated solution and cancel all remaining work.
  • Keep hot state worker-local.
  • Evaluate diverse deterministic branch orders across workers.
  • Avoid a contended shared cache initially.

Acceptance criteria

  • Results are race-free under ThreadSanitizer or an equivalent check.
  • Cancellation is prompt and no worker accesses a destroyed winning state.
  • Support an explicit worker-count option and deterministic single-thread mode.
  • Report scaling and variability for 1, 2, 4 and available hardware threads.
  • Tests exercise success, exhaustion and cancellation paths.

References

## Background Search branches are independent once a partial state is copied. Since only one solution is needed, workers can stop as soon as any branch succeeds. Static root partitioning is likely to be severely imbalanced. ## Proposed work - Expand the search to an over-decomposed shallow frontier. - Schedule frontier states dynamically with work stealing or an atomic task queue. - Publish the first validated solution and cancel all remaining work. - Keep hot state worker-local. - Evaluate diverse deterministic branch orders across workers. - Avoid a contended shared cache initially. ## Acceptance criteria - Results are race-free under ThreadSanitizer or an equivalent check. - Cancellation is prompt and no worker accesses a destroyed winning state. - Support an explicit worker-count option and deterministic single-thread mode. - Report scaling and variability for 1, 2, 4 and available hardware threads. - Tests exercise success, exhaustion and cancellation paths. ## References - https://viddrobnic.com/writing/partridge/ - https://www.tunbury.org/2025/12/17/partridge-puzzle/ - https://github.com/lightln2/partridge-solver
Sign in to join this conversation.
No Branch/Tag Specified
Branches Tags
Labels
No items
No labels
Milestone
No items
No Milestone
Assignees
Clear assignees
mcp mgrettondann (Matthew Gretton-Dann)
No Assignees
1 Participants
Notifications
Due Date
No due date set.
Dependencies

No dependencies set.

Reference: mgrettondann/partridge-cpp#11