Industry Insights Blog

DFT Challenge: Evaluating The True Cost Of Test

rgoering — Thu, 05 Nov 2009 14:00:00 GMT

Remember DFT? “Design For Test” faded into the background in recent years as the industry turned its focus to DFM, but if anything test is an even larger concern than it was 10 or 15 years ago. That’s because test is becoming more difficult and expensive at nanometer process nodes, especially with the drive for low-power design and the increasing prevalence of on-chip analog and mixed-signal circuitry.

A recent discussion with Sanjiv Taneja, vice president for Encounter Test at Cadence, showed me that the traditional way we’ve evaluated test costs is way too limited. Test cost is traditionally calculated in terms of capital costs and operating costs. Test engineers focus on optimizing throughput in order to minimize the amount of time each IC spends on the tester. One way that’s done is minimizing test data volume.

While minimizing time on the tester is still important, Sanjiv notes that there are additional criteria that must be considered to evaluate the true cost of test. These include:

Impact of power on yield and test cost. If a test program turns on all the power modes during test, it can result in very high switching activity and excessive IR drop. Good chips can fail on the tester, reducing yield and increasing costs.

Integration of DFT with design implementation flow. Synthesis tools should optimize for testability as well as area, timing and power. Otherwise, test structures can impact routability and timing closure. Poor design/test integration will decrease productivity and thus increase costs.

Analog/mixed-signal test. If analog IP takes up 20 percent of a system-on-chip, it probably accounts for over 50 percent of the test cost. Analog test often requires an expensive, manual approach. Sometimes built-in self test (BIST) is used, but this requires extra work and planning.

Cost of escaped defects. If you think test costs are high, what does it cost for a defective chip to escape detection until system test, or until it’s out in the field? Shipping bad parts to customers can not only kill budgets – it can kill companies.

Ramping to volume production. Process interactions and process variability make it difficult to ramp to volume production at 45 nm and below. Given today’s time-to-market concerns, a delayed yield ramp can be a huge expense.

All of the challenges listed above impact designers, and all can be alleviated through EDA tools. For example, power-aware automatic test pattern generation (ATPG) can make the right tradeoffs between test power reduction and test time reduction. DFT automation tools can hook up BIST engines to a chip test interface, and translate BIST set-up and run-time sequences to test interface ports. Advanced fault modeling and test-point insertion techniques can reduce the risk of escaped defects. And diagnostic EDA tools can speed yield ramps by figuring out the root causes of failures.

Cadence offers such capabilities in the Encounter Test product line, which is being shown at this week’s International Test Conference (ITC) in Austin, Texas. The ITC program, meanwhile, has a strong DFT emphasis. It includes a keynote and a plenary invited address that focus on the integration of design and test, as well as panel discussions on DFT for analog and low-power design. Cadence has representatives on both panels.

DFT has been around for a long time. I started writing about it in 1984 for Computer Design magazine, well before the term “EDA” was even invented. Here we are now, 25 years later, and it turns out that DFT is more important than ever. Some things never go out of style.

Greatest Moments In EDA Innovation

rgoering — Tue, 03 Nov 2009 14:00:00 GMT

Innovation is the lifeblood of the EDA industry, and it is only because of innovation from many sources – including academia and industry – that modern IC design is possible at all. Today at Cadence (Nov. 3, 2009), we are celebrating Cadence Innovation Day. As such, it seems like a good time to consider the “greatest” innovations that shaped our industry.

Also this week, the EDA Consortium will present the 16th annual Phil Kaufman award to Prof. Randal Bryant, whom I interviewed for a recent Industry Insights blog. This award is the EDA industry’s highest honor, and a look at the past 16 award winners provides some good background into the history of EDA innovation.

Here are my nominations (not necessarily in order) for the “greatest moments in EDA innovation.” Any further suggestions are welcome.

1. Spice simulation

Spice (Simulation Program with Integrated Circuit Emphasis) was one of the very first EDA programs, and it’s still the gold standard today for analog and custom circuit simulation. Spice was derived from a program called Cancer, which came out of a class project led by Prof. Ron Rohrer (2002 Kaufman award winner). Prof. Donald Peterson (1995 Kaufman award winner) oversaw the Cancer rewrite that became Spice, which was first publicly presented in 1973.

2. Verilog HDL

The Verilog language ushered in the present era of language-based IC design, and made RTL synthesis and simulation possible. Verilog was developed by Phil Moorby, 2005 Kaufman award winner, at Gateway Design Automation in the early 1980s. When former Cadence CEO Joe Costello won the Kaufman award in 2004, one reason cited was Cadence’s 1989 purchase of Gateway and subsequent opening of Verilog for standardization.

3. Multi-level logic synthesis

Nearly all complex digital circuits are designed with logic synthesis today. Synthesis was first applied to two-level logic with programs such as Espresso. However, a breakthrough in multi-level synthesis was required to make the technology practical for contemporary IC design. That came about in the 1980s through efforts such as IBM’s Yorktown Silicon Compiler project and the MIS and SIS programs from U.C. Berkeley. Prof. Robert Brayton, 2007 Kaufman award winner, was a leader of these efforts.

4. Automated IC layout

Today’s ICs could not be designed without placement and routing software. Prof. Ernest Kuh, who was at U.C. Berkeley from 1956 to 1993, helped lay the groundwork for IC physical design in the 1970s and 1980s. He won the 1998 Phil Kaufman award for his foundational work in circuit layout theory, partitioning, floorplanning, placement and routing.

5. Structured VLSI design

EDA innovation is not just about tools and algorithms – it’s about methodologies. Prof. Carver Mead, winner of the 1996 Phil Kaufman award, is known not only for his work in areas such as silicon compilation, but also as the co-author along with Lynn Conway of “Introduction to VLSI Design” in 1980. This seminal book set forth a structured methodology for the design of large-scale ICs.

The innovators mentioned above have set a high bar to follow. But given the emphasis that Cadence is placing on innovation and R&D, it just could be that someone at today’s innovation awards ceremony will follow in their footsteps.

Richard Goering

Users Outline New Approaches To Mixed-Signal Verification

rgoering — Mon, 02 Nov 2009 14:00:00 GMT

At the Cadence Mixed-Signal Design Summit, held Oct. 27, I had a hard time finding a seat in a packed auditorium. One reason for the summit’s popularity was its hands-on, practical nature. A series of user presentations showed how designers are solving real problems in mixed-signal verification. Below are quick summaries of five such presentations.

Jess Chan (Qualcomm), Robert Milkovits (Jazz), Prasanth Aprameyan (Micron), Kumar Abhishek (Freescale),
and Yuval Shay (STMicroelecrtronics) presented at the Mixed-Signal Design Summit (left to right).

Top-down approach guides mixed-signal simulation

