Article

Free access

Measured performance of a programmed implementation of the subscripted D-Algorithm

Authors:

C. Benmehrez,

J. F. McDonaldAuthors Info & Claims

DAC '83: Proceedings of the 20th Design Automation Conference

Pages 308 - 315

Published: 27 June 1983 Publication History

PDF eReader

Abstract

Hypothesized performance improvements of the subscripted D-Algorithm have now been confirmed by a series of benchmark comparisons with the Roth's DALG. The major concept exploited by the subscripted algorithm is the acquisition of control over a submodule by back-propagation of multiple simultaneously sensitized D_j paths. The existence of these simultaneously sensitizable control paths has now been verified for many circuits of very large size. The run time required to establsih such control paths is usually about the same as the time that DALG takes to find a single test. Hence, for high fan-in submodules the performance enhancements are impressive. The algorithm readily finds multiple control paths in circuits with high fan-out and reconvergence. The algorithm even backpropagates readily through Exclusive-Or trees. Therefore, apprehension that multiple control paths would suffer mutual interference in practical circuits is not completely justified.

References

[1]

Paul M. DeRusso, R. J. Roy, and Charles M. Close, "State Variables for Engineers", John Wiley & Sons, Inc., Sect. 5-7, pp. 349-354.

Digital Library

Google Scholar

[2]

L.H. Goldstein, #"Controllability/Observability Analysis of Digital Circuits", IEEE Transactions on Circuits and Systems, Vol. CAS-26 No. 9, September 1979.

Google Scholar

[3]

J.P. Roth, W.C. Bouricius, P.R. Schneider, "Programmed Algorithms to Compute Tests to Detect and Distinguish Between Failures in Logic Circuits", IEEE Transactions on Elec. Comp., EC-16, October 1967.

Crossref

Google Scholar

[4]

D.B. Armstrong, "On Finding a Nearly Minimal Set of Fault Detection Tests for Combinational Logic Nets", IEEE Transactions on Elec. Comp. Vol. EC-15, pp. 66-73, February 1966.

Crossref

Google Scholar

[5]

A.N. Airpetian, and J.F. McDonald, "Improved Test Set Generation Algorithm for Combinational Logic Control", Proc. Ninth Annual International Symposium on Fault-Tolerant Computing (Madison, Wisconsin), June 20-22, 1979, pp. 133-136.

Google Scholar

[6]

D.C. Bossen and S.J. Hong, "Cause Effect Analysis for Multiple Fault Detection in Combinational Networks", IEEE Transactions on Comp., Vol. C-20, No. 11, November 1971.

Google Scholar

[7]

J.P. Hayes, "Test Generation Using Equivalent Normal Forms", Design Automation & Fault Tolerant Computing, Vol. III, Issue 3/4, pp. 131-154.

Google Scholar

[8]

P. Goel, "An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits", Proc. 1980 Fault Tolerant Computing Symposium, October 1980, pp. 145-151.

Google Scholar

[9]

J.P. Roth, "Diagnosis of Automata Failures, A Calculus & a Method", Vol. 10, IBM Journal of Research & Development, pp. 278-291, July 1966.

Google Scholar

[10]

C. Benmehrez and J.F. McDonald, "The Subscripted D-Algorithm-ATPG With Multiple Independent Control Paths", IEEE Automatic Test Program Generation Workshop, San Francisco, California, March 15-16, 1983

Google Scholar

[11]

S., Wang, "Implementation and Performance Evaluation of the Subscripted DALG," RPI Tech. Rept. FTCS82-4, (also Master's Thesis, May, 1982).

Google Scholar

[12]

C.,Benmehrez, "Controllability/Observability Concepts in the Subscripted D-Algorithm," PhD Dissertation, Rensselaer Polytechnic Institute, May 1983.

Digital Library

Google Scholar

Cited By

View all

Sandireddy RAgrawal V(2005)Diagnostic and Detection Fault Collapsing for Multiple Output CircuitsProceedings of the conference on Design, Automation and Test in Europe - Volume 210.1109/DATE.2005.121(1014-1019)Online publication date: 7-Mar-2005
https://dl.acm.org/doi/10.1109/DATE.2005.121
Ladjadj MMcDonald J(1987)Benchmark runs of the subscripted D-Algorithm with observation path mergers on the Brglez-Fujiwara circuitsProceedings of the 24th ACM/IEEE Design Automation Conference10.1145/37888.37964(509-515)Online publication date: 1-Oct-1987
https://dl.acm.org/doi/10.1145/37888.37964
Ladjadj MMcDonald JHo DMurray WThomas D(1986)Use of the subscripted DALG in submodule testing with applications in cellular arraysProceedings of the 23rd ACM/IEEE Design Automation Conference10.5555/318013.318068(346-353)Online publication date: 2-Jul-1986
https://dl.acm.org/doi/10.5555/318013.318068
Show More Cited By

Index Terms

Measured performance of a programmed implementation of the subscripted D-Algorithm

Recommendations

Delay Performance and Implementation of Quaternary Logic Circuits
ICCUBEA '15: Proceedings of the 2015 International Conference on Computing Communication Control and Automation

Application of multiple-valued logic (MVL) in the design of digital devices opens additional opportunities. Multiple-valued logic also offers a possibility of increasing the functional complexity, implementing circuits that can perform comparable to the ...
Controllability/observability concepts in the subscripted d-algorithm
Efficient implementation of retiming
ICCAD '94: Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design

Retiming is a technique for optimizing sequential circuits. It repositions the registers in a circuit leaving the combinational cells untouched. The objective of retiming is to find a circuit with the minimum number of registers for a specified clock ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '83: Proceedings of the 20th Design Automation Conference

June 1983

700 pages

ISBN:0818600268

Publisher

IEEE Press

Publication History

Published: 27 June 1983

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
167
Total Downloads

Downloads (Last 12 months)29
Downloads (Last 6 weeks)8

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Sandireddy RAgrawal V(2005)Diagnostic and Detection Fault Collapsing for Multiple Output CircuitsProceedings of the conference on Design, Automation and Test in Europe - Volume 210.1109/DATE.2005.121(1014-1019)Online publication date: 7-Mar-2005
https://dl.acm.org/doi/10.1109/DATE.2005.121
Ladjadj MMcDonald J(1987)Benchmark runs of the subscripted D-Algorithm with observation path mergers on the Brglez-Fujiwara circuitsProceedings of the 24th ACM/IEEE Design Automation Conference10.1145/37888.37964(509-515)Online publication date: 1-Oct-1987
https://dl.acm.org/doi/10.1145/37888.37964
Ladjadj MMcDonald JHo DMurray WThomas D(1986)Use of the subscripted DALG in submodule testing with applications in cellular arraysProceedings of the 23rd ACM/IEEE Design Automation Conference10.5555/318013.318068(346-353)Online publication date: 2-Jul-1986
https://dl.acm.org/doi/10.5555/318013.318068
Trischler ELambert POfek HO'Neill LPistilli PLosleben PNash JShaklee DPreas BLerman H(1984)An integrated design for testability and automatic test pattern generation systemProceedings of the 21st Design Automation Conference10.5555/800033.800797(209-215)Online publication date: 25-Jun-1984
https://dl.acm.org/doi/10.5555/800033.800797

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Delay Performance and Implementation of Quaternary Logic Circuits

Controllability/observability concepts in the subscripted d-algorithm

Efficient implementation of retiming