Last week was the EDAC Kauffman Award dinner. One minor advantage of being a blogger is that I got invited along as press. “Will blog for food”. This year’s winner was Professor Randal Bryant, usually just known as Randy Bryant.
I knew of Randy as the inventor of switch level simulation with a tool called MOSSIM. Up until that point, all simulation of semiconductor had been done using Spice type algorithms, worrying about the transfer functions of the transistors. But with the coming of Mead and Conway, computer scientists were starting to want a much simpler model of the world so that they could apply programming techniques to design. Treat transistors as switches that were either on or off and with a unit delay (all transistors turned on and off at the same speed). MOSSIM was the first of these so-called switch level simulators developed in about 1980. At VLSI we developed a similar tool, called VSIM. Later, the switch model would be enhanced to add timing (and, surprise, ours was called TSIM). Funny now to realize that in the early 1980s IC design was largely done without timing, using Spice for paths that looked like they might be important.
Randy Bryant was also the inventor of BDDs, binary decision diagrams. BDDs are a very efficient representation of combinational logic and are one of the key technologies underlying logic optimization and hence underlying both synthesis and formal verification. The advantage of BDDs is that despite being a fairly compressed representation of the circuit, many logic operations can be done efficiently directly on the BDD, without needing to expand the representation into something less space efficient and then recompress it again afterwards. They are not good at representing everything; multipliers are notorious for exploding BDD size but they are hard to represent period.
Randy first published his ideas in 1986. An amazing fact that came to light at the Kauffman award dinner was that his paper just kept getting more and more citations. Usually a paper generates a flurry of interest soon after publication and then it dies down. But 15 years after publication for most of the early part of this decade, Randy’s paper wasn’t just the most cited paper in EDA, it was the most cited paper in the whole of computer science.
The Kauffman Award is awarded based on the impact that individuals have had on EDA. The ideas in MOSSIM, while very important in the early 1980s have dwindled in importance since as simulation has moved up to higher levels. But given that every synthesis and formal verification tool relies heavily on BDDs over 20 years after their conception I think that the “impact” is unarguable.