Title
Algorithms for compacting error traces
Abstract
In this paper, we present a concept of compacting the error traces generated by pseudo-random/random simulations. The new shorter error trace not only decreases the time of user's debugging process but also reduces the simulation time required to verify the bug fixes. Two algorithms CET1 and CET2 are presented to perform the task of compacting the error trace. Both algorithms first use an efficient approach to eliminate the redundant states to generate the unique states of the error trace. Then, CET1 build the connected graph of these unique states by computing the reachable states by one cycle for each unique state, and then apply Dijkstra's shortest path algorithm to find out the shortest error trace in the connected graph. Compared with CET1, CET2 computes the reachable states by one cycle for those unique states, when they are needed in Dijkstra's shortest path algorithm to find the shortest error trace. After finding the shorter trace, the corresponding input/output test vectors are generated. The experimental results show that both algorithms can reduce the length of error traces dramatically for most cases using reasonable memory. For cases required longer CPU time to find the shortest trace, CET2 is up to 37 times faster than CET1.
Year
DOI
Venue
2003
10.1145/1119772.1119792
Asia and South Pacific Design Automation Conference
Keywords
Field
DocType
compacting error trace,shortest path algorithm,error trace,shorter trace,new shorter error trace,reachable state,connected graph,shortest trace,unique state,algorithms cet1,shortest error trace,error detection,integrated circuit design,logic design,input output,logic simulation
Logic synthesis,Computer science,CPU time,Algorithm,Electronic engineering,Error detection and correction,Real-time computing,Logic simulation,Integrated circuit design,Connectivity,Dijkstra's algorithm,Debugging
Conference
ISBN
Citations 
PageRank 
0-7803-7660-9
9
0.67
References 
Authors
9
2
Name
Order
Citations
PageRank
Yirng-an Chen130423.80
Fang-Sung Chen290.67