Algorithm Overview

OpenTestability implements multiple algorithms for testability analysis and reconvergent fanout detection.

Overview

COP Algorithm (NEW in v1.0.1)

Controllability Observability Program

Overview

COP calculates probability-based testability metrics:

• C1: Probability of signal being 1 (controllability)
• Obs: Probability of observing signal at output (observability)
• COP: Combined metric (C1 × Obs) - lower values indicate easier testing

Algorithm Steps

1. Initialize Primary Inputs
   • C1 = 0.5 (equal probability of 0 or 1)
   • Obs calculated backward from outputs
2. Forward Pass (Controllability)
   • Calculate output probability from input probabilities
   • Use probabilistic gate models
3. Backward Pass (Observability)
   • Start from primary outputs (Obs = 1.0)
   • Propagate observability backward
4. Reconvergence Adjustment (NEW)
   • Detect reconvergent fanout points
   • Calculate correlation coefficients
   • Apply Bayesian correlation adjustments

Probabilistic Gate Models

AND Gate

P(out=1) = P(a=1) × P(b=1)

OR Gate

P(out=1) = P(a=1) + P(b=1) - P(a=1)×P(b=1)

NOT Gate

P(out=1) = 1 - P(in=1)

XOR Gate

P(out=1) = P(a=1)×(1-P(b=1)) + (1-P(a=1))×P(b=1)

Reconvergence-Aware Observability

At reconvergent points, COP adjusts observability using correlation:

Obs_adjusted = Obs_base × (1 - correlation_coefficient)

Where correlation is calculated from:

• Shared signal count in reconvergent paths
• Path lengths
• Fanout cone overlap

Example

Circuit: a AND b → n1, n1 INV → z

Controllability:
  a: C1=0.5 (primary input)
  b: C1=0.5 (primary input)
  n1: C1=0.5×0.5=0.25
  z: C1=1-0.25=0.75

