PLATYPUS: a PLA test pattern generation tool

ABSTRACT

PLATypus (PLA Test pattern generation and logic simulation tool) is an efficient tool for large PLAs which is interfaced with other existing PLA tools such as the constrained/unconstrained, simple/multiple folding program PLEASURE and the logic minimizer ESPRESSO II-C developed at the University of California at Berkeley. PLATYPUS uses biased random test generation as a quick preprocess followed by a deterministic test generation process to achieve the best balance between efficient run time and test set minimality. The algorithm adopted in the deterministic phase is exact, i.e., it achieves the highest possible test coverage by generating a test for every testable fault. Powerful heuristics are introduced in the area of fault processing order, backend fault simulation, “don't-care” bit fixing, and on-the-fly test compaction to achieve the best performance of PLATYPUS. The deterministic test generation algorithm is based on both complementation and tautology check of a logic cover. Both complementation and tautology check are performed by an advanced method used in the logic minimizer ESPRESSO-II. PLATYPUS supports both folded and unfolded PLAs, and both crosspoint and stuck-at fault models. PLATYPUS can also be used as a logic simulation tool and redundancy identifier. Test pattern generation has been performed by PLATYPUS on a large number of industrial PLAs.

REFERENCES

• 1: H. Fleisher and L. I. Maissel, "An introduction to array logic," IBM I. Res. DeveZop., vol. 19,pp. 98-109,Mar. 1975.
• 2: R. Rudell, A. 5angiovanni-Vincentelli and G. De Mieh,li, "A Finite-S~a~~ Machine Synthesis System" Proc. 1985 Internat~mal Symposium on Circuits and Systems, Xyoto, Japan, 1985.
• 3: R. Proebsting, Electronics, p.82, Oct, 28,1976.
• 4: Frederick J. Hill , Gerald R. Peterson, Introduction to Switching Theory and Logical Design, John Wiley & Sons, Inc., New York, NY, 1981
• 5: S. Bozorgui-Nesbat and E. J. McCluskey, "Lower Overhead Design for Testability of Programmable Logic Arrays," P~oc. 19&f International Test Conference, Philadelphia, October 1984.
• 6: K. Son and D. K. Pradhan, "Design of Programmable Logic Arrays for Testability," Proc. /EEE International Test Conference, November 11-13, 1980, pp163-166.
• 7: S. J. Hong and D. L. Ostapko, "FITPLA: A Programmable Logic Array for Function Independent Testing," Dig. lOth Int. S37np. FTC., Kyoto, Japan, 1980, pp131-136.
• 8: H. Fujiwara and K. Kinoshila, "A Design of Programmable logic Arrays with Universal Tests," IEEE Trans. o~ Comp., pp 823-828, Nov. 1981.
• 9: K.S. Ramana~ha and N. H. Biswas, "A Design for Teslability of Unde~ectable Crosspoint :Faults in Programmable Logic Arrays,* /EF, E Trans. on Colnp., June 1983.
• 10: K.A. Hun, J. Y. Jou and J. A. Abraham, "Built-In Tests For VLSI Finite- State Machines," Dig. o/ Papers 14th Irtt'l Con/. on Faul, t-Tolerant Computing, June 1984.
• 11: Robert King Brayton , Alberto L. Sangiovanni-Vincentelli , Curtis T. McMullen , Gary D. Hachtel, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1984
• 12: Giovanni De Micheli , Alberto Sangiovanni-Vincentelli, PLEASURE: a computer program for simple/multiple constrained/unconstrained folding of Programmable Logic Arrays, Proceedings of the 20th conference on Design automation, p.530-537, June 27-29, 1983, Miami Beach, Florida, United States
• 13: G. De Micheli and M. Santomauro, " SMILE: A computer program for partitioning of programmed logic array,* Computer Aided Design. No. 2, pp. 89-97, March 1983 and Memorandum UCBIERL, No. 82/74.
• 14: G. Mah, "PANDA - a PLA generator for multiply folded arrays," M.S. Report, Dept. EECS, U.C. Berkeley 1983.
• 15: S. j. Hong and D. L. Ostapko, "Fault analy:ds and test generation for programmable logic arrays (PLA's),N ~ Trans. Comput., vol. C-28, pp.617 626, Sept. 1979.
• 16: Charles W. Cha, A testing strategy for PLAs, Proceedings of the 15th conference on Design automation, p.326-334, June 19-21, 1978, Las Vegas, Nevada, United States
• 17: J. E, Smith, "Detection of faults in prog':ammable logic arrays," {EEE Trans. Comput., vol, C-28, pp. 845-853, Nov. 1979.
• 18: E.I. Muehldorf and T. W. Williams, "Optimized stuck fault test pattern generation for PLA macros," Digest o/Papers, 1977 Sernicondz~tor Test Sympos/z~n, pp.89-10I, Oct. 1977.
• 19: E.I. Muehldorf, G. P. Papp and T. W. Williams, *E{ficient test pattern generation for embedded PLAs," Proceedings of 1980 IEEE Test Conference. pp. 349-358, Sept. 1980.
• 20: E.B. Eichelberger and E. Lindbloom, "A heuristic test-pattern generator for programmable logic arrays,* IBMJ. Res. Develop,, vol. 24, pp.15-22, Jan, 1980.
• 21: Pradip Bose , Jacob A. Abraham, Test generation for programmable logic arrays, Proceedings of the 19th conference on Design automation, p.574-580, January 1982
• 22: F. Somenzi, S, Gai, M. Mezzalama and P. Prinetto, "PART: programmable array testing based on a partitioning algorithm," IEEE Trans. CAD, vol. CAD-3, pp. 142-149, April 1984.
• 23: J. Paul Roth, Computer Logic, Testing and Verification, W. H. Freeman & Co., New York, NY, 1980
• 24: S.J. Hong, R. G. Gain and D. L. Os~apko, "MII~I: a heuristic approach for logic minimization," IBM)'. o/Res, and Dew., vol. 18,pp. 443-458, Sept. 1974.
• 25: Y. Tamir and C. H. Sequin, "Design and application of self-testing comparatots implemented with MOS PLA's," /EEE Trans. Comput., vol. C-33, pp. 493- 506.,June 1984.
• 26: M. Hofmann and A. R. Newton, "A Domino CMOS logic synthesis system," Proc. 1985 }nterTtational Symposium on Circuits amf Systems, June 1985.
• 27: R. Rudell, and A. Sangiovanni-Vincentelli, "I~PRESSO-MV: Algorithms for multiple-valued logic minimization," Proc. 198~: International Symposium on CircuLts and ~ystems, June 1985.
• 28: David Landskov , Scott Davidson , Bruce Shriver , Patrick W. Mallett, Local Microcode Compaction Techniques, ACM Computing Surveys (CSUR), v.12 n.3, p.261-294, Sept. 1980 [doi>10.1145/356819.356822]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Logic arrays
  B.7 INTEGRATED CIRCUITS

  J. Computer Applications

General Terms:
Algorithms, Design, Measurement, Performance, Theory