Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Switch from Watch list and/or Dancing links to a complete bi-graph from Lit to Clause #278

Open
shnarazk opened this issue Jan 11, 2025 · 0 comments
Assignees

Comments

@shnarazk
Copy link
Owner

shnarazk commented Jan 11, 2025

It's time to ditch all the 2024 work!

No more reference updates. Clauses have no data about other clauses.

  • if you can use a SIMD crate, progress == watch1 || progress == watch2 is cheap.
clauses_contain[propagating]
  .iter()
  .filter(|ci| clause[ci].watch1 == propagating || clause[ci].watch2 == propagating)
  .map(|ci| asg.propagate{&mut clause[ci], propagating))
  .fold(PropagationResult::Propagated, |acc val| acc.join(val));

or

clauses.par_iter_mut()
  .filter(|c| c.watch1 == propagating || c.watch2 == propagating)
  .map(|&mut c| c.propagate(propapating)  // Oh, c doesn't know its id.
  .fold(...)

Is this very slow even we can use rayon here?
Maybe you can't use rayon. propagate will update AssignStack.

But by switching to stage-based propagation from online propagation, the propagation process can be described as map-reduce iteration.

enum PropagationResult {
  Propagated(Vec<(Lit, ClauseId)>),
  Conflicting(Vec<(Lit, ClauseId)>),
}

clauses.par_iter_mut()
  .map(|&mut c| c.propagate(propagating)
  .fold(PropagationResult::Propagated(Vec::new()), merger);
@shnarazk shnarazk self-assigned this Jan 11, 2025
@shnarazk shnarazk changed the title Switch from *Watch list* and/or *Dancing Links* to complete graph from Lit to Clause Switch from _Watch list_ and/or _Dancing Links_ to complete graph from Lit to Clause Jan 11, 2025
@shnarazk shnarazk changed the title Switch from _Watch list_ and/or _Dancing Links_ to complete graph from Lit to Clause Switch from Watch list and/or Dancing Links to complete graph from Lit to Clause Jan 11, 2025
@shnarazk shnarazk changed the title Switch from Watch list and/or Dancing Links to complete graph from Lit to Clause Switch from Watch list and/or Dancing Links to a complete bigraph from Lit to Clause Jan 11, 2025
@shnarazk shnarazk changed the title Switch from Watch list and/or Dancing Links to a complete bigraph from Lit to Clause Switch from Watch list and/or Dancing Links to a complete bi-graph from Lit to Clause Jan 11, 2025
@shnarazk shnarazk changed the title Switch from Watch list and/or Dancing Links to a complete bi-graph from Lit to Clause Switch from Watch list and/or Dancing links to a complete bi-graph from Lit to Clause Jan 11, 2025
@shnarazk shnarazk pinned this issue Jan 11, 2025
This was linked to pull requests Jan 11, 2025
@shnarazk shnarazk unpinned this issue Jan 25, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant