Amdahl’s Law is a Law (Hey, a New Post!)

At this year’s DAC, Bill Dally, Stanford professor and Chief Scientist at Nvidia, gave a keynote speech in which he claimed that Amdahl’s law is not a law, but an observation. This uses the popular interpretation of law to mean “proven correct”. However, in scientific terms, stating something is a law has nothing to do with whether it is correct or not.

In scientific terms, a law is a relationship between two or more entities. Some well know laws are:

• Newton’s second law of motion
  • F = mA
• Ohm’s law
  • E = Ir
• Newton’s law of universal gravitation
  • F = G*m1*m2/r^2

Newton’s second law relates force, mass, and acceleration. Ohm’s law relates voltage, current and resistance. Newton’s law of universl gravitation relates gravitation force to the mass and distance of two bodies.

A law allows us to derive the value of an unknown quantity from other known quantities. Knowing voltage and resistance, Ohm’s law gives us current.

What quantities does Amdahl’s law relate? Amdahl’s law is a relationship between parallelism, number of processors, and speedup. It is usually used to compute the maximum speedup that can be obtained for an application given an infinite number of processors. Parallel speedup is limited by the portion of the application that is sequential (cannot be parallelized). For example, if 10% of the execution time cannot be parallelized, the maximum speedup obtainable through parallelism is 10X.

So, Amdahl’s law does meet the requirements for being a scientific law. Then, what do we make of Dally’s statement? Other than trying to be provocative, I think the point he was trying to make is that, in the applications he is addressing, the sequential portion is essentially zero. In this case speedup is equal to the number of processors. But, this still follows Amdahl’s law.

Bugs Are Easy and in Deep Chip

Somehow, the powers that be decided that my post on languages was worthy of a wider audience. We made it to Deep Chip! Deep Chip is John Cooley’s site that is read by every hardware designer on the planet.

Here is the link:

http://deepchip.com/wiretap/090219.html

If anyone wants to comment on this and somehow finds this post (unfortunately, John doesn’t allow “self promotion”) , please feel free to post comments.

Languages: Software got it Right, Hardware got it Wrong

In the late Sixties, efforts were underway to define the second generation of programming languages. The first generation of languages, FORTRAN, algol, and cobol, had been in user for almost ten years and enough experience had been built up to allow improved languages to be built. At the time, IBM was the dominant player in programming languages and was in a position to define a language and have it become the defacto standard programming language. The language they designed, called PL/1, was basically a superset of the existing mainstream languages of the time. It had features to support scientific computing, business computing, and systems programming. IBM made PL/1 its flagship programming language and they expected it to become the dominant programming language in the industry.

Meanwhile, at Bell Labs, a programming language called C was being developed. The philosophy behind C was completely opposite to that of PL/1. Instead of being a superset of all existing languages, C was a minimal common subset. C made it easy to create libraries that made up for the lack of features found in other languages. The practice of having a standard library associated with a language started with the C language. Essentially, C is not a language for writing programs, it is a language for writing libraries. Applications are built by putting libraries together. In fact, it is not possible to write a Hello World program in C without using a library (stdio). Today, all modern programming languages still follow this basic philosophy.

The whole Open Source movement is enabled by the philosophy behind C. Imagine if Pl/1 had won the language race and the only way to add new standard features was to add them to the language. The PL/1 compiler was controlled by IBM and the language was not designed to be easily compilable. The software industry would not be as nearly as advanced today if PL/1 had won the language wars.

Contrast this with how hardware design languages have evolved. The analogs of FORTRAN, algol, and cobol in hardware are Verilog and VHDL. These were first generation hardware description languages (HDLs) developed about twenty years ago. Shortly after that, specialized verification languages, such as e and Vera, were introduced that added features useful for verification. Then, along came assertion languages such as PSL and SVA. Today, the hardware design world is migrating to a language called SystemVerilog. Can you guess which path it took? Yup, the PL/1 path. SystemVerilog is a superset of Verilog, Vera, and SVA. The initial release version was version 3.1a. That’s right, it took three major revisions to get it right, then someone decided to add some functionality to get version 3.1. Oh, but wait, that still wasn’t enough, we just had to have a few extra features to get to 3.1a.

And it gets worse. In 35 years, there has been exactly one revision of the C language. SystemVerilog is due for a revision next year after only five years. Verilog has undergone four major revisions in twenty years. The proprietary languages, e and Vera, are changed practically every quarter.

The cost of all this is that it is much harder to innovate in hardware design than it is in software design. At Nusym, we spend 90% of our effort (and money) on language support rather than our core differentiating technology. To illustrate this problem, we have spent dozens of person-years developing Verilog and Vera infrastructure for our tool. By contrast, we had one person spend three months to prototype it on C.

Is there a solution to this problem? Well, there are C-based hardware design languages, such as SystemC. But, using C directly as a hardware design language is trying to fit a square peg into a round hole. Developers and users of SystemC do leverage the ability to easily create libraries, but the goal of this language is to raise the level of abstraction, not create a minimal hardware design/verification language.

It would be interesting to think of what a real equivalent of C for hardware design/verification would be. If there is any interest, I can post my ideas of how to do this and others can contribute. I don’t know if anything would come out of this, but it might be interesting to look at.

From 400 to 400 million

I designed my first ASIC in 1981. It had 400 gates and was part of a large mainframe computer. At the time, this was state-of-the-art. Since then, ASIC density has grown by more than five orders of magnitude.

After designing a lot of hardware, I became interested in the process of design itself. It seemed to me that we kept stumbling across the same problems and inefficiencies time and time again. I began to see that improving the development process was a more challenging problem than design itself. I became interested in verification as I saw it as the most challenging problem.

One day, around 1990, I read an article in EE Times describing a new way of verifying hardware called formal verification. The article promised that all you would have to do is give your design to the tool and it would tell you what all the bugs are. Well, I thought this was the most exciting in the world and, so, I started studying it. I learned enough to be dangerous, but quickly realized that I had a different perspective than all other experts in the area because of my hardware background. I had my own ideas and decided to pursue them, eventually leading to a Ph.D. in formal verification. I then went on to found an EDA company, Nusym Technology, Inc., based on these ideas.

For a long time, I have wanted to find a forum to present what I have learned about designing complex hardware/software systems. I hope this will be informative and I welcome any discussion, especially as I think some of what I will say will be controversial.