Methods for distribution of test generation programs

Abstract

As described herein, circuit testing algorithms, or portions thereof, can be executed in a distributed manner so that their execution can be over a network of processors. In one aspect, the results that are obtained by such distributed execution are ensured to be consistent with the results that would be obtained by executing them in a non-distributed manner. Thus, in one aspect, the algorithms, or portions thereof, have to be made distributable. The algorithms, or portions thereof, are made distributable by isolating any random number generation therewith to be independent of each other. This isolation applies to any random number generation associated with different call instances of the same algorithm as well. In one aspect, the isolation is accomplished by ensuring that the calculation of random number sequences for the algorithms, or portions thereof, is not dependent on random number sequences calculated for the others or between call instances of the same algorithm.

1 .- 7 . (canceled) 
   
   
       8 . A method of generating test patterns for testing electronic circuits, the method implemented by one or more computers, the method comprising:
 from a plurality of algorithms related to test pattern generation, selecting at least two algorithms that can be executed in parallel;   isolating generation of random number sequences associated with the selected algorithms by ensuring that random number sequence generation of at least one of the selected algorithms does not depend on random number sequence generation of other of the selected algorithms; and   ensuring that random number sequence generation associated with one or more call instances of at least one of the algorithms does not depend on random number sequence generation of other call instances of the same algorithm.   
   
   
       9 . The method of  claim 8  wherein, ensuring that random number sequence generation related to the one or more call instances of the at least one of the algorithms does not depend on random number sequence generation related to other call instances of the same algorithm comprises computing the random number sequences associated with the one or more call instances of the algorithm based on invariant data associated with the one or more call instances of the algorithms. 
   
   
       10 . The method of  claim 9  wherein, the invariant data comprises calling parameters associated with the one or more call instances. 
   
   
       11 . The method of  claim 10  wherein, the same algorithm relates to pattern generation targeted to a first selected fault and the calling parameters comprises properties of the first selected fault. 
   
   
       12 . A method of generating test patterns for testing electronic circuits, the method implemented by one or more computers for executing one or more algorithms related to test pattern generation, the method comprising:
 ensuring that random number sequence generation associated with one or more call instances of at least one of the one or more algorithms related to test pattern generation is independent of random number sequence generation of other call instances of the same algorithm.   
   
   
       13 . The method of  claim 12  wherein, ensuring comprises computing the random number sequences associated with the one or more call instances of the same algorithm based on invariant data associated with the one or more call instances of the same algorithm. 
   
   
       14 . The method of  claim 13  wherein, the invariant data associated with the different call instances of the same algorithm comprises calling parameters associated with the one or more call instances. 
   
   
       15 . The method of  claim 14  wherein, the same algorithm relates to pattern generation targeted to a first selected fault and the calling parameters comprises properties of the first selected fault. 
   
   
       16 . The method of  claim 12  wherein, ensuring comprises computing the random number sequences associated with the one or more call instances of the same algorithm deterministically. 
   
   
       17 . A method of generating test patterns for use in testing the operation of a simulated electronic circuit comprising:
 allocating at least first and second test pattern generation algorithms to at least first and second controlled processors for processing by the at least first and second controlled processors to produce respective first and second test pattern results, the processing by the at least first and second controlled processors being controlled by a controlling processor;   seeding a number generator to establish a first known starting number;   controlling the first controlled processor to start the processing of the first test pattern generation algorithm at the first starting number to produce the first test pattern results;   seeding a number generator to establish a second known starting number;   controlling the second controlled processor to start the processing of the second test pattern generation algorithm at the second known starting number to produce the second test pattern results;   providing the first and second test pattern results to the controlling processor; and   assembling the first and second test pattern results into at least a portion of one or more test patterns in the same sequence that would be the case if the first and second test pattern generation algorithms had been performed sequentially by a single processor.   
   
   
       18 . A method according to  claim 17  wherein the first and second algorithms are separate instances of the same algorithm. 
   
   
       19 . A method according to  claim 17  wherein the first and second known starting numbers are the same number. 
   
   
       20 . A method according to  claim 17  wherein a plurality of test pattern generation algorithms are allocated to a plurality of controlled processors for processing non-sequentially, the method comprising seeding at least one number generator to provide known starting numbers for each of the allocated plurality of test pattern generation algorithms. 
   
   
       21 . A method according to  claim 17  comprising allocating at least one test pattern generation algorithm to controlled processors such that test pattern results corresponding to random sequences for pattern fill for the at least one algorithm are processed independently of fault propagation and justification performed by the at least one algorithm. 
   
   
       22 . A method according to  claim 17  wherein the first and second algorithms comprise separate instances of performance of the same algorithm and wherein the first and second starting numbers are different. 
   
   
       23 . A method according to  claim 17  wherein the first and second algorithms comprise separate instances of the same algorithm and wherein the first and second starting numbers are the same. 
   
   
       24 . A method according to  claim 17  wherein the first and second algorithms comprise separate instances of the same algorithm and wherein the second starting number is deterministically determined. 
   
   
       25 . A method according to  claim 24  wherein the acts of seeding to known starting numbers comprises seeding based upon at least one call parameter. 
   
   
       26 . A method according to  claim 24  in which the second starting number is determined deterministically based upon a sequence indicating parameter provided by the controlling processor. 
   
   
       27 . A method according to  claim 24  in which the second starting number is computed deterministically based upon a sequence computation algorithm provided by the controlling processor to the controlled processor that is performing the second algorithm. 
   
   
       28 . A method according to  claim 17  wherein plural number generators are used to generate the starting numbers. 
   
   
       29 . A method according to  claim 17  wherein a single number generator is used to generate the starting numbers. 
   
   
       30 . A method according to  claim 17  comprising the act of reseeding a number generator from one seed value to a prior seed value upon completion of the performance of a test pattern generation algorithm that started processing at a number determined by the number generator from the one seed value. 
   
   
       31 . A method according to  claim 17  comprising the act of producing an electronic circuit embodying a circuit design tested by test patterns generated in accordance with the method of  claim 17 . 
   
   
       32 . One or more computer-readable storage media storing computer-executable instructions for causing a computer to perform a method comprising:
 ensuring that random number sequence generation associated with one or more call instances of at least one of the one or more algorithms related to test pattern generation is independent of random number sequence generation of other call instances of the same algorithm.