The authors propose a novel linear-time algorithm for identifying, in a large combinatorial circuit, a large set of faults that are undetectable by a given test vector. Although this so-called X-algorithm does not identify all the undetectable faults, empirical evidence is offered to show that the reduction in the number of remaining faults to be simulated is significant. The algorithm is intended as a simple, fast preprocessing step to be performed after a test vector has been generated, but before the (often lengthy) process of fault simulation begins. The empirical results indicate that the X-algorithm is both useful (indicated by the utility factor) and good (indicated by the effectiveness factor). It provides as much as a 50% reduction in the number of faults that need to be simulated. Moreover, the algorithm seems to identify a large fraction of the undetectable faults. >

The authors develop a formal group-theoretic model, called the Cayley graph model, for designing, analyzing, and improving such networks. They show that this model is universal and demonstrate how interconnection networks can be concisely represented in this model. It is shown that this model enables the authors to design networks based on representations of finite groups. They can then analyze these networks by interpreting the group-theoretic structure graph theoretically, Using these ideas, and motivated by certain well-known combinatorial problems, they develop two classes of networks called star graphs and pancake graphs. These networks are shown to have better performance than previous networks.>

The problem is presented in the context of some recent theoretical advances on a related problem, called random satisfiability. These recent results indicate the theoretical limitations inherent in the problem of computing signal probabilities. Such limitations exist even if one uses Monte Carlo techniques for estimating signal probabilities. Theoretical results indicate that any practical method devised to compute signal probabilities would have to be evaluated purely on an empirical basis. An improved algorithm is offered for estimating the signal probabilities that takes into account the first-order effects of reconvergent input leads. It is demonstrated that this algorithm is linear in the product of the size of the network and the number of inputs. Empirical evidence is given indicating the improved performance obtained using this method over the straightforward probability computations. The results are very good, and the algorithm is very fast and easy to implement.>

The test point insertion problem is that of selecting t nodes in a combinational network as candidates for inserting observable test points, so as to minimize the number of test vectors needed to detect all single stuck-at faults in the network. In this paper we describe a dynamic programming approach to selecting the test points and provide an algorithm that inserts the test points optimally for fanout-free networks. We further extend this algorithm to general combinational networks with reconvergent fanout. We also analyze the time complexity of the algorithm and show that it runs in Ο(n-t) time, where n is the size of the network and t is the number of test points to be inserted.

This paper investigates group graphs as a source of interconnection networks. It is shown that while these graphs possess many properties desirable in all interconnection networks, their diversity allows the generation of interconnection networks which may be optimized with regard to a variety of specific parameters. Techniques are described for generating, combining, and analyzing these graphs with respect to their order, diameter, fault tolerance, etc. A theorem is derived which shows that a large important class of group graphs are optimally fault tolerant. A number of examples are included.

In analyzing the effectiveness of min-cut partitioning heuristics, we are faced with the task of constructing ``random'' looking test networks with a prescribed cut-set size in its optimal partition. We present a technique for constructing networks over a given set of components that has been a priori partitioned into two parts. The networks have the property that the optimal partition, i.e., one that minimizes the size of the cut-set, is the predefined partition, and this partition has a cut-set of a given size. Furthermore, these networks can be designed to possess certain statistical properties, such as a desired mean and standard deviation for the number of components per net, so that they truly reflect the input space in the application domain. We also extend these techniques to the generalized partitioning problem.

Recently, a fast (linear) heuristic for improving min-cut partitions of VLSI networks was suggested by Fiduccia and Mattheyses [6]. In this-paper we generalize their ideas and suggest a class of increasingly sophisticated heuristics. We then show, by exploiting the data structures originally suggested by them, that the computational complexity of any specific heuristic in the suggested class remains linear in the size of the network.

Most NP-completeness results for test generation problems involve a reduction to the redundancy problem, which explicitly encodes the satisfiability problem. In this correspondence we investigate the complexity of a more modest problem-that of estimating the size of a test set under the constraint that the circuit is irredundant. We show that even this constrained problem is NP-hard in the strong sense.

We present examples of hard tautologies in propositional calculus by encoding instances of the assertions made by Ramsey's theorem. We provide evidence that these tautologies are indeed hard by 1. showing that there are no short proofs for these tautologies in certain restricted classes of proof systems; 2. relating a proof of these tautologies to the problem of determining the diagonal Ramsey numbers for graphs.