Yuval Shay, staff engineer for mixed-signal verification at STMicroelectronics, gave a presentation entitled “Mixed-language simulation of sigma-delta ADC with AMS Designer.” In the presentation, he outlined a “top-down” hierarchical verification methodology that uses the Cadence Virtuoso AMS Designer simulator within the Virtuoso Analog Design Environment (ADE).

The idea behind the top-down methodology is to start verification as soon as the design effort starts. To accomplish this, engineers create models at the highest level possible and slowly expand the hierarchy “downwards,” substituting behavioral models with transistor-level models until full-chip, transistor-level simulations can be executed. The same testbench developed for the behavioral level can run the full transistor-level design.

Shay identified three basic steps to ST’s methodology:

Partition design into analog and digital domains. Simulate analog blocks with Virtuoso Spectre simulator (Spice) and digital blocks with Cadence NC-Sim.
Run signal path verification for modulator and digital filter.
Run full-chip functional verification, including transistor level models and post-layout netlists.

Shay said this approach has “proven to be a very good solution” for his company’s needs.

Modeling methodology moves real numbers

Simulating real number traffic is an important part of mixed-signal simulation, but there are some tricks to it, according to Jess Chen, senior staff engineer at Qualcomm. His presentation was entitled “A modeling methodology for verifying functionality of a wireless chip.”

There are some challenges with real number traffic in event-driven simulations, Chen said. He prefers a “baseband equivalent” approach that passes multiple real numbers on a single wire. Advantages: the models run fast by suppressing the carrier, they produce realistic signals at the DAC outputs and ADC inputs, IQ swapping is easy to detect, and noise is easy to include.

Chen said his group considered various options for simulating real number traffic, and used a PLI function. This makes it possible to pass real vectors between Verilog modules, use bidirectional real number traffic, switch between voltage and current on the fly, and use a resolution function for real number drivers. Qualcomm applied this methodology to a wireless SoC and found over 100 functional bugs before tapeout.

Full chip Spice simulation really does work

Think full-chip Spice simulation is impractical? Kumar Abhishek, senior analog and mixed-signal design engineer at Freescale Semiconductor, showed how it can work in a presentation entitled “Full chip Spice simulation methodology for zero defect silicon.”

What Abhishek described is actually a Verilog-AMS/Spice co-simulation approach. In a microcontroller SoC, he used Spice models for blocks such as ADC, DAC, voltage regulator, LCD controller, and clock generator. Verilog-AMS models were used for a crystal driver, analog sensor model, and supply driver. Verilog-AMS monitors were used for display, clock profile, data converter, and power monitor.

Abhishek showed a list of microcontroller verification challenges, including those related to analog behavior, power management, and pad rings. He said the AMS/Spice co-simulation approach is “robust” or gives 90 percent confidence in most cases. He also showed a number of test cases and talked about setup times and simulation run times. For example, in a test case with 6M transistors, power-up simulations took a setup time of 2-3 days and a run time of 15 hours.

He concluded that the proposed full-chip Spice methodology is useful for catching corner cases for complex mixed-signal SoCs, especially in complex power-gating scenarios. Abhishek noted, however, that it is “not a replacement” for the existing SoC mixed-signal verification flow, but a complement that can help attain 100 percent coverage for complex protocols.

How to capture design intent

Robert Milkovits, director of technical support at Jazz Semiconductor, gave a presentation entitled “Capturing AMS design intent.” He first spoke of “design intent holes and misses,” including:

Incomplete coverage for circuit analysis
Design sensitivity not uncovered
Parasitic effects on performance
Layout implementation discrepancies
Insufficient time for optimization and coverage analysis

Milkovits talked about how Cadence Virtuoso platform updates in IC6.1 help users represent design intent. He noted that constraint management is integral to design intent, and showed how Virtuoso constraints help “address both the big picture and the design details.”

A look at flash memory verification

Prashanth Aprameyan, senior verification manager at Micron Technology, spoke on “Mixed signal verification – a NAND memory perspective.” He said that NAND memory verification is very similar to other mixed-signal verification, and noted that “for us, verification cost is as important as design cost.”

NAND flash memory includes a memory array, sense amplifiers, high-voltage circuits, controller and logic, and low-voltage analog, pad and I/O. Micron uses both Verilog-A and digital Verilog modeling of the memory array. The Cadence Virtuoso UltraSim simulator, a fast Spice simulator, is extensively used for NAND flash verification. Micron is also investigating wreal behavioral modeling with Verilog-AMS.

Apremeyan noted that full-chip simulation time is becoming prohibitive, that it would be nice to have all electrical aspects of verification under a single tool, and that design for yield (DFY) analysis in fast Spice would be helpful.

Q&A panel

In a Q&A panel following the presentations, panelists fielded questions on the difficulty and cost of developing analog behavioral models, whether designers should do their own verification, modeling for performance verification, SoC-level and IP challenges, and test.

The summit also featured a keynote by Paul Emerson, general manager for the analog and logic business at Texas Instruments, and several presentations on Cadence’s mixed-signal solutions. Videos will be available on-line in November. Another review of the summit can be found in Paul McLellan’s blog.

Richard Goering

User Interview: How To Estimate Power Early

rgoering — Thu, 29 Oct 2009 13:00:00 GMT

Early power estimation makes it much easier to manage IC power, according to Camille Kokozaki, director of design automation services at Integrated Device Technology (IDT). At the recent CDNLive! Silicon Valley, he presented a case study of architectural power estimation with a 65nm system-on-chip with 250K logic cells and a maximum frequency of 400 MHz.

Kokozaki described a flow that uses five steps:

“Back of envelope” estimations in spreadsheet provide assumptions about voltage, dynamic power factor, leakage power factor, design for test overhead, and other factors.
Power estimation from InCyte Chip Estimator uses a provided model library. InCyte estimates dynamic power sensitivity versus activity.
Cadence Encounter RTL Compiler provides estimation from early synthesis run.
More accurate estimation based on full synthesis netlist.
Power calculation from post-layout netlist.

Accuracy increases with each successive step, but the higher levels of abstraction provide a greater ability to influence power.

In an interview following his presentation, Kokozaki discussed his approach to power estimation further. In the attached video clip, he discusses the importance of power analysis at an architectural level, and talks about his use of spreadsheets, InCyte, and pre-synthesis and post-synthesis power estimations.

If video fails to launch click here.

For the chip described in the CDNLive! case study, IDT employed clock gating. Kokozaki said IDT also uses more advanced power management techniques where appropriate.

Kokozaki had a warning about the use of activity levels in power estimates. “Be very careful about activity and what it means,” he said. “There are cases where a 10 percent activity for a particular mode can consume even more power than a 15 percent activity rate on a different mode in the same design. You have to know what you’re putting in there. I also advise people to not go overboard and use a much higher activity rate than what they end up seeing.”

Richard Goering

Panelists: 32 nm HKMG Is Ready To Roll

