Those of you who follow the Math Mutation facebook feed may have noticed that a book I co-authored was just released: "Formal Verification: An Essential Toolkit for Modern VLSI Design". Now, I need to caution you that this is not a Math Mutation book-- it's a technical book, aimed at electrical and computer engineers invovled in chip design. However, I do think Math Mutation listeners might have some interest in the core concepts on which the book is based. So, today I'll try to give you a brief summary of what Formal Verification is, and why it's worth writing a book about.
You're probably aware that modern computer chips are pretty complicated, by many measures the most complex devices ever created by man. For new ones coming out this year, the number of transistors is measured in the billions. So it makes sense to ask the question: how do we know these things will work? It would be prohibitively expensive to just build them first and then test them, so we need to discover and fix as many of the bugs as possible during the design stage. The process of finding these bugs is known as design validation. For many years, the most popular technology used in design validation has been simulation: testing how a software model of the design will behave for various sets of inputs.
Unfortunately, even a simple chip design has so many possible behaviors that there is no way to simulate them all. For example, suppose you are designing a simple integer adder: it will take 2 numbers as inputs, each expressed with 32 bits, or binary digits, which can each be 1 or 0. It will then output their sum. How many possible input sets are there for this design? Since each input has 32 bits, it has 2^32 possible values, thus resulting in 2^64 possible values for the pair. If we assume we have a fast simulator that can check 2^20 values per second, that means that we will need 2^44 seconds to check all possible values-- over half a million years. Most managers are not very happy when given a time estimate on this order to finish a project. And needless to say, most chips sold today are many orders of magnitude more complex than a simple adder.
So, what can we do to make sure our chip designs really will work? A variety of technologies have been developed over the past few decades to try to find a good set of example values to simulate. And they do seem to be doing a decent job: most electronic devices you buy today seem to more-or-less do what you want them to. But it still seems like there should be a better way to validate them: no matter how good you make it, simulation and related methods can never cover more than a tiny portion of your design's possible behaviors.
That's where formal verification comes in. The idea of formal verification is to take a totally different approach: instead of trying specific values for your design, why not just mathematically prove that it will always be correct? That way you don't have to worry about trying every possible test case. If there is a single set of values that would generate an incorrect result, your proof will fail, and you will know your design has a bug. If you do succeed in mathematically proving your design correct, then you know that there is no bug, and do not need to waste time simulating lots of testcases. In effect, formally verifying a design is equivalent to simulating all possible values. Many would argue that philosophically, this is really the "right" way to validate chip designs. You may have heard the famous Guindon quote, "Writing is nature’s way of letting you know how sloppy your thinking is." Formal Verification pioneer Leslie Lamport expanded on this with "Math is nature's way of letting you know how sloppy your writing is.", and later added "Formal math is nature's way of letting you know how sloppy your math is."
You've probably guessed by now that there has to be a catch. Formal verification is easier defined than done: when billions of transistors are involved, how do we even get our heads around the problem of creating mathematical proofs? It's far beyond what anyone could manually do, so to make this method a possibility, humans need to be aided by intelligent software that helps to automate proofs. To further complicate matters, it's also been shown that any formal verification system needs to internally solve what are known as NP-complete problems. If you remember our discussion way back in episode 13, an NP-complete problem is "provably hard" in some sense, meaning that no piece of computer software can ever solve it efficiently in 100% of cases. However, researchers have worked for many years to try to develop practical software that could utilize clever tricks to enable real proofs on a wide variety of actual industrial product designs.
The good news is that, in the past decade, formal technology has advanced to the point where it really is practical for an average design engineer to use in many cases. While formal verification software can't handle full multi-billion-transistor chip designs, it can often enable an engineer to create solid proofs on major sub-blocks that go into a chip design, massively reducing overall risk of bugs. Using formal verification software remains a bit of an art though. Due to the NP-completeness issue, the software may get stuck or progress very slowly: the user must often give subtle hints and suggest shortcuts to enable the proofs to complete. In addition, formal verification is a problem that is impossible to fully automate: no matter how good your software gets at proving stuff, a human still has to somehow be able to tell it what stuff to prove-- what is the overall intent of the design in the first place? Ultimately, someone has to carefully transfer the design intent from their human brain into a machine-readable form, and understand the possible limitations and pitfalls in this process. Sadly, computer software that directly plugs into your brain is probably still many years away, and even then I have the feeling that many of us think too sloppily to enable this level of verification directly.
Thus, the need for a Formal Verification book. While there have been many books on Formal Verification published over the past few decades, most have focused on internal algorithms that would be needed to develop the software involved. Our book is one of the first real practical manuals designed to help deesign and validation engineers use formal verification software on real-life design targets.
Anyway, that quick summary should give you an idea of what our new book is about. If you're in a field where you do chip design or something related, please visit our book's website at http://formalverificationbook.com, order a copy, and tell all your friends about it! If you're not in this field, the book probably won't make much sense to you, but hopefully you've still enjoyed this episode of the podcast.
And this has been your Math Mutation for today.
References:
- http://formalverificationbook.com
- https://en.wikipedia.org/wiki/Logic_simulation
- https://en.wikipedia.org/wiki/Formal_verification
- http://joeduffyblog.com/2009/01/09/tla-math-is-natures-way-of-letting-you-know-how-sloppy-your-writing-is/
- http://mathmutation.blogspot.com/2011/12/13-another-problem-for-millenium.html
