Browse Prior Art Database

Scan Chain Optimization

IP.com Disclosure Number: IPCOM000119323D
Original Publication Date: 1991-Jan-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 4 page(s) / 126K

Publishing Venue

IBM

Related People

Eisenmenger, DD: AUTHOR [+2]

Abstract

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.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Scan Chain Optimization

      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.

      The scan 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
the chain.

      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.

      This program 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.

      MULTIPLE CHAINS.  Multiple chains are handled by grouping all
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
associativity.

      CHAIN 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.

      LATCH 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. ...