List view
We need a clear, extensible contract for describing how Boolean expressions will be: 1. Constructed (symbols, operations, etc.), 2. Manipulated (heuristics, transformations, conversions), and 3. Analyzed (minimizaton, probability, prime implicants). The goal is an interface that remains simple for small-scale use yet scalable for advanced tasks (like device-level parallelism, or large-scale transformations). ## Proposed Interface Elements 1. **IR (Intermediate Representation)** - A minimal data structure to represent nodes (variables, operators) and edges (inputs). - Negation can be stored via negative indices or separate booleans—determine one consistent scheme. 2. **Builder Class** - Creates expressions from textual or structured inputs. - Avoids direct manual node/pointer manipulation in user code. - Ensures sub-expression memoization (optional) to avoid duplication. 3. **Pass/Transformation Pipeline** - Each pass is a function or class transforming the IR (e.g. NNF conversion, gate coalescing, probability annotation). - A Pass Manager object sequences multiple passes, enabling “pipelines.” 4. **Heuristics & Minimization** - Provide clear hooks to plug in advanced algorithms (ESPRESSO-like minimization, BDD-based rewriting). - Keep heuristics modular so they can be combined or swapped without rewriting the entire system. 5. **Conversion APIs** - Converters to normal forms (AIG, CNF, DNF, BDD, etc.). - Each converter is a self-contained pass or set of passes returning a new representation. 6. **Device-Friendly Structures (Optional)** - IR is easy to copy to GPU memory (SYCL) for data-parallel passes. - Minimizes pointer chasing; might use arrays of indices. ## Requirements & Constraints - Must handle thousands of nodes efficiently. - Must allow for partial or incremental transformations. - Must allow for additional annotations (e.g., probability distributions, prime-implicant caching). - Should clearly define when pass transformations are in-place vs. produce new IR objects. ## Open Questions 1. How should we manage negation? (negative indices vs. separate bool array) 2. Should the builder store references in a host-owned structure or a device-shared buffer from the start? 3. Will we adopt a single “universal IR” for all forms, or produce specialized IRs for AIG, CNF, etc.? 4. How do we store intermediate data (like prime implicant sets, partial evaluation for probability) without bloating the IR? ## Acceptance Criteria - A documented interface (header files, class diagrams, etc.) describing IR, passes, and builder usage. - At least one example pass (e.g., NNF conversion) showing how passes integrate. - A demonstration of hashing or node identity logic to avoid duplicate sub-expressions. - Basic tests proving correct transformations in a small code sample. ## Next Steps - Discuss and finalize negation storage. - Draft the IR and builder class skeletons. - Write a prototype pass manager pipeline. - Collect feedback from domain experts on prime implicant or probability integration.
Overdue by 3 month(s)•Due by July 28, 2025•0/3 issues closed