Test scheduling for high performance VLSI system implementations

A powerful suboptimum heuristic for scheduling tests on general-purpose high-performance VLSI system implementations is presented. A simple model that represents a system and its organization, at any level, by a labeled resource allocation graph between test functions and test and system resources was introduced. The resource allocation graph was utilized to produce a scheduling model and a simple schedulability condition. An algorithm based on mechanisms for generating optimum schedules was presented. The algorithm performs a preliminary greedy scan for valid scheduling cycles. The partial scan seeds an iterative improvement procedure which utilizes a controlled incremental departure from local optima to schedule functions that require an equal number of tests. Methods to utilize the algorithm for a general number of tests per function were also outlined. The implementation of an experimental version of the algorithm showed good performance