MARCO GSRC Calibrating Achievable Design: Bookshelf

Scan Chain Optimization Slot

Work in progress: last updated Wed Apr 11 20001

(see other slots)

Ken Boese, Sun Cho, Andrew B. Kahng and Mike Oliver

Contents

I. Introduction 
II. Data Formats
III.Publicly available instances, solutions and reference performance results
IV. Executable Utilities (converters, generators, statistics browsers, evaluators, constraint verifiers)
V. Optimizers and other non-trivial executables
VI. Source codes
VII. References

I. Introduction

This slot deals with techniques and applications for minimizing the total length of a scan chain. Some of the fundamental techniques are described in Scan Chain Optimization: Heuristic and Optimal Solutions by Boese, Kahng and Tsay (1994).  For other relevant papers, see References.

II. Data Formats

The locations of the cells in the scan chain to be optimized, together with any partial-order constraints (i.e. requirements that a specified cell come before another specified cell) and specifications of which cells are permitted to be the input or output, are specified in the format described here.
 

III. Publicly available instances, solutions and reference performance results

  Here compared are five instances.  For each, a table is provided showing solution cost (the leftmost column) against
  time in seconds (the second column).  The right-hand column is a count of the "major loops", and may be taken as
  a guide to the time/quality tradeoff inherent in the choice of a value for the "-ml" switch in UCLA_ScanOpt2.2 .

 "Windows" is an AMD Athlon K7 800MHz running Windows NT 4.0 SP6a.
  "Linux" is the same machine, running Linux RedHat 6.2.  "Solaris" is a Sparc Ultra-10 300MHz running Solaris 7. 

t500 has 520 total cells (500 "loose" plus 2 subgroups of 10 each)      
It can be generated with the command
   UCLA_ScanGen2.2 -lc 500 > t500
Windows   Linux   Solaris

t1000 has 1020 total cells (1000 loose, 2 subgroups of 10 each)          
It can be generated with the command
   UCLA_ScanGen2.2 -lc 1000 > t1000
Windows   Linux   Solaris

t5000 has 5020 total cells (5000 loose, 2 subgroups of 10 each)          
It can be generated with the command
   UCLA_ScanGen2.2 -lc 5000 > t5000
Windows   Linux   Solaris

t10000 has 10020 total cells (10000 loose, 2 subgroups of 10 each)
It can be generated with the command
   UCLA_ScanGen2.2 -lc 10000 > t10000
Windows   Linux   Solaris                                                

t10kg has 10000 total cells (500 loose, 95 subgroups of 100 each)
It can be generated with the command
   UCLA_ScanGen2.2 -lc 500 -glc 100 -sg 95 > t10kg
Windows   Linux   Solaris
IV. Executable Utilities

ScanChain Instance Generator

UCLA_ScanGen2.2 (Sparc Solaris 2.7) (Intel Linux) (Win95/98/NT)
produces scan chain problems with specified characteristics, prints help file when invoked with -h.
Usage:
 UCLA_ScanGen2.2  [-sg SubGroups] [-po PartialOrderConstraints]
         [-gpo SubgroupPartialOrderConstraints]
         [-sigma Sigma] [-gsigma SubgroupSigma]
         [-offset Offset]
         [-eio] [-ssc | -sgg] [-unif] [-gunif] 
         [-h]
Meanings of the switches explained here.
V. Optimizers and non-trivial executables
 
UCLA_ScanOpt2.2 (Sparc Solaris 2.7) (Intel Linux) (Win95/98/NT)
Optimizes ordering for a given scan chain. Depending on the command-line options, produces output files giving the best solution found, the history of solution quality and time expended at various steps of the optimization, and an xgraph file for viewing the solution. Prints help file when invoked with -h.
Usage:
 UCLA_ScanOpt2.2  -rfile inputfile  [-ml MajorLoops]
          [-des Descents] [-gdes SubgroupDescents]
          [-km  KickMove] [-gkm SubgroupKickMove]
          [-nn NumNear] [-only2] [-gonly2]
          [-pfreq PrintFrequency] [-rs RandSeed]
          [-tfile TourOutFile] [-sfile StatsOutFile] [-xfile XgraphOutFile]
          [-h]
Meanings of the switches explained here.
VI. Source codes
Full source code is available here
VI. References
    Tragoudas, S.; Denny, N.
         Testing for path delay faults using test points. 1999. CONF PAPER

    Hirech, M.; Beausang, J.; Xinli Gu.
         A new approach to scan chain reordering using... 1998. CONF PAPER

    Kobayashi, S.; Edahiro, M.; Kubo, M.
         Scan-chain optimization algorithms for... 1998. CONF PAPER

    Narayanan, S.; Das, A.
         An efficient scheme to diagnose scan chains. 1997. CONF PAPER

    Layout-driven chaining of scan flip-flops. 
         IEE Proc., Comput. Digit. Tech. (UK), Nov. 1996, vol.143, (no.6):421-5.

    Roncken, M.; Aarts, E.; Verhaegh, W.
         Optimal scan for pipelined testing: an... 1996. CONF PAPER

    Reconfiguration techniques for a single scan chain. 
     IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. (USA), June...

    Kwang-Ting Cheng
         Partial scan designs without using a separate scan clock. 1995. CONF PAPER

    Narayanan, S.; Njinda, C.; Breuer, M.
         Optimal sequencing of scan registers. 1992. CONF PAPER -- NOT CURRENTLY AVAILABLE

    Corno, F.; Prinetto, P.; Sonza Reorda, M.; Violante, M.
         Exploiting symbolic techniques for partial scan flip... 1998. CONF PAPER

    Corno, F.; Prinetto, P.; Rebaudengo, M.; Sonza Reorda, M.
         Partial scan flip flop selection for... 1996. CONF PAPER

    Barbagallo, S.; Lobetti Bodoni, M.; Medina, D.; Corno, F.; and others.
         Scan insertion criteria for low design impact. 1996. CONF PAPER
oliver@cs.ucla.edu,abk@cs.ucsd.edu