Scan Chain Optimization
Original Publication Date: 1991-Jan-01
Included in the Prior Art Database: 2005-Apr-01
Eisenmenger, DD: AUTHOR [+2]
This article describes use of simulated annealing to solve a Traveling Salesman Problem (TSP) as it pertains to scan chains in a VLSI chip design. Considerations are made for solving multiple chains, maintaining the logic phase of the nets that make up the chain, and handling multiple pins in the nets.
Scan Chain Optimization
describes use of simulated annealing to
solve a Traveling Salesman Problem (TSP) as it pertains to scan
chains in a VLSI chip design. Considerations are made for solving
multiple chains, maintaining the logic phase of the nets that make up
the chain, and handling multiple pins in the nets.
chains that exist in a logic design are not always
just two-pin connections. It is common practice that a connection in
the chain, called a net, connect to more than the input of the next
latch. The net may also feed other logic in the design. In Fig. 1,
see the nets that connect block AB to block AC and block AE to block
AF. When the rechaining is done, consideration should be given to
the fact that block AB will be wired to the two "A" blocks anyway.
When changes in the tour are being analyzed, the distance calculated
from the input of a SRL should not be to pin 90 of block AB,
but instead to all the pins in net AB90, except, of course, for the
SRL that is being disconnected and will connect to somewhere else in
It is also
common to change polarity of the nets as the chain
progresses through the design. This is done so other logic hanging
off a SRL scan-out pin (block AE in Fig. 1) will function as the
logic designer wishes. If you assume that pin 90 is the "on" phase
and pin 91 is the "off" phase of the SRL circuit, then all SRLs in
Fig. 1 cannot be rechained, at random, to anywhere else in the chain.
Consideration must be given to what phase is entering the SRL and
what phase is leaving the SRL.
works by solving a TSP using simulated annealing.
An original tour of cities is supplied as input. The tour is defined
by the order in which the cities are listed. A city is either a
single SRL or it may be a group of logic blocks. Each city has a
single entrance, or input pin, and at least one exit, the output pin.
In the case of multi-pin nets, there are several points where it is
valid to exit the city.
CHAINS. Multiple chains are handled by
the cities in a single chain together and marking them as a group.
Then, each group is processed to completion before the next group is
started. This allows for very controlled rechaining regarding either
breaking a chain due to gating, or subchaining a chain due to latch
BREAKING. Because it is common to
introduce gating into
a scan chain, it is necessary to break a scan chain at the gating.
If the gating was disregarded, logic function would not be
maintained. Supporting multiple chains for this reason allows all
chains to be solved in a single run.
ASSOCIATIVITY. Sometimes it is necessary
to keep a set
of latches in a chain together as a group. It may not matter how
they are chained in their group, as long as they stay connected to
each other. ...