Публікація: Set operation speed-up of fault simulation
Завантаження...
Дата
2004
Назва журналу
ISSN журналу
Назва тома
Видавництво
EWDTW
Анотація
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.
Опис
Ключові слова
set operations, data structures, performance analysis, fault simulation
Бібліографічний опис
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)