Cool Verification

The Relevance of Formal Methods

2009-10-20T22:13:24-05:00

In a fascinating (to me) twist of fate, I will be moderating a panel on the “next big thing” in formal methods at FMCAD 2009 in Austin, Texas. The panel, entitled “What will be the next breakthrough solutions in formal?” is being held from 11:50-14:00 on Wednesday, November 18, and is made up of four distinguished panelists:

Harry Foster, Mentor Graphics
Ziyad Hanna, Jasper Design Automation
Kevin Harer, Synopsys
Axel Scherer, Cadence

Those of you who have been reading Cool Verification for awhile will note that I have never really discussed the topic of formal methods on this blog. Truth is, I’ve yet to come across a situation on a project where I needed to use formal to get the job done. My theory is that there are a couple of issues preventing wide-spread adoption of formal tools in a standard verification flow. First, the impression I get is that using formal well requires special expertise to write appropriate properties, partition the design, and interpret the results of the tools. Second, the fact that you need special tools at all. In other words, the fact that I need a separate tool in my flow other than Questasim, VCS, or IUS (not to mention a separate license) makes it difficult for someone to try out formal techniques outside the tool flow of a typical project.

During the panel I plan to ask panelists about just such issues, plus several other questions proposed by thoughtful engineers just like you on the Google Moderator site set up for just this purpose. In fact, I’d like to request your assistance. If you have a question you’d like to see asked of one of the panelists please submit it (or vote on your favorites) via the Google Moderator site or by mailing me directly at jl at coolverification dot com.

I’m also quite interested to hear any stories readers may have with respect to the adoption (or lack thereof) of formal tools in your respective companies and current projects. There are several types of formal tools out there… Any types of tools you’ve had great success with in particular? Or great failures? Does the choice of formal technique heavily depend on the application domain in question? What do you think the EDA vendors need to address in tool functionality/usability in order for you to consider adopting formal more broadly?

And of course, if you’re planning on being in Austin for FMCAD please let me know!

The Past, Present and Future of the Design Automation Conference

2009-08-03T13:38:00-05:00

It’s over. After weeks of preparation (on my part, a year on the part of countless others), and a week of staying up late then getting up early, the 46th Annual Design Automation Conference has finally come to a close. One of the main highlights of the conference was the Synopsys-hosted Conversation Central interactive forum on social media. I also enjoyed my opportunity to participate on a Pavilion Panel on “Seeking the Holy Grail of Verification Coverage Closure”, to present the new VMM 1.2 updates in the Synopsys theater, and to give a presentation entitled “Zero to Sequences in 30 Minutes” in the OVM World booth. Special thanks to all of you who spent time talking with me on Monday and Tuesday sharing your thoughts with me on that topic to help me prepare for the panel. And of course, there was the ever-enjoyable Denali Party (click here for pictures)!

Throughout the conference though, I had a nagging suspicion that I was missing some perspective on where we’ve been as an EDA industry, where we are currently, and where we’re going in the future. This being only my third DAC, it wasn’t clear to me if anyone was around from the earlier days who would be able to help me fill a gap in my industry knowledge. After asking around, I quickly realized that I needed to speak with Marie and Pat Pistilli, founders of the aptly named MP Associates and organizers of the very first DAC back in 1964 (and every DAC since). At the time, DAC was, according to Pat actually called SHARE, which stood for the “Society to Help Avoid Redundant Effort”.

Pat Pistilli, MP Associates

I was able to arrange a time to meet with Pat on Wednesday evening before the DAC party. I wasn’t really sure what to expect, and Google wasn’t much help. So naturally, I asked Pat to tell me about his background and how he ended up founding DAC. In the late 50s Pat was working at Bell Laboratories on a project called “Safeguard”. (For info on Safeguard, check out the ever-useful Wikipedia. Also, this site dedicated to the Mickelson Safeguard Complex contains a list of references that appear to be relevant). The idea of the project was to create a computer that could quickly identify which Soviet ICBMs were duds and which were real during a nuclear attack.