rgoering — Wed, 28 Oct 2009 14:30:00 GMT

The 32/28 nm Common Platform high-k metal gate (HKMG) technology is “ready and open for business,” according to the title of a breakfast panel at the ARM Techcon3 conference Oct. 22. Panelists from IBM, ARM and Cadence talked about the benefits of HKMG, the requirements it places on the design flow, and the deep and early collaboration that made a supporting ecosystem with libraries and tools possible.

All of the panelists talked about the Common Platform/ARM/Cadence collaboration, which began in 2008 just a few months after the Common Platform started its process development work. Starting that early is very unusual, according to Jaya Jagannathan, director of semiconductor technology business development and marketing for IBM’s System and Technology group.

Jaya Jagannathan (IBM), Rob Aitken (ARM), and Vassilios Gerousis (Cadence)
discuss the Common Platform 32 nm HKMG technology (left to right).

HKMG, introduced by the Common Platform at 32 nm, promises significant power and performance advantages. The main benefit of HKMG, according to Jagannathan, is that it allows the scaling of gate lengths to continue. This had almost stopped at 90 nm, he said, because gate oxides were only a few angstroms – and atoms – in width. But HKMG, which uses thicker materials, allows scaling to resume. Further, he said, HKMG allows the “densest SRAM in the industry at 32 nm.”

Jagannathan also said that the 32/28 nm process uses a “gate first” approach in which gates are processed towards the beginning of the process flow. This, he said, allows a 50 percent scaling from one generation to another, while minimizing design restrictions and avoiding the addition of complex process steps. “Based on all the work we’ve done jointly, I can tell you that we can achieve the gate density we promised, we can achieve the performance we promised, and we can achieve the simplicity that we promised with gate first,” he said.

Why 32/28 nm? 32 nm is the main process node, but it’s designed so that a 10 percent optical shrink will enable the half-node of 28 nm. Today, Jagannathan said, a 32 nm low-power (LP) process design kit (PDK) is available in a beta release, and a 28 nm LP PDK is available in an alpha release. IBM has been providing multi-project wafers (MPWs) to customers and partners including ARM and Cadence.

Rob Aitken, R&D fellow at ARM, noted that a physical IP library for the 32/28 nm HKMG process is available for download now. It includes 12 memory compilers, logic libraries, and new multi-channel libraries. The multi-channel libraries make it possible to reduce leakage by using cells that have slightly longer gate lengths. It’s an alternative to the use of high voltage-threshold cells, which can reduce performance.

“The HKMG process is really quite different from previous processes,” Aitken noted. As such, ARM and the Common Platform worked together on design rules, manufacturability, and the library itself. Aitken said ARM has had five tapeouts with the Common Platform 32 nm process, and one 28 nm tapeout. These test chips made it possible to demonstrate early collaboration and to work on design rules.

ARM also used the test chips to run feasibility studies. Engineers found that the 32 nm LP process is able to attain frequencies in the GHz range on critical paths at a nominal operating point.

Vassilios Gerousis, senior architect at Cadence, discussed two 32 nm test chips that Cadence developed with IBM, as described in a previous blog. One let Cadence develop a CMP model, and showed that the 32 nm process has less relative copper loss than 45 nm but higher variability. Another showed that the random variation is large compared to stress, which is a systematic variation. Results may change as the process matures, he noted.

Gerousis noted that Cadence has focused on several areas related to 32 nm, including advanced layout rules, a high-frequency router option to NanoRoute, manufacturing awareness, and the ability to handle large designs. “32 nm is really a breakthrough in terms of layout rules. The number of layout rules is tremendous, and the impact on layout tools is also large,” he noted. NanoRoute is “100 percent compatible” with these layout rules, he said, and the Cadence Virtuoso Space-Based Router supports 32/28 nm layout rules as well. To help with random variations, Cadence is supporting statistical design for timing, signal integrity and leakage.

Panel moderator Ana Molnar Hunter, vice president of foundry for Samsung Semiconductor, closed the panel by stating that “we’re seeing tremendous customer interest in this technology because of the advantages HKMG brings to customers. There’s a lot of excitement and a lot of built-up demand.” Indeed, a full room for an early morning breakfast panel is itself a sign of interest. Designing in a new process node is never easy, but it appears that those who want to move forward will find plenty of ecosystem support.

Richard Goering

Panelists Broaden Scope Of Low-Power Discussion

rgoering — Mon, 26 Oct 2009 13:00:00 GMT

Most of the discussion about low-power design has centered around the RTL-to-GDSII flow for digital ICs. But the real problem is much broader, according to panelists from AMD, Sonics, Wipro, and Cadence at the recent Power Forward Initiative (PFI) Low-Power Design Summit Oct. 20.

Entitled “The Low-Power Evolution: Challenges and Opportunities,” the panel was chartered to take a high-level view of how low power design is changing and how it impacts product development. As moderator, I noticed (but wasn’t surprised) that panelists said very little about the RTL-to-GDSII digital IC design flow. Instead, the focus was on early power estimation, analog/mixed-signal design, embedded software, packaging, and other areas where automation is still lacking. Some interesting comments are noted below.

SoC integration complexity and power

“The SoC integration problem is growing as we add more and more cores together, we have more and more power domains, more and more clock domains, and a higher level of problems to solve,” said Scott Evans, director of software at IC interconnect provider Sonics. “CPF [Common Power Format] allows you to describe what you’re trying to build, but then it’s even easier to add more complexity to your design.”

Analog/mixed-signal design

Ron Burns, general manager for semiconductor and systems solutions at design services firm Wipro, said his biggest concern with respect to low power is analog/mixed signal design. He noted that his company is designing an increasing number of systems-on-chip (SoCs) with analog interfaces. “What we’ve found is that digital is performing well even down to below 40 nm,” he said. “What we’re concerned about now is making sure we have the right flow for analog and digital.” He said he’d like to see the same IP library format across both domains.

“We’ve done a fairly good job of automation and risk reduction in the digital portion of the design, and we’re pushing forward into analog/mixed-signal and starting to address packaging alternatives,” noted Steve Carlson, vice president of solutions marketing at Cadence.

Ron Burns (Wipro), Steve Presant (AMD), Scott Evans (Sonics), and Steve Carlson
(Cadence) discuss low power at the PFI Summit (left to right).

Embedded software and operating systems

“Being able to take advantage of power at the software level is a huge factor in terms of being able to save power,” said Evans. “Providing interaction with the hardware so software can control it better is certainly a place that needs a lot more work and a lot more automation.”

There’s a “huge opportunity” to take a more holistic approach towards estimating hardware and software together, said Steve Presant, fellow at AMD. He suggested “an environment where an application profile describes power, and an OS considers that and interacts with the hardware.”

The link to packaging

