inFact - Easier Than Sudoku?
inFact - Easier Than Sudoku?
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….
More Blog Posts
- Part 1: The 2012 Wilson Research Group Functional Verification Study
- Those nasty wire’s and reg’s in Verilog
- Getting AMP’ed Up on the IEEE Low-Power Standard
- Prologue: The 2012 Wilson Research Group Functional Verification Study
- Even More UVM Debug in Questa 10.2
- IEEE Approves New Low Power Standard
- Verification Horizons DVCon Issue Now Available
- Get your IEEE 1800-2012 SystemVerilog LRM at no charge
- IEEE 1800™-2012 SystemVerilog Standard Is Published
- See You at DVCon 2013!
- May, 2013
- April, 2013
- March, 2013
- February, 2013
- January, 2013
- December, 2012
- November, 2012
- October, 2012
- July, 2012
- June, 2012
- May, 2012
- March, 2012
- February, 2012
- January, 2012
- December, 2011
- November, 2011
- October, 2011
- September, 2011
- July, 2011
- June, 2011
- Intelligent Testbench Automation Delivers 10X to 100X Faster Functional Verification
- Part 9: The 2010 Wilson Research Group Functional Verification Study
- Verification Horizons DAC Issue Now Available Online
- Accellera & OSCI Unite
- The IEEE's Most Popular EDA Standards
- UVM Register Kit Available for OVM 2.1.2
- May, 2011
- April, 2011
- User-2-User’s Functional Verification Track
- Part 7: The 2010 Wilson Research Group Functional Verification Study
- Part 6: The 2010 Wilson Research Group Functional Verification Study
- SystemC Day 2011 Videos Available Now
- Part 5: The 2010 Wilson Research Group Functional Verification Study
- Part 4: The 2010 Wilson Research Group Functional Verification Study
- Part 3: The 2010 Wilson Research Group Functional Verification Study
- March, 2011
- February, 2011
- January, 2011
- December, 2010
- October, 2010
- September, 2010
- August, 2010
- July, 2010
- June, 2010
- The reports of OVM’s death are greatly exaggerated (with apologies to Mark Twain)
- New Verification Academy Advanced OVM (&UVM) Module
- The Dog That Didn’t Bark
- DAC: Day 1; An Ode to an Old Friend
- UVM: Joint Statement Issued by Mentor, Cadence & Synopsys
- Static Verification
- OVM/UVM at DAC 2010
- DAC Panel: Bridging Pre-Silicon Verification and Post-Silicon Validation
- Accellera’s DAC Breakfast & Panel Discussion
- May, 2010
- Easier UVM Testbench Construction – UVM Sequence Layering
- North American SystemC User Group (NASCUG) Meeting at DAC
- An Extension to UVM: The UVM Container
- UVM Register Package 2.0 Available for Download
- Accellera’s OVM: Omnimodus Verification Methodology
- High-Level Design Validation and Test (HLDVT) 2010
- New OVM Sequence Layering Package – For Easier Tests
- OVM 2.0 Register Package Released
- OVM Extensions for Testbench Reuse
- April, 2010
- SystemC Day Videos from DVCon Available Now
- On Committees and Motivations
- The Final Signatures (the meeting during the meeting)
- UVM Adoption: Go Native-UVM or use OVM Compatibility Kit?
- UVM-EA (Early Adopter) Starter Kit Available for Download
- Accellera Adopts OVM 2.1.1 for its Universal Verification Methodology (UVM)
- March, 2010
- February, 2010
- January, 2010
- December, 2009
- A Cliffhanger ABV Seminar, Jan 19, Santa Clara, CA
- Truth in Labelling: VMM2.0
- IEEE Std. 1800™-2009 (SystemVerilog) Ready for Purchase & Download
- December Verification Horizons Issue Out
- Evolution is a tinkerer
- It Is Better to Give than It Is to Receive
- Zombie Alert! (Can the CEDA DTC “User Voice” Be Heard When They Won’t Let You Listen)
- DVCon is Just Around the Corner
- The “Standards Corner” Becomes a Blog
- I Am Honored to Honor
- IEEE Standards Association Awards Ceremony
- ABV and people from Missouri...
- Time hogs, blogs, and evolving underdogs...
- Full House – and this is no gamble!
- Welcome to the Verification Horizons Blog!
- November, 2009
- October, 2009
- September, 2009
- August, 2009
- July, 2009
- May, 2009
RT @CalyptoDesign: Read Shawn McCloud's article "Raising the Bar for Power Optimization" in Chip Design. #DAC50 #Power #EDA #SemiEDA http:/… about 4 hours ago
RT @dave_59: What's the deal with those wire's and reg's in #Verilog and #SystemVerilog. http://t.co/520olnyog4 about 4 hours ago
What's the deal with those wire's and reg's in #Verilog and #SystemVerilog. http://t.co/520olnyog4 7:20 AM May 13
My DAC moment http://t.co/LA5S97gDQU #SemiEDA #Verilog 2:57 PM May 9