Set operation speed-up of fault simulation

Zaychenko, S. A.; Parfentiy, A. N.; Kamenuka, E. A.; Ktiaman, H.

Публікація:
Set operation speed-up of fault simulation

dc.contributor.author	Zaychenko, S. A.
dc.contributor.author	Parfentiy, A. N.
dc.contributor.author	Kamenuka, E. A.
dc.contributor.author	Ktiaman, H.
dc.date.accessioned	2016-09-02T12:04:27Z
dc.date.available	2016-09-02T12:04:27Z
dc.date.issued	2004
dc.description.abstract	In this paper there are presented data structures and algorithms for performing set theory operations upon lists of defects within deductive fault simulation method of digital systems. There are suggested 4 types of data structures and calculation procedures, which provide maximum performance for basic operations required for effective software implementation of the method. Hardware designers and manufacturers demand significant performance acceleration for fault simulation and automatic test patterns generation tools (ATPG) [1] for large-scale digital systems, being targeted into the application specific integrated circuits (ASIC’s). Over 50% of existing ATPG systems [1-4] use deductive method of fault simulation to obtain table of faults, covered by the applied test. The performance distribution analysis of computation cycle during test-vector processing within deductive method (fig. 1) shows, that about 70% of time is spent on performing set theory’s operations upon lists of faults: union, intersection and complement (difference). That’s why the software implementation performance of the deductive method strongly depends on implementation efficiency of the set theory operations.Software implementation of the set operations may use classic storage data structures and algorithms, which efficiency differs for various numbers of elements under processing. Relatively to deductive fault simulation method, the particular computations at the same time are performed upon sets with various range of elements number. That’s why, there is no well-known data structure in general programming, which provides acceptable performance of implementation of the set operations for deductive fault simulation method. The research goal is to analyze and select optimal data structures and processing algorithms of set theory operations, that will provide the highest performance and lowest memory usage for software implementation of the deductive fault simulation method. The research tasks include: – analysis of classic data structures, being used in discrete mathematics [5,6] and general programming [7-9] for implementation of set theory operations; – development of the computation strategy, which provides high speed and low memory usage for fault simulation of large-scale digital systems; – efficiency assessment of the developed strategy.	uk_UA
dc.identifier.citation	Zaychenko S. A. Set operation speed-up of fault simulation /S.A. Zaychenko, A.N. Parfentiy, E.A. Kamenuka, H. Ktiaman//Proceedings of East-West Design & Test Workshop (EWDTW’04)	uk_UA
dc.identifier.uri	http://openarchive.nure.ua/handle/document/2022
dc.language.iso	en	uk_UA
dc.publisher	EWDTW	uk_UA
dc.subject	set operations	uk_UA
dc.subject	data structures	uk_UA
dc.subject	performance analysis	uk_UA
dc.subject	fault simulation	uk_UA
dc.title	Set operation speed-up of fault simulation	uk_UA
dc.type	Article	uk_UA
dspace.entity.type	Publication