Abstract:
A system for detecting/avoiding memory usage conflicts when generating and merging multi-threaded software test cases. Initially, a test case generator is given a unique segment of memory which it can use. A plurality of test cases are generated, one at a time, by the test case generator. When the first test case is generated, the memory segment used is noted. When each of the second through Nth test cases is generated, a memory segment of the same size as the first test case, but not overlapping that of the previously assigned test case(s), is assigned to each subsequent test case.

Description:
TECHNICAL FIELD  
         [0001]    The present invention relates generally to computer systems, and more particularly, to a system for preventing memory usage conflicts when generating and merging test cases used in the development and testing of computer processor architectures.  
         Statement of the Problem  
         [0002]    When generating computer processor architecture test cases for an N-threaded processor architecture, it is desirable to generate test cases with N separate executable code streams, i.e., one code stream for each thread. Previously existing methods for generating N-threaded test cases typically separately generate N single-threaded test cases and merge them into one test case. When these methods are employed, the N test cases which are merged must not share any memory space, otherwise the desired behavior of the individual test cases will not occur. Therefore, each individual test case must be generated and then checked to see whether any of the used memory segments overlap. If any overlap occurs, the test cases cannot be merged, and the test cases are then generated again. Since memory allocation performed by presently existing tools is a random process, closure may never be reached, and thus a need exists for a method to assure that memory overlap between the test cases doe not occur when the cases are generated.  
         Solution to the Problem  
         [0003]    The present system overcomes the aforementioned problems of the prior art and achieves an advance in the field by providing a system for generating and merging multi-threaded computer processor architecture test cases. Initially, a test case generator is given a unique segment of memory which it can use. A plurality of test cases are generated, one at a time, by the test case generator. When the first test case is generated, the memory segment used is noted. When each of the second through Nth test cases is generated, a memory segment of the same size as the first test case, but not overlapping that of the previously assigned test case(s), is assigned to each subsequent test case. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0004]    [0004]FIG. 1 is a diagram illustrating exemplary components configured in accordance with the present system;  
         [0005]    [0005]FIG. 2 is a flowchart illustrating, at a high level, steps which may be performed in practicing one embodiment of the method of the present invention; and  
         [0006]    [0006]FIG. 3 is an example showing memory allocation for a multi-threaded test case. 
     
    
     DETAILED DESCRIPTION  
       [0007]    [0007]FIG. 1 is a diagram illustrating data flow through exemplary functional components configured in accordance with the present system  100  for testing the architecture of a target computer processor. In an exemplary embodiment, the functionality for each of these components is performed by software run on a workstation. These components of the system  100  include a probability generator  103 , a test case generator  101 , an architectural simulator  110 , a hardware simulator  115 , and a results comparator  120 .  
         [0008]    The hardware simulator  115  is a software program compiled from RTL (Register Transfer Level) code representing the hardware implementation of the target processor. Two examples of RTL languages are Verilog and VHDL. The RTL code is compiled and translated into gate/transistor-level netlists. These netlists are then used to create an executable module that functions as hardware simulator  115 , which simulates the exact functionality of the target processor hardware. The architectural simulator  110  is also a software program, which in the present exemplary embodiment, is written in the ‘C’ programming language.  
         [0009]    Architectural simulator  110  simulates the desired target processor and implements essentially the same architectural rules as the RTL running in hardware simulator  115 .  
         [0010]    In typical operation, a multi-threaded test case is passed as input to both simulators  110 / 115 . The multi-threaded test case comprises a plurality of individual test case threads (separately executable segments of test case code). The simulators are run synchronously and the output from both is compared. As explained below, the results comparator  120  generates a ‘pass’ or ‘fail’ result  125  indicating whether the results of the two simulators  110  and  115  are identical. The architectural simulator  110  implements the rules of the target processor architecture as simply as possible. The RTL running in hardware simulator  115 , on the other hand, includes ‘micro-architectural’ features which optimize the speed or reliability of the hardware, such as pipelines, buffers, error-checkers, bypass signals, etc. The comparison makes sure that the hardware simulator still gets the correct results after implementing the added RTL complexity.  
         [0011]    An extremely simplified test case example is shown below:  
         [0012]    Simplified Test Case Example  
         [0013]    Thread  0 :  
         [0014]    load r 1 =memory[0x11000] 
         [0015]    load r 2 =memory[0x15000] 
         [0016]    r 3 =add r 1 , r 2   
         [0017]    end  
         [0018]    Thread  1 :  
         [0019]    load r 1 =memory[0x21000] 
         [0020]    load r 2 =memory[0x25000] 
         [0021]    r 3 =add r 1 , r 2   
         [0022]    end  
         [0023]    Initial memory:  
                                                       0x11000   0x5           0x15000   0x4           0x21000   0x3           0x25000   0x3                      
 
         [0024]    Output from Results Comparator  120 :  
         [0025]    . . .  
         [0026]    Thread 1  r 3 =add r 1 , r 2   
         [0027]    Error: register mismatch r 3 :  
                                                       RTL sim:   r3: 0x9           Arch sim:   r3: 0x6                      
 
         [0028]    In the above example, the test case initializes two threads. Each thread loads two values from memory and then adds them together. The “Output from Results Comparator” shows an example of what might appear if the results from the simulators  110 / 115  differed. In this case, the simulators disagree about the result of the addition operation. In looking at the initial memory, it can be seen that the architectural simulator appears to have the correct answer (0x3+0x3=0x6). It can also be seen that the answer produced by the hardware (RTL) simulator, (0x9), would be the correct answer if the addition used the Thread  0  values for r 1  and r 2  instead of the Thread  1  values. From this observation one might suspect, e.g., that the RTL is incorrect and that it used values from the Thread  0  registers instead of the thread  1  registers for the addition.  
         [0029]    [0029]FIG. 2 is a flowchart illustrating, at a high level, steps which may be performed in practicing one embodiment of the method of the present system. FIG. 3 is an example showing memory allocation for a multi-threaded test case for a target processor, i.e., the processor whose architecture is to be tested by simulation. Operation of the present system  100  is best understood by viewing FIGS. 1, 2, and  3  in conjunction with one another. As shown in FIG. 2, at step  203 , a probability generator  203  reads a probability input file  102  containing a structure for determining the memory range for each case in the test run. As described in detail below, a ‘line’ containing values for determining the memory segment size for each thread (and corresponding test case) is selected from the probability input file  102 . An example of a probability input file  102  and its function in generating test cases is set forth further below.  
         [0030]    At step  205 , probability generator  103  generates a starting address ‘S’, representing the starting memory location in memory  300  at which the first test case (Thread  1 )  301  will be loaded. Address S is the start of the segment of memory from which the first test case can choose addresses for memory operations. Memory  300  represents the total memory available to the target processor. At step  210 , the memory end address ‘E’ for the first thread  301  is generated by probability generator  103 . The size of the memory segment M for each of the threads  301 ( 1 )- 301 (N) is then determined by subtracting starting address ‘S’ from end address ‘E’, at step  215 . A given test case will only use some subset of the memory locations within the given range.  
         [0031]    At step  220 , a check is made to determine whether the total number of  
         [0032]    threads (N), each of size ‘M’, will fit into memory  300  between the memory starting address ‘S’ and the highest available memory address ‘H’, by determining the result of the following relation: 
         S+(M*N)&lt;H 
         [0033]    If the above relation is false (i.e., the total thread size exceeds the amount of available memory), then an error is reported at step  221 . If the above relation is true, the amount of available memory  300  is sufficient to contain all of the threads  301 ( 1 )- 301 (N), and therefore the merged test cases  105  will fit into available memory  300 . Then, at step  225 , test case generator generates thread  301 ( 1 ) for test case T=1. At step  230 , the loop shown in block  235  is performed to generate test cases  2  through N using threads  301 ( 2 )- 301 (N). As shown in block  235 , the size of the memory segment allocated to each test case T is determined, at step  236 , by calculating a starting address S and an end address E for each test case, as indicated above with respect to step  215 . Then, at step  237 , test case T is generated by test case generator  101 .  
         [0034]    At step  240 , test cases  1  through N are merged into a multi-threaded test case  105 . At step  245 , the multi-threaded test case  105  is run on an architectural simulator  110  and on an RTL functional model via a hardware simulator  115 . Each test case contains the initial state to set up before running the case and the instructions to be executed. This state is initialized before each simulation is run. The output from these two simulators is compared at step  250 , using results comparator  120 , and any difference in results is signaled as a failure to be debugged.  
         [0035]    The following example illustrates the generation of multiple test cases using a probability input file  102 . Exemplary contents of a probability input file  102 , which, in an exemplary embodiment, is used for determining the memory range for each case in a given test run, is shown below:  
         [0036]    Line  1  25% Address 0x100000 to 0x300000 (2 megabytes)  
         [0037]    Line  2  25% Address 0x100000 to 0x500000 (4 megabytes)  
         [0038]    Line  3  50% Address 0x100000 to 0x900000 (8 megabytes)  
         [0039]    Probability generator  103  selects one of the address segment lines in the file  102  based on the probabilities associated with the lines (step  203 ) and sets the memory start address S and end address E to the respective predetermined memory addresses in the selected line (steps  205  and  210 ). In an exemplary embodiment, a number from 0-99 is chosen randomly to determine which line is selected. In the above example, if the number selected is 0-24, Line  1  is used; if the number selected is 25-49, Line  2  is used; otherwise (if the number selected is 50-99), Line  3  is used. Over a large number of test runs, each line will be selected the percentage of the time specified in the probability input file  102 .  
         [0040]    In the present example, assume that Line  2  (the ‘4 megabytes’ line) is selected. Probability generator  103  uses the information in this line to determine a value for M, the common memory segment size for each of the threads  301 ( 1 )- 301 (N), by subtracting starting address S from end address E (step  215 ):  
         [0041]    S=0x100000  
         [0042]    E=0x500000  
         [0043]    M=0x500000−0x100000=0x400000  
         [0044]    Assume there are  4  threads (N=4), and that the highest memory address available is H=0x2000000. Before proceeding, a check is made to verify that the total number of threads (N) will fit into memory  300  between the memory starting address ‘S’ and the highest available memory address ‘H’, [i.e., S+(M*N)&lt;H] (step  220 ):  
         [0045]    0x100000+(0x400000*4)=0x1100000, which is less than 0x2000000.  
         [0046]    Next (step  225 ), the T=1 case is generated using the original values for S and E supplied by the probability generator.  
         [0047]    For threads T=2 to N, the values of S and E are adjusted by adding M to each value (block  235 ):  
         [0048]    T=2:  
         [0049]    S=0x100000+0x400000=0x500000  
         [0050]    E=0x500000+0x400000=0x900000  
         [0051]    T=3:  
         [0052]    S=0x500000+0x400000=0x900000  
         [0053]    E=0x900000+0x400000=0xd00000  
         [0054]    T=N (=4):  
         [0055]    S=0x900000+0x400000=0xd00000  
         [0056]    E=0xd00000+0x400000=0x1100000  
         [0057]    At this point, the block  235  loop is completed and the individual test cases are then merged into a single test case (step  240 ).  
         [0058]    While exemplary embodiments of the present invention have been shown in the drawings and described above, it will be apparent to one skilled in the art that various embodiments of the present invention are possible. For example, the configuration of system components shown in FIG. 1, as well as the specific set of steps shown in FIG. 2, and the examples used herein, should not be construed as limited to the specific embodiments described in this document. Modification may be made to these and other specific elements of the invention without departing from its spirit and scope as expressed in the following claim