Anti-Symmetry and Logic Simulation

This review discusses anti-symmetry and logic simulation by Ko-Lung Yuan, covering topics such as classical symmetry, symmetry detection, experimental results, and conclusions.

• Symmetry
• Logic Simulation
• Review
• Ko-Lung Yuan
• Anti-Symmetry

frontera_s Follow

Uploaded on Feb 16, 2025 | 0 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.

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.

Presentation Transcript

1. Anti-Symmetry and Logic Simulation Reviewer Ko-Lung Yuan

2. Outline Abstract Introduction Classical Symmetry Anti-Symmetry Symmetry Detection Experimental Results Conclusion Comment

3. Abstract

4. Simulation Na ve simulation has state explosion problem, but we can use symmetry to reduce the possible state Symmetry detection is an important progress This paper want to give a simulation method based on symmetry detection with anti-symmetry detection joined

5. Logic Simulation Flow I think it might be Symmetry Detection State-Space Transformation Circuit Gate State Machine Boolean Function Function Correction Simulation

6. Introduction Detecting symmetries has proven to be useful in many areas of EDA Permutation-based symmetry detection algorithm Capture the idea of rearranging things

7. Symmetry Type Total symmetry Ex. ? = ???? Partial symmetry Ex. ? = ??? + ? Weak symmetry Other permutation-based symmetries This paper just focus on total symmetry and partial symmetry

8. Symmetry Detection Examining pairs of variables Symmetric variable pair If they can be exchanged without altering the output of the function Symmetric variable pairs are transitive Totally symmetric Every pair of input variables is a symmetric pair Partially symmetric A function is partially symmetric in the variables ?1, ,?? if (??,??) is a symmetric pair for all ? and ?, 1 ? < ? ?

9. Symmetric Pairs Detection Using cofactors to do detection The cofactors of f with respect to ?1 are the functions ?0? ? and ?1? ? They are computed by setting the variable ?1to 0 and then to 1 The procedure for computing a cofactor depends on the representation of the function

10. Cofactor Cofactors can be computed with respect to a single variable or a set of variables It is common to compute cofactors with respect to pairs of variables There are four such cofactors ?00 ?01 ?10 ?11 Different relations between these cofactors can be use to define different types of symmetry

11. Classical Symmetry There are six possible relations in these four cofactors, each of which represents a certain type of symmetry Relation Symmetry Type ?01= ?10 ?00= ?11 ?01= ?11 ?10= ?11 ?10= ?00 ?01= ?00 Ordinary Multi-Phase Single-Variable A Single-Variable B Multi-Phase Single-Variable A Multi-Phase Single-Variable B

12. Symmetry Correction The only relation that truly represents symmetry is ?01= ?10, ordinary symmetry The other relations can be corrected to become symmetric

13. Symmetric Detection The detection algorithm tests only for ordinary symmetry The other five relations are detected by transforming the state space of the function, and then testing for ordinary symmetry

14. Multi-Phase Symmetry ?00= ?11 It is possible to treat the multi-phase relation as ordinary symmetry after performing a state-space transformation and add a NOT gate to one of the inputs State space transformation (symmetry)

15. Single-Variable Symmetry ?01= ?11?10= ?11 Conjugate symmetry It is possible to treat conjugate symmetries as if they were ordinary symmetries using a stat-space transformation and a collection of XOR gates on the function inputs State space transformation (symmetry) ?01= ?11 XOR

16. Multi-Phase Single-Variable Symmetry These types of symmetry can be handled by combining the techniques for multi-phase and conjugate symmetry State space transformation (symmetry) ?10= ?00 XOR

17. State Machine The result of symmetry detection is a multi-dimensional state machine which represents the state of Boolean function. Each dimension of the state machine represents a cluster of symmetric variables Non-clustered input variable The dimension will have two states representing input values of zero and one Cluster of n variables The dimension will have n+1 states with the state representing the number of ones in the inputs

18. State Machine (cont.) Example of state machine {B,C,D} A 0,0 1,0 2,0 3,0 0,1 1,1 2,1 3,1

19. Anti-Symmetry ?01= ?10can be written ?01 ?10= 0 If we reformulate our six relations and replace the constant zero with the constant one, we obtain the six anti-symmetry relations Relation Symmetry Type ?01 ?10= 1 ?01 ?11= 1 ?01 ?11= 1 ?10 ?11= 1 ?10 ?00= 1 ?01 ?00= 1 Ordinary Multi-Phase Single-Variable A Single-Variable B Multi-Phase Single-Variable A Multi-Phase Single-Variable B

20. Symmetry Correction Anti-symmetries can be transformed into ordinary symmetries using state-space transformations These transformations are easier to visualize if we place the four cofactors into a hyper-linear structure There are several different state-space transformations that will transform anti-symmetry into an ordinary symmetry

21. Simple Method Complement one of the cofactors ?01?? ?10 If ?01 ?10= 1 is true, then ?01 ?10 ?10= 0 and ?01 = 0 are also true ?00 ?01 ?00 ?01 ?00 ?01 ?10 ?11 ?10 ?11 ?10 ?11

22. Simple Method (cont.) An ordinary anti-symmetry is found between the variables are A and B and that ?01has been complemented Trans. Func. A B

23. Simple Method (cont.) A NOT gate and an AND gate required for every anti- symmetric pair (for detection) but just one XOR gate needed (for correction) The proliferation of gates may negate the benefit of detecting the anti-symmetry

24. Over-Kill Method Instead of just complementing ?01 ( or ?10) we also complement ?11 This method eliminates the AND gates and NOT gates. Regardless of how many anti-symmetric variable pairs are detected for a function, only a single XOR gate is required on the output. This XOR gate must have one input for each detected anti-symmetric pair

25. Over-Kill Method (cont.) Sophisticated Corrective Actions ?00 ?01 ?00 ?01 ?00 ?01 ?10 ?11 ?10 ?11 ?10 ?11

26. Over-Kill Method (cont.) Simple Corrective Function Trans. Func. A B

27. Symmetry Detection Problems There are several problems in determining the inputs of the XOR gate First, when combining anti-symmetry with conjugate symmetry, adding inputs to the correcting XOR becomes more complicated Second, we need to determine what should happen when a variable is added twice to the correcting XOR Third, we need to determine how to detect anti- symmetry with respect to clustered variables

28. Ordinary Symmetry Ordinary symmetry can be detected by examining cofactors along the anti-diagonals If there are more than two dimensions, the diagonal tests must be repeated for each of the planes containing the two variables There is no required relationship between separate diagonals or between separate planes

29. Ordinary Symmetry (conj.) Example {B,C,D} A 0,0 1,0 2,0 3,0 0,1 1,1 2,1 3,1

30. Multi-Phase Symmetry M.P. can be detected by reversing the structure along one dimension and then testing for ordinary symmetry {B,C,D} A 0,1 1,1 2,1 3,1 0,0 1,0 2,0 3,0

31. Conjugate Symmetry Conj. can be detected by reversing the odd numbered rows (starting with 0 at the top) or the odd numbered columns (starting with 0 at the left) and then testing for ordinary symmetry

32. Conjugate Multi-Phase Symmetry C.M.P. can be detected by reversing the even numbered rows and columns In practice this is accomplished by reversing the entire structure and then reversing the odd rows or columns

33. Anti-Symmetry When an anti-symmetry exists between any two variables in two different clustered pairs, then an anti-symmetry exists between every pair of variables in the two of clustered variables A function must alternate with its complement along each back-diagonal To convert the anti-symmetry into an ordinary symmetry, we invert the functions in the odd- numbered rows or the odd-numbered columns

34. Clustered-Variable State Machine Example Ordinary Symmetry (a,b) Anti-Symmetry (a,b) (c,d) K L F (c,d) K L F L F G L F G F G H F G H

35. Clustered-Variable State Machine (cont.) Example Anti-Symmetry State space transformation (a,b) (a,b) (c,d) K L F (c,d) K L F L F G L F G F G H F G H

36. A clustered Corrective Function Example Trans. Func. A B When A equals one or B equals one Correct the output

37. XOR Gate Inputs Create a list of the input variables that must be added to the inputs of the XOR gate When new anti-symmetries are detected, new input variables are added to the list When we add an input to the list, we check to see whether it is currently on the list. If so, then we remove it instead of adding it

38. Experimental Results ISCAS 85 benchmarks-they are specified at the gate level rather than at the Boolean function level They exhibit a wide variety of symmetries of all types Each simulation was performed on a dedicated 2.06 Ghz Xeon processor with 2 GB of 233 Mhz memory The simulation rate is 500,000 input vectors/sec All of the simulations are compiled simulations Symmetry detection takes less than a second for each circuit in simulation

39. Exp1 Determine the number of anti-symmetries that appear in these circuits This experiment verifies that anti-symmetries are indeed prevalent enough to be worth pursuing

40. Exp2 Determine the number of classical symmetries in each of the four categories

41. Ex3 Symmetry masking phenomenon

42. Ex4 Simulation running time (not include symmetry detection time)

43. Conclusion Even though detecting anti-symmetries is somewhat more difficult than detecting classical symmetries, the detection can be done quickly, virtually always with beneficial results There are other types of relations that may permit detection of even more symmetries

44. Comment-Advantage Stimulate my thoughts of symmetries

45. Comment-Disadvantage The key word simulation in the title does not be well described Not well organized, it is hard to follow the architecture of this paper No preliminaries and any definitions No enough background and explanation for readers Some Several non-clear description and denotation Many stupid mistakes Non-clear picture Experimental results are not effective