An Optimum Algorithm for Compacting Error Traces for Efficient Design Error Debugging

Diagnosing counterexamples with error traces has acted as one of the most critical steps in functional verification. Unfortunately, error traces are normally very lengthy such that designers need to spend considerable effort to understand them. To alleviate the designers' burden for debugging,...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 2006-11, Vol.55 (11), p.1356-1366
Main Authors: Yen, Chia-Chih, Jou, Jing-Yang
Format: Article
Language:English
Subjects:
Algorithms
Compacting
Debugging
diagnosis
error checking
Errors
Handles
Mathematical models
Optimization
satisfiability
Searching
simulation
Verification
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Diagnosing counterexamples with error traces has acted as one of the most critical steps in functional verification. Unfortunately, error traces are normally very lengthy such that designers need to spend considerable effort to understand them. To alleviate the designers' burden for debugging, we present a SAT-based algorithm for reducing the lengths of error traces. The algorithm performs the paradigm of the binary search algorithm to halve the search space recursively. Furthermore, it applies a novel theorem to guarantee gaining the shortest lengths for the error traces. Based on the optimum algorithm, we develop two robust heuristics to handle real designs. Experimental results demonstrate that our approaches greatly surpass previous work and, indeed, have promising solutions
ISSN:0018-9340
1557-9956
DOI:10.1109/TC.2006.174