Wipro’s Burns cited a case in which his company designed a graphics accelerator IC while separately working with a packaging partner. “The only way to transfer information from the design database to the packaging house was through Excel files,” he said. “We don’t yet see a seamless way to interoperate between packaging and design. The reality is that the packaging companies use custom internal tools, and interoperability just isn’t possible.”

Early estimations

“It is critical for us to be able to estimate power and performance at very early stages,” said AMD’s Presant. Today, he said, “we do a lot of work based on Excel and we use a spreadsheet to make estimates based on area approximations and voltage and frequency estimates. It’s very crude. I think the future is transaction-level power approximations, so if you know that a certain transaction or activity carries a certain amount of energy with it, you can approximate power that way.”

As an IP provider, Evans said, Sonics needs its IP models to work with models from other sources. “We need some type of standardization for power estimation for models, so that when you plug in the models you know what you’re looking at and you can provide those early estimates,” he said.

Carlson talked about how emulation can provide a dynamic power analysis, help users evaluate the impact of software, and make it possible to select a “window” of operations for detailed analysis.

It’s the whole product

I started to make a point that I’ll bring out a little more here. The end consumer of an electronics product does not care how much power an IC dissipates. The consumer cares how long the battery life is, what it will cost to run the device, or what the environmental impact is. Low power isn’t just about digital chips – it’s about the entire system, with its analog components, packages, printed circuit boards, wiring, enclosures, fans, heat sinks, and software. With the help of the Common Power Format (CPF) and some good tools, we have made great progress in automating the low-power design flow for digital ICs. But as PFI Summit panelists noted, the time has come to take a broader look at low-power design.

Richard Goering

User Interview: An Under The Hood Look At PDKs

rgoering — Thu, 22 Oct 2009 13:00:00 GMT

Well-made process design kits (PDKs) are critical for successful IC design, and design teams should keep in touch with PDK technology development, according to Kristin Liu, principal CAD engineer at National Semiconductor. In an interview at the recent CDNLive! Silicon Valley, she talked about the challenges of PDK development and explained “model playback,” the topic of her CDNLive! paper.

Liu is involved in PDK development and automation, project management, customer support, PDK methodology and flow definition, circuit modeling, benchmarking, and new CAD tool implementation. She is working on BiCMOS processes for the analog ICs that National develops. National’s PDKs include customized schematic symbols, parameterized cells (Pcells), verification runsets, customized utilities, mask design libraries, and standard cell libraries. The PDKs are used in the Cadence design environment.

In the video clip below, Liu talks about the challenges of PDK development, the need for accurate device characterization, and National’s use of the Cadence Spectre simulator.

If this video fails to play please click here.

Liu’s CDNLive! paper was entitled “A Conventional Model Playback Utility In The Cadence Design Environment.” Model playback, she explained, is a utility developed at National Semiconductor that lets designers examine how a model behaves in real time. It lets designers “play back” the device characterization with customized design specifications. Designers can compare device behaviors among different processes, validate the model with different simulators, or view the model accuracy between the simulation results and the silicon measurement data, all in real time.

Liu has some words of advice for the IC design teams who rely on PDKs. “As an RF IC designer myself earlier, I felt frustrated and helpless with PDK issues,” she said. “Now I realize that it is important for designers to be involved in the PDK methodology definition. I’d encourage designers to work as closely as possible with PDK developers for feature enhancements, demos, design guides, design automation, and design flow benchmarking. This will maximize design productivity and reduce human error.”

Richard Goering

Cadence’s Andreas Kuehlmann To Head IEEE Council On EDA

rgoering — Wed, 21 Oct 2009 13:00:00 GMT

With a deep involvement in conferences, publications, educational programs and awards, the IEEE Council on EDA (CEDA) is a behind-the-scenes organization that has a large influence on the professional EDA community. Andreas Kuehlmann, Cadence fellow and director of Cadence Research Labs, will become president of IEEE CEDA in January – and he’s aiming to “ramp up” CEDA’s activities and increase its visibility and value.

Whether or not you’ve heard of IEEE CEDA, you’ve certainly heard of the Design Automation Conference (DAC), which CEDA co-sponsors. In fact, the council sponsors or co-sponsors over a dozen EDA-related conferences, including the International Conference on Computer Aided Design (ICCAD) and Design Automation and Test in Europe (DATE). CEDA publishes the IEEE Transactions on CAD and the newly-launched IEEE Embedded Systems Letters. The council offers a Distinguished Speaker Series and sponsors the A. Richard Newton and Phil Kaufman awards.

In this short video, Andreas talks about why CEDA was formed, what activities CEDA is involved in, what his priorities will be as CEDA president, and how people can get involved.

If this video fails to launch click here.

Andreas will succeed current CEDA president John Darringer, director of the design automation department at IBM Research. Additional members of Andreas’ team include the following:

Prof. Donatella Scuito from Politecnico di Milano in Italy will become president-elect (and president after Andreas’ two-year term).
Sani Nassif, manager of the IBM Austin Research Laboratory, will become vice president of conferences.
Prof. David Atienza Alonso of the Complutense University of Madrid will become vice president of finance.
Prof. Rajesh Gupta of the University of California/San Diego remains as vice president of publications.
Shishpal Rawat, director of EDA investments for Intel, remains as vice president of technical activities.

I wish this team well in their efforts to bring more value to the EDA community.

Richard Goering

OpenAccess – So Much To Celebrate, So Much To Do

rgoering — Mon, 19 Oct 2009 12:00:00 GMT

Two distinct messages emerged from the Silicon Integration Initiative (Si2) OpenAccess Conference last week. One is that the OpenAccess database is a great EDA standards success story, perhaps the biggest such story of all. Another is that there’s still a lot of work to do so OpenAccess can offer even more capabilities for next-generation IC design.

OpenAccess, initially developed by Cadence, has been in the public domain since 2002. Today it is managed by Si2’s OpenAccess Coalition, which includes several dozen semiconductor and EDA vendors, including Cadence, Synopsys, Mentor Graphics, and Magma. Many people may not realize that OpenAccess is constantly being maintained and updated by a sizable development group at Cadence.

Setting the theme for the conference, Sumit DasGupta, senior vice president of engineering at Si2, proclaimed that “OpenAccess is here and it is now.” All four major EDA vendors have adopted it for parts of their flows, and it’s become a compelling development platform for startups, he noted. But DasGupta cautioned that “this is no time for complacency. We have to get back to work and keep pushing the envelope with OpenAccess.”

Steve Schulz, Si2 president, said OpenAccess is “the largest EDA standards effort in the history of our industry.” Now, he said, OpenAccess is in the “early majority phase.” He talked about how Renesas uses OpenAccess throughout its IC development process, and how IBM bases its custom design flow on OpenAccess. Later at the conference, Jose del Cano of Intel described how his company uses OpenAccess to integrate internal tools with commercial EDA tools.

