Co-evolutionary high-level test synthesis

ABSTRACT

The main approach of this paper is utilizing bio-inspired evolutionary strategies for high level test synthesis. In this paper a genetic algorithm (GA) is implemented to schedule a data-flow graph considering latency. Also, module binding is performed with another GA concurrently, considering resource constraints. The register allocation is performed using another GA which minimizes the number of registers. Then a co-evolutionary strategy merges the results of these three solutions, targeting testability improvement. Experimental results show using the proposed approach results in improvement in fault coverage with no or negligible overhead in area and delay.

REFERENCES

• 1: Michael C. McFarland , Alice C. Parker , Raul Camposano, Tutorial on high-level synthesis, Proceedings of the 25th ACM/IEEE conference on Design automation, p.330-336, June 12-15, 1988, Atlantic City, New Jersey, United States
• 2: M. C. McFarland, A. C. Parker, and R. Camposano, "The High-Level Synthesis of Digital Systems," Proceedings of the IEEE, Vol. 78, No. 2, pp. 310--318, Feb 1990.
• 3: Michael L. Bushnell, Vishwani D. Agrawal, Essentials of Electronic Testing for Digital, Memory and Mixed-Signal VLSI Circuits, Kluwer Academic Publishers, 2000.
• 4: S. Dey, A. Raghunatan, and R. K. Roy, "Considering Testability during High-Level Design," ASP DAC, pp. 205--210, 1998.
• 5: L.J. Avra, E.J. McCluskey, "High-level synthesis of testable design: An overview of university systems," IEEE International Test Conference - Test Synthesis Seminar, Washington D.C., 1994.
• 6: Kenneth D. Wagner , Sujit Dey, High-level synthesis for testability: a survey and perspective, Proceedings of the 33rd annual conference on Design automation, p.131-136, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240543]
• 7: Mike Tien-Chien Lee, High-Level Test Synthesis of Digital VLSI Circuits, Artech House, Inc., Norwood, MA, 1997
• 8: Tien-Chien Lee , Niraj K. Jha , Wayne H. Wolf, Behavioral synthesis of highly testable data paths under the non-scan and partial scan environments, Proceedings of the 30th international conference on Design automation, p.292-297, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164897]
• 9: J. Steensma, F. Catthor, and H.D. Man, " Test of high Throughput Data Paths with Symbolic Controllability and Observability Descriptions," In Proceedings of 6th Workshop New Directions for testing, pp 67--76, May 1992.
• 10: Frank F. Hsu , Janak H. Patel, High-level variable selection for partial-scan implementation, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.79-84, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288564]
• 11: M. L. Flottes , R. Pires , B. Rouzeyre , L. Volpe, Scanning datapaths: a fast and effective partial scan selection technique, Proceedings of the conference on Design, automation and test in Europe, p.921-922, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 12: Saeed Safari , Amir Hossein Jahangir , Hadi Esmaeilzadeh, A parameterized graph-based framework for high-level test synthesis, Integration, the VLSI Journal, v.39 n.4, p.363-381, July 2006 [doi>10.1016/j.vlsi.2005.08.004]
• 13: T. Yang , Z. Peng, An efficient algorithm to integrated scheduling and allocation in high-level test synthesis, Proceedings of the conference on Design, automation and test in Europe, p.74-81, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 14: R. Camposano, W. Rosenstiel, "Synthesizing Circuits from Behavioral Descriptions," IEEE Transactions on CAD/ICAS, Vol. 8, No. 2, pp. 171--180, February 1989.
• 15: F. J. Kurdahi , A. C. Parker, REAL: a program for REgister ALlocation, Proceedings of the 24th ACM/IEEE conference on Design automation, p.210-215, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37920]
• 16: Agoston E. Eiben , J. E. Smith, Introduction to Evolutionary Computing, SpringerVerlag, 2003
• 17: D. Beasley, D. R. Bull, and R. R. Martin, "An overview of genetic algorithms: Part 1, fundamentals," University Computing, vol. 15, no. 2, pp. 58--69, 1993.
• 18: P. G. Paulin , J. P. Knight , E. F. Girczyc, HAL: a multi-paradigm approach to automatic data path synthesis, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.263-270, July 1986, Las Vegas, Nevada, United States
• 19: M.K. Dhodhi and et. al., "Datapath synthesis using a problem-space genetic algorithm," Proc. Of IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 14, pp 934--944, Aug. 1995.
• 20: HOPE (version 2.0), Dong S. Ha ([e-mail]), Web: http://www.ee.vt.edu/ha, Virginia Polytechnic Institute & State University.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

General Terms:
Algorithms, Design, Reliability

Keywords:
co-evolutionary algorithm, genetic algorithm, high-level test synthesis, module binding, register allocation, scheduling