Vasudevan receives Best Paper Award for verification algorithm

Often the gap between design specification and implementation seems small. A graphic designer is designing and simultaneously creating the finished product. A fashion couturier is taking measurements, making sketches and patterns, and then, voila!, the finished dress is ready. In electrical and computer engineering, however, specification and implementation can seem like remote and isolated processes. 

“I was talking to a collaborator [in industry] recently who said that after the design phase is over, they spend about eight-and-a-half to 10 months checking to see if what they designed is correct, validating, and debugging,” said Assistant Professor Shobha Vasudevan.

Vasudevan and her graduate students focus on expediting this debugging—or verification—process. GoldMine, a research software tool developed in her lab, automates part of the process and is used at multinational technology companies like IBM, Qualcomm, Texas Instruments, and Advanced Micro Devices. 

The latest development on this tool—an algorithm known as coverage-guided mining—provides significant new efficiencies, and that work garnered Vasudevan and her team the Best Paper Award at the 27th International Conference on VLSI Design, which was held in Mumbai earlier this year.

“This is an algorithm that had immediate impact in industry,” Vasudevan said. “It’s an academic tool, but  it performs better than commercially available software solutions.”

In some ways, the new algorithm is like a gold miner’s sieve, filtering out extraneous coding properties—known as assertions—and saving only a smaller set of high-quality assertions, like gold chips being separated from sediment.

The coverage-guided mining algorithm automatically compares the existing assertions against the intended design parameters, and it retains only those that correlate, based on a set threshold. Their results show that the assertions are both expressive—meaning they accurately reflect the design intent—and also concise, making them easier for engineers to assess.

Many products, like a cellphone or tablet, are composed of millions, if not billions of transistors. Hence their logic-level design is extremely complex, heterogeneous and massive. This magnitude is seemingly impossible for a team of engineers to parse through, manually crafting the most appropriate assertions, without encumbering and slowing the design process. Vasudevan’s new algorithm is an improved means of automating this process, so that the engineers can focus their time on the most relevant design issues.

At most companies, according to Vasudevan, about seven out of 10 engineers on a design team do verification work, while the other three attend to the actual design. As our cellphones and tablets have become smarter and faster, sleeker and lower power, numerous design hurdles have appeared that require a more sophisticated verification procedure, more time invested, and more manpower.

“There is no free lunch here,” Vasudevan said of these new products. “In exchange for the plethora of desirable features is the tradeoff of a very complex design that we have no means to verify. We design systems that we do not know how to check and validate. The more complicated the design, the greater the verification challenge." 

Because GoldMine is used at major technology companies, the new coverage-guided algorithm has already been successfully implemented in commercial applications with excellent results. One of the student authors of the award-winning paper, Lingyi Liu (PhD ’13), graduated late last year and has joined Synopsys, the electronic design automation company, where he is working on state-of-the-art verification technologies. 

The other authors include graduate students David Sheridan and Hyungsul Kim, from ECE and Computer Science at Illinois, respectively. Debjit Pal, another graduate student from Vasudevan’s lab, presented the paper at the conference.

“The power of the idea inspired my students and myself to work very hard on it,” Vasudevan said. “This [award] is a testimony to my students’ hard work. Without them, none of these ideas would see the light of day.” 

Overall, more than 700 papers were submitted to VLSI Design 2014, with about 150 selected for the conference.

“The best paper award means a lot to me because ... it’s a recognition from my community for GoldMine,” Vasudevan said. “It’s gratifying that something we built from ground up ... from the first line of code ... [is] having a real impact, and it’s encouraging that the community thinks it is a prominent piece of work.”

For consumers, anxious for the next smartphone upgrade or, perhaps, for a new electric vehicle model, the efficiencies offered by GoldMine and this new algorithm herald even faster developments. It means less time spent before the ideas in the design room become products in hand.