But don’t break out the champagne – at least not for long. There’s no rest in store for OpenAccess developers. In his keynote speech, Barry Dennington, senior vice president at NXP and chairman of the Si2 board, hailed OpenAccess as “something to be very proud of.” He said, however, that “OpenAccess needs a lot more work, it needs a lot more adoption, and the roadmap needs to be very clear.”

Specifically, Dennington said, porting existing libraries and design data to OpenAccess is not cheap, OpenAccess needs to be adopted by NXP’s IP providers, and 45 nm designs are taxing database performance and memory usage. How far can OpenAccess go, he asked? Could it replace other exchange formats, like GDSII?

“OpenAccess has proven to be a great standard,” Dennington said. “Cadence has led by example by pulling together Virtuoso and Encounter [on OpenAccess]. But we still need more EDA industry tools to connect with OpenAccess.” Intel’s del Capo wants OpenAccess to extend to new “domains,” such as post-silicon debug and large-scale layout visualization.

A presentation by Michaela Guiney, product engineering director for OpenAccess at Cadence and co-architect in the OpenAccess Coalition change team, made it clear that a tremendous amount of effort is going into improvements for OpenAccess. In January 2008, she noted, a new version called Data Model 4 (DM4) was introduced, with enhancements in such areas as constraints, routing constructs, and vias. Today it’s used in a number of popular EDA products, and the development team has improved its functionality, reliability, and performance in the meantime. In fact, there were 13 DM4 releases in 2008 and 2009.

An upcoming release at the end of 2009 will add more new capabilities, including performance enhancements. 2010 will bring further improvements in performance and capacity, as well as constraint modeling, Guiney said. She added that Cadence is working with foundries to understand 32 nm design rules, and plans to contribute 32/28 nm constraints to the OpenAccess Coalition in mid-2010. Meanwhile, coalition working groups are working to improve debugging, parasitic handling, and scripting interfaces.

A personal note: As an EE Times editor, I started writing about OpenAccess in its early days, and I followed its development as it moved from controversy to acceptance and adoption. It has, indeed, been a great success story, but the final chapter is far from written – we’re just getting to the good parts of the book.

Richard Goering

CDNLive! - How To Succeed At Formal Verification

rgoering — Thu, 15 Oct 2009 13:00:00 GMT

Four customer presentations at CDNLive! Silicon Valley, held Oct. 5-16, provided some valuable tips for users and prospective users of formal verification tools. The presenters included three users of Cadence Incisive Formal Verifier (IFV) and one user of the recently announced Incisive Enterprise Verifier (IEV). I came away from these presentations with some fresh perspectives on what it takes to be successful with formal verification, including the criteria listed below.

1. Choose the right problem

Formal verification can be a killer application if applied to the right block or chip. Chaitanya Kosaraju of Xilinx described his use of IFV to verify a multiplexed pad interface block. Due to the large number of input combinations, such a block would be very time-consuming to verify using a traditional simulation testbench. Using IFV, Kosaraju was able to verify in a month a block that would have taken 3-4 months using a testbench approach.

2. Use formal verification early

Balekudru Krishna of Chelsio Communications noted that his company has been very successful with “designer-centric” formal verification, where verification engineers and design engineers collaborate early in the design process. He presented a case study of IFV use with a datapath block in a page manager module, in which the goal was to start formal verification very early and complete an end-to-end verification of the module.

IEV provides a “dual power” interface between formal verification and simulation engines, allowing new capabilities such as property-driven simulation, formal-assisted simulation, and simulation-assisted formal analysis. One big win, said Ying Yu of Marvell, is the ability it gives designers to do some fairly extensive verification before a testbench is developed and deployed. She said IEV enabled a simulation bring-up time of three days for a memory controller module, a process that could have taken months with a traditional approach.

3. Have a plan

Yogesh Bhagwat of Cisco talked about his use of IFV as the primary verification tool for a DDR3 command buffer ASIC. His methodology started with the creation of a formal verification test plan. This plan identified subsets of modules suitable for formal verification, and identified interfaces for which assertions needed to be written. Subsequent steps include writing properties for requirements, writing constraints for inputs, and writing cover statements for monitoring coverage.

4. Design for formal verification

The Chelsio presentation cited a number of ways that designers can help make formal verification more successful. These include carefully partitioning the design with clear boundaries, using smaller logic cones, isolating modules that use FIFOs or require liveness guarantees, and being willing to re-partition the design if required for optimal use of formal verification. These are also good coding practices, Krishna noted.

5. Strategize to avoid convergence problems

Chelsio engineers ran into some state-space problems when trying to verify a page manager that managed 1,024 pages. They realized they only needed to evaluate states for one page at a time, and replaced a component of the module with a manual abstraction that served as a stub that maintained states for just one page. To boost proof convergence, they also kept datapath and control path circuitry independent, and took advantage of data type symmetry to create reduced instances of the design.

6. Use automated features when available

A key element of Xilinx’ success with the pad interface block was the use of the IFV Connectivity Package, which automatically generates assertions from a spreadsheet.

7. Keep attending CDNLive!

Well, nobody actually made this point during the above-mentioned presentations, but it seems to me that listening to customer experiences like these will be helpful to anyone involved in design or verification. CDNLive! papers will be available on-line to Cadence Community members within the next few weeks.

Richard Goering

What Lies Beyond The SystemC TLM-2.0 Standard?

rgoering — Wed, 14 Oct 2009 13:00:00 GMT

By supporting SystemC model interoperability, the Transaction Level Modeling (TLM-2.0) standard from the Open SystemC Initiative (OSCI) was a watershed event in the development of ESL flows. But it was not the final answer. At a recent virtual platform panel, participants noted that TLM-2.0 is a good start, but much more remains to be done. For example, panelists talked about debug tool interoperability, configuration and control, model interfaces, and defining “best practices” for model development.

To discover what more needs to be done with respect to model interoperability, I recently sat down with some of Cadence’s SystemC experts. We talked about what TLM-2.0 has accomplished, and what still remains to be done.

First, some background. In 2005, OSCI introduced TLM-1.0, which defined a standard set of APIs for transaction-level communications. This standard, however, didn’t define the content of those communications. TLM-2.0 defines the content of transactions with a “generic payload” that describes the necessary data structures. TLM-2.0 was announced in July 2008.

“TLM-2.0 has done a pretty good job of addressing interoperability, at least for memory-mapped busses,” said Neeti Bhatnagar, engineering director at Cadence. She noted that TLM-2.0 processor IP is beginning to appear, although there’s still a lack of other types of IP. EDA tools are supporting TLM-2.0 as well. For example, Cadence in May announced an expanded verification solution that natively recognizes TLM-2.0 constructs in order to automate debug and analysis without requiring any model instrumentation.

Neeti said there are currently two main types of users for TLM-2.0. Most commonly, this standard is used for virtual platform development, where designers use the “loosely timed” (LT) TLMs defined by the standard. The other use is architectural performance analysis, which generally involves more accurate “approximately timed” (AT) models.

