A‑QED2: Scaling Verification via Decomposition

Verifying modern hardware accelerators is hard. Quick Error Detection (QED) helps, but it does not scale well to large designs. A recent paper offers a practical improvement.

Introducing A-QED2: The Next Evolution in Verification

The paper is “Scaling Up Hardware Accelerator Verification using A-QED with Functional Decomposition” (FMCAD 2021). It extends the QED methodology. Traditional QED looks for bugs by checking whether behavior stays consistent. It can struggle when the hardware block is too large. A-QED2 is designed to fix that.

QED relies on a simple rule. If you apply the same input twice, you should get the same output twice. This is Functional Consistency (FC). FC can find many bugs even without a full specification. It is like pressing 2+2 on a calculator several times. If the answer changes, something is wrong.

Targeting Loosely Coupled Accelerators (LCAs)

A-QED2 targets loosely coupled accelerators (LCAs). An LCA is not part of the CPU core. It is a specialized unit connected over a bus. It runs heavy computations on its own. Examples include:

• AES encryption/decryption units
• Speech and audio compression engines
• Image filters (e.g., color to grayscale)
• AI inference units for neural-network predictions

Many LCAs are “non-interfering.” That means the output for an input does not depend on past requests. This makes FC checks effective.

The Power of Decomposition

A-QED2 uses functional decomposition. It does not verify a huge accelerator as one block. Instead, it breaks the design into smaller sub-functions. Then it checks FC on each part.

This change improves runtime a lot. In one study of 17 accelerators (about 300K–600K gates), full FC finished only 2 designs within 12 hours. With decomposition, 10 designs finished in minutes. The goal is not just speed. The goal is to make deep verification feasible.

Beyond Consistency: Proving Correctness

FC alone does not prove correctness. A broken accelerator that always outputs zero is still consistent. So A-QED2 adds Single-Action Correctness (SAC).

SAC needs a reference or spec. It checks that for each supported operation, at least one case produces the correct output. If you prove FC (stable behavior) and SAC (can be correct), you can conclude full functional correctness for all input sequences. The paper also checks Response Bound (RB). RB ensures results arrive within a time limit. It can catch deadlocks and latency bugs.

Real-World Validation and Impact

The method was tested on 109 buggy versions of 16 accelerators. The set ranged from small blocks to very large designs (over 200M gates), including NVIDIA’s NVDLA. Conventional methods often did not finish. A-QED2 verified decomposed parts in minutes. It found all bugs that simulation found. It also reduced total effort by about 5× on average (up to 9× on the largest designs).

In bug-hunting tests, 10 completed cases contained 90 bugs. FC alone found 49 of them. It did this without knowing the intended function. This shows FC is a strong complementary tool.

Expert Perspectives on the Innovation

Paul Cunningham (Cadence Verification) notes that pushing FC proofs into decomposed sub-functions greatly improves runtime and scalability. They also highlights that the formal link from FC + SAC to full correctness is a meaningful contribution.

Raúl Camposano (former Synopsys CTO) traces self-consistency checking back to the 1990s. They argue A-QED2 makes the idea practical for today’s common loosely coupled accelerators. They call FC + SAC a complete correctness criterion for this class of hardware.

Conclusion: A Scalable Path Forward

Hardware accelerators keep growing in number and complexity. Verification must scale with them. A-QED2 offers a scalable approach through decomposition. It enables faster and more thorough checks of consistency and correctness. This can improve confidence in next-generation chips.