Boolean Relations: Extracting Functions for Solutions

extracting functions from boolean relations n.w
1 / 60
Embed
Share

Uncover the power of extracting functions from Boolean relations with Jordi Cortadella from Universitat Politècnica de Catalunya. Dive into examples and methodologies for deriving functions from binary sets to develop efficient solutions.

  • Boolean Relations
  • Functions
  • Jordi Cortadella
  • Catalunya
  • Solutions
rayaanacharya
vkai Follow

Uploaded on | 2 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. Extracting Functions from Boolean Relations Jordi Cortadella Universitat Polit cnica de Catalunya

  2. Boolean relation: example a b c f 0 1 0 1 0 1 0 a b c 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 ? x f ? a y b z c ? ? = ?? + ?? ? a c b 3/22/2025 Extracting functions from BRs 2

  3. Boolean relation: example x y z a b c f 0 1 0 1 0 1 0 a b c 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 ? x f ? a b y z c ? ? = ?? + ?? ? a c b 3/22/2025 Extracting functions from BRs 3

  4. Boolean relation: example x y z a b c f 0 1 0 1 0 1 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 x 0 y z 0 ? = ?? + ?? ? 3/22/2025 Extracting functions from BRs 4

  5. Boolean relation: example x y z a b c f 0 1 0 1 0 1 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 x 0 0 0 y 0 0 z 0 0 0 ? = ?? + ?? ? 3/22/2025 Extracting functions from BRs 5

  6. Boolean relation: example x y z a b c f 0 1 0 1 0 1 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 x 0 0 0 0 y 0 0 z 1 0 0 ? = ?? + ?? ? 3/22/2025 Extracting functions from BRs 6

  7. Boolean relation: example x y z a b c f 0 1 0 1 0 1 0 0 0 | 01 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 x 0 0 | 01 0 0 y 0 0 | 01 z 1 0 0 | 01 ? = ?? + ?? ? 3/22/2025 Extracting functions from BRs 7

  8. Boolean relation: example x y z a b c f 0 1 0 1 0 1 0 0 0 | 01 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 x 0 0 | 01 1 y 0 0 | 01 z 0 0 0 | 01 ? = ?? + ?? ? 3/22/2025 Extracting functions from BRs 8

  9. Boolean relation: example x y z a b c f 0 1 0 1 0 1 0 0 0 | 01 1 0 0 0 | 01 1 0 0 0 | 01 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 x 1 y z 0 1 0 0 0 | 01 ? = ?? + ?? ? 3/22/2025 Extracting functions from BRs 9

  10. Boolean relation: example x y z a b c f 0 1 0 1 0 1 0 0 0 | 01 1 0 0 0 | 01 1 0 0 0 | 01 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 x 1 1 y z 1 1 0 0 0 | 01 ? = ?? + ?? ? 3/22/2025 Extracting functions from BRs 10

  11. Boolean relation: example x y z a b c f 0 1 0 1 0 1 0 0 0 | 01 1 0 | 11 0 0 | 01 1 0 | 11 0 0 | 01 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 x 1 1 y z 1 1 0 | 11 0 0 | 01 ? = ?? + ?? ? 3/22/2025 Extracting functions from BRs 11

  12. Boolean relation: example x y z a b c f 0 1 0 1 0 1 0 0 0 | 01 1 0 | 11 0 0 | 01 1 0 | 11 0 0 | 01 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 x y z 1 0 | 11 0 0 | 01 ? = ?? + ?? ? 3/22/2025 Extracting functions from BRs 12

  13. Boolean relation: example x y z a b c f 0 1 0 1 0 1 0 0 0 | 01 1 0 | 11 0 0 | 01 1 0 | 11 0 0 | 01 1 0 | 11 0 0 | 01 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 x y z ? = ?? + ?? ? 3/22/2025 Extracting functions from BRs 13

  14. Boolean relation: example x y z a b c a b c 0 0 | 01 1 0 | 11 0 0 | 01 1 0 | 11 0 0 | 01 1 0 | 11 0 0 | 01 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 ? x f ? a b y z c ? a c b 3/22/2025 Extracting functions from BRs 14

  15. Boolean relation: example a x f c x y z a b c y 0 0 | 01 1 0 | 11 0 0 | 01 1 0 | 11 0 0 | 01 1 0 | 11 0 0 | 01 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 z b x f a a b y z c x c f y b z a 3/22/2025 Extracting functions from BRs 15

  16. BR: characteristic function 3/22/2025 Extracting functions from BRs 16

  17. Solving a Boolean Relation 3/22/2025 Extracting functions from BRs 17

  18. Solving a Boolean Relation 3/22/2025 Extracting functions from BRs 18

  19. Exact 2-level solvers The concept of prime must be redefined F. Somenzi and R.K. Brayton (1989) Method similar to Quine-McCluskey Extension of primes to c-primes S. Jeong and F. Somenzi (1992) Formulate the problem as a Binate Covering Problem 3/22/2025 Extracting functions from BRs 19

  20. Heuristic 2-level solvers Based on ESPRESSO: A. Ghosh, S. Devadas and A. R. Newton (1992) Y. Watanabe and R. K. Brayton (1993) GYOCRO x:=Initial Solution; do REDUCE(x); EXPAND(x); IRREDUNDANT(x); while x is improved; 3/22/2025 Extracting functions from BRs 20

  21. Modern approaches Jie-Hong R. Jiang, Hsuan-Po Lin and Wei-Lun Hung, Interpolating Functions from Large Boolean Relations, ICCAD 2009. David Ba eres, Jordi Cortadella, and Mike Kishinevsky, A Recursive Paradigm to Solve Boolean Relations, DAC 2004.

  22. Subclasses of Boolean Relations a b x y a b x y a b x y 10 11 01 00 01 10 11 10 11 1 00 01 10 11 10 00 01 10 11 00 | 11 1 1 |1 10 Completely Specified Functions Incompletely Specified Functions General Boolean Relations We have efficient ISF solvers 3/22/2025 Extracting functions from BRs 22

  23. ISF solvers exact, expensive ?? (? inputs inputs,? output output) Quine-McCluskey (SOP, exact) DC Scherzo (SOP, ZDDs) Off Espresso (SOP, heuristic) On Minato-Morreale (BDDs) ? Craig Interpolation (AIG, SAT) inexpensive, inexact 3/22/2025 Extracting functions from BRs 23

  24. Example ?? ?? ?? ?? ?? ?? ?? ?? {??} ?? ?? ?? ?? ?? ? ?? {??,??} ?? ?? ?? ?? ?? ?? {??,??,??} ?? ?? ?? ?? ?? ?? {??} ?? ?? ?? ?? ?? ? = ? + ? ? = ? ? = ? ? = ?? ? = ? ? = ? ? = ? ? = ? + ? Decoupling individual functions ?? ? ?? ?? ?? ?? ? ???(?) ?? ?? ???(?) ?? ?? 3/22/2025 Extracting functions from BRs 24

  25. Decoupling the outputs ?? ?? ?? ?? ?? ?? ?? ?? {??} ?? ?? ?? ?? ?? ? ?? {??,??} ?? ?? ?? ?? ?? ?? {??,??,??} ?? ?? ?? ?? ?? ?? {??} ?? ?? ?? ?? ?? ? = ? ? = ? ? = ? ? = ? ? = ? ? = ? ? = ? ? = ? Decoupling individual functions ?? ?? = ???,?,?,? ??(?,?,?,?) ?????,?,? = ? ???,?,?,? ?? ?? ???(?) ?? ?????,?,? = ? ???,?,?,? ?? = ???,?,?,? ??(?,?,?,?) ?? ?? Easy implementation with BDDs or AIGs 3/22/2025 Extracting functions from BRs 25

  26. Decoupling the outputs ?? ?? ?? ?? ?? ?? ?? ?? {??} ?? ?? ?? ?? ?? ? ?? {??,??} ?? ?? ?? ?? ?? ?? {??,??,??} ?? ?? ?? ?? ?? ?? {??} ?? ?? ?? ?? ?? ? = ? ? = ? ? = ? ? = ? ? = ? ? = ? ? = ? ? = ? Decoupling individual functions ????(?,?,?) ?? ?? ?? ?? ???(?) ?? ? ? ?? ? ? ? ? ? ? ? ? ?? ?? ? ? 3/22/2025 Extracting functions from BRs 26

  27. ICCAD 2009: Reduce and substitute ?? ??? ?? ? ?? ?? ?? ??? ?? ? ?? ?? ? ? ??,? ? ?,? ??,? ?? ?? ?? ?? ???,???,??? ?? ?? ?? ??? ?? ? ?? ?? ISF solver (interpolation) ?? ??? ?? ?? ?? ? ?? ??? ?? ?? ? ?? ? Subs Subs ? Subs Subs ? ?? ??? ?? ?? ? ?? ??? ?? ?? ?? ? ?? ??? ?? ?? ?? ? ? = ? ? = ? ? = ? ? ? = ? ? = ? ? = ? 3/22/2025 Extracting functions from BRs 27

  28. ICCAD 2009: Reduce and substitute ?? ??? ?? ?? ??? ? = ? ? = ? ? = ? ? ?? ??? ?? ??? ?? ??? ?? ??? ?? ??? The final result depends on the order of the reductions ??,? ? ?? ?? ???,???,??? ?? ??? ?? ??? ? = ? + ? ? = ? ? = ? ?? ??? ?? ?? ??? ?? ??? ?? ??? abstractions: using AIGs ISF minimization: using Craig interpolation 3/22/2025 Extracting functions from BRs 28

  29. x y a b 00 01 10 11 00 01 10 11 Boolean relation 3/22/2025 Extracting functions from BRs 29

  30. 00 01 10 11 00 01 10 11 3/22/2025 Extracting functions from BRs

  31. 00 01 10 11 00 01 10 11 3/22/2025 Extracting functions from BRs

  32. 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 01 10 01 11 ?? ?? 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 Semi Semi lattice lattice 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 Functions ? = ? ? ? = ? ? = ? ? 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11 ? = ?? ? = ? ? = ? ? = ? ? ? = ? + ? ? = ?? ? = ? + ? ? = ? ? = ? ? ? = ? ? ? = ? + ? ? = ? + ? ? = ? ? 3/22/2025 Extracting functions from BRs

  33. Maximum flexibility ?? 00 01 10 11 ?? ?? ?? Less flexibility Functions 3/22/2025 Extracting functions from BRs

  34. ?? 00 01 10 11 ?? ?? 00 01 10 11 ?? 10 00 | 11 1 1 | 1 ?? 00 01 10 11 ?? 10 00 11 01 Optimum-cost function 3/22/2025 Extracting functions from BRs

  35. ?? ?? Number of inputs Number of outputs O 22?+? Functions Size of the semi-lattice Extracting functions from BRs 3/22/2025

  36. Incompletely specified functions Shortcut: use ISF minimizers ! (ESPRESSO, Minato-Morreale, Scherzo) Extracting functions from BRs 3/22/2025

  37. x y a b 10 00 01 10 11 00 | 11 1 01 |10 10 00 1 10 11 1 01 |10 01 |10 10 00 11 10 00 01 10 11 01 10 11 11 01 |10 01 |10 01 |10 01 |10 10 00 01 01 10 00 01 10 10 00 11 01 10 00 11 10 10 11 01 01 10 11 01 10 10 11 11 01 10 11 11 10 ? + ? ? ? ? + ? ? + ? ? = ? ? ? = ? ? ? ? ? + ? ? ? 1 ? ? ? ? ? + ? ? ? 3/22/2025 Extracting functions from BRs

  38. The recursive approach (DAC 2004, BREL)

  39. Projections ( abs) a b x 1 00 01 10 11 x a bx y a b x y 10 1 00 01 10 11 10 00 01 10 11 00 | 11 1 01 |10 R merge a b y 0 1 00 01 10 11 y R R is an incompletely specified function, but has more flexibility than R (R R ) 3/22/2025 Extracting functions from BRs 39

  40. ISF projection BR 3/22/2025 Extracting functions from BRs 40

  41. ISF ISF minimizer done ! 3/22/2025 Extracting functions from BRs 41

  42. ISF ISF minimizer incompatible ! 3/22/2025 Extracting functions from BRs 42

  43. The recursive paradigm a b x y x y x y x y 10 10 1 10 10 11 11 10 00 01 10 11 00 | 11 1 01 |10 00 | 11 1 01 |10 projection minimization compatible? ISF ? = 1 ? = ? with more flexibility 3/22/2025 Extracting functions from BRs 43

  44. The recursive paradigm a b x y x y x y x y 10 10 1 10 10 11 11 10 00 01 10 11 00 | 11 1 01 |10 00 | 11 1 01 |10 projection minimization compatible? ISF ? = 1 ? = ? with more flexibility 3/22/2025 Extracting functions from BRs 44

  45. ISF ISF minimizer incompatible ! 3/22/2025 Extracting functions from BRs 45

  46. The recursive paradigm pick one conflict a b x y x y x y x y 10 10 1 10 10 11 11 10 00 01 10 11 00 | 11 1 01 |10 00 | 11 1 01 |10 projection minimization compatible? ISF ? = 1 ? = ? with more flexibility 3/22/2025 Extracting functions from BRs 46

  47. The recursive paradigm x y 10 00 1 a b x y 01 |10 10 00 01 10 11 00 | 11 1 01 |10 split x y 10 11 1 01 |10 3/22/2025 Extracting functions from BRs 47

  48. ISF ISF minimizer incompatible ! 3/22/2025 Extracting functions from BRs 48

  49. BR1 BR2 3/22/2025 Extracting functions from BRs 49

  50. The recursive paradigm x y x y x y x y 10 00 1 10 10 00 1 10 00 11 01 00 | 11 1 01 |10 a b x y 01 |10 10 00 01 10 11 00 | 11 1 01 |10 ISF split x y 10 11 1 01 |10 3/22/2025 Extracting functions from BRs 50

Related


No related presentations.

More Related Content