What’s missing?

Now that TLM 2.0 is available, we are beginning to see areas where additional standards or interoperability guidelines may be needed. For example, some users are interested in cycle accurate modeling using TLM 2.0.

“TLM-2.0 defines cycle accurate but doesn’t say too much more about it,” noted George Frazier, senior member of consulting staff. Neeti said there seems to be some interest right now in using cycle-accurate models with TLM-2.0, and some users are trying to figure out how to do so for more accurate performance analysis, but it is really loosely timed modeling that has seen the most proliferation and interest.

Neeti also observed that although processor models are becoming available in TLM-2.0 wrappers, each processor model has its own software debugger. There is no standard debug API for processor models, and processor debug tools are not interoperable in a standard way.

TLM 2.0 allows temporal decoupling where a process can run ahead of the simulator to provide a significant increase in simulation performance. When users plug together models from different vendors to assemble virtual platforms, it could be challenging to fine-tune temporal decoupling across all the processes in the system to arrive at the necessary accuracy-versus-performance tradeoff. “Things could get tricky because models are not running in lockstep,” said Bishnupriya Bhattacharya, senior member of consulting staff.

CCI provides the “next step”

In February 2009, OSCI introduced the Configuration, Control and Inspection (CCI) working group. This group seeks to develop “instrumentation standards” for models from different providers, making it possible to configure and control models and simplifying system-level debug and analysis. According to the OSCI announcement, the group is considering configuration parameters, register characteristics, power and performance data probing, command interfaces, save/restore, and other issues related to configuration, control and debug. (Cadence already supports save/restore for SystemC as announced in May as a part of the expanded verification solution).

Bishnupriya put it this way. “TLM-2.0 is about model-to-model interoperability. CCI is trying to accomplish the next step, which is model-to-tool interoperability. One of the first few areas it’s looking into is how you can make parameters part of the model definition, as opposed to being tool specific.”

The CCI working group is still gathering requirements, and the full scope of what it will consider is not yet determined. There has been little coverage of CCI in the trade press. But anyone interested in ESL flows should keep an eye on this evolving effort. It may help define the next level of SystemC model interoperability.

Richard Goering

Why Stress Gives Designers Headaches at 45 nm and Below

rgoering — Mon, 12 Oct 2009 16:00:00 GMT

Transistor stress may become the dominant source of systematic variation at 45 nm and below, yet there’s been surprisingly little discussion about this issue. Today, stress-induced variability is primarily a concern for design teams who are pushing the envelope in terms of advanced nodes or performance. Tomorrow, it may impact most ASIC and SoC designers.

I became aware of this issue during the Advanced Node panel at the Cadence Ecosystem booth at the Design Automation Conference. Panelists noted that stress is a major cause of systematic variability at 32/28 nm, that regular Spice models don’t comprehend stress properly, and that placement needs to be optimized to control stress-induced variability. To get more information about stress, I talked to Nishath Verghese, engineering group director for electrical DFM at Cadence.

Unlike emotional stress, transistor stress in deep submicron ICs is intentionally induced for the most part, and is generally a good thing. By placing tensile or compressive stress onto NMOS or PMOS devices, Nishath noted, you change the lattice structure inside a transistor channel, allowing electron mobility to be higher. This boosts performance. Also, by changing the velocity at which transistors saturate, stress can allow higher performance at high voltages.

There are various ways of inducing stress, and the actual methods vary from one foundry process to another. One way is to “strain” silicon by introducing another layer on top of silicon, such as silicon germanium (SiGe). Another is to introduce a “capping” layer, such as a silicon nitride layer over a polysilicon gate. Dual stress liner (DSL) is a technology in which both NMOS and PMOS devices are stressed, while single stress liner (SSL) stresses only one of these device types.

Note that I said above that stress is “intentionally induced for the most part.” Stress is unintentionally induced by shallow trench isolation (STI), which uses oxide to isolate transistors and results in silicon dioxide abutting against silicon. “Even if somebody says they don’t use strain and don’t need to model stress, that is not correct,” Nishath said.

At 65 nm, Nishath noted, designers cared only about the distance between a transistor gate and the nearest STI edge. At 45 nm and below, what becomes important is the width of the STI channel. Knowing that requires a knowledge of where the next transistor is. We have thus introduced a proximity effect, meaning that one transistor is influenced by the placement of its neighbors. If the next transistor is placed too close or too far away, “my stress is changed and the performance of my device has changed,” Nishath said.

The main impact of stress is timing variability, and at 45 nm stress can cause variability by as much as 15 percent, Nishath said. At 32 nm the variability will probably be higher. This makes it hard to close timing. “If you want to account for this you either need to margin excessively, which means your timing closure gets longer, or you need to actually calculate the impact,” Nishath said.

So what to do? Foundries are now modeling stress effects by creating extensions to the classic BSIM model that take proximity information as an input. The standard digital design flow, however, assumes that every standard cell is independent of all others. The Cadence Encounter Digital Implementation System, in combination with Cadence Litho Electrical Analyzer (LEA), can derate standard cells during timing closure based on their contextual influences. Further, LEA can “score” cells based on characteristics of neighboring cells, and EDI runs a post-placement optimization that moves cells around to mitigate stress-induced variability.

The next question is how to help analog designers. Their problem, Nishath said, is that because of proximity effects, post-layout simulations no longer match the schematic. Analog designers need to capture stress variability effects before post-layout simulation. Cadence is working on solutions in this area.

Awareness may be the biggest hurdle. “I think people have kind of swept [stress] under the rug at 45 nm,” Nishath said. “People close to fabs have a very good understanding of it, but people going to foundries are probably less aware of it.” It sounds like transistor stress will be a much more frequently discussed issue in the near future.

Richard Goering

Combining Formal Analysis and Simulation Provides New Capabilities

rgoering — Thu, 08 Oct 2009 13:00:00 GMT

In the early days of formal verification technology, some advocates thought it would replace block-level simulation. While this works for certain types of blocks, nowadays we see formal analysis technology as a complement to simulation that has some strengths – such as an ability to quickly find interesting states – and weaknesses, most notably limited capacity. Simulation overcomes capacity limits, but can miss tough corner-case bugs and leave deep coverage points unexercised. What if we could combine simulation and formal analysis, and leverage the strengths of both?

Cadence this week announced Incisive Enterprise Verifier (IEV), an integrated verification solution that includes all the capabilities of the Incisive Enterprise Simulator (IES) and Incisive Formal Verifier (IFV). An IEV user can run simulation or formal analysis, just as they were run before. What IEV adds is a “dual power” capability that provides a tight integration between simulation and formal analysis, adding several new capabilities to the verification arsenal. These capabilities allow designers and verification engineers to find additional bugs, and to exercise interesting coverage points in the design that could not be achieved with standalone formal analysis or simulation.

