The increasing complexity of logic circuits has made the problem of test generation intractable. In this dissertation we investigate three different techniques to speed up the test generation process. The first approach attempts to exploit the hierarchy inherent in any complex digital design. An intermediate high-level representation is proposed, and algorithms to perform forward implication and backtracing in the proposed framework are developed. Results of test generation experiments based on this approach are also presented. The second technique deals with the use of heuristics in test generation algorithms. Based on an extensive study of five existing testability measures, a composite test generation strategy is evaluated. The composite strategy uses multiple testability measures to aid the test generation guidance heuristic. Our results indicate that this strategy not only gives better fault coverage but also reduces the average time taken per fault. Finally we investigate the viability of parallel processing for test generation. Schemes for mapping test generation algorithms onto different classes of parallel machines are presented. The performance of these mapping strategies is predicted based on uniprocessor turnaround times and an estimate of the communication delays.

Multiprocessing is an effective architectural approach to enhance the performance of computer systems. However, various problems involved in multiprocessing may severely degrade system performance. This research has mainly centered on the memory interference problem in tightly coupled multiprocessor computer systems. Depending on the nature of the memory-requesting mechanism, discussion is centered on two important cases of such systems. The memory interference in multiprocessor systems with time-division-multiplexed (TDM) busses is first discussed. A general model for the memory interference in synchronous multiprocessor systems which allow arbitrary memory request rates, non-uniform memory references, and unequal processor priorities is presented next. Several application examples which make use of the memory interference models derived are presented. First, an algorithm is proposed for the estimation of the execution time of a program running in a multiprocessor system. Such an algorithm can be used to pick a computation decomposition which best utilizes the available computing power. A case study of the effect of computation decomposition on the performance of Gaussian Elimination is presented. The execution of matrix multiplication in a multiprocessor system with virtual memory was evaluated by simulation, in which a memory interference model capable of dealing with priority was used to dynamically modify various job execution times according to the number of processors and I/O channels active in the system.