Modeling language and method for address translation design mechanisms in test generation

• US 7,370,296 B2
• Filed: 05/25/2004
• Issued: 05/06/2008
• Est. Priority Date: 05/25/2004
• Status: Expired due to Fees

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Emek, Roy, Katz, Yoav, Koyfman, Anatoly, Vinov, Michael, Adir, Allon
• Primary Examiner(s): Dinh; Paul
• Assistant Examiner(s): Doan; Nghia M.
• Application Number:
  US10/853,041
• Publication Number:
  US 20050278702A1
• Time in Patent Office: 1,442 Days
• Field of Search: 716 3- 5, 716/17, 716/18, 716/1, 702117-123, 703/1, 703/2, 703 13- 22, 712225-227, 717124-140
• US Class Current: 716/104
• CPC Class Codes: G06F 11/2257 using expert systems
• CPC Class Codes: G06F 11/263 Generation of test inputs, e.g. test vectors, patterns or sequences ; with adaptation of the tested hardware for testability with external testers

Abstract

Methods and systems are disclosed that enhance the ability of a test generator to automatically deal with address translation in a processor design, and without need for creating specific code. A model of the address translation mechanism of a design-under-test is represented as a directed acyclic graph and then converted into a constraint satisfaction problem. The problem is solved by a CSP engine, and the solution used to generate test cases for execution. Using the model, testing knowledge can be propagated to models applicable to many different designs to produce extensive coverage of address translation mechanisms.

Claims

1. A method for testing an address translation mechanism of a design-under-test comprising the steps of:

modeling said address translation mechanism as a directed acyclic graph having nodes and edges that connect said nodes, wherein said nodes represent stages of said mechanism, and said edges represent state transitions between said stages, wherein in said address translation mechanism a virtual address is translated into a physical address, wherein modeling said address translation mechanism comprises establishing tables that are linked to said nodes by table edges, and entering match conditions in entries of said tables, wherein satisfaction of one of said match conditions causes one of said state transitions to occur via a designated one of said table edges, and generating testing knowledge relevant to test programs for a second design-under-test by entering in at least a portion of said tables close match events comprising additional conditions that differ from said match conditions wherein satisfaction of said additional conditions do not satisfy said match conditions;

formulating a constraint satisfaction problem from said directed acyclic graph by creating a Boolean variable for each of said nodes and said edges, wherein said Boolean variable indicates if a respective one of said nodes or said edges is used in one of said state transitions;

solving said constraint satisfaction problem so as to generate a test case for said design-under-test; and

executing said test case in said design-under-test.

2. The method according to claim 1, further comprising the step of associating multi-access architectural rules of said design-under-test with said directed acyclic graph for traversal thereof, wherein said multi-access architectural rules specify a plurality of access methods to a memory location.

3. The method according to claim 1, further comprising the step of establishing translation tables that are linked to said edges.

4. The method according to claim 1, further comprising the step of establishing multi-access architectural rules for traversal of said directed acyclic graph, wherein said multi-access architectural rules specify a plurality of access methods to a memory location.

5. The method according to claim 4, wherein said multi-access architectural rules are implemented as logical tables.

6. The method according to claim 1, wherein said step of generating testing knowledge is performed by value partitioning.

7. The method according to claim 1, wherein said step of generating testing knowledge is performed by memorizing values of modeled attributes that were produced in a previous constraint satisfaction problem.

8. The method according to claim 1, wherein said step of generating testing knowledge is performed by biasing at least a portion of said nodes and said edges of said directed acyclic graph.

9. The method according to claim 1, further comprising the step of entering transformations in said tables that correspond to different ones of said match conditions.

10. A computer software product, including a computer-readable medium in which computer program instructions are stored, which instructions, when read by a computer, cause the computer to perform a method for testing an address translation mechanism of a design-under-test comprising the steps of:

modeling said address translation mechanism as a directed acyclic graph having nodes and edges that connect said nodes, wherein said nodes represent stages of said mechanism, and said edges represent state transitions between said stages, wherein in said address translation mechanism a virtual address is translated into a physical address, wherein modeling said address translation mechanism comprises establishing tables that are linked to said nodes by table edges, and entering match conditions in said tables, wherein satisfaction of one of said match conditions causes one of said state transitions to occur via a designated one of said table edges, and generating testing knowledge relevant to test programs for a second design-under-test by entering in at least a portion of said tables close match events comprising additional conditions that differ from said match conditions wherein satisfaction of said additional conditions do not satisfy said match conditions;

formulating a constraint satisfaction problem from said directed acyclic graph by creating a Boolean variable for each of said nodes and said edges, wherein said Boolean variable indicates if a respective one of said nodes or said edges is used in one of said state transitions;

solving said constraint satisfaction problem so as to generate a test case for said design-under-test; and

executing said test case in said design-under-test.

11. The computer software product according to claim 10, wherein said computer is further instructed to perform the step of establishing multi-access architectural rules for traversal of said directed acyclic graph, wherein said multi-access architectural rules specify a plurality of access methods to a memory location.

12. The computer software product according to claim 10, wherein said computer is further instructed to perform the step of establishing translation tables that are linked to said edges.

13. The computer software product according to claim 10, wherein said computer is further instructed to perform the step of establishing multi-access architectural rules for traversal of said directed acyclic graph, wherein said multi-access architectural rules specify a plurality of access methods to a memory location.

14. The computer software product according to claim 13, wherein said multi-access architectural rules are implemented as logical tables.

15. The computer software product according to claim 10, wherein said step of generating testing knowledge is performed by value partitioning.

16. The computer software product according to claim 10, wherein said step of generating testing knowledge is performed by memorizing values of modeled attributes that were produced in a previous constraint satisfaction problem.

17. The computer software product according to claim 10, wherein said step of generating testing knowledge is performed by biasing at least a portion of said nodes and said edges of said directed acyclic graph.

18. The computer software product according to claim 10, wherein said computer is further instructed to perform the step of entering transformations in said tables that correspond to different ones of said match conditions.

19. A verification system for an address translation mechanism of a design-under-test comprising:

a processor operative to access a declarative model of said address translation mechanism, wherein a virtual address is translated into a physical address, said address translation mechanism being represented as a directed acyclic graph having nodes and edges that connect said nodes, wherein said nodes represent stages of said mechanism, and said edges represent state transitions between said stages corresponding to respective ones of said nodes being connected by said edges, wherein said processor is operative to apply multi-access architectural rules for traversal of said directed acyclic graph with said nodes, and said multi-access architectural rules specify a plurality of access methods to a memory location, wherein said model of said address translation mechanism by comprises tables that are linked to said nodes by table edges, match conditions being entered in said tables, wherein satisfaction of one of said match conditions causes one of said state transitions to occur via a designated one of said table edges, and a memory holding testing knowledge relevant to test programs for a second design-under-test, said testing knowledge being automatically generated by said verification system using said declarative model by including in at least a portion of said tables close match events comprising additional conditions that differ from said match conditions wherein satisfaction of said additional conditions do not satisfy said match conditions;

said processor being operative to formulate a constraint satisfaction problem from said directed acyclic graph by creating a Boolean variable for each of said nodes and said edges, wherein said Boolean variable indicates if a respective one of said nodes or said edges is used in one of said state transitions; and

said processor being operative for solving said constraint satisfaction problem to generate a test case for said design-under-test and to output said test case for execution in said design-under-test.

20. The verification system according to claim 19, wherein said processor is operative to establish said multi-access architectural rules so as to govern different translations.

21. The verification system according to claim 20, wherein said multi-access architectural rules are implemented as logical tables.

22. The verification system according to claim 19, wherein said testing knowledge is generated by value partitioning.

23. The verification system according to claim 19, wherein said testing knowledge is generated by memorizing values of modeled attributes that were produced in a previous constraint satisfaction problem.

24. The verification system according to claim 19, wherein said testing knowledge is generated by biasing at least a portion of said nodes and said edges of said directed acyclic graph.

25. The verification system according to claim 19, wherein said tables include transformation entries that correspond to different ones of said match conditions.