Building a computer with enough horsepower to handle this important task was a largely manual effort at the time. It also took up quite a bit of space (4 rooms, according to Pat)! First, engineers would create schematics for a module describing how a circuit should behave. Several modules were eventually placed together in a “pizza tray” after appropriate placement was determined. Unlike today’s modern design environments where we can build test benches or use formal tools to verify our designs, engineers at the time relied on design reviews with peers to find issues in schematics before they were sent off to another team to be placed and routed. After the schematics were developed, it took another 16-18 weeks to create an individual board, followed by another 10 weeks of debug. Ouch! Besides the obvious problem of not being able to run simulations in advance of actually building the device, there was the problem of applying design rules to the placement and routing of individual modules. With actual wires crisscrossing the board one can imagine the problems that could occur if rules were not followed.

The now-obvious question that occurred to Pat and engineers at other companies at the time was, “What if a computer program could be written to automate the work currently being done by hand?” In theory, the computer ought to be able to do a better job, if only it was possible to enter the design into the computer in the first place.

Pat used an IBM 704 mainframe computer (see user’s guide here, complete with the BESYS operating system) and worked with a team to develop a program written in Fortran to create the automated place and route tool BLADES – the Bell Labs Automated Design System. BLADES eventually helped cut the time spent creating and debugging a board from 6 months to 6 weeks, and included a pseudo-language to allow schematics to be described in a way readable by computer.

BLADES took about 4 hours to do an automated place and route, including:

1.5 hours to do 800-2000 placement iterations
1.5-2 hours to do the routing for the chosen placement

During his work on creating BLADES, Pat “became obsessed with the whole concept of [Electronic Design Automation].” As circuits were generated by BLADES the results were saved on tapes. Those tapes eventually and serendipitously made up a component library.

According to Pat, he met regularly with Joe Behar, a mathematician from IBM who was working on similar problems from a much different perspective. At some point, they realized it would be useful to get together with a larger group of engineers who were also working on the same problem. Pistilli and Behar organized a Birds of a Feather session at the 1962 IEEE workshop in Miami [1] which lead to the creation of the first DAC in 1964. According to Pistilli, he was at a planning meeting for the first DAC on the day Kennedy was assassinated (November 22, 1963). Marie and Pat put up the money for the first DAC and went on to host 136 attendees (making a profit in the process). By 1966 in New Orleans, there were approximately 650 attendees [2]. By comparison, the largest DAC to date was the 1998 DAC in San Francisco, which had 21,659 total attendees [1].

Other interesting facts:

1968 was the first year DAC had sponsors.
The 19th DAC in 1982 was the first with exhibits.
Of the first 7 companies exhibiting at DAC, only Mentor Graphics and HP are still around with their original names.
Marie and Pat founded MP Associates to run the conference. Today, their son-in-laws Kevin Lepine and Lee Wood are co-presidents of the company.
MP Associates organized the first Euro-DAC in 1992, which later merged with Euro-ASIC and the European Design and Test Conference (ED&TC) to form Design Automation and Test in Europe (DATE) conference. Euro-DAC was modeled it after DAC. MP Associates does not organize the conference currently.
DAC got 682 paper submissions and selected 148 papers this year. Authors of rejected papers get feedback on how they can improve, and Pat estimates that many of these papers are enhanced and then resubmitted to other conferences.

I have to admit – it was fascinating listening to Pat describe his early engineering work and subsequently his and Marie’s efforts supporting DAC. The question that came to mind, though, was how could the lessons of the past be applied to today, and to those engineers just getting started in the EDA industry. I also wondered if the technical side of DAC has drifted too far away from the industry focus present in the early years of the conference to focus on “academia and algorithms”, as Pat described it.

Those of you who spent your time in the exhibition hall may not have noticed, but there was a “secret” conference going on in parallel – the academic conference. I got a glimpse of this “academic DAC” on Tuesday at the CEDA luncheon where Dr. Jeannette M. Wing, assistant director of the National Science Foundation (NSF), was the keynote speaker. On the other hand, DVCon tends to be strictly focused on industry trends and solutions to real-life problems.

According to Pat, DAC added a user track some years back to try to address the problem of a growing academic influence to the conference. I still wonder though, given I found little desire or need to venture off of the exhibit floor, whether the user track is enough to really push the conference back to its industrial roots.

