Recent grads develop revolutionary software

When Conor Madigan '00 and Matthew Moskewicz '00 began working on electrical engineering professor Sharad Malik's research team last year, they did not expect to develop technology that would make companies like Intel drool.

But that is exactly what these recent graduates — then seniors — did when they designed software that examines computer chips in just hours when competing software takes months.

"I am hugely proud of them," Malik said. "This [breakthrough] is amazing. I wish it would happen more often."

The software, named Chaff, solves Boolean satisfiability problems — multivariable puzzles that arise in many mathematical and real-world situations — 10 to 100 times faster than previous methods. In the world of computer chips, such technology is invaluable in chip verification, the process of testing chip performance and fallibility.

Before Chaff, companies could only perform partial tests of the chips because the investigations were too time consuming, Malik said. And the incomplete examinations were not a guarantee that the chips were foolproof.

Now, thanks to Madigan and Moskewicz's software, the chip-making process will be faster and more reliable, and the chips are certain to function as expected.

"With this [software], we'll be reducing the amount of time it takes to develop chips by one-half," Madigan said.

Madigan and Moskewicz did not expect to create new software when they first began their work with Malik. In fact, though Moskewicz's work on the research team served as his independent work, Madigan was actually working with a different professor — he spent only his free time tackling the problem.

The seniors soon realized, however, that they had a chance to make quite a contribution to the already widely studied field.

"We started to read papers [on Boolean satisfiability] . . . and then we started to write our own code," Madigan said. "It was a surprise to us to find that we could write software as fast as the others already developed."

As they became thoroughly familiar with the problem, the two seniors said they were optimistic enough to ask Malik if they could continue their work during the summer. Malik encouraged them to carry on.

It was over the summer that Madigan and Moskewicz finished their software. Since then, Madigan, now a graduate student at the Massachusetts Institute of Technology; Moskewicz, a computer science doctoral student at the University of California-Berkeley and Malik, have been assailed by e-mails from companies asking for the technology.

Get the best of the ‘Prince’ delivered straight to your inbox. Subscribe now »

Malik is pursuing the possibility of a software patent through the University Office of Technology Licensing, though he said they are expensive and hard to police.

"There's not anything that prevents big companies like Intel . . . from using our product internally for verification," Moskewicz explained. "And we can't even know they're using it. It's irritating."

The first detailed paper on Chaff will be released this June at the 38th Design Automation Conference.