Algorithms

This section covers the various algorithms available in aigverse for working with And-Inverter Graphs (AIGs) and other logic representations. These algorithms enable simulation, optimization, and verification of logic networks.

Simulation

Simulation algorithms allow you to evaluate the outputs of a logic network for all possible input combinations, effectively generating truth tables for the network’s outputs and internal nodes.

Functional Simulation

For simulating AIGs with truth tables, the simulate() and {py:func} ~aigverse.algorithms.simulate_nodes functions allow you to obtain truth tables for outputs and internal nodes of an AIG.

 1from aigverse.networks import Aig
 2from aigverse.algorithms import simulate, simulate_nodes
 3
 4# Create a sample AIG
 5aig = Aig()
 6a = aig.create_pi()
 7b = aig.create_pi()
 8f_and = aig.create_and(a, b)
 9f_or = aig.create_or(a, b)
10aig.create_po(f_and)
11aig.create_po(f_or)
12
13# Simulate the outputs
14output_tts = simulate(aig)
15
16# Print the truth tables
17print("Truth tables of outputs:")
18for i, tt in enumerate(output_tts):
19    print(f"  Output {i}: {tt.to_binary()}")
20
21# Simulate all nodes
22node_tts = simulate_nodes(aig)
23
24# Print the truth table of each node
25print("\nTruth tables of nodes:")
26for node, tt in node_tts.items():
27    print(f"  Node {node}: {tt.to_binary()}")

Truth tables of outputs:
  Output 0: 1000
  Output 1: 1110

Truth tables of nodes:
  Node 4: 0001
  Node 3: 1000
  Node 2: 1100
  Node 1: 1010
  Node 0: 0000

Optimization

AIG optimization aims to reduce the number of AND gates and inverters in a circuit while maintaining its logical functionality. Different optimization techniques target various aspects of the AIG structure.

Basic Optimization Workflow

The typical optimization workflow involves:

  1. Creating or loading an AIG

  2. Applying one or more optimization algorithms

  3. Verifying correctness through equivalence checking

1from aigverse.io import read_aiger_into_aig
2
3# Load the i10 benchmark circuit - a real-world example
4aig = read_aiger_into_aig("examples/i10.aig")
5
6# Print statistics about the loaded circuit
7print(f"i10 benchmark:")
8print(f"  I/O: {aig.num_pis}/{aig.num_pos}")
9print(f"  AND gates: {aig.num_gates}")

i10 benchmark:
  I/O: 257/224
  AND gates: 2675

Resubstitution

Resubstitution identifies portions of logic that can be expressed using existing signals in the network. This technique is particularly effective at identifying and eliminating redundant logic.

 1from aigverse.algorithms import aig_resubstitution
 2
 3# Clone the AIG for comparison
 4aig_resub = aig.clone()
 5
 6# Apply resubstitution
 7aig_resub = aig_resubstitution(aig_resub, window_size=12)
 8
 9print(f"Original AND gates: {aig.num_gates}")
10print(f"After resubstitution: {aig_resub.num_gates} AND gates")
11print(f"Reduction: {aig.num_gates - aig_resub.num_gates} gates ({(aig.num_gates - aig_resub.num_gates) / aig.num_gates * 100:.2f}%)")

Original AND gates: 2675
After resubstitution: 2173 AND gates
Reduction: 502 gates (18.77%)

Sum-of-Products Refactoring

SOP (Sum of Products) refactoring collapses parts of the AIG into truth tables, then re-synthesizes those portions using Sum-of-Products representations. This can find more efficient implementations for complex logic functions.

 1from aigverse.algorithms import sop_refactoring
 2
 3# Clone the AIG for comparison
 4aig_refactor = aig.clone()
 5
 6# Apply SOP refactoring
 7aig_refactor = sop_refactoring(aig_refactor, use_reconvergence_cut=True)
 8
 9print(f"Original AND gates: {aig.num_gates}")
10print(f"After SOP refactoring: {aig_refactor.num_gates} AND gates")
11print(f"Reduction: {aig.num_gates - aig_refactor.num_gates} gates ({(aig.num_gates - aig_refactor.num_gates) / aig.num_gates * 100:.2f}%)")

Original AND gates: 2675
After SOP refactoring: 2239 AND gates
Reduction: 436 gates (16.30%)