One new capability, said Sarah Lynne Cooper Lundell, senior product marketing manager at Cadence, is property-driven simulation. Typically, assertions in simulation are passive, and simply act as monitors. With IEV, assertions can actually drive stimulus into the design. This is especially helpful in the design bring-up stage, where you can use assertions to simulate and find bugs. The same assertions can be used for simulation, formal analysis, and acceleration or emulation, enabling verification reuse.

Another new capability is formal-assisted simulation. Here, you identify an interesting state you want to reach, and formal analysis gets you to that state very quickly. Simulation takes over from there. It would be harder to reach that state with simulation alone due to the probabilistic nature of simulation-based stimulus.

A third new capability is simulation-assisted formal analysis. In this case, you stop the simulation after reaching a certain point in time, and turn on the formal engine to take a deeper look and explore around that state. You can run a full formal analysis, but it isn’t a full formal proof because you’re not going back to reset and proving a property over all possible conditions. Simulation-assisted formal analysis allows you to find deep bugs and coverage points without facing the capacity limits of traditional formal tools.

Tom Anderson, product marketing director at Cadence, provided an example of how simulation and formal analysis can work together. “Imagine a scenario in which a processor has to hit a certain sequence of instructions at the same time as a cache miss and an interrupt. It takes thousands of cycles to set up and is probably not reachable from reset in pure formal analysis. But by simulating and jumping around to interesting places in the design while leveraging the power of formal analysis at appropriate points, you have a much better chance of being able to hit that scenario.”

Another advantage of combining simulation with formal analysis is an ability to find coverage points that could be missed by simulation or formal analysis alone. Today, Tom noted, there’s an assumption that all coverage is gathered from simulation. But because IEV can work with SystemVerilog Assertion (SVA) or Property Specification Language (PSL) coverage properties, and because Cadence has a unified coverage database, a coverage point hit in formal analysis is treated no differently from a coverage point hit with simulation. In either case you can choose to bring it into the same database, check it off, and call it done.

All of IEV’s dual power capabilities can be used early in the verification flow, before a testbench is created. “With the combination of formal analysis and simulation engines, you are able to find bugs earlier in the process,” Sarah noted. “You don’t have to wait for a testbench to be available to do deeper verification. When you get to the testbench environment, you can better focus your efforts because you are working with cleaner blocks. IEV is also helpful in the final stage of verification, providing metrics that increase your overall confidence level that you are done. ”

The net result, Sarah said, will be improved productivity. “This will lead to a shift in which formal analysis will become a bigger part of mainstream verification, and not just something done on the side by experts. IEV’s dual power integration of formal analysis and simulation engines will enable widespread usage, and I expect over time IEV will become a standard solution on design and verification engineers’ desktops,” she said.

Whatever the claims, no one verification technology can solve all problems. Our best option is to leverage the advantages of all available technologies and apply them as most appropriate. Incisive Enterprise Verifier is an important step in this direction.

Richard Goering

Q&A Interview: CMO John Bruggeman Presents Bold Vision For EDA

rgoering — Wed, 07 Oct 2009 13:00:00 GMT

John Bruggeman, Cadence’s new Chief Marketing Officer (CMO), is bringing a fresh sense of excitement and vision to Cadence and the EDA industry. In this interview he talks about EDA as a “noble cause” that can help save the planet, and he challenges the EDA industry to rediscover its importance. He also tells why he joined Cadence and what he hopes to accomplish. John is responsible for Cadence’s strategy, products, marketing, ecosystem, and channel.

Q: You’ve held executive marketing positions for some leading software companies including America Online, Netscape, Octel, and Wind River. What attracted you to EDA?

A: I wasn’t attracted to EDA -- I was attracted to the problem. The problem is so compelling that I had to find the place that was most likely to solve it.

The world has become digital. From the electronics we use daily in our handhelds, to the cars we drive and the planes we fly on, digital technology has enabled more functionality, capability and possibility than we could ever have imagined. But that is a double-edged sword. On the one hand, the promise of what can be is phenomenal. We can find new energy sources, clean up the planet, and make the world safer. We can improve air quality and design a car that doesn’t need fossil fuels.

At the heart of this vision are the SoCs [systems on chip] that go together and make up systems. The problem – the other edge of the sword -- is that the more we dream, the more complex SoCs become. Complexity has far outpaced our ability to deliver systems. It’s outpacing physics and taking us beyond what we can control, manage, and test. Complexity makes it difficult to manufacture high-quality systems at a cost we can afford.

So who in this world can solve the complexity problem? Who could enable all the good things I just talked about and save the planet? At first I thought it was the embedded software guys, because more and more software is enabling digital systems. But then I saw that software cannot live independently from the chip. Next I thought it might be the chip companies themselves, but I was at Intel just long enough to realize that they are just trying to manage the problem, not solve the problem. So I came to believe that if anyone will solve it, it’s the EDA industry. We deliver the tools that make it possible for semiconductor companies to manage complexity, cost, power, and quality.

I went to EDA to save the planet. This is a noble cause.

Q: If you go back 10 or 20 years ago, EDA was a rapidly growing industry with a real sense of excitement. Now there’s little if any growth and the excitement is lacking. What happened?

A: We forgot about our quest. We asked, “how can I do layout better? How can I do verification better?” Making an SoC is hard. Our customers are struggling to develop all this functionality at a cost and quality the market will bear, and we forgot we enable that.

We thought this was a rapidly commoditizing, unimportant, tactical little industry that delivered some good software people use. We forgot it was necessary. We lost sight of the big problem. And because of that customers did what I would do, which is to say, “if you want to be tactical and you want to be a commodity and you want to be unimportant we’ll have a discount discussion.”

I think we’re at a breaking point in the EDA industry. EDA tools have to get bigger, they have to get broader, and they have to get more ambitious. In doing so, we’ll capture more value again. We’ll become important and we’ll become strategic for our customers. Customers don’t mind paying for value. We just haven’t been delivering the value.

Q: You recently commented that IC design is starting to focus on IP integration as much as original design. What are the implications for EDA tools?

A: Think about what an integrator does versus what a designer does. It’s two separate tasks. You wouldn’t think that the exact same tools would do both tasks. But this has been an industry that’s said, “I have a hammer so everything looks like a nail.” Well, I’m telling you that integration is a screw and you need a screwdriver, not a hammer.

Q: How will Cadence help customers with SoC integration?

A: We’re going to get right in there with them. We’re going to provide the right tools, we’re going to provide the right services, and we’re going to build out the right ecosystem. I think you will absolutely see some significant initiatives and programs that map into our vision for the marketplace.

Q: What attracted you to Cadence?

A: I think Cadence is the EDA player that is most likely to take on a leadership role for the industry and to take the industry beyond where it is today. Cadence has tremendous strength in its management team, the depth and breadth of its technology and product line, and the power of its installed base. We have the willingness to lead.

