DNB*LAN

Digital Logic Test Set Reduction

This project tried to find new heuristic methods to generate minimal test sets with high percentages of Fault Coverage (FC) for testing digital circuits. We used the Expected State Action Reward State Action (E-SARSA) Reinforcement Learning (RL) algorithm to test five heuristic methods against the International Symposium of Circuits and Systems (ISCAS) 1986 C17 and C432. Descriptions of these benchmark circuits may be found here. The five actions our RL agent were allowed to make were the following

Random

Random string of input bits.

Single, Primary Input Gate Statistics

This method will first select a previously tested vector with the highest Success Factor (SF), and then modifies a random group of n-bits to change the output for the most common n-bit gate connected to our circuit's Primary Inputs (PIs) (eg. if a random group of 4 bits will make a NAND gate output 1, and 4-input NANDS are the most common gate connected to the circuits PIs, then we modify those 4 bits such that a NAND will output a 0).

All, Primary Input Gate Statistics

Same as the previous action, but now we perform this modification to all groups of n-bits in a previously tested vector with the highest SF

Single, Circuit Gate Statistics

This is the same as “Single, Primary Input Gate Statistics,” but now we consider the most common gate in the entire circuit rather than just what's connected to our PIs.

All, Circuit Gate Statistics

Same as “Single, Circuit Gate Statistics,” but now we perform this modification to all groups of n-bits in a previously tested vector with the highest SF.

Where SF = additional FC achieved * log(t), here t is the number of test vectors tested for that episode. Test vectors with the highest SF chosen to be modified were "parent vectors" and the modified vector was a "child vector." The current SF value was assigned to the child vector and the parent SF was updated by averaging in the child's SF. The reward function was -1 for each vector, to encourage the agent to find a minimal path to our FC threshold.

Some quick notes on the images shown:

• Quick analysis shows how even the ISCAS86 circuits may be infeasible to thoroughly test on low power laptops, taking 50 hours for C432.
• As we introduce more agents to smooth the state action pair values, we see that all the actions start to become the same value. This implies that all actions are equally as effective, hence our heuristics are no better than random.
• Higher episode counts begin to favor higher total FC state action pairs, which makes sense as higher total FC means the agent is closer to meeting the total FC threshold.
• The agent found a test set of 7 for C17 and 55 for C432.