Observability (backward from z):
  z: Obs=1.0 (primary output)
  n1: Obs=1.0
  a: Obs=1.0×0.5=0.5 (b's value affects observation)
  b: Obs=1.0×0.5=0.5

COP:
  a: COP=0.5×0.5=0.25
  b: COP=0.5×0.5=0.25
  n1: COP=0.25×1.0=0.25
  z: COP=0.75×1.0=0.75

Parallel Computation

For circuits >100,000 gates, COP automatically:

• Identifies reconvergent regions
• Processes regions concurrently
• Achieves 3-4x speedup

SCOAP Algorithm

Sandia Controllability Observability Analysis Program

Overview

SCOAP calculates three metrics for each signal:

• CC0: Combinational Controllability to 0
• CC1: Combinational Controllability to 1
• CO: Combinational Observability

Lower values indicate better testability.

Algorithm Steps

1. Initialize Primary Inputs
   • CC0 = CC1 = 1 (directly controllable)
   • CO = calculated backward from outputs
2. Forward Pass (Controllability)
   • For each gate, calculate output controllability from input controllability
   • Use gate-specific transfer functions
3. Backward Pass (Observability)
   • Start from primary outputs (CO = 0)
   • Propagate observability backward through gates

Gate Transfer Functions

AND Gate

CC0(out) = min(CC0(inputs)) + 1
CC1(out) = sum(CC1(inputs)) + 1

OR Gate

CC0(out) = sum(CC0(inputs)) + 1
CC1(out) = min(CC1(inputs)) + 1

NAND Gate

CC0(out) = sum(CC1(inputs)) + 1
CC1(out) = min(CC0(inputs)) + 1

NOT/INV Gate

CC0(out) = CC1(in) + 1
CC1(out) = CC0(in) + 1

XOR Gate

CC0(out) = min(CC0(a)+CC0(b), CC1(a)+CC1(b)) + 1
CC1(out) = min(CC0(a)+CC1(b), CC1(a)+CC0(b)) + 1

Observability Calculation

For each input of a gate:

CO(input) = CO(output) + 1 + Σ(CC1 of other inputs)

Example

Circuit: a AND b → n1, n1 INV → z

Controllability:
  a: CC0=1, CC1=1 (primary input)
  b: CC0=1, CC1=1 (primary input)
  n1: CC0=min(1,1)+1=2, CC1=(1+1)+1=3
  z: CC0=3+1=4, CC1=2+1=3

Observability (backward from z):
  z: CO=0 (primary output)
  n1: CO=0+1=1
  a: CO=1+1+CC1(b)=1+1+1=3
  b: CO=1+1+CC1(a)=1+1+1=3

Applications

• Test Generation: Identify hard-to-test signals
• Design-for-Test: Guide scan chain insertion
• Fault Coverage: Predict testability before manufacturing

Reconvergent Fanout Detection

Reconvergent fanout occurs when a signal splits and reconverges at a common point.

Why It Matters

1. Test Pattern Generation: Affects ATPG complexity
2. Delay Analysis: Critical for timing verification
3. Power Analysis: Switching activity correlation
4. Fault Coverage: Impacts fault detection

Example

     a
    / \
   /   \
  b     c
   \   /
    \ /
     d

Signal a fans out to gates producing b and c, which reconverge at gate d.

Basic Reconvergence Algorithm

Algorithm

for each node in circuit:
    fanout_targets = get_fanout_nodes(node)
    if len(fanout_targets) > 1:
        # Check for reconvergence
        for i, target1 in enumerate(fanout_targets):
            for target2 in fanout_targets[i+1:]:
                common = find_common_successors(target1, target2)
                if common:
                    record_reconvergence(node, common[0])

Complexity

• Time: O(n² × m) where n = nodes, m = avg fanout
• Space: O(n)

Characteristics

• ✓ Simple and fast
• ✓ Detects immediate reconvergence
• ✗ May miss complex patterns
• ✗ No depth information

Simple Reconvergence Algorithm

Enhancements Over Basic

1. Path Tracking: Records all paths between fanout and reconvergence
2. Depth Metrics: Calculates reconvergence distance
3. Fanout Degree: Tracks number of fanout branches

Algorithm

for each high_fanout_node:
    paths = {}
    for each fanout_branch:
        path = trace_forward(branch)
        paths[branch] = path
    
    # Find intersection points
    for i, path1 in enumerate(paths):
        for path2 in paths[i+1:]:
            intersection = set(path1) & set(path2)
            if intersection:
                first_common = find_closest(intersection)
                record_with_metrics(node, first_common, paths)

Additional Metrics

• Reconvergence Depth: Number of levels between fanout and reconvergence
• Path Count: Number of distinct paths
• Intermediate Nodes: Nodes between fanout and reconvergence

Complexity

• Time: O(n² log n)
• Space: O(n × k) where k = avg path length

Advanced Reconvergence Algorithm

Advanced Features

1. Multi-Level Detection: Finds nested reconvergence patterns
2. Path Enumeration: Enumerates all paths, not just shortest
3. Structural Metrics: Comprehensive circuit statistics
4. Reconvergence Trees: Hierarchical reconvergence structure

Algorithm

def advanced_reconvergence_analysis(dag):
    results = []
    
    # Phase 1: Build fanout tree
    fanout_trees = build_fanout_trees(dag)
    
    # Phase 2: Detect all reconvergence points
    for tree in fanout_trees:
        reconverge_points = find_all_reconvergence_points(tree)
        
        # Phase 3: Enumerate paths
        for point in reconverge_points:
            all_paths = enumerate_all_paths(tree.root, point)
            
            # Phase 4: Calculate metrics
            metrics = {
                'depth': calculate_depth(all_paths),
                'complexity': calculate_complexity(all_paths),
                'criticality': assess_criticality(all_paths, scoap_data)
            }
            
            results.append({
                'fanout': tree.root,
                'reconverge': point,
                'paths': all_paths,
                'metrics': metrics
            })
    
    return results

Detected Patterns

Simple Reconvergence

  A
 / \
B   C
 \ /
  D

Nested Reconvergence

    A
   / \
  B   C
 / \ / \
D   E   F
 \  |  /
   \ | /
     G

Multi-Level Reconvergence

     A
    /|\
   B C D
   |X X|
   E F G
    \|/
     H

Complexity

• Time: O(n³) worst case, O(n² log n) average
• Space: O(n² ) for path storage

Output Metrics

{
  "fanout_point": "n5",
  "reconverge_point": "n20",
  "path_count": 4,
  "min_depth": 3,
  "max_depth": 7,
  "avg_depth": 4.5,
  "intermediate_nodes": 12,
  "complexity_score": 8.5,
  "all_paths": [...]
}

Algorithm Comparison

Use Case Recommendations

Performance Comparison (v1.0.1)

Test on various circuit sizes:

Note: Parallel mode automatically activates for circuits >100,000 gates.

Sequential Circuit Handling

All algorithms handle sequential circuits using the time-frame expansion approach:

Concept

1. Break at Flip-Flops: Treat each clock cycle as a separate combinational slice
2. Pseudo-I/O:
   • Flip-flop Q outputs → pseudo primary inputs
   • Flip-flop D inputs → pseudo primary outputs
3. Clock Ignored: Clock signal excluded from data path analysis

Example

// Sequential circuit with feedback
DFFRX1 reg1(.D(n5), .CK(clk), .Q(state));
AND2X1 g1(.A(state), .B(input), .Y(n5));

Analysis Approach:

• State is treated as a primary input (for current time frame)
• n5 is treated as a primary output (determines next state)
• Result: Acyclic graph suitable for analysis

This is equivalent to:

• ATPG scan chain approach
• Static timing analysis
• Standard EDA tool methodology

Future Enhancements

Recent Additions (v1.0.1)

1. Reconvergence Integration - Implemented
   • Automatic reconvergence detection in COP/SCOAP
   • Bayesian correlation adjustments
   • Three algorithm options with auto-selection
2. Parallel Processing - Implemented
   • Thread-based parallel computation
   • Automatic activation for circuits >100k gates
   • 3-4x speedup on large designs
3. Verilog Auto-Pipeline - Implemented
   • One-command analysis from Verilog files
   • Automatic parsing, DAG creation, and analysis
   • Simplified workflow

Planned Improvements

1. Machine Learning Integration
   • Predict hard-to-test patterns
   • Optimize based on historical data
2. *COP (Combinational Observability Probability)

• Parker, K.P., McCluskey, E.J., “Probabilistic Treatment of General Combinational Networks,” IEEE Transactions on Computers, 1975.
• Correlation-aware extensions in OpenTestability v1.0.1

SCOAP

• L.H. Goldstein, “Controllability/Observability Analysis of Digital Circuits,” IEEE Transactions on Circuits and Systems, 1979.
• Original SCOAP paper from Sandia National Laboratories

Reconvergent Fanout

• P. Goel, “An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits,” IEEE Trans. on Computers, 1981.
• S.B. Akers et al., “On the Role of Independent Fault Sets in the Generation of Minimal Test Sets,” Proc. ITC, 1987.
• Xu & Edirisuriya, “A New Way of Detecting Reconvergent Fanout Branch Pairs in Logic Circuits,” 2004.

General Test Generation

• M. Abramovici, M.A. Breuer, A.D. Friedman, “Digital Systems Testing and Testable Design,” Computer Science Press, 1990.
• N.K. Jha, S. Gupta, “Testing of Digital Systems,” Cambridge University Press, 2003.

Additional Resources

• Reconvergence Integration Guide
• Reconvergence Quickstart
• Command Reference
• Getting Started
• Examples
• API Documentation
• GitHub Repository
• Report Issues
• Discussions
• Contributing

• Changelog

• P. Goel, “An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits,” IEEE Trans. on Computers, 1981.
• S.B. Akers et al., “On the Role of Independent Fault Sets in the Generation of Minimal Test Sets,” Proc. ITC, 1987.

General Test Generation

• M. Abramovici, M.A. Breuer, A.D. Friedman, “Digital Systems Testing and Testable Design,” Computer Science Press, 1990.
• N.K. Jha, S. Gupta, “Testing of Digital Systems,” Cambridge University Press, 2003.

Further Reading

• See ALGORITHM_GUIDE.md for implementation details
• Check API documentation for function references
• Review examples for practical applications