Steve Teig describes building Tancell, the first commercial analytical placer for chip design, using simulated annealing to solve placement and routing problems. He explains how Tangent scaled the technology and why superior products alone don't guarantee success in the semiconductor tools market.
Chapters
Now one other thing from my days at Trilogy is that in 1983 there was an article in Science on what's now called simulated annealing, a at that time brand new general purpose combinatorial optimization technology. So a way of taking a function with 100,000 variables, a very complex function and be able to try to find a near global optimum. The moment I saw the paper, I could see this was going to be a transformative technology and that I needed to learn a lot about it. The metaphor basically, their metaphor is you have this 100,000 variable function, imagine that you represent this by 100,000 particles where the energy function of that system of particles matches the function you are trying to optimize. Simulate the system at a very high temperature and then very slowly cool it down until the whole thing coalesces into a very low energy crystal. This struck me as a really beautiful and powerful idea, but I also wanted to challenge their assumptions because the fact is that the next level of questions one wanted to ask, in my opinion, were all inadequately answered in those early influential papers. Really, what temperature should you start at? How much should you change the temperature by? How do you decide when you should change the temperature? When should you stop? What kinds of transformations should you do, et cetera, et cetera, et cetera. So I started working on the mathematics for that, starting with their metaphor and trying to build a technology for general purpose optimization. Now this served me well because even though Trilogy went public, it became clear that they weren't going to be the transformative company we had all hoped and so with 4 other folks, 3 of whom were colleagues at Tangent including my boss there, we started a company called Tangent at which I became the CTO. Now Tangent was a company that built software for chip design. At that time, there was the very beginning of a sea change in chip design. Before this time roughly, the way people would design chips is that somebody would manually specify where every transistor on the chip was where every wire was going on the chip— going to go on the chip. Completely crazy. It obviously doesn't scale. And so somebody had the clever idea of, well, why don't we have small collections of transistors to build basic functions like AND and OR and plus, and we're going to put them in a standard library of cells, cells that can go in rows, and we're going to have rows of these components separated by empty spaces called channels where we're going to put the wires, rows of components, wires, rows of components, wires as a way of making it easier to assemble chips. And the folks that started Tangent realized if only we could automate that procedure, automate the placement of where the cells were going to go and the routing of where the wires were going to go, we could make it possible for anybody to design a chip quickly and really have an impact on the electronics industry. So even though I knew absolutely nothing about placement or routing, they made me the CTO of this company and so I spent the summer of 1984 reading what was at that time the entire literature on placement and routing. I got all the proceedings from all of the relevant conferences and I sat by the pool at my apartment complex with 5 feet of tomes and just read from one end to the other and then we jumped in and tried to build our first product, Tancell, which as it turns out despite its coming from 1984 and 1985 has been pretty influential. We built the first commercial analytical placer, which is now the standard technique for large-scale placement today, 30 years later. We built the first commercial adaptive simulated annealing system, All that math I've been doing on annealing paid off and I was able to use it to do optimization within Tancell and that too is still used today and was used very popularly for about 20 years. So I try to build technologies with leverage, that general purpose optimization I was able to apply to the special purpose problem of placing cells. We had the first commercial timing-driven place and route system, the first congestion-based place and route system. These are all the standard philosophies for chip design even still today. Unfortunately, even though we built Tancell, it worked, it was a good product, it was beating other products that people were trying to develop, it didn't matter. We were ahead of the market and that sea change to move to cells in this way, while it did happen, didn't happen until about 3 years after we built Tancell. So it was hard to make a really successful business out of this and we had to change course a little bit. Well, it turns out there was another sea change happening in chips right about this time, this is '86 or so now, where the folks who manufacture chips figured out ways that they could put multiple levels of wiring above the transistors rather than beside the transistors to try to fill the entire chip with these cells, a sea of cells or sea of gates as it came to be called. You have this large jigsaw puzzle worth of cells filling up the space and then lots and lots of wires on top. Well, that problem looked much harder than how to place components in rows. Nobody knew how to solve it. The people who invented that technology to make it possible to manufacture. People at other companies, we didn't know how to solve it either, I definitely didn't know how to solve it either. But I did know that we had a general purpose optimization technology that we could use as a bit of a science laboratory to figure out how best to attack a difficult problem like this. And it paid off, we actually figured out how to do it. And we invented modern, what's called area-based place and route, the basis of the technology for how people have laid out chips ever since. We basically took that general combinatorial optimization technology that old annealing stuff and kept evolving it and evolving it and refining it and improving it and it ended up being powerful enough to solve this problem. We also built it on top of very carefully constructed scalable infrastructure. At that time, people were making chips with 5,000 or 10,000 cells, but it wasn't very long thereafter that there were 200,000 or 300,000 cells, but we built a system that was able to scale enough that we were able to ride that wave and we more than doubled the capacity of what you could put on a chip of a given size with Tangate, that product. So that became quite successful, which in turn caused Tangent to be acquired by Cadence, a very large company, and the Cadence products from the late '80s, early '90s of Gate Ensemble, Cell Ensemble, which generated more than $3 billion in revenue, all have Tangate inside them.
