In this paper, we describe TSOtool, a program to check the behavior of the memory subsystem in a shared memory multiprocessor. TSOtool runs pseudo-randomly generated programs with data races on a system compliant with the total store order (TSO) memory consistency model; it then checks the results of the program against the formal TSO specification. Such analysis can expose subtle memory errors like data corruption, atomicity violation and illegal instruction ordering. While verifying TSO compliance completely is an NP-complete problem, we describe a new polynomial time algorithm which is incorporated in TSOtool. In spite of being incomplete, it has been successful in detecting several bugs in the design of commercial microprocessors and systems, during both pre-silicon and post-silicon phases of validation.

This paper addresses the problem of locating design errors in a sequential circuit. For single-error circuits, we consider a signal ƒ as a potential error source only if the circuit can be completely rectified by re-synthesizing ƒ (i.e., changing the function of signal ƒ). In order to handle larger circuits, we do not rely on Binary Decision Diagram. Instead, we search for potential error sources by a modified sequential fault simulation process. The main contributions of this paper are two-fold: (1) we derive the necessary and sufficient condition of whether an erroneous input sequence (i.e., an input sequence producing erroneous responses) can be corrected by changing the function of a particular internal signal; and (2) we propose a modified fault simulation procedure to check this condition. Our approach does not rely on any error model, and thus, is suitable for general types of errors. Furthermore, it can be easily extended to identify multiple errors. Experimental results on ISCAS89 benchmark circuits are presented to demonstrate its capability.

Algorithmic state machine (ASM) descriptions or hardware flowcharts have been used successfully to describe and verify large systems like the IBM 3081. Hardware flowcharts are intuitively appealing in their specification of control flow and data path operations. Nevertheless, previous mechanizations of hardware flowcharts lacked a formal semantics which prevented a rigorous analysis of implementations refined from ASM descriptions, and the ability to equate composed ASM descriptions to purely behavioral descriptions. To address these concerns, we describe an algorithmic register transfer language which has a formal semantics along with an algebra which is used to reason about composed ASM descriptions.