Another issue that I was hoping for some perspective on was that of future directions – that is to say, what is coming down the road for people relatively new to the EDA industry? Pat felt that miniaturization and microwaves were two technology trends to watch in the years ahead. Of course, the elephant in the room for engineers in EDA is the persistent fear that we may be in a dying industry. But Pat begs to differ: “No matter what happens, you have to design things,” he said. You’re also “going to have to have tools.” That would seem to bode well for EDA. However, Pat ended with a word of caution. “If we don’t stay together, we’re going to fall behind.”

So, how do we stick together to hold our ground against the crashing waves of the global economy and changes in technology? I started my blog back in 2005 with the hope that engineers within companies would be encouraged to do a better job communicating. Flash forward to 2009, where the Conversation Central discussions, blog postings, and #46DAC tweets going on throughout the week were a constant reminder of the ever-increasing need and desire of engineers to communicate across global and corporate boundaries. By remembering the past, refocusing DAC on its industrial and problem-solving roots, and enhancing engineering coordination and communication via new social-media technologies, DAC can help the industry move on to bigger and brighter days ahead.

Additional Sources and Comments

[1] Goering, Richard. “At 40, signs of age-and youth”, EETimes, June 2, 2003

[2] Pistilli says there were 136 people, Goering in [1] says 137. Pistilli suggests there were 650 attendees at the 1966 DAC, Goering in [1] says there were 636.

We love DAC, but can't follow instructions!

2009-07-31T09:06:51-05:00

We love DAC, but can't follow instructions!
Originally uploaded by brillianthue

This wild mob of DAC lovers was seen roaming around the South Hall Tuesday afternoon at DAC. I tried my very best to corral them to stand *right next to each other* and to *squeeze together*!!! Sadly, my effort failed, so you may get the impression from this photo that they only slightly prefer DAC over the nearest alternative EDA conference ;-).

Thoughts on Jasper ActiveDesign?

2009-07-31T02:44:42-05:00

Update August 12, 2009: Holly and Kathryn have asked me to change the link to the demo from a direct link (that opened the demo but made it appear as if the viewer was me) to a landing page link to a generic Demos on Demand page for Jasper. I've asked for a more direct link but Demos on Demand apparently doesn't make that easy to do. Look for the demo entitled "Jasper Design Automation: ActiveDesign". Hopefully the demo will still be visible on that page when you head over there to take a look!

Earlier this year at DVCon, Kathryn Kranen and Holly Stump met with me to discuss Jasper’s new design exploration tool, ActiveDesign. I ended up meeting with Holly and Rajeev Ranjan, Jasper’s CTO at DAC earlier this week to discuss the topic of my Wednesday panel, “Seeking the Holy Grail of Verification Coverage Closure.” During that discussion the topic of ActiveDesign came up again, which jogged my memory that I hadn’t posted on the topic after DVCon.

ActiveDesign is a tool to let designers perform a behavioral analysis of an as-yet-to-be-completed design before a testbench is available to actually stimulate behaviors. To the best of my understanding, you can describe a behavior you’d like to see (such as “ack == 1 for 2 clock cycles”), and ActiveDesign will tell you whether the behavior could ever occur given the code you’ve already written, and if so, under what conditions. If a condition can occur, it will show you a waveform diagram with the relevant signals that would have to be asserted over time to cause the desired behavior. You can also leave behind notes for yourself, such as “Could we get by with a 2 clock cycle delay instead of a 5 cycle delay?” Those notes are saved in a database for later use. Luckily, Holly provided me with a link to an interesting ActiveDesign online demo. The 40 minute demo shows off the tool’s functionality in much more detail. I’d recommend skipping ahead to about the 8:55 mark when the dull slideware stops and the real demo actually begins.

While the tool sounds like an interesting way to perform early design exploration, I’m not convinced it will be widely used. Why not? Basically, designers can be a stodgy lot… they’d much rather browse through files in vi or emacs, or draw diagrams out on whiteboards than try something that involves formal <gasp> technology :-). Am I wrong? Does anyone out there have experience with ActiveDesign? Does it actually help with RTL development, or does it get in the way of the “tried and true” hand-drawn diagram method? Enquiring minds want to know!

Denali DAC 2009 Party Pictures Posted!

2009-07-29T11:46:44-05:00

Ted Vucurevich
Originally uploaded by brillianthue

Just a quick note that I've posted my photos from the Denali party last night on Flickr. Let me know what you think!

Also, congratulations to Karen Bartleson of Synopsys for winning the EDA's Next Top Blogger competition!