At Cadence, we have a fresh team who’s excited and energized and willing to work with our customers to re-invigorate this industry.

Q: What are your priorities at Cadence?

A: One is to rally the company around a clear, consistent strategy. Another is to make sure that the products and the product roadmap are delivering against that strategy. Then we market the heck out of it so people are aware of how all this works together, and we make sure we’re delivering as much customer value as we can.

Q: There’s been a decline in EDA marketing. What kind of marketing is needed to bring EDA out to the forefront again?

A: I think we lost our way. We did a ton of point product marketing. We forced the marketplace and the customer to add it all up, and put it together into pieces that made sense and that matter. While my EDA brethern continue to do that, I’m going to go up a level. I’m going to talk about solutions and initiatives. I’m going to talk about stuff that matters to executives who are trying to run businesses. And we’re going to apply our technology to solve their problems without ignoring the users we’ve been talking to for the past five to ten years.

Q: How will your experience in embedded software with Wind River help you in your role at Cadence?

A: At Wind River, my customers were the customers of EDA customers. We sold to semiconductor vendors’ customers, and I have a unique point of view and perspective because I lived the pain our customers lived.

The world is becoming more and more a software world, and EDA vendors have not understood that. That doesn’t mean they don’t go into software, or experiment from time to time and try to add software capabilities, but they’re not embedded software people. I think that in the coming months and years, a deep understanding of embedded software will be essential to the success of EDA players. I’ve learned a lot about that and I can bring some unique perspectives to this industry.

Richard Goering

Q&A Interview: Kaufman Award Winner Discusses Verification Advances

rgoering — Mon, 05 Oct 2009 13:00:00 GMT

Dr. Randal Bryant, Dean of Computer Science at Carnegie-Mellon University, will receive the EDA industry’s highest honor – the Phil Kaufman award – in November for his pioneering work in formal verification and simulation. In this interview, he answers questions about his past contributions to EDA and shares his perspectives about today’s formal verification technology. The Kaufman award is given annually by the EDA Consortium and the IEEE Council on Electronic Design Automation.

Q: What is your response to winning the 2009 Phil Kaufman award?

A: I’m very pleased. One thing I like about the award is that it’s a reflection of the tight link between academia and the EDA industry. The research work that’s done by universities can be adopted very quickly by the EDA industry. You don’t see that in a lot of other fields.

Q: As a PhD student at MIT in 1979, you developed the first switch-level simulator. Why was that a step forward at the time, and is the technology still used today?

A: The idea behind switch-level simulation was to model a transistor circuit, but treat transistors as simple switches that are either open or closed. It’s purely at the logic level and you don’t try to capture circuit timing very closely. By contrast, the only transistor-level simulator at the time was Spice. Spice is an amazing tool, but the advantage of switch-level is that it can really do chip-level simulation.

With the move to standard cell design, switch-level simulation isn’t used as much today. But people who do full-custom design use switch-level simulation. People who design specialized circuits like embedded memory use it. It’s useful for classes of circuits where you really can’t come up with a gate-level representation.

Q: What you may be best known for, in EDA circles, is your 1986 paper on binary decision diagrams [BDDs]. This helped lay the foundation for formal verification. What was significant about the paper when it came out?

A: One contribution was the data structure itself and how it works and the cool stuff you could do with it. It was one of the first tools for solving heavy-duty Boolean problems. Nowadays we have very good Boolean SAT [satisfiability] solvers, but at the time, they were very weak. If you tried to throw any complex question into a SAT solver, like “is this fault testable,” it would just die. BDDs could handle it. And they can do more than Boolean satisfiability, because what they encode is all the ways a Boolean formula can be true, whereas a SAT solver just gives you one of those ways.

The idea [for BDDs] goes back to the 1950s. My work was to refine them and show some algorithms that can build upon and operate on BDDs. My first thinking about [BDDs] was for test generation.

Q: When were BDDs applied to formal model checking?

A: In 1987 we had a graduate student here, Ken McMillan, who is now at Cadence. He was Ed Clarke’s graduate student. Within two weeks of arriving on campus, he figured out a way to take my [BDD] work and Ed Clarke’s work and create the first symbolic model checker. Today just about all model checkers are symbolic.

Nowadays, equivalence checkers use a variety of strategies including SAT checking and BDDs. When they work well, BDDs are excellent. Tools will often start with a BDD-based strategy, but they need some fallback in case the memory requirements become unreasonable.

[Editor’s note: In 1997 Bryant, McMillan, and two others shared the ACM Kanellakis Award for their pioneering work in BDD-based symbolic model checking].

Q: Do BDDs have some limitations?

A: Yes. The biggest problem with BDDs is the memory requirement. They tend to either come back with results almost instantly, or they get mired down using so much memory the machine starts thrashing.

Q: Another technology you developed is symbolic trajectory evaluation (STE), a formal method based on symbolic simulation. What is it and how has it been applied?

A: STE is a form of symbolic simulation that provides capabilities similar to model checking, but in a more limited way. It’s done by simulating a circuit, but the circuit returns not just 0s and 1s but functions of different values. It is used heavily within Intel and similar tools are used internally by other companies.

Q: What’s your assessment of today’s formal verification market?

A: It hasn’t really taken off. There are many instances of tools that showed great promise and didn’t quite make it. Companies with strong internal EDA groups have been more successful than those trying to buy commercial tools. In particular, companies like Intel and IBM make a lot of use of formal verification. It works for companies where they’ve really developed a culture of expertise.

Q: What needs to happen for formal tools to be more widely deployed?

A: The tools have to get better and more turnkey, and you have to have a motivated and trained community. People have to be committed to it and be willing to make changes to the design flow. A recent move that’s been successful is to call them property checkers and not claim to do full formal verification – it’s a great way to track down whatever bugs you want to look for. We also have newer languages describing properties. These are steps in a direction that will help people understand the possibilities.

Q: Can formal verification be applied to software validation?

A: It’s a harder problem. With hardware you kind of know all the states of the system, and even though it’s exponential complexity, you’ve got a handle on it. In a software program it’s more difficult to track all the different variables in the program and their possible values. There’s been some success in very specific domains. The most impressive, actually, has been Microsoft – they’ve developed a number of tools that use different formal verification techniques to look for synchronization errors.

Q: What are formal verification researchers looking at today?

A: There’s a lot of interest in software. I think it’s sort of a natural extension. There’s an urgency from some companies, and there are a lot more bugs.

Q: What are your current research interests?

A: I’m a dean of the school of computer science, so my work often has to do with being a dean. I’ve also become very interested in what can be done with large sets of data from a computational point of view. A great example of that would be a company like Google and all the web pages and information they gather. I think there is a potential EDA angle. If you think about all the simulation runs that are done, mining that data and figuring out what’s going on with it would be interesting research.

Richard Goering