# inFact - Easier Than Sudoku?

### Mike Andrews

Posted Aug 12, 2009

Hi, I’m Mike Andrews, and I’m a Technical Marketing Engineer (TME) at Mentor Graphics, working on our Intelligent Testbench Automation (iTBA) product, namely inFact. The inFact tool employs rule-based (sometimes called graph-based) techniques to generate stimulus during testbench simulation, as a more efficient alternative to constrained random.

During a recent conversation about the complexity of creating the rule graphs that are the essential input of our tool, I half joked that it is like a logic puzzle, but easier than Sudoku. Of course, as the saying goes, many a true word is spoken in jest.
For a certain type of application, specifically the pseudo-random selection of values for the various fields of the test sequences that get sent to the testbench drivers, the analogy holds up rather well.

The puzzle is basically about numbers and ordering, and the solutions in many cases can be trivial, in others a little less so. In almost every case there is a very simple solution that provides value and could probably even be produced via perl-scripts or other simple forms of automation from the variable constraints and cover groups. Often there are other more complex solutions to the same puzzle, that further refine the efficiency of the stimulus, perhaps from a standard 10x improvement over constrained random up to 20x or 50x or even higher.

I had been working on just such a puzzle the day before and was quite pleased with the result. Discarding the obvious easy solution (I am supposed to be the expert after all), I started, much like Sudoku, with the low-hanging fruit, and quickly drew up the simple rules for a few of the variables and their associated cover groups. I then looked for trickier cases where the same variable was used in multiple cross-coverage groups, meaning that these may or may not have to appear in more than one place in the graph (this being the ‘ordering’ part of the puzzle). In some cases, different sub-ranges of one variable might be crossed with different sub-ranges of the others, adding a 3rd dimension to the relatively straightforward logic problem.

After about 45 minutes of (dare I say) puzzling ‘fun,’ with a couple of short bouts of head-scratching and occasional interruptions, I had a satisfactory solution that could potentially save a few more days or maybe weeks of simulation over the course of the verification project. The original trivial solution would probably have sufficed but, as usual, I found the process entertaining, since as a TME I am, of course, a geek in marketers’ clothing.

Later on, during a bus ride to the airport, the marketing side of me came up with an idea – maybe we could sell a cut-down version of the product within the quite lucrative computer game market. We have a quite colorful development environment, so we’re good on the graphics, and the game-play seems to be engaging for lovers of logic puzzles like me. I can picture bored engineers sitting in their airline seats trading their obsession for Solitaire or Minesweeper for our inFact puzzle-game (we might need a new product name for that market though – suggestions anyone?). We could also do an online version, or maybe even a Facebook app.

Once again the marketing side of my nature came to the fore – we need some hook to stop the game from being a short-lived fad. What we needed is a “High Score” concept to appeal to the competitive nature of our graph game addicts-to-be. A minor enhancement could calculate the statistical estimate of how many test sequences a constrained random stimulus generator would take to reach the same coverage goal, and then divide that by the number of required graph paths, and award the result as the user’s ‘score’ (representing their potential verification speed-up). Gamers could then ‘level-up’ as they raise their high score and get rewarded with more challenging puzzles. High scorers could be listed on a leader board for bragging rights (the current high score for the ‘constrained random : inFact’ ratio is around 250:1). Now all I need is a schedule from engineering…. and while I’m at it, let’s put the Wii port on the roadmap….