Device, System and Method of Verification of Address Translation Mechanisms

Abstract

Device, system and method of verification of address translation mechanisms. For example, an apparatus for testing an address translation mechanism of a design-under-test, the apparatus including: a test generator to receive a specification of at least one address translation table, and to generate one or more constraint-satisfaction-problem projectors over a plurality of attributes of said address translation table.

1 . An apparatus for testing an address translation mechanism of a design-under-test, the apparatus comprising:
 a test generator to receive a specification of at least one address translation table, and to generate one or more constraint-satisfaction-problem projectors over a plurality of attributes of said address translation table.   
     
     
         2 . The apparatus of  claim 1 , wherein the test generator is to generate a first constraint-satisfaction-problem projector to project over attributes of a first address translation table specification, and to generate a second, different, constraint-satisfaction-problem projector to project over attributes of a second, different, address translation table specification. 
     
     
         3 . The apparatus of  claim 1 , wherein the specification comprises:
 information indicating a format of a translation table entry;   a projector implementing a match rule;   a projector implementing a translation rule; and   a projector between a location of said translation table entry and a content of said translation table entry.   
     
     
         4 . The apparatus of  claim 1 , wherein the constraint-satisfaction-problem projector comprises a constraint-satisfaction-problem projector over at least:
 a first variable representing an input address of said address translation table;   a second variable representing an output address of said address translation table;   a third variable representing availability of translation of said input address; and   a fourth variable representing a size of translation region.   
     
     
         5 . The apparatus of  claim 4 , wherein if a value of the third variable indicates availability of translation of said input address, the constraint-satisfaction-problem projector further comprises a constraint-satisfaction-problem projector over at least:
 a fifth variable representing a location of a translation table entry usable for translation said input address; and   a sixth variable representing a content of the translation table entry usable to translate said input address.   
     
     
         6 . The apparatus of  claim 1 , wherein the test generator is to extract from said specification:
 a first variable representing an input address of said address translation table;   a second variable representing an output address of said address translation table;   a third variable representing availability of translation of said input address;   a fourth variable representing a size of translation region;   a fifth variable representing a location of a translation table entry usable for translation said input address; and   a sixth variable representing a content of the translation table entry usable to translate said input address,   
       wherein the test generator is to apply a pre-defined projector generation algorithm to generate said one or more constraint-satisfaction-problem projectors, 
       wherein the test generator is to solve one or more constraint-satisfaction-problems to generate a test case for said design-under-test. 
     
     
         7 . A method for testing an address translation table of a design-under-test, the method comprising:
 setting a match parameter indicating whether a translation table entry is able to correctly translate an input address;   synchronizing entry fields of said address translation table with entry data of said address translation table;   if the synchronization succeeds and the match parameter is not false, running a match relation function;   if, after running said match relation function, said match parameter is not false, running a transformation relation function; and   if substantially no domains of the address translation table are modified by said transformation relation function, determining whether a previously-initialized set of translation table entries is consistent with a current match status.   
     
     
         8 . The method of  claim 7 , further comprising:
 generating a constraint-satisfaction-problem over substantially all attributes of said address translation table.   
     
     
         9 . The method of  claim 8 , further comprising:
 solving said constraint-satisfaction-problem to generate a test case for said design-under-test.   
     
     
         10 . The method of  claim 7 , wherein determining comprises:
 determining which sets of translation table entries are usable for address translation;   determining that one or more translation table entries are inconsistent with one or more constraints associated with said address translation table; and   removing said one or more inconsistent translation table entries.   
     
     
         11 . The method of  claim 10 , further comprising:
 removing one or more empty sets of translation table entries.   
     
     
         12 . The method of  claim 11 , further comprising:
 removing substantially all values of variables that no sets of translation table entries exist that are able to translate them.   
     
     
         13 . The method of  claim 12 , further comprising:
 if substantially all addresses have a translation, setting said match parameter to be true.   
     
     
         14 . The method of  claim 12 , further comprising:
 if substantially all addresses do not have a translation, setting said match parameter to be false.   
     
     
         15 . A computer program product comprising a computer-useable medium including a computer-readable program, wherein the computer-readable program when executed on a computer causes the computer to:
 receive a specification of at least one address translation table, and generate one or more constraint-satisfaction-problem projectors over a plurality of attributes of said address translation table.   
     
     
         16 . The computer program product of  claim 15 , wherein the computer-readable program causes the computer:
 to generate a first constraint-satisfaction-problem projector to project over attributes of a first address translation table specification, and   to generate a second, different, constraint-satisfaction-problem projector to project over attributes of a second, different, address translation table specification.   
     
     
         17 . The computer program product of  claim 15 , wherein the specification comprises:
 information indicating a format of a translation table entry;   a projector implementing a match rule;   a projector implementing a translation rule; and   a projector between a location of said translation table entry and a content of said translation table entry.   
     
     
         18 . The computer program product of  claim 15 , wherein the constraint-satisfaction-problem projector comprises a constraint-satisfaction-problem projector over at least:
 a first variable representing an input address of said address translation table;   a second variable representing an output address of said address translation table;   a third variable representing availability of translation of said input address; and   a fourth variable representing a size of translation region.   
     
     
         19 . The computer program product of  claim 18 , wherein if a value of the third variable indicates availability of translation of said input address, the constraint-satisfaction-problem projector further comprises a constraint-satisfaction-problem projector over at least:
 a fifth variable representing a location of a translation table entry usable for translation said input address; and   a sixth variable representing a content of the translation table entry usable to translate said input address.   
     
     
         20 . The computer program product of  claim 15 , wherein the computer-readable program causes the computer:
 to extract from said specification:
 a first variable representing an input address of said address translation table; 
 a second variable representing an output address of said address translation table; 
 a third variable representing availability of translation of said input address; 
 a fourth variable representing a size of translation region; 
 a fifth variable representing a location of a translation table entry usable for translation said input address; and 
 a sixth variable representing a content of the translation table entry usable to translate said input address, 
   
       to apply a pre-defined projector generation algorithm to generate said one or more constraint-satisfaction-problem projectors, and 
       to solve one or more constraint-satisfaction-problems to generate a test case for said design-under-test.