EECS 298-11: Special CAD Seminar
Wednesday, Feb. 14, 1995, 3pm
400 Cory Hall, Hughes Room


Identifying Sequential Redundancies Without Search

Miron Abramovici
AT&T Bell Laboratories, Murray Hill

Previous solutions to the difficult problem of identifying sequential
redundancy are either based on incorrect theoretical results, or rely on 
unrealistic simplifying assumptions, or are applicable only to small circuits.
This talk will discuss the limitations of the existing definitions of 
sequential redundancy and introduce a new concept of c-cycle redundancy as 
a generalization of the conventional notion of sequential redundancy. 
Removing c-cycle redundancies allows circuit simplifications which are not 
possible with conventional redundancy. I will present an efficient algorithm, 
FIRES, to identify c-cycle redundancies without search. FIRES does not have
the limitations of existing methods. It does not assume the existence of 
a global reset nor does it require any state transition information. FIRES has 
provably polynomial-time complexity and is practical for large circuits. 
However, it is not guaranteed to identify all redundancies in a circuit. 
Experimental results on benchmark circuits show that FIRES identifies a 
large number of redundancies. In general, the redundant faults 
identified by FIRES are not easy targets for state-of-the-art sequential test 
generators. The  talk  will  also   present
surprising  examples that contradict common expectations regarding
redundancy in sequential circuits.

This work was done with M. Iyer (Synopsys) and D. Long (Bell Labs).