Parallel hardware accelerated switch level fault simulation

Abstract

Switch level faults, as opposed to traditional gate level faults, can more accurately model physical faults found in an integrated circuit. However, existing fault simulation techniques have a worst-case computational complexity of O(n²), where n is the number of devices in the circuit. This paper presents a novel switch level extension to parallel fault simulation and the switch level circuit partitioning needed for parallel processing. The parallel switch level fault simulation technique uses 9-valued logic, N and P-type switch state tables, and a minimum operation in order to simulate all faults in parallel for one switch. The circuit partitioning method uses reverse level ordering, grouping, and subgrouping in order to partition transistors for parallel processing. This paper also presents an algorithm and complexity measure for parallel fault simulation as extended to the switch level. For the algorithm, the switch level fault simulation complexity is reduced to O(L²), where L is the number of levels of switches encountered when traversing from the output to the input. The complexity of the proposed algorithm is much less than that for traditional fault simulation techniques.