Automated method for testing cache

A method for determining all legal states of a control logic cache design, comprising the steps of:

• determining a list of all possible input transactions having an effect on state of the cache;
• determining an initial cache state;
• determining an initial sequence of input transactions to reach the initial cache state;
• generating a list of allowed states by associating the list of all possible input transactions with each legal cache state, starting with the initial cache state, said step of generating a list of allowed states including
• initializing a list of legal cache states with the initial cache state;
• initializing the sequence of input transactions for the initial state as the initial sequence of input transactions;
• initializing a list of search cache states with the initial cache state;
• applying each input transaction sequentially to a current search cache state until all input transactions of the list of input transactions have been applied to the current search cache state and
• if application of an input transaction to the current search cache results in a new cache state not in the list of legal cache states, then listing the resulting state in the list of legal cache states and the list of search cache states, and generating a sequence of input transactions for the new cache state from the sequence of input transactions for the current cache state and the current input transaction,
• until each input transaction has been applied to the current search cache state, thereupon setting a current search cache state as a next cache state in the search cache state list, and until all cache states in the search
• cache state list have had all input transactions applied thereto;
• and
• generating a sequence of input transactions for each allowed state capable of changing the state of the cache from the initial cache state to said allowed state.