Cut Rewriting

Cut rewriting identifies small subgraphs (cuts) in the AIG and replaces them with pre-computed optimal implementations from a library. This technique leverages NPN-equivalence classes to find the best possible implementation for each cut.

 1from aigverse.algorithms import aig_cut_rewriting
 2
 3# Clone the AIG for comparison
 4aig_rewrite = aig.clone()
 5
 6# Apply cut rewriting
 7aig_rewrite = aig_cut_rewriting(aig_rewrite, cut_size=4)
 8
 9print(f"Original AND gates: {aig.num_gates}")
10print(f"After cut rewriting: {aig_rewrite.num_gates} AND gates")
11print(f"Reduction: {aig.num_gates - aig_rewrite.num_gates} gates ({(aig.num_gates - aig_rewrite.num_gates) / aig.num_gates * 100:.2f}%)")

Original AND gates: 2675
After cut rewriting: 2200 AND gates
Reduction: 475 gates (17.76%)

Balancing

Balancing performs (E)SOP factoring to minimize the number of levels in the AIG.

 1from aigverse.algorithms import balancing
 2from aigverse.networks import DepthAig
 3
 4# Clone the AIG for comparison
 5aig_balance = aig.clone()
 6
 7# Apply balancing
 8aig_balance = balancing(aig_balance, rebalance_function="sop")
 9
10# Compute depth
11original_depth = DepthAig(aig).num_levels
12balanced_depth = DepthAig(aig_balance).num_levels
13
14print(f"Original depth: {original_depth} levels")
15print(f"After balancing: {balanced_depth} levels")
16print(f"Reduction in depth: {original_depth - balanced_depth} levels ({(original_depth - balanced_depth) / original_depth * 100:.2f}%)")

Original depth: 50 levels
After balancing: 32 levels
Reduction in depth: 18 levels (36.00%)

Combining Optimization Techniques

For best results, optimization techniques are typically applied in combination, often in multiple passes. The order of application can significantly impact the final result.

 1# Apply optimization techniques in sequence
 2aig_opt = aig.clone()
 3
 4# First pass
 5aig_opt = aig_resubstitution(aig_opt)
 6aig_opt = sop_refactoring(aig_opt)
 7aig_opt = aig_cut_rewriting(aig_opt)
 8
 9# Second pass
10aig_opt = aig_resubstitution(aig_opt)
11aig_opt = sop_refactoring(aig_opt)
12
13print(f"\nTotal optimization results:")
14print(f"- Original: {aig.num_gates} AND gates")
15print(f"- Optimized: {aig_opt.num_gates} AND gates")
16print(f"- Total reduction: {aig.num_gates - aig_opt.num_gates} gates ({(aig.num_gates - aig_opt.num_gates) / aig.num_gates * 100:.2f}%)")

Total optimization results:
- Original: 2675 AND gates
- Optimized: 1950 AND gates
- Total reduction: 725 gates (27.10%)

Some algorithms offer the inplace=True keyword argument for performance-sensitive pipelines of chained optimization. Calling functions such as aig_resubstitution() and sop_refactoring() with inplace=True mutates the passed network and returns None:

1from aigverse.algorithms import cleanup_dangling
2
3aig_fast = aig.clone()
4aig_resubstitution(aig_fast, inplace=True)
5sop_refactoring(aig_fast, inplace=True)
6
7# Explicit cleanup step after in-place chaining
8aig_fast = cleanup_dangling(aig_fast)

Note

When choosing this route, users are responsible to call cleanup_dangling() to obtain a structurally valid AIG.

Equivalence Checking

Equivalence checking algorithms verify that two logic networks implement the same function, which is especially important after performing optimizations.

1from aigverse.algorithms import equivalence_checking
2
3# Verify that our optimized circuit from the previous section maintains functional equivalence
4are_equivalent = equivalence_checking(aig, aig_opt)
5print(f"\nOriginal and optimized benchmark circuits are equivalent: {are_equivalent}")
6print(f"This confirms our optimization preserved the circuit's functionality while reducing")
7print(f"the gate count from {aig.num_gates} to {aig_opt.num_gates} AND gates.")

Original and optimized benchmark circuits are equivalent: True
This confirms our optimization preserved the circuit's functionality while reducing
the gate count from 2086 to